polygeo-core 0.1.0

Proof-bearing native topology core for PolyGeo
Documentation
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 {}
}

/// Law-bearing coefficient system used by exact chain algebra.
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;
}

/// Coefficient systems with exact additive inverses.
pub trait Ring: CoefficientSystem {
    fn negate(&self, value: &Self::Element) -> Self::Element;
    fn lift_i64(&self, value: i64) -> Self::Element;
}

/// Rings whose multiplication is commutative.
pub trait CommutativeRing: Ring {}

/// Commutative rings with no nonzero zero divisors.
pub trait IntegralDomain: CommutativeRing {}

/// Integral domains with canonical Euclidean division and gcd.
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;
}

/// Integral domains in which every nonzero element is invertible.
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))
    }
}

/// A canonical injective ring morphism from `Source` into `Self`.
pub trait RingMorphism<Source: Ring>: Ring {
    fn inject(&self, value: &Source::Element) -> Self::Element;
}

/// Evidence that `Self` is the fraction field generated by `Base`.
pub trait FractionFieldOf<Base: IntegralDomain>: Field + RingMorphism<Base> {
    fn base_ring(&self) -> &Base;
}

/// The canonical ring of arbitrary-precision integers.
#[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)
    }
}

/// Law-bearing fraction-field constructor over one integral domain.
#[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)
    }
}

/// The exact rational field generated by arbitrary-precision integers.
pub type RationalField = FractionField<IntegerRing>;

/// Canonical reduced arbitrary-precision rational scalar.
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
    }
}

/// External relation between a coefficient system and one machine encoding.
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;
}

/// Canonical arbitrary-precision integer encoding.
#[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
    }
}

/// Canonical normalized arbitrary-precision rational encoding.
#[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
    }
}