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 = K.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() == K.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::primitive_int::*;
    /// # use feanor_math::rings::zn::*;
    /// // we create the field tower F3/F2/F1
    /// let p = 11;
    /// let F1 = GFdyn(StaticRing::<i64>::RING.pow(p, 2) as u64);
    /// let F2 = GFdyn(StaticRing::<i64>::RING.pow(p, 4) as u64);
    /// let F3 = GFdyn(StaticRing::<i64>::RING.pow(p, 8) as u64);
    /// 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())) ||
    ///         !F3.eq_el(&F3.canonical_gen(), &g.map(F1.canonical_gen())) ||
    ///         !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));
        }
    }

    ///
    /// Computes the Galois group of this ring if it is galois, and otherwise it returns `None`.
    /// 
    /// The galois group is the group of all automorphisms that fix the base field.
    /// 
    fn galois_group<'a, S>(self_: S) -> Option<Vec<GaloisAutomorphism<S>>>
        where S: 'a + RingStore<Type = Self> + Clone,
            El<S>: 'a
    {
        let K = self_;
        let KX = DensePolyRing::new(K.clone(), "X");
        let gen_poly = K.generating_poly(&KX, K.inclusion());
        if KX.is_zero(&derive_poly(&KX, &gen_poly)) {
            debug_assert!(!K.is_galois());
            return None;
        }
        let (factorization, unit) = Self::factor_poly(&KX, &gen_poly);
        debug_assert!(K.is_one(&unit));
        if factorization.len() != K.rank() {
            debug_assert!(!K.is_galois());
            return None;
        } else {
            return Some(
                factorization.into_iter().map(move |(factor, _)| {
                    assert!(KX.degree(&factor) == Some(1));
                    KX.base_ring().negate(KX.base_ring().div(KX.coefficient_at(&factor, 0), KX.coefficient_at(&factor, 1)))
                }).map(move |x| GaloisAutomorphism { ring: K.clone(), map_generator_to: x })
                .collect()
            );
        }
    }
}

pub struct GaloisAutomorphism<F: RingStore>
    where F::Type: ExtensionField
{
    ring: F,
    map_generator_to: El<F>
}

impl<F: RingStore> GaloisAutomorphism<F>
    where F::Type: ExtensionField
{
    pub fn get_map<'a>(&'a self) -> ExtensionFieldEmbedding<&'a F, &'a F, Identity<&'a <F::Type as RingExtension>::BaseRing>> {
        ExtensionFieldEmbedding {
            from: &self.ring,
            to: &self.ring,
            map_generator_to: self.ring.clone_el(&self.map_generator_to),
            base_ring_hom: self.ring.base_ring().identity()
        }
    }

    pub fn is_identity(&self) -> bool {
        self.ring.eq_el(&self.map_generator_to, &self.ring.canonical_gen())
    }

    pub fn compose(&self, rhs: &GaloisAutomorphism<F>) -> GaloisAutomorphism<F>
        where F: Clone
    {
        assert!(self.ring.get_ring() == rhs.ring.get_ring());
        GaloisAutomorphism {
            ring: self.ring.clone(),
            map_generator_to: self.get_map().map_ref(&rhs.map_generator_to)
        }
    }
}

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()
    }

    fn galois_group<'a>(&'a self) -> Option<Vec<GaloisAutomorphism<&'a Self>>> {
        <Self::Type as ExtensionField>::galois_group(self)
    }
}

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());
}

#[test]
fn test_galois_group() {
    let Fq = GF::<5>(3);

    let mut galois_group = Fq.galois_group().unwrap();

    assert_eq!(5, galois_group.len());
    let id = galois_group.remove(
        galois_group.iter().enumerate().filter(|(_, g)| g.is_identity()).next().unwrap().0
    );
    let frob = galois_group.remove(
        galois_group.iter().enumerate().filter(|(_, g)| Fq.eq_el(&Fq.pow(Fq.canonical_gen(), 3), &g.get_map().map(Fq.canonical_gen()))).next().unwrap().0
    );
    let frob2 = galois_group.remove(
        galois_group.iter().enumerate().filter(|(_, g)| Fq.eq_el(&Fq.pow(Fq.canonical_gen(), 9), &g.get_map().map(Fq.canonical_gen()))).next().unwrap().0
    );
    let frob3 = galois_group.remove(
        galois_group.iter().enumerate().filter(|(_, g)| Fq.eq_el(&Fq.pow(Fq.canonical_gen(), 27), &g.get_map().map(Fq.canonical_gen()))).next().unwrap().0
    );
    let frob4 = galois_group.remove(
        galois_group.iter().enumerate().filter(|(_, g)| Fq.eq_el(&Fq.pow(Fq.canonical_gen(), 81), &g.get_map().map(Fq.canonical_gen()))).next().unwrap().0
    );
    let ordered_galois_group = [id, frob, frob2, frob3, frob4];
    for i in 0..5 {
        assert!(ordered_galois_group[i].compose(&ordered_galois_group[(5 - i) % 5]).is_identity());
    }
}