geoit 0.0.2

/// Exact rational number: num/den, always in canonical form.
///
/// Invariants:
/// - den > 0
/// - gcd(|num|, den) == 1
/// - Zero is Rat { num: 0, den: 1 }
#[derive(Clone, Copy, Debug)]
pub struct Rat {
    pub(crate) num: i128,
    pub(crate) den: u128,
}

fn gcd(mut a: u128, mut b: u128) -> u128 {
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

impl Rat {
    pub fn new(num: i128, den: i128) -> Self {
        assert!(den != 0, "Rat: denominator is zero");
        let (num, den) = if den < 0 {
            (-num, (-den) as u128)
        } else {
            (num, den as u128)
        };
        let g = gcd(num.unsigned_abs(), den);
        Rat {
            num: num / g as i128,
            den: den / g,
        }
    }

    pub const ZERO: Rat = Rat { num: 0, den: 1 };

    /// Raw constructor: assumes already canonical (GCD = 1, den > 0).
    /// Used by the codec for decoded data that was produced by encoding a valid Rat.
    #[inline]
    pub fn new_raw(num: i128, den: u128) -> Self {
        debug_assert!(den > 0);
        Rat { num, den }
    }
    pub const ONE: Rat = Rat { num: 1, den: 1 };
    pub const NEG_ONE: Rat = Rat { num: -1, den: 1 };

    #[inline]
    pub fn num(self) -> i128 {
        self.num
    }
    #[inline]
    pub fn den(self) -> u128 {
        self.den
    }
    #[inline]
    pub fn is_zero(self) -> bool {
        self.num == 0
    }
    #[inline]
    pub fn is_positive(self) -> bool {
        self.num > 0
    }
    #[inline]
    pub fn is_negative(self) -> bool {
        self.num < 0
    }
    #[inline]
    pub fn abs(self) -> Self {
        Rat {
            num: self.num.abs(),
            den: self.den,
        }
    }

    /// Construct from already-canonical numerator and denominator.
    /// Caller guarantees: den > 0, gcd(|num|, den) == 1.
    pub(crate) fn from_raw(num: i128, den: u128) -> Self {
        debug_assert!(den > 0);
        Rat { num, den }
    }

    pub fn recip(self) -> Self {
        assert!(!self.is_zero(), "Rat: reciprocal of zero");
        if self.num > 0 {
            Rat {
                num: self.den as i128,
                den: self.num as u128,
            }
        } else {
            Rat {
                num: -(self.den as i128),
                den: (-self.num) as u128,
            }
        }
    }

    /// Checked addition — returns None on overflow beyond i128.
    pub fn checked_add(self, rhs: Self) -> Option<Self> {
        use crate::scalar::bigint::BigInt;
        let a_num = BigInt::from_i128(self.num);
        let a_den = BigInt::from_u128(self.den);
        let b_num = BigInt::from_i128(rhs.num);
        let b_den = BigInt::from_u128(rhs.den);
        let ad = a_num.mul(&b_den);
        let cb = b_num.mul(&a_den);
        let num_big = ad.add(&cb);
        let den_big = a_den.mul(&b_den);
        let g = num_big.abs().gcd(&den_big);
        let num_reduced = num_big.div(&g);
        let den_reduced = den_big.div(&g);
        let num = num_reduced.to_i128()?;
        let den = den_reduced.to_u128()?;
        if den == 0 {
            return None;
        }
        Some(Rat { num, den })
    }

    /// Checked multiplication — returns None on overflow beyond i128.
    pub fn checked_mul(self, rhs: Self) -> Option<Self> {
        let g1 = gcd(self.num.unsigned_abs(), rhs.den);
        let g2 = gcd(rhs.num.unsigned_abs(), self.den);
        let a = self.num / g1 as i128;
        let b = self.den / g2;
        let c = rhs.num / g2 as i128;
        let d = rhs.den / g1;
        let num = a.checked_mul(c)?;
        let den = b.checked_mul(d)?;
        Some(Rat { num, den })
    }
}

impl PartialEq for Rat {
    fn eq(&self, other: &Self) -> bool {
        self.num == other.num && self.den == other.den
    }
}
impl Eq for Rat {}

impl PartialOrd for Rat {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Rat {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // a/b vs c/d: compare a*d vs c*b — use BigInt to avoid overflow
        use crate::scalar::bigint::BigInt;
        let lhs = BigInt::from_i128(self.num).mul(&BigInt::from_u128(other.den));
        let rhs = BigInt::from_i128(other.num).mul(&BigInt::from_u128(self.den));
        lhs.cmp(&rhs)
    }
}

impl std::ops::Neg for Rat {
    type Output = Self;
    fn neg(self) -> Self {
        Rat {
            num: -self.num,
            den: self.den,
        }
    }
}

impl std::ops::Add for Rat {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        let g = gcd(self.den, rhs.den);
        let lcm_half = self.den / g;
        let d_over_g = rhs.den / g;
        if let (Some(ad), Some(cb)) = (
            self.num.checked_mul(d_over_g as i128),
            rhs.num.checked_mul(lcm_half as i128),
        ) {
            if let Some(num_sum) = ad.checked_add(cb) {
                if let Some(new_den) = lcm_half.checked_mul(rhs.den) {
                    let g2 = gcd(num_sum.unsigned_abs(), new_den);
                    return Rat {
                        num: num_sum / g2 as i128,
                        den: new_den / g2,
                    };
                }
            }
        }
        // Overflow in i128: fall back to BigInt intermediates
        self.checked_add(rhs)
            .expect("Rat addition overflow beyond BigInt → i128 capacity")
    }
}

impl std::ops::Sub for Rat {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        self + (-rhs)
    }
}

impl std::ops::Mul for Rat {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        if self.is_zero() || rhs.is_zero() {
            return Rat::ZERO;
        }
        let g1 = gcd(self.num.unsigned_abs(), rhs.den);
        let g2 = gcd(rhs.num.unsigned_abs(), self.den);
        let a = self.num / g1 as i128;
        let b = self.den / g2;
        let c = rhs.num / g2 as i128;
        let d = rhs.den / g1;
        if let (Some(num), Some(den)) = (a.checked_mul(c), b.checked_mul(d)) {
            return Rat { num, den };
        }
        use crate::scalar::bigint::BigInt;
        let num_big = BigInt::from_i128(a).mul(&BigInt::from_i128(c));
        let den_big = BigInt::from_u128(b).mul(&BigInt::from_u128(d));
        Rat {
            num: num_big
                .to_i128()
                .expect("Rat mul overflow beyond i128 after cross-reduction"),
            den: den_big
                .to_u128()
                .expect("Rat mul overflow beyond u128 after cross-reduction"),
        }
    }
}

impl std::ops::Div for Rat {
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        assert!(!rhs.is_zero(), "Rat: division by zero");
        self * rhs.recip()
    }
}

impl std::ops::AddAssign for Rat {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}
impl std::ops::SubAssign for Rat {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}
impl std::ops::MulAssign for Rat {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl From<i64> for Rat {
    fn from(n: i64) -> Self {
        Rat {
            num: n as i128,
            den: 1,
        }
    }
}
impl From<(i64, i64)> for Rat {
    fn from((n, d): (i64, i64)) -> Self {
        Rat::new(n as i128, d as i128)
    }
}

impl std::fmt::Display for Rat {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.den == 1 {
            write!(f, "{}", self.num)
        } else {
            write!(f, "{}/{}", self.num, self.den)
        }
    }
}

impl std::hash::Hash for Rat {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.num.hash(state);
        self.den.hash(state);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn zero() {
        let z = Rat::ZERO;
        assert!(z.is_zero());
        assert_eq!(z, Rat::from(0i64));
    }
    #[test]
    fn canonical() {
        let r = Rat::new(6, 4);
        assert_eq!(r.num(), 3);
        assert_eq!(r.den(), 2);
    }
    #[test]
    fn neg_num() {
        let r = Rat::new(-6, 4);
        assert_eq!(r.num(), -3);
        assert_eq!(r.den(), 2);
    }
    #[test]
    fn neg_den() {
        let r = Rat::new(6, -4);
        assert_eq!(r.num(), -3);
        assert_eq!(r.den(), 2);
    }
    #[test]
    fn both_neg() {
        let r = Rat::new(-6, -4);
        assert_eq!(r.num(), 3);
        assert_eq!(r.den(), 2);
    }
    #[test]
    fn zero_num() {
        let r = Rat::new(0, 5);
        assert!(r.is_zero());
        assert_eq!(r.den(), 1);
    }

    #[test]
    fn add() {
        assert_eq!(Rat::new(1, 2) + Rat::new(1, 3), Rat::new(5, 6));
    }
    #[test]
    fn sub() {
        assert_eq!(Rat::new(5, 6) - Rat::new(1, 3), Rat::new(1, 2));
    }
    #[test]
    fn mul() {
        assert_eq!(Rat::new(2, 3) * Rat::new(3, 5), Rat::new(2, 5));
    }
    #[test]
    fn div() {
        assert_eq!(Rat::new(2, 3) / Rat::new(4, 5), Rat::new(5, 6));
    }
    #[test]
    fn recip_test() {
        assert_eq!(Rat::new(3, 7).recip(), Rat::new(7, 3));
    }
    #[test]
    fn neg_test() {
        assert_eq!((-Rat::new(3, 7)).num(), -3);
    }
    #[test]
    fn ord_test() {
        assert!(Rat::new(1, 3) < Rat::new(1, 2));
    }
    #[test]
    fn display_test() {
        assert_eq!(format!("{}", Rat::new(3, 7)), "3/7");
    }

    #[test]
    fn large_i128_addition() {
        let a = Rat::new(i64::MAX as i128, 1);
        let b = Rat::new(i64::MAX as i128, 1);
        let c = a + b;
        assert_eq!(c.num(), (i64::MAX as i128) * 2);
    }

    #[test]
    fn checked_add_beyond_i128() {
        let a = Rat::new(i128::MAX / 2 + 1, 1);
        let b = Rat::new(i128::MAX / 2 + 1, 1);
        assert!(a.checked_add(b).is_none());
    }

    #[test]
    fn large_mul_cross_reduced() {
        // Values that would overflow i64 but cross-reduce to fit i128
        let big = i64::MAX as i128;
        let a = Rat::new(big, 7); // (i64::MAX)/7
        let b = Rat::new(7, big); // 7/(i64::MAX)
        let c = a * b; // cross-reduces to 1
        assert_eq!(c, Rat::ONE);
    }

    #[test]
    #[should_panic(expected = "denominator is zero")]
    fn zero_den() {
        let _ = Rat::new(1, 0);
    }
    #[test]
    #[should_panic(expected = "reciprocal of zero")]
    fn recip_zero() {
        let _ = Rat::ZERO.recip();
    }
    #[test]
    #[should_panic(expected = "division by zero")]
    fn div_zero() {
        let _ = Rat::from(1) / Rat::ZERO;
    }
}