geoit 0.0.2

//! Arbitrary-precision rational number.
//!
//! `BigRat` = `BigInt` numerator / `BigUint` denominator, always in canonical form:
//! - denominator > 0
//! - gcd(|numerator|, denominator) == 1
//! - zero is `BigRat { num: BigInt::zero(), den: BigUint::one() }`
//!
//! This type exists as the overflow escape from `Rat` (i64/u64).
//! Every operation attempts demotion back to `Rat` via `to_rat()`.

use crate::scalar::bigint::{BigInt, BigUint};
use crate::scalar::rat::Rat;
use std::cmp::Ordering;

/// Arbitrary-precision rational number: num/den, always canonical.
#[derive(Clone, Debug)]
pub struct BigRat {
    num: BigInt,
    den: BigUint,
}

impl BigRat {
    // ─── Constructors ───

    pub fn zero() -> Self {
        BigRat {
            num: BigInt::zero(),
            den: BigUint::one(),
        }
    }

    pub fn one() -> Self {
        BigRat {
            num: BigInt::one(),
            den: BigUint::one(),
        }
    }

    /// Construct from numerator and denominator. Normalizes to canonical form.
    /// Panics if denominator is zero.
    pub fn new(num: BigInt, den: BigInt) -> Self {
        assert!(!den.is_zero(), "BigRat: denominator is zero");

        if num.is_zero() {
            return Self::zero();
        }

        // Ensure denominator is positive
        let (num, den_mag) = if den.is_negative() {
            (num.neg(), den.magnitude().clone())
        } else {
            (num, den.magnitude().clone())
        };

        // Reduce by GCD
        let g = num.magnitude().gcd(&den_mag);
        if g.is_one() {
            BigRat { num, den: den_mag }
        } else {
            let reduced_num = BigInt::from_sign_mag(num.is_negative(), num.magnitude().div(&g));
            let reduced_den = den_mag.div(&g);
            BigRat {
                num: reduced_num,
                den: reduced_den,
            }
        }
    }

    /// Construct from a `Rat` (i64/u64) — lossless promotion.
    pub fn from_rat(r: Rat) -> Self {
        if r.is_zero() {
            return Self::zero();
        }
        BigRat {
            num: BigInt::from_i128(r.num()),
            den: BigUint::from_u128(r.den()),
        }
    }

    /// Raw constructor from pre-normalized parts. Used by codec.
    pub fn from_parts(num: BigInt, den: BigUint) -> Self {
        debug_assert!(!den.is_zero());
        BigRat { num, den }
    }

    /// Construct from i128 integer.
    pub fn from_i128(v: i128) -> Self {
        if v == 0 {
            return Self::zero();
        }
        BigRat {
            num: BigInt::from_i128(v),
            den: BigUint::one(),
        }
    }

    /// Construct from (i128 num, i128 den). Convenience.
    pub fn from_i128_pair(num: i128, den: i128) -> Self {
        Self::new(BigInt::from_i128(num), BigInt::from_i128(den))
    }

    // ─── Accessors ───

    pub fn numerator(&self) -> &BigInt {
        &self.num
    }
    pub fn denominator(&self) -> &BigUint {
        &self.den
    }

    pub fn is_zero(&self) -> bool {
        self.num.is_zero()
    }
    pub fn is_positive(&self) -> bool {
        self.num.is_positive()
    }
    pub fn is_negative(&self) -> bool {
        self.num.is_negative()
    }

    pub fn abs(&self) -> BigRat {
        BigRat {
            num: self.num.abs(),
            den: self.den.clone(),
        }
    }

    /// Try to demote to `Rat` (i128/u128). Returns `None` if value doesn't fit.
    pub fn to_rat(&self) -> Option<Rat> {
        let n = self.num.to_i128()?;
        let d = self.den.to_u128()?;
        if d == 0 {
            return None;
        }
        // Already canonical (gcd == 1), so just construct directly
        Some(Rat::from_raw(n, d))
    }

    /// Reciprocal. Panics on zero.
    pub fn recip(&self) -> BigRat {
        assert!(!self.is_zero(), "BigRat: reciprocal of zero");
        if self.num.is_positive() {
            BigRat {
                num: BigInt::from_sign_mag(false, self.den.clone()),
                den: self.num.magnitude().clone(),
            }
        } else {
            BigRat {
                num: BigInt::from_sign_mag(true, self.den.clone()),
                den: self.num.magnitude().clone(),
            }
        }
    }

    // ─── Arithmetic ───

    pub fn neg(&self) -> BigRat {
        BigRat {
            num: self.num.neg(),
            den: self.den.clone(),
        }
    }

    /// a/b + c/d = (a*d + c*b) / (b*d), then reduce.
    pub fn add(&self, rhs: &BigRat) -> BigRat {
        if self.is_zero() {
            return rhs.clone();
        }
        if rhs.is_zero() {
            return self.clone();
        }

        // Cross-multiply
        let ad = self.num.mul(&BigInt::from_sign_mag(false, rhs.den.clone()));
        let cb = rhs.num.mul(&BigInt::from_sign_mag(false, self.den.clone()));
        let new_num = ad.add(&cb);
        let new_den = BigInt::from_sign_mag(false, self.den.mul(&rhs.den));

        BigRat::new(new_num, new_den)
    }

    pub fn sub(&self, rhs: &BigRat) -> BigRat {
        self.add(&rhs.neg())
    }

    /// (a/b) * (c/d) = (a*c) / (b*d), with cross-reduction.
    pub fn mul(&self, rhs: &BigRat) -> BigRat {
        if self.is_zero() || rhs.is_zero() {
            return BigRat::zero();
        }

        // Cross-reduce to minimize intermediate sizes
        let g1 = self.num.magnitude().gcd(&rhs.den);
        let g2 = rhs.num.magnitude().gcd(&self.den);

        let num_a = BigInt::from_sign_mag(self.num.is_negative(), self.num.magnitude().div(&g1));
        let den_b = self.den.div(&g2);
        let num_c = BigInt::from_sign_mag(rhs.num.is_negative(), rhs.num.magnitude().div(&g2));
        let den_d = rhs.den.div(&g1);

        let new_num = num_a.mul(&num_c);
        let new_den = den_b.mul(&den_d);

        // Already fully reduced from cross-reduction
        BigRat {
            num: new_num,
            den: new_den,
        }
    }

    pub fn div(&self, rhs: &BigRat) -> BigRat {
        self.mul(&rhs.recip())
    }
}

// ─── Comparison ───

impl PartialEq for BigRat {
    fn eq(&self, other: &Self) -> bool {
        // Both canonical: equal iff num and den match
        self.num == other.num && self.den == other.den
    }
}
impl Eq for BigRat {}

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

impl Ord for BigRat {
    fn cmp(&self, other: &Self) -> Ordering {
        // a/b vs c/d: compare a*d vs c*b (both denominators positive)
        let lhs = self
            .num
            .mul(&BigInt::from_sign_mag(false, other.den.clone()));
        let rhs = other
            .num
            .mul(&BigInt::from_sign_mag(false, self.den.clone()));
        lhs.cmp(&rhs)
    }
}

// ─── Display ───

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

// ─── Operator impls ───

impl std::ops::Neg for BigRat {
    type Output = BigRat;
    fn neg(self) -> BigRat {
        BigRat::neg(&self)
    }
}

impl std::ops::Neg for &BigRat {
    type Output = BigRat;
    fn neg(self) -> BigRat {
        BigRat::neg(self)
    }
}

impl std::ops::Add for &BigRat {
    type Output = BigRat;
    fn add(self, rhs: Self) -> BigRat {
        BigRat::add(self, rhs)
    }
}

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

impl std::ops::Mul for &BigRat {
    type Output = BigRat;
    fn mul(self, rhs: Self) -> BigRat {
        BigRat::mul(self, rhs)
    }
}

impl std::ops::Div for &BigRat {
    type Output = BigRat;
    fn div(self, rhs: Self) -> BigRat {
        BigRat::div(self, rhs)
    }
}

// ─── From ───

impl From<Rat> for BigRat {
    fn from(r: Rat) -> Self {
        BigRat::from_rat(r)
    }
}

impl From<i128> for BigRat {
    fn from(v: i128) -> Self {
        BigRat::from_i128(v)
    }
}

impl From<i64> for BigRat {
    fn from(v: i64) -> Self {
        BigRat::from_i128(v as i128)
    }
}

// ═══════════════════════════════════════════════════════════
// TESTS
// ═══════════════════════════════════════════════════════════

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

    // ─── Construction ───

    #[test]
    fn bigrat_zero() {
        let z = BigRat::zero();
        assert!(z.is_zero());
        assert_eq!(format!("{}", z), "0");
    }

    #[test]
    fn bigrat_one() {
        let one = BigRat::one();
        assert!(one.is_positive());
        assert_eq!(format!("{}", one), "1");
    }

    #[test]
    fn bigrat_from_i128_pair() {
        let r = BigRat::from_i128_pair(6, 4);
        assert_eq!(format!("{}", r), "3/2"); // reduced
    }

    #[test]
    fn bigrat_from_i128_pair_negative_den() {
        let r = BigRat::from_i128_pair(3, -4);
        assert!(r.is_negative());
        assert_eq!(format!("{}", r), "-3/4");
    }

    #[test]
    fn bigrat_from_i128_pair_both_negative() {
        let r = BigRat::from_i128_pair(-3, -4);
        assert!(r.is_positive());
        assert_eq!(format!("{}", r), "3/4");
    }

    #[test]
    #[should_panic(expected = "denominator is zero")]
    fn bigrat_zero_den() {
        let _ = BigRat::from_i128_pair(1, 0);
    }

    // ─── Arithmetic ───

    #[test]
    fn bigrat_add_basic() {
        let a = BigRat::from_i128_pair(1, 2);
        let b = BigRat::from_i128_pair(1, 3);
        let c = a.add(&b);
        assert_eq!(format!("{}", c), "5/6");
    }

    #[test]
    fn bigrat_add_integer() {
        let a = BigRat::from_i128(3);
        let b = BigRat::from_i128(4);
        let c = a.add(&b);
        assert_eq!(format!("{}", c), "7");
    }

    #[test]
    fn bigrat_sub_basic() {
        let a = BigRat::from_i128_pair(3, 4);
        let b = BigRat::from_i128_pair(1, 4);
        let c = a.sub(&b);
        assert_eq!(format!("{}", c), "1/2");
    }

    #[test]
    fn bigrat_sub_to_zero() {
        let a = BigRat::from_i128_pair(3, 7);
        assert!(a.sub(&a).is_zero());
    }

    #[test]
    fn bigrat_mul_basic() {
        let a = BigRat::from_i128_pair(2, 3);
        let b = BigRat::from_i128_pair(3, 5);
        let c = a.mul(&b);
        assert_eq!(format!("{}", c), "2/5"); // (2*3)/(3*5) = 6/15 = 2/5
    }

    #[test]
    fn bigrat_mul_with_reduction() {
        let a = BigRat::from_i128_pair(7, 12);
        let b = BigRat::from_i128_pair(4, 21);
        let c = a.mul(&b);
        assert_eq!(format!("{}", c), "1/9"); // (7*4)/(12*21) = 28/252 = 1/9
    }

    #[test]
    fn bigrat_mul_zero() {
        let a = BigRat::from_i128_pair(3, 7);
        assert!(a.mul(&BigRat::zero()).is_zero());
    }

    #[test]
    fn bigrat_div_basic() {
        let a = BigRat::from_i128_pair(2, 3);
        let b = BigRat::from_i128_pair(4, 5);
        let c = a.div(&b);
        assert_eq!(format!("{}", c), "5/6"); // (2/3) / (4/5) = (2*5)/(3*4) = 10/12 = 5/6
    }

    #[test]
    fn bigrat_recip() {
        let a = BigRat::from_i128_pair(3, 7);
        let b = a.recip();
        assert_eq!(format!("{}", b), "7/3");
    }

    #[test]
    fn bigrat_recip_negative() {
        let a = BigRat::from_i128_pair(-3, 7);
        let b = a.recip();
        assert_eq!(format!("{}", b), "-7/3");
    }

    #[test]
    #[should_panic(expected = "reciprocal of zero")]
    fn bigrat_recip_zero() {
        let _ = BigRat::zero().recip();
    }

    // ─── Comparison ───

    #[test]
    fn bigrat_ord() {
        let a = BigRat::from_i128_pair(1, 3);
        let b = BigRat::from_i128_pair(1, 2);
        assert!(a < b);
    }

    #[test]
    fn bigrat_ord_negative() {
        let a = BigRat::from_i128_pair(-1, 2);
        let b = BigRat::from_i128_pair(1, 2);
        assert!(a < b);
    }

    #[test]
    fn bigrat_eq() {
        let a = BigRat::from_i128_pair(2, 4);
        let b = BigRat::from_i128_pair(1, 2);
        assert_eq!(a, b);
    }

    // ─── Conversion to Rat ───

    #[test]
    fn bigrat_to_rat_fits() {
        let a = BigRat::from_i128_pair(3, 7);
        let r = a.to_rat();
        assert!(r.is_some());
        let r = r.unwrap();
        assert_eq!(r.num(), 3);
        assert_eq!(r.den(), 7);
    }

    #[test]
    fn bigrat_to_rat_negative() {
        let a = BigRat::from_i128_pair(-5, 3);
        let r = a.to_rat().unwrap();
        assert_eq!(r.num(), -5);
        assert_eq!(r.den(), 3);
    }

    #[test]
    fn bigrat_to_rat_doesnt_fit() {
        // Construct a BigRat with numerator larger than i128::MAX
        let big_num = BigInt::from_i128(i128::MAX).add(&BigInt::one());
        let r = BigRat::new(big_num, BigInt::one());
        assert!(r.to_rat().is_none());
    }

    #[test]
    fn bigrat_from_rat_roundtrip() {
        let r = Rat::new(355, 113);
        let b = BigRat::from_rat(r);
        let r2 = b.to_rat().unwrap();
        assert_eq!(r, r2);
    }

    // ─── Overflow behavior ───

    #[test]
    fn bigrat_large_arithmetic() {
        // Compute with values that would overflow i128 Rat
        let a = BigRat::from_i128_pair(i128::MAX, 1);
        let b = BigRat::from_i128_pair(i128::MAX, 1);
        let c = a.add(&b);
        assert!(c.is_positive());
        // This won't fit in Rat (i128)
        assert!(c.to_rat().is_none());
    }

    #[test]
    fn bigrat_mul_large_then_demote() {
        // (i128::MAX / 4) * 2 should fit back in i128
        let quarter_max = i128::MAX / 4;
        let a = BigRat::from_i128_pair(quarter_max, 1);
        let b = BigRat::from_i128_pair(2, 1);
        let c = a.mul(&b);
        let r = c.to_rat();
        assert!(r.is_some());
        assert_eq!(r.unwrap().num(), quarter_max * 2);
    }

    // ─── Stress tests ───

    #[test]
    fn bigrat_repeated_add() {
        // 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + ...
        let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47];
        let mut sum = BigRat::zero();
        for &p in &primes {
            sum = sum.add(&BigRat::from_i128_pair(1, p));
        }
        // Verify denominator divides product of all primes
        assert!(!sum.is_zero());
        assert!(sum.is_positive());
    }

    #[test]
    fn bigrat_mul_inverse_roundtrip() {
        let a = BigRat::from_i128_pair(355, 113);
        let b = a.mul(&a.recip());
        assert_eq!(b, BigRat::one());
    }

    #[test]
    fn bigrat_continued_fraction_stress() {
        // Build the continued fraction convergent for π: 3 + 1/(7 + 1/(15 + 1/(1 + ...)))
        // Convergents: 3, 22/7, 333/106, 355/113, ...
        let terms: &[i128] = &[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1];
        let mut result = BigRat::from_i128(0);
        for &t in terms.iter().rev() {
            let term = BigRat::from_i128(t);
            if result.is_zero() {
                result = term;
            } else {
                result = term.add(&result.recip());
            }
        }
        // Should be very close to 355/113 extended
        assert!(result.is_positive());
    }
}