use crate::algorithms::poly_factor::FactorPolyField;
use crate::field::{Field, FieldStore};
use crate::homomorphism::{Homomorphism, Identity};
use crate::ring::*;
use crate::rings::extension::*;
use crate::rings::poly::derive_poly;

use super::poly::dense_poly::DensePolyRing;
use super::poly::PolyRingStore;

///
/// Trait for fields that are a finite and simple extensions of a base field, i.e.
/// are generated by a single element that is algebraic over the base field.
/// 
/// Note that this is technically already satisfied whenever a ring implements
/// `Field + FreeAlgebra`, but to provide interesting additional functionality, we
/// also require `FactorPolyField`. This is necessary to e.g. compute galois groups
/// or maps between extension fields.
/// 
/// # Example
/// The simplest example is certainly a finite field.
/// ```
/// # use feanor_math::ring::*;
/// # use feanor_math::rings::extension::galois_field::*;
/// # use feanor_math::rings::fieldextension::*;
/// # use feanor_math::rings::zn::zn_64::*;
/// # use feanor_math::rings::zn::*;
/// let Fp = Zn::new(7).as_field().ok().unwrap();
/// let Fq = GFdyn(49);
/// assert!(Fq.base_ring().get_ring() == Fp.get_ring());
/// assert!(Fq.is_galois());
/// ```
/// 
pub trait ExtensionField: Field + FreeAlgebra + FactorPolyField {

    ///
    /// Checks whether this field extension is galois, i.e. normal and separable.
    /// 
    /// A separable field extension is one where every polynomial that is irreducible
    /// over the base field is square-free over the extension field.
    /// 
    /// A normal field extension is one where every polynomial that is irreducible
    /// over the base field and has a root in the extension field completely splits there.
    /// 
    fn is_galois(&self) -> bool {
        let K = RingRef::new(self);
        let KX = DensePolyRing::new(K, "X");
        let gen_poly = RingRef::new(self).generating_poly(&KX, K.inclusion());
        if KX.is_zero(&derive_poly(&KX, &gen_poly)) {
            // not separable
            return false;
        }
        let (factorization, unit) = Self::factor_poly(&KX, &gen_poly);
        debug_assert!(K.is_one(&unit));
        return factorization.len() == self.rank();
    }
    
    ///
    /// Computes a homomorphism `Self -> Target` if it exists, otherwise `Err` is returned.
    /// 
    /// Note that this homomorphism is NOT canonical in the sense that it maps the canonical
    /// generator of `self` to the canonical generator of `target`. Furthermore, note that usually
    /// extension fields have nontrivial automorphisms. If this is the case, there are many
    /// such homomorphisms, and an arbitrary one among them is returns.
    /// 
    /// # Example
    /// 
    /// We use them via the more convenient interface exposed through [`ExtensionFieldStore`].
    /// ```
    /// # use feanor_math::ring::*;
    /// # use feanor_math::rings::extension::galois_field::*;
    /// # use feanor_math::rings::fieldextension::*;
    /// # use feanor_math::rings::zn::zn_64::*;
    /// # use feanor_math::rings::zn::*;
    /// assert!(GFdyn(25).has_hom(&GFdyn(125)).is_none());
    /// assert!(GFdyn(25).has_hom(&GFdyn(625)).is_some());
    /// ```
    /// However be careful, since these homomorphisms do not have to be "canonical"!
    /// ```
    /// # use feanor_math::ring::*;
    /// # use feanor_math::rings::extension::galois_field::*;
    /// # use feanor_math::rings::fieldextension::*;
    /// # use feanor_math::rings::zn::zn_64::*;
    /// # use feanor_math::homomorphism::*;
    /// # use feanor_math::rings::extension::*;
    /// # use feanor_math::rings::zn::*;
    /// // we create the field tower F3/F2/F1
    /// let F1 = GFdyn(9);
    /// let F2 = GFdyn(81);
    /// let F3 = GFdyn(6561);
    /// let f = F1.has_hom(&F3).unwrap();
    /// let g = F2.has_hom(&F3).unwrap().compose(F1.has_hom(&F2).unwrap());
    /// assert!(!F3.eq_el(&F3.canonical_gen(), &f.map(F1.canonical_gen())));
    /// assert!(!F3.eq_el(&F3.canonical_gen(), &g.map(F1.canonical_gen())));
    /// assert!(!F3.eq_el(&f.map(F1.canonical_gen()), &g.map(F1.canonical_gen())));
    /// ```
    /// 
    fn into_hom<F, T, H>(self_: F, target: T, base_ring_hom: H) -> Result<ExtensionFieldEmbedding<F, T, H>, (F, T)>
        where T: RingStore,
            F: RingStore<Type = Self>,
            T::Type: ExtensionField,
            H: Homomorphism<<<Self as RingExtension>::BaseRing as RingStore>::Type, <<T::Type as RingExtension>::BaseRing as RingStore>::Type>
    {
        let K = &target;
        let KX = DensePolyRing::new(K, "X");
        let gen_poly = self_.generating_poly(&KX, K.inclusion().compose(&base_ring_hom));
        let (factorization, unit) = <T::Type as FactorPolyField>::factor_poly(&KX, &gen_poly);
        debug_assert!(K.is_one(&unit));
        if let Some((factor, _)) = factorization.into_iter().filter(|(f, _)| KX.degree(f) == Some(1)).next() {
            let root = K.negate(K.div(KX.coefficient_at(&factor, 0), KX.coefficient_at(&factor, 1)));
            return Ok(ExtensionFieldEmbedding { from: self_, to: target, map_generator_to: root, base_ring_hom: base_ring_hom });
        } else {
            return Err((self_, target));
        }
    }
}

pub struct ExtensionFieldEmbedding<F: RingStore, T: RingStore, H>
    where F::Type: ExtensionField, T::Type: ExtensionField,
        H: Homomorphism<<<F::Type as RingExtension>::BaseRing as RingStore>::Type, <<T::Type as RingExtension>::BaseRing as RingStore>::Type>
{
    from: F,
    to: T,
    map_generator_to: El<T>,
    base_ring_hom: H
}

impl<F: RingStore, T: RingStore, H> Homomorphism<F::Type, T::Type> for ExtensionFieldEmbedding<F, T, H>
    where F::Type: ExtensionField, T::Type: ExtensionField,
        H: Homomorphism<<<F::Type as RingExtension>::BaseRing as RingStore>::Type, <<T::Type as RingExtension>::BaseRing as RingStore>::Type>
{
    type DomainStore = F;
    type CodomainStore = T;

    fn domain<'a>(&'a self) -> &'a Self::DomainStore {
        &self.from
    }

    fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
        &self.to
    }

    fn map(&self, x: <F::Type as RingBase>::Element) -> <T::Type as RingBase>::Element {
        self.map_ref(&x)
    }

    fn map_ref(&self, x: &<F::Type as RingBase>::Element) -> <T::Type as RingBase>::Element {
        let poly_ring = DensePolyRing::new(self.to.base_ring(), "X");
        let x_poly = self.from.poly_repr(&poly_ring, x, &self.base_ring_hom);
        return poly_ring.evaluate(&x_poly, &self.map_generator_to, &self.to.inclusion());
    }
}

pub trait ExtensionFieldStore: FieldStore + FreeAlgebraStore
    where Self::Type: ExtensionField
{
    delegate!{ ExtensionField, fn is_galois(&self) -> bool }

    ///
    /// See [`ExtensionField::into_hom()`].
    /// 
    fn into_hom<T, H>(self, target: T, base_ring_hom: H) -> Result<ExtensionFieldEmbedding<Self, T, H>, (Self, T)>
        where T: RingStore,
            T::Type: ExtensionField,
            H: Homomorphism<<<Self::Type as RingExtension>::BaseRing as RingStore>::Type, <<T::Type as RingExtension>::BaseRing as RingStore>::Type>
    {
        <Self::Type as ExtensionField>::into_hom(self, target, base_ring_hom)
    }

    ///
    /// See [`ExtensionField::into_hom()`].
    /// 
    fn has_hom<'a, T>(&'a self, target: &'a T) -> Option<ExtensionFieldEmbedding<&'a Self, &'a T, Identity<&'a <Self::Type as RingExtension>::BaseRing>>>
        where T: RingStore,
            T::Type: ExtensionField,
            <T::Type as RingExtension>::BaseRing: RingStore<Type = <<Self::Type as RingExtension>::BaseRing as RingStore>::Type>
    {
        assert!(self.base_ring().get_ring() == target.base_ring().get_ring());
        self.into_hom(target, self.base_ring().identity()).ok()
    }
}

impl<R> ExtensionFieldStore for R
    where R: RingStore, R::Type: ExtensionField
{}

#[cfg(test)]
use self::galois_field::GF;
#[cfg(test)]
use super::finite::FiniteRingStore;

#[test]
fn test_as_embedding() {
    let R = GF::<3>(5);
    let S = GF::<6>(5);

    crate::homomorphism::generic_tests::test_homomorphism_axioms(R.has_hom(&S).unwrap(), R.elements());
    
    let S = GF::<4>(5);
    assert!(R.has_hom(&S).is_none());
}