use crate::matrix::OwnedMatrix;
use crate::ring::*;
use crate::seq::*;
use crate::homomorphism::*;
use super::poly::{PolyRingStore, PolyRing};

///
/// Contains [`extension_impl::FreeAlgebraImpl`], an implementation of [`FreeAlgebra`] based
/// on polynomial division.
/// 
pub mod extension_impl;

///
/// Contains [`galois_field::GF()`] and [`galois_field::GFdyn()`] which are simple functions
/// to create finite fields.
/// 
pub mod galois_field;

///
/// A ring `R` that is an extension of a base ring `S`, generated by a single element
/// that is algebraic resp. integral over `S`. While sounding quite technical, this includes
/// a wide class of important rings, like number fields or galois fields.
/// 
/// We also require that `R` must be a free `S`-module, with a basis given by the powers 
/// of [`FreeAlgebra::canonical_gen()`].
/// 
/// # Nontrivial Automorphisms
/// 
/// Rings of this form very often have nontrivial automorphisms. In order to simplify situations
/// where morphisms or other objects are only unique up to isomorphism, canonical morphisms between rings
/// of this type must also preserve the canonical generator. 
/// 
/// # Examples
/// One of the most common use cases seems to be the implementation of finite fields (sometimes
/// called galois fields).
/// ```
/// # use feanor_math::assert_el_eq;
/// # use feanor_math::ring::*;
/// # use feanor_math::rings::zn::*;
/// # use feanor_math::primitive_int::*;
/// # use feanor_math::rings::extension::*;
/// # use feanor_math::divisibility::*;
/// # use feanor_math::rings::finite::*;
/// // we have to decide for an implementation of the prime field
/// let prime_field = zn_static::Fp::<3>::RING;
/// let galois_field = extension_impl::FreeAlgebraImpl::new(prime_field, [2, 1, 0]);
/// // this is now the finite field with 27 elements, or F_27 or GF(27) since X^3 + 2X + 1 is irreducible modulo 3
/// assert_eq!(Some(27), galois_field.size(&StaticRing::<i64>::RING));
/// 
/// // currently, this ring unfortunately does not implement `Field`; However, we can already do division
/// for x in galois_field.elements() {
///     if !galois_field.is_zero(&x) {
///         galois_field.println(&x);
///         let inv_x = galois_field.checked_div(&galois_field.one(), &x).unwrap();
///         assert_el_eq!(&galois_field, &galois_field.one(), &galois_field.mul(x, inv_x));
///     }
/// }
/// ```
/// 
pub trait FreeAlgebra: RingExtension {

    type VectorRepresentation<'a>: VectorFn<El<Self::BaseRing>>
        where Self: 'a;

    ///
    /// Returns a fixed element that generates this ring as a free module over the base ring.
    /// 
    fn canonical_gen(&self) -> Self::Element;

    ///
    /// Returns the rank of this ring as a free module over the base ring.
    /// 
    fn rank(&self) -> usize;

    ///
    /// Returns the representation of the element w.r.t. the canonical basis, that is the basis given
    /// by the powers `x^i` where `x` is the canonical generator given by [`FreeAlgebra::canonical_gen()`]
    /// and `i` goes from `0` to `rank - 1`.
    /// 
    /// In this sense, this is the opposite function to [`FreeAlgebra::from_canonical_basis()`].
    /// 
    fn wrt_canonical_basis<'a>(&'a self, el: &'a Self::Element) -> Self::VectorRepresentation<'a>;

    ///
    /// Returns the element that has the given representation w.r.t. the canonical basis, that is the basis given
    /// by the powers `x^i` where `x` is the canonical generator given by [`FreeAlgebra::canonical_gen()`]
    /// and `i` goes from `0` to `rank - 1`.
    /// 
    /// In this sense, this is the opposite function to [`FreeAlgebra::wrt_canonical_basis()`].
    /// 
    fn from_canonical_basis<V>(&self, vec: V) -> Self::Element
        where V: ExactSizeIterator + DoubleEndedIterator + Iterator<Item = El<Self::BaseRing>>
    {
        assert_eq!(vec.len(), self.rank());
        let x = self.canonical_gen();
        let mut result = self.zero();
        for c in vec.rev() {
            self.mul_assign_ref(&mut result, &x);
            self.add_assign(&mut result, self.from(c));
        }
        return result;
    }
}

pub trait FreeAlgebraStore: RingStore
    where Self::Type: FreeAlgebra
{
    delegate!{ FreeAlgebra, fn canonical_gen(&self) -> El<Self> }
    delegate!{ FreeAlgebra, fn rank(&self) -> usize }

    ///
    /// See [`FreeAlgebra::wrt_canonical_basis()`].
    /// 
    fn wrt_canonical_basis<'a>(&'a self, el: &'a El<Self>) -> <Self::Type as FreeAlgebra>::VectorRepresentation<'a> {
        self.get_ring().wrt_canonical_basis(el)
    }

    ///
    /// See [`FreeAlgebra::from_canonical_basis()`].
    /// 
    fn from_canonical_basis<V>(&self, vec: V) -> El<Self>
        where V: ExactSizeIterator + DoubleEndedIterator + Iterator<Item = El<<Self::Type as RingExtension>::BaseRing>>
    {
        self.get_ring().from_canonical_basis(vec)
    }

    ///
    /// Returns the generating polynomial of this ring, i.e. the monic polynomial `f(X)` such that this ring is isomorphic
    /// to `R[X]/(f(X))`, where `R` is the base ring.
    /// 
    fn generating_poly<P, H>(&self, poly_ring: P, hom: H) -> El<P>
        where P: PolyRingStore,
            P::Type: PolyRing,
            H: Homomorphism<<<Self::Type as RingExtension>::BaseRing as RingStore>::Type, <<P::Type as RingExtension>::BaseRing as RingStore>::Type>
    {
        assert!(hom.domain().get_ring() == self.base_ring().get_ring());
        poly_ring.sub(
            poly_ring.from_terms([(poly_ring.base_ring().one(), self.rank())].into_iter()),
            self.poly_repr(&poly_ring, &self.pow(self.canonical_gen(), self.rank()), hom)
        )
    }

    ///
    /// Returns the polynomial representation of the given element `y`, i.e. the polynomial `f(X)` of degree at most
    /// [`FreeAlgebraStore::rank()`] such that `f(x) = y`, where `y` is the canonical generator of this ring, as given by
    /// [`FreeAlgebraStore::canonical_gen()`].
    /// 
    fn poly_repr<P, H>(&self, to: P, el: &El<Self>, hom: H) -> El<P>
        where P: PolyRingStore,
            P::Type: PolyRing, 
            H: Homomorphism<<<Self::Type as RingExtension>::BaseRing as RingStore>::Type, <<P::Type as RingExtension>::BaseRing as RingStore>::Type>
    {
        let coeff_vec = self.wrt_canonical_basis(el);
        to.from_terms(
            (0..self.rank()).map(|i| coeff_vec.at(i)).enumerate()
                .filter(|(_, x)| !self.base_ring().is_zero(x))
                .map(|(j, x)| (hom.map(x), j))
        )
    }
}

#[stability::unstable(feature = "enable")]
pub fn create_multiplication_matrix<R: FreeAlgebraStore>(ring: R, el: &El<R>) -> OwnedMatrix<El<<R::Type as RingExtension>::BaseRing>> 
    where R::Type: FreeAlgebra
{
    let mut result = OwnedMatrix::zero(ring.rank(), ring.rank(), ring.base_ring());
    let mut current = ring.clone_el(el);
    let gen = ring.canonical_gen();
    for i in 0..ring.rank() {
        {
            let current_basis_repr = ring.wrt_canonical_basis(&current);
            for j in 0..ring.rank() {
                *result.at_mut(j, i) = current_basis_repr.at(j);
            }
        }
        ring.mul_assign_ref(&mut current, &gen);
    }
    return result;
}

impl<R: RingStore> FreeAlgebraStore for R
    where R::Type: FreeAlgebra
{}

#[cfg(any(test, feature = "generic_tests"))]
pub fn generic_test_free_algebra_axioms<R: FreeAlgebraStore>(ring: R)
    where R::Type: FreeAlgebra
{
    let x = ring.canonical_gen();
    let n = ring.rank();
    
    let xn_original = ring.pow(ring.clone_el(&x), n);
    let xn_vec = ring.wrt_canonical_basis(&xn_original);
    let xn = ring.sum(Iterator::map(0..n, |i| ring.mul(ring.inclusion().map(xn_vec.at(i)), ring.pow(ring.clone_el(&x), i))));
    assert_el_eq!(&ring, &xn_original, &xn);

    let x_n_1_vec_expected = (0..n).map_fn(|i| if i > 0 {
        ring.base_ring().add(ring.base_ring().mul(xn_vec.at(n - 1), xn_vec.at(i)), xn_vec.at(i - 1))
    } else {
        ring.base_ring().mul(xn_vec.at(n - 1), xn_vec.at(0))
    });
    let x_n_1 = ring.pow(ring.clone_el(&x), n + 1);
    let x_n_1_vec_actual = ring.wrt_canonical_basis(&x_n_1);
    for i in 0..n {
        assert_el_eq!(ring.base_ring(), &x_n_1_vec_expected.at(i), &x_n_1_vec_actual.at(i));
    }

    // test basis wrt_root_of_unity_basis linearity and compatibility from_root_of_unity_basis/wrt_root_of_unity_basis
    for i in (0..ring.rank()).step_by(5) {
        for j in (1..ring.rank()).step_by(7) {
            if i == j {
                continue;
            }
            let element = ring.from_canonical_basis(Iterator::map(0..n, |k| if k == i { ring.base_ring().one() } else if k == j { ring.base_ring().int_hom().map(2) } else { ring.base_ring().zero() }));
            let expected = ring.add(ring.pow(ring.clone_el(&x), i), ring.int_hom().mul_map(ring.pow(ring.clone_el(&x), j), 2));
            assert_el_eq!(&ring, &expected, &element);
            let element_vec = ring.wrt_canonical_basis(&expected);
            for k in 0..ring.rank() {
                if k == i {
                    assert_el_eq!(ring.base_ring(), &ring.base_ring().one(), &element_vec.at(k));
                } else if k == j {
                    assert_el_eq!(ring.base_ring(), &ring.base_ring().int_hom().map(2), &element_vec.at(k));
                } else {
                    assert_el_eq!(ring.base_ring(), &ring.base_ring().zero(), &element_vec.at(k));
                }
            }
        }
    }
}