use crate::algorithms::conv_mul::ConvMulComputation;
use crate::algorithms::poly_factor::FactorPolyField;
use crate::divisibility::*;
use crate::impl_wrap_unwrap_homs;
use crate::impl_wrap_unwrap_isos;
use crate::integer::IntegerRing;
use crate::integer::IntegerRingStore;
use crate::matrix::Matrix;
use crate::mempool::MemoryProvider;
use crate::pid::PrincipalIdealRing;
use crate::rings::field::AsField;
use crate::rings::field::AsFieldBase;
use crate::delegate::DelegateRing;
use crate::rings::finite::*;
use crate::rings::poly::PolyRingStore;
use crate::rings::poly::dense_poly::DensePolyRing;
use crate::vector::vec_fn::RingElVectorViewFn;
use crate::ring::*;
use crate::algorithms;
use crate::vector::VectorView;
use crate::iters::*;
use crate::mempool::DefaultMemoryProvider;

use super::*;

/// 
/// Implementation for rings that are generated by a single algebraic element over a base ring,
/// equivalently a quotient of a univariate polynomial ring `R[X]/(f(X))`.
/// 
/// # Example
/// ```
/// # use feanor_math::ring::*;
/// # use feanor_math::rings::extension::*;
/// # use feanor_math::primitive_int::*;
/// # use feanor_math::rings::extension::extension_impl::*;
/// # use feanor_math::{default_memory_provider, assert_el_eq};
/// 
/// let base_ring = StaticRing::<i64>::RING;
/// // ring of integers in the 6th cyclotomic number field
/// let ring = FreeAlgebraImpl::new(base_ring, [-1, 1], default_memory_provider!());
/// let root_of_unity = ring.canonical_gen();
/// assert_el_eq!(&ring, &ring.one(), &ring.pow(root_of_unity, 6));
/// ```
/// 
/// # A note on division
/// 
///  - if the base ring is a field, then F[X] is a PID - we can use XGCD
///  - if the base ring is Z, then we can consider Z[X]/(f(X)) ⊗ Q and f has the same factorization in Q as
///    in Z (Gauss' lemma)
///  - if the base ring is Z/nZ, then it is already quite difficult (GB-like difficulties, see the following).
///    We need to use either general linear algebra or GBs (if that is not really the same anyway)
///  - if the base ring is a free extension itself, things are again complicated. In general,
///    it seems like we cannot avoid Groebner basis here, as even checking whether a polynomial is
///    in (f(X), g(X, Y), h(X, Y, Z), ...) - i.e. is zero modulo that ideal - requires them;
///    I do not think that I will implement this here - possibly create a trait `IdealMembershipRing`
///    and an implementation of general quotient rings
///  
/// As an example why already the "simple" case Z/9Z is difficult, consider
/// 
/// f = X^2 + 2X
/// g = 3X + 1
/// h = 3X^3 - 2X
/// 
/// The question is, is h in (f, g) over Z9[X] or equivalently, can we divide h/f in Z9[X]/(g)
/// 
/// Note that "euclidean division" can give
/// ```text
/// h - g*X^2 + f = 0
/// h - f*3*X - g*X - 2*g = 7
/// h - f*3*X - 3*f = X
/// ```
/// In fact, this already behaves mostly like general GB-style situations
/// 
pub struct FreeAlgebraImplBase<R, V, M>
    where R: RingStore, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    base_ring: R,
    x_pow_rank: V,
    memory_provider: M
}

pub struct FreeAlgebraEl<R, M>
    where R: RingStore, M: MemoryProvider<El<R>>
{
    values: M::Object
}

/// 
/// Implementation for rings that are generated by a single algebraic element over a base ring,
/// equivalently a quotient of a univariate polynomial ring `R[X]/(f(X))`. For details, see
/// [`FreeAlgebraImplBase`].
/// 
pub type FreeAlgebraImpl<R, V, M = DefaultMemoryProvider> = RingValue<FreeAlgebraImplBase<R, V, M>>;

impl<R, V, M> FreeAlgebraImpl<R, V, M>
    where R: RingStore, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    pub const fn new(base_ring: R, x_pow_rank: V, memory_provider: M) -> FreeAlgebraImpl<R, V, M> {
        RingValue::from(FreeAlgebraImplBase {
            base_ring, x_pow_rank, memory_provider
        })
    }
}

impl<R, V, M> FreeAlgebraImpl<R, V, M>
    where R: RingStore, R::Type: FactorPolyField, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    pub fn as_field(self) -> Result<AsField<Self>, Self> {
        let poly_ring = DensePolyRing::new(self.base_ring(), "X");
        let f = poly_ring.from_terms(
            self.get_ring().x_pow_rank.iter().enumerate().map(|(i, c)| (self.base_ring().negate(self.base_ring().clone_el(c)), i))
                .chain([(self.base_ring().one(), self.get_ring().x_pow_rank.len())].into_iter())
        );
        let (factorization, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &f);
        assert_el_eq!(self.base_ring(), &self.base_ring().one(), &unit);
        if factorization.len() == 0 || (factorization.len() == 1 && factorization[0].1 == 1) {
            return Ok(RingValue::from(AsFieldBase::promise_is_field(self)));
        } else {
            return Err(self);
        }
    }
}

impl<R, V, M> Clone for FreeAlgebraImplBase<R, V, M>
    where R: RingStore + Clone, V: VectorView<El<R>> + Clone, M: MemoryProvider<El<R>> + Clone
{
    fn clone(&self) -> Self {
        Self {
            base_ring: self.base_ring.clone(),
            x_pow_rank: self.x_pow_rank.clone(),
            memory_provider: self.memory_provider.clone()
        }
    }
}

impl<R, V, M> PartialEq for FreeAlgebraImplBase<R, V, M>
    where R: RingStore, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    fn eq(&self, other: &Self) -> bool {
        self.base_ring.get_ring() == other.base_ring.get_ring() && self.rank() == other.rank() && (0..self.rank()).all(|i| self.base_ring.eq_el(self.x_pow_rank.at(i), other.x_pow_rank.at(i)))
    }
}

impl<R, V, M> RingBase for FreeAlgebraImplBase<R, V, M>
    where R: RingStore, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    type Element = FreeAlgebraEl<R, M>;

    fn clone_el(&self, val: &Self::Element) -> Self::Element {
        FreeAlgebraEl { values: self.memory_provider.get_new_init(self.rank(), |i| self.base_ring.clone_el(val.values.at(i))) }
    }

    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
        for i in 0..self.rank() {
            self.base_ring.add_assign_ref(&mut lhs.values[i], &rhs.values[i]);
        }
    }

    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        self.add_assign_ref(lhs, &rhs);
    }

    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
        for i in 0..self.rank() {
            self.base_ring.sub_assign_ref(&mut lhs.values[i], &rhs.values[i]);
        }
    }

    fn negate_inplace(&self, lhs: &mut Self::Element) {
        for i in 0..self.rank() {
            self.base_ring.negate_inplace(&mut lhs.values[i]);
        }
    }

    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        self.mul_assign_ref(lhs, &rhs);
    }

    default fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
        let mut tmp = self.memory_provider.get_new_init(self.rank() * 2, |_| self.base_ring.zero());
        <_ as ConvMulComputation>::add_assign_conv_mul(self.base_ring().get_ring(), &mut tmp[..], &lhs.values[..], &rhs.values[..], &self.memory_provider);
        for i in (self.rank()..tmp.len()).rev() {
            for j in 0..self.rank() {
                let add = self.base_ring.mul_ref(self.x_pow_rank.at(j), &tmp[i]);
                self.base_ring.add_assign(&mut tmp[i - self.rank() + j], add);
            }
        }
        for i in 0..self.rank() {
            lhs.values[i] = std::mem::replace(&mut tmp[i], self.base_ring.zero());
        }
    }

    fn from_int(&self, value: i32) -> Self::Element {
        self.from(self.base_ring.int_hom().map(value))
    }

    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
        (0..self.rank()).all(|i| self.base_ring.eq_el(lhs.values.at(i), rhs.values.at(i)))
    }
    
    fn is_commutative(&self) -> bool {
        self.base_ring.is_commutative()
    }

    fn is_noetherian(&self) -> bool {
        self.base_ring.is_noetherian()
    }
    
    fn dbg<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        let poly_ring = DensePolyRing::new(self.base_ring(), "θ");
        poly_ring.get_ring().dbg(&RingRef::new(self).poly_repr(&poly_ring, value, &self.base_ring().identity()), out)
    }

    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) {
        self.mul_assign(lhs, self.from_int(rhs));
    }
    
    fn characteristic<I: IntegerRingStore>(&self, ZZ: &I) -> Option<El<I>>
        where I::Type: IntegerRing
    {
        self.base_ring().characteristic(ZZ)
    }
}

// impl<R, M> RingBase for FreeAlgebraImplBase<R, SparseVectorMut<R>, M>
//     where R: RingStore, M: MemoryProvider<El<R>>
// {
//     fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
//         let mut tmp = self.memory_provider.get_new_init(self.rank() * 2, |_| self.base_ring.zero());
//         algorithms::conv_mul::add_assign_convoluted_mul(&mut tmp[..], &lhs.values[..], &rhs.values[..], self.base_ring(), &self.memory_provider);
//         for i in self.rank()..tmp.len() {
//             for (j, c) in self.x_pow_rank.nontrivial_entries() {
//                 let add = self.base_ring.mul_ref(c, &tmp[i]);
//                 self.base_ring.add_assign(&mut tmp[i - self.rank() + j], add);
//             }
//         }
//         for i in 0..self.rank() {
//             lhs.values[i] = std::mem::replace(&mut tmp[i], self.base_ring.zero());
//         }
//     }
// }

pub struct WRTCanonicalBasisElementCreator<'a, R, V, M>
    where R: RingStore, R::Type: FiniteRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    base_ring: &'a FreeAlgebraImplBase<R, V, M>
}

impl<'a, R, V, M> Clone for WRTCanonicalBasisElementCreator<'a, R, V, M>
    where R: RingStore, R::Type: FiniteRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    fn clone(&self) -> Self { *self }
}

impl<'a, 'b, R, V, M> FnOnce<(&'b [El<R>], )> for WRTCanonicalBasisElementCreator<'a, R, V, M>
    where R: RingStore, R::Type: FiniteRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    type Output = El<FreeAlgebraImpl<R, V, M>>;

    extern "rust-call" fn call_once(mut self, args: (&'b [El<R>], )) -> Self::Output {
        self.call_mut(args)
    }
}

impl<'a, 'b, R, V, M> FnMut<(&'b [El<R>], )> for WRTCanonicalBasisElementCreator<'a, R, V, M>
    where R: RingStore, R::Type: FiniteRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    extern "rust-call" fn call_mut(&mut self, args: (&'b [El<R>], )) -> Self::Output {
        self.base_ring.from_canonical_basis(args.0.iter().map(|x| self.base_ring.base_ring().clone_el(x)))
    }
}

impl<'a, R, V, M> Copy for WRTCanonicalBasisElementCreator<'a, R, V, M>
    where R: RingStore, R::Type: FiniteRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{}

impl<R, V, M> FiniteRing for FreeAlgebraImplBase<R, V, M>
    where R: RingStore, R::Type: FiniteRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    type ElementsIter<'a> = MultiProduct<<R::Type as FiniteRing>::ElementsIter<'a>, WRTCanonicalBasisElementCreator<'a, R, V, M>, RingElementClone<'a, R::Type>, Self::Element>
        where Self: 'a;

    fn elements<'a>(&'a self) -> Self::ElementsIter<'a> {
        multi_cartesian_product((0..self.rank()).map(|_| self.base_ring().elements()), WRTCanonicalBasisElementCreator { base_ring: self }, RingElementClone::new(self.base_ring().get_ring()))
    }

    fn size<I: IntegerRingStore>(&self, ZZ: &I) -> Option<El<I>>
        where I::Type: IntegerRing
    {
        let base_ring_size = self.base_ring().size(ZZ)?;
        if ZZ.get_ring().representable_bits().is_none() || ZZ.abs_log2_ceil(&base_ring_size).unwrap() * self.rank() < ZZ.get_ring().representable_bits().unwrap() {
            Some(ZZ.pow(base_ring_size, self.rank()))
        } else {
            None
        }
    }

    fn random_element<G: FnMut() -> u64>(&self, mut rng: G) -> <Self as RingBase>::Element {
        self.from_canonical_basis((0..self.rank()).map(|_| self.base_ring().random_element(&mut rng)))
    }
}

impl<R, V, M> DivisibilityRing for FreeAlgebraImplBase<R, V, M>
    where R: RingStore, R::Type: PrincipalIdealRing, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
        let mut mul_matrix = RingRef::new(self).create_multiplication_matrix(rhs);
        let mut lhs_matrix = DenseMatrix::zero(self.rank(), 1, self.base_ring());
        let data = self.wrt_canonical_basis(&lhs);
        for j in 0..self.rank() {
            *lhs_matrix.at_mut(j, 0) = data.at(j);
        }
        let solution = algorithms::smith::solve_right(&mut mul_matrix, lhs_matrix, self.base_ring())?;
        return Some(self.from_canonical_basis((0..self.rank()).map(|i| self.base_ring().clone_el(solution.entry_at(i, 0)))));
    }
}

impl<R, V, M> RingExtension for FreeAlgebraImplBase<R, V, M>
    where R: RingStore, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    type BaseRing = R;

    fn base_ring<'a>(&'a self) -> &'a Self::BaseRing {
        &self.base_ring
    }

    fn from(&self, x: El<Self::BaseRing>) -> Self::Element {
        let mut data = Some(x);
        FreeAlgebraEl { values: self.memory_provider.get_new_init(self.rank(), |i| if i == 0 { std::mem::replace(&mut data, None).unwrap() } else { self.base_ring.zero() }) }
    }

    fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
        for i in 0..self.rank() {
            self.base_ring.mul_assign_ref(&mut lhs.values[i], rhs);
        }
    }
}

impl<R, V, M> FreeAlgebra for FreeAlgebraImplBase<R, V, M>
    where R: RingStore, V: VectorView<El<R>>, M: MemoryProvider<El<R>>
{
    type VectorRepresentation<'a> = RingElVectorViewFn<&'a R, &'a [El<R>], El<R>>
        where Self: 'a;

    fn canonical_gen(&self) -> Self::Element {
        FreeAlgebraEl { values: self.memory_provider.get_new_init(self.rank(), |i| if i == 1 { self.base_ring.one() } else { self.base_ring.zero() }) }
    }

    fn wrt_canonical_basis<'a>(&'a self, el: &'a Self::Element) -> Self::VectorRepresentation<'a> {
        (&el.values[..]).as_el_fn(self.base_ring())
    }

    fn from_canonical_basis<W>(&self, mut vec: W) -> Self::Element
        where W: ExactSizeIterator + DoubleEndedIterator + Iterator<Item = El<Self::BaseRing>>
    {
        assert_eq!(self.rank(), <_ as ExactSizeIterator>::len(&vec));
        FreeAlgebraEl { values: self.memory_provider.get_new_init(self.rank(), |_| vec.next().unwrap()) }
    }

    fn rank(&self) -> usize {
        self.x_pow_rank.len()
    }
}

impl_wrap_unwrap_homs!{
    <{R1, V1, M1, R2, V2, M2}> FreeAlgebraImplBase<R1, V1, M1>, FreeAlgebraImplBase<R2, V2, M2>
        where R1: RingStore, R1::Type: PrincipalIdealRing, V1: VectorView<El<R1>>, M1: MemoryProvider<El<R1>>,
            R2: RingStore, R2::Type: PrincipalIdealRing, V2: VectorView<El<R2>>, M2: MemoryProvider<El<R2>>,
            R2::Type: CanHomFrom<R1::Type>
}

impl_wrap_unwrap_isos!{
    <{R1, V1, M1, R2, V2, M2}> FreeAlgebraImplBase<R1, V1, M1>, FreeAlgebraImplBase<R2, V2, M2>
        where R1: RingStore, R1::Type: PrincipalIdealRing, V1: VectorView<El<R1>>, M1: MemoryProvider<El<R1>>,
            R2: RingStore, R2::Type: PrincipalIdealRing, V2: VectorView<El<R2>>, M2: MemoryProvider<El<R2>>,
            R2::Type: CanIsoFromTo<R1::Type>
}

impl<R1, V1, M1, R2, V2, M2> CanHomFrom<FreeAlgebraImplBase<R1, V1, M1>> for FreeAlgebraImplBase<R2, V2, M2>
    where R1: RingStore, V1: VectorView<El<R1>>, M1: MemoryProvider<El<R1>>,
        R2: RingStore, V2: VectorView<El<R2>>, M2: MemoryProvider<El<R2>>,
        R2::Type: CanHomFrom<R1::Type>
{
    type Homomorphism = <R2::Type as CanHomFrom<R1::Type>>::Homomorphism;

    fn has_canonical_hom(&self, from: &FreeAlgebraImplBase<R1, V1, M1>) -> Option<Self::Homomorphism> {
        if self.rank() == from.rank() {
            let hom = self.base_ring.get_ring().has_canonical_hom(from.base_ring.get_ring())?;
            if (0..self.rank()).all(|i| self.base_ring.eq_el(self.x_pow_rank.at(i), &self.base_ring.get_ring().map_in_ref(from.base_ring.get_ring(), from.x_pow_rank.at(i), &hom))) {
                Some(hom)
            } else {
                None
            }
        } else {
            None
        }
    }

    fn map_in(&self, from: &FreeAlgebraImplBase<R1, V1, M1>, el: <FreeAlgebraImplBase<R1, V1, M1> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
        FreeAlgebraEl { values: self.memory_provider.get_new_init(self.rank(), |i| self.base_ring.get_ring().map_in_ref(from.base_ring.get_ring(), &el.values[i], hom)) }
    }
}

impl<R1, V1, M1, R2, V2, M2> CanIsoFromTo<FreeAlgebraImplBase<R1, V1, M1>> for FreeAlgebraImplBase<R2, V2, M2>
    where R1: RingStore, V1: VectorView<El<R1>>, M1: MemoryProvider<El<R1>>,
        R2: RingStore, V2: VectorView<El<R2>>, M2: MemoryProvider<El<R2>>,
        R2::Type: CanIsoFromTo<R1::Type>
{
    type Isomorphism = <R2::Type as CanIsoFromTo<R1::Type>>::Isomorphism;

    fn has_canonical_iso(&self, from: &FreeAlgebraImplBase<R1, V1, M1>) -> Option<Self::Isomorphism> {
        if self.rank() == from.rank() {
            let iso = self.base_ring.get_ring().has_canonical_iso(from.base_ring.get_ring())?;
            if (0..self.rank()).all(|i| from.base_ring.eq_el(&self.base_ring.get_ring().map_out(from.base_ring.get_ring(), self.base_ring.clone_el(self.x_pow_rank.at(i)), &iso), from.x_pow_rank.at(i))) {
                Some(iso)
            } else {
                None
            }
        } else {
            None
        }
    }

    fn map_out(&self, from: &FreeAlgebraImplBase<R1, V1, M1>, el: <FreeAlgebraImplBase<R2, V2, M2> as RingBase>::Element, iso: &Self::Isomorphism) -> <FreeAlgebraImplBase<R1, V1, M1> as RingBase>::Element {
        FreeAlgebraEl { values: from.memory_provider.get_new_init(self.rank(), |i| self.base_ring.get_ring().map_out(from.base_ring.get_ring(), self.base_ring.clone_el(&el.values[i]), iso)) }
    }
}

#[cfg(test)]
use crate::primitive_int::StaticRing;
#[cfg(test)]
use crate::default_memory_provider;
#[cfg(test)]
use crate::rings::zn::zn_64::Zn;
#[cfg(test)]
use crate::rings::zn::zn_static;

#[cfg(test)]
fn test_ring1_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, [i64; 2], DefaultMemoryProvider>, Vec<FreeAlgebraEl<StaticRing<i64>, DefaultMemoryProvider>>) {
    let ZZ = StaticRing::<i64>::RING;
    let R = FreeAlgebraImpl::new(ZZ, [1, 1], default_memory_provider!());
    let mut elements = Vec::new();
    for a in -3..=3 {
        for b in -3..=3 {
            elements.push(R.from_canonical_basis([a, b].into_iter()));
        }
    }
    return (R, elements);
}

#[cfg(test)]
fn test_ring2_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, [i64; 3], DefaultMemoryProvider>, Vec<FreeAlgebraEl<StaticRing<i64>, DefaultMemoryProvider>>) {
    let ZZ = StaticRing::<i64>::RING;
    let R = FreeAlgebraImpl::new(ZZ, [1, -1, 1], default_memory_provider!());
    let mut elements = Vec::new();
    for a in [-2, 0, 1, 2] {
        for b in [-2, 0, 2] {
            for c in [-2, 0, 2] {
                elements.push(R.from_canonical_basis([a, b, c].into_iter()));
            }
        }
    }
    return (R, elements);
}

#[test]
fn test_ring_axioms() {
    let (ring, els) = test_ring1_and_elements();
    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
    let (ring, els) = test_ring2_and_elements();
    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());

    let base_ring = zn_static::Fp::<257>::RING;
    let x_pow_rank = vec![base_ring.neg_one(); 64];
    let ring = FreeAlgebraImpl::new(base_ring, x_pow_rank, default_memory_provider!());
    let mut rng = oorandom::Rand64::new(0);
    let els = (0..10).map(|_| ring.from_canonical_basis((0..64).map(|_| ring.base_ring().random_element(|| rng.rand_u64()))));
    crate::ring::generic_tests::test_ring_axioms(&ring, els);
}

#[test]
fn test_free_algebra_axioms() {
    let (ring, _) = test_ring1_and_elements();
    generic_test_free_algebra_axioms(ring);
    let (ring, _) = test_ring2_and_elements();
    generic_test_free_algebra_axioms(ring);
}

#[test]
fn test_division() {
    let base_ring = Zn::new(4);
    let i = base_ring.int_hom();
    let ring = FreeAlgebraImpl::new(base_ring, [i.map(-1), i.map(-1)], default_memory_provider!());

    assert_el_eq!(&ring, 
        &ring.from_canonical_basis([i.map(1), i.map(3)].into_iter()), 
        &ring.checked_div(&ring.one(), &ring.from_canonical_basis([i.map(2), i.map(3)].into_iter())).unwrap()
    );

    let a = ring.from_canonical_basis([i.map(2), i.map(2)].into_iter());
    let b = ring.from_canonical_basis([i.map(0), i.map(2)].into_iter());
    assert_el_eq!(&ring, &a, &ring.mul(ring.checked_div(&a, &b).unwrap(), b));

    assert!(ring.checked_div(&ring.one(), &a).is_none());
}

#[test]
fn test_division_ring_of_integers() {
    let base_ring = StaticRing::<i64>::RING;
    let ring = FreeAlgebraImpl::new(base_ring, [11, 0], default_memory_provider!());

    // the solution to Pell's equation is 10^2 - 3^2 * 11 = 1
    let u = ring.from_canonical_basis([10, 3].into_iter());
    let u_inv = ring.from_canonical_basis([10, -3].into_iter());

    assert_el_eq!(&ring, &u_inv, &ring.checked_div(&ring.one(), &u).unwrap());
    assert_el_eq!(&ring, &ring.pow(u_inv, 3), &ring.checked_div(&ring.one(), &ring.pow(u, 3)).unwrap());

    assert!(ring.checked_div(&ring.from_canonical_basis([2, 0].into_iter()), &ring.from_canonical_basis([3, 0].into_iter())).is_none());
}

#[test]
fn test_divisibility_axioms() {
    let (ring, els) = test_ring1_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
    let (ring, els) = test_ring2_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
}

#[test]
fn test_cubic_mul() {
    let base_ring = zn_static::Zn::<256>::RING;
    let modulo = base_ring.int_hom();
    let ring = FreeAlgebraImpl::new(base_ring, [modulo.map(-1), modulo.map(-1), modulo.map(-1)], default_memory_provider!());
    let a = ring.from_canonical_basis([modulo.map(0), modulo.map(-1), modulo.map(-1)].into_iter());
    let b = ring.from_canonical_basis([modulo.map(-1), modulo.map(-2), modulo.map(-1)].into_iter());
    assert_el_eq!(&ring, &b, &ring.pow(a, 2));
}