use std::fmt::Debug;
use num_bigint::BigInt;
use num_integer::Integer;
use num_rational::Ratio;
use num_traits::{Signed, Zero};
mod sealed {
pub trait CoefficientSystem {}
pub trait Encoding {}
}
pub trait CoefficientSystem: sealed::CoefficientSystem + Clone + Debug + 'static {
type Element: Clone + Debug + Eq;
fn zero(&self) -> Self::Element;
fn is_zero(&self, value: &Self::Element) -> bool;
fn add_assign(&self, target: &mut Self::Element, value: &Self::Element);
fn multiply(&self, left: &Self::Element, right: &Self::Element) -> Self::Element;
fn same_system(&self, other: &Self) -> bool;
}
pub trait Ring: CoefficientSystem {
fn negate(&self, value: &Self::Element) -> Self::Element;
fn lift_i64(&self, value: i64) -> Self::Element;
}
pub trait CommutativeRing: Ring {}
pub trait IntegralDomain: CommutativeRing {}
pub trait EuclideanDomain: IntegralDomain {
fn quotient_remainder(
&self,
dividend: &Self::Element,
divisor: &Self::Element,
) -> Option<(Self::Element, Self::Element)>;
fn gcd(&self, left: &Self::Element, right: &Self::Element) -> Self::Element;
}
pub trait Field: IntegralDomain {
fn inverse(&self, value: &Self::Element) -> Option<Self::Element>;
fn divide(
&self,
numerator: &Self::Element,
denominator: &Self::Element,
) -> Option<Self::Element> {
self.inverse(denominator)
.map(|inverse| self.multiply(numerator, &inverse))
}
}
pub trait RingMorphism<Source: Ring>: Ring {
fn inject(&self, value: &Source::Element) -> Self::Element;
}
pub trait FractionFieldOf<Base: IntegralDomain>: Field + RingMorphism<Base> {
fn base_ring(&self) -> &Base;
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct IntegerRing;
impl sealed::CoefficientSystem for IntegerRing {}
impl CoefficientSystem for IntegerRing {
type Element = BigInt;
#[inline]
fn zero(&self) -> Self::Element {
BigInt::zero()
}
#[inline]
fn is_zero(&self, value: &Self::Element) -> bool {
value.is_zero()
}
#[inline]
fn add_assign(&self, target: &mut Self::Element, value: &Self::Element) {
*target += value;
}
#[inline]
fn multiply(&self, left: &Self::Element, right: &Self::Element) -> Self::Element {
left * right
}
#[inline]
fn same_system(&self, _other: &Self) -> bool {
true
}
}
impl Ring for IntegerRing {
#[inline]
fn negate(&self, value: &Self::Element) -> Self::Element {
-value
}
#[inline]
fn lift_i64(&self, value: i64) -> Self::Element {
BigInt::from(value)
}
}
impl CommutativeRing for IntegerRing {}
impl IntegralDomain for IntegerRing {}
impl EuclideanDomain for IntegerRing {
fn quotient_remainder(
&self,
dividend: &Self::Element,
divisor: &Self::Element,
) -> Option<(Self::Element, Self::Element)> {
(!divisor.is_zero()).then(|| {
let modulus = divisor.abs();
let (quotient, remainder) = dividend.div_mod_floor(&modulus);
if divisor.is_negative() {
(-quotient, remainder)
} else {
(quotient, remainder)
}
})
}
fn gcd(&self, left: &Self::Element, right: &Self::Element) -> Self::Element {
left.gcd(right)
}
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct FractionField<A>(A);
impl<A: IntegralDomain> FractionField<A> {
#[must_use]
pub const fn new(base: A) -> Self {
Self(base)
}
}
pub type RationalField = FractionField<IntegerRing>;
pub type ExactRational = Ratio<BigInt>;
impl sealed::CoefficientSystem for RationalField {}
impl CoefficientSystem for RationalField {
type Element = ExactRational;
#[inline]
fn zero(&self) -> Self::Element {
ExactRational::zero()
}
#[inline]
fn is_zero(&self, value: &Self::Element) -> bool {
value.is_zero()
}
#[inline]
fn add_assign(&self, target: &mut Self::Element, value: &Self::Element) {
*target += value;
}
#[inline]
fn multiply(&self, left: &Self::Element, right: &Self::Element) -> Self::Element {
left * right
}
fn same_system(&self, other: &Self) -> bool {
self.0.same_system(&other.0)
}
}
impl Ring for RationalField {
fn negate(&self, value: &Self::Element) -> Self::Element {
-value
}
#[inline]
fn lift_i64(&self, value: i64) -> Self::Element {
ExactRational::from_integer(BigInt::from(value))
}
}
impl CommutativeRing for RationalField {}
impl IntegralDomain for RationalField {}
impl Field for RationalField {
fn inverse(&self, value: &Self::Element) -> Option<Self::Element> {
(!value.is_zero()).then(|| ExactRational::new(value.denom().clone(), value.numer().clone()))
}
}
impl RingMorphism<IntegerRing> for RationalField {
fn inject(&self, value: &BigInt) -> Self::Element {
ExactRational::from_integer(value.clone())
}
}
impl FractionFieldOf<IntegerRing> for RationalField {
fn base_ring(&self) -> &IntegerRing {
&self.0
}
}
pub trait ValueEncoding<A: CoefficientSystem>: sealed::Encoding + Clone + Debug + 'static {
type Stored: Clone + Debug + Eq;
fn encode(value: A::Element) -> Self::Stored;
fn element(value: &Self::Stored) -> &A::Element;
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct BigIntEncoding;
impl sealed::Encoding for BigIntEncoding {}
impl ValueEncoding<IntegerRing> for BigIntEncoding {
type Stored = BigInt;
#[inline]
fn encode(value: BigInt) -> Self::Stored {
value
}
#[inline]
fn element(value: &Self::Stored) -> &BigInt {
value
}
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct ReducedFractionEncoding;
impl sealed::Encoding for ReducedFractionEncoding {}
impl ValueEncoding<RationalField> for ReducedFractionEncoding {
type Stored = ExactRational;
#[inline]
fn encode(value: ExactRational) -> Self::Stored {
value
}
#[inline]
fn element(value: &Self::Stored) -> &ExactRational {
value
}
}