vsrg 0.6.0

/// A fraction represented by integer numerator and denominator.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Fraction {
    numerator: i32,
    denominator: i32,
}

impl From<i32> for Fraction {
    fn from(value: i32) -> Self {
        Self {
            numerator: value,
            denominator: 1,
        }
    }
}

impl Fraction {
    /// Creates a normalized fraction.
    ///
    /// Returns [`None`] if `denominator` is zero, or if the normalized numerator or denominator
    /// cannot be represented as an [`i32`].
    pub fn new(numerator: i32, denominator: i32) -> Option<Self> {
        Self::normalize_i64(i64::from(numerator), i64::from(denominator))
    }

    /// Adds two fractions, returning [`None`] on overflow.
    pub fn checked_add(self, rhs: Self) -> Option<Self> {
        let left_denominator = i64::from(self.denominator);
        let right_denominator = i64::from(rhs.denominator);
        let gcd = gcd_i64(left_denominator, right_denominator);
        let left_scale = right_denominator / gcd;
        let right_scale = left_denominator / gcd;

        let numerator = i64::from(self.numerator)
            .checked_mul(left_scale)?
            .checked_add(i64::from(rhs.numerator).checked_mul(right_scale)?)?;
        let denominator = left_denominator.checked_mul(left_scale)?;

        Self::normalize_i64(numerator, denominator)
    }

    /// Subtracts from this fraction, returning [`None`] on overflow.
    pub fn checked_sub(self, rhs: Self) -> Option<Self> {
        let left_denominator = i64::from(self.denominator);
        let right_denominator = i64::from(rhs.denominator);
        let gcd = gcd_i64(left_denominator, right_denominator);
        let left_scale = right_denominator / gcd;
        let right_scale = left_denominator / gcd;

        let numerator = i64::from(self.numerator)
            .checked_mul(left_scale)?
            .checked_sub(i64::from(rhs.numerator).checked_mul(right_scale)?)?;
        let denominator = left_denominator.checked_mul(left_scale)?;

        Self::normalize_i64(numerator, denominator)
    }

    /// Multiplies two fractions, returning [`None`] on overflow.
    pub fn checked_mul(self, rhs: Self) -> Option<Self> {
        let left_cross_gcd = gcd_i64(i64::from(self.numerator).abs(), i64::from(rhs.denominator));
        let right_cross_gcd = gcd_i64(i64::from(rhs.numerator).abs(), i64::from(self.denominator));

        let left_numerator = i64::from(self.numerator) / left_cross_gcd;
        let right_denominator = i64::from(rhs.denominator) / left_cross_gcd;
        let right_numerator = i64::from(rhs.numerator) / right_cross_gcd;
        let left_denominator = i64::from(self.denominator) / right_cross_gcd;

        let numerator = left_numerator.checked_mul(right_numerator)?;
        let denominator = left_denominator.checked_mul(right_denominator)?;

        Self::normalize_i64(numerator, denominator)
    }

    /// Divides two fractions, returning [`None`] on overflow or divide by 0.
    pub fn checked_div(self, rhs: Self) -> Option<Self> {
        self.checked_mul(rhs.checked_recip()?)
    }

    /// Returns the reciprocal of this fraction, or [`None`] if this fraction is zero.
    pub fn checked_recip(self) -> Option<Self> {
        Self::normalize_i64(i64::from(self.denominator), i64::from(self.numerator))
    }

    /// Returns the reciprocal of this fraction.
    ///
    /// # Panics
    ///
    /// Panics if this fraction is zero.
    pub fn recip(self) -> Self {
        self.checked_recip()
            .expect("attempt to take the reciprocal of zero")
    }

    fn normalize_i64(mut numerator: i64, mut denominator: i64) -> Option<Self> {
        if denominator == 0 {
            return None;
        }

        if denominator < 0 {
            numerator = numerator.checked_neg()?;
            denominator = denominator.checked_neg()?;
        }

        let gcd = gcd_i64(numerator.abs(), denominator);
        numerator /= gcd;
        denominator /= gcd;

        Some(Self {
            numerator: i32::try_from(numerator).ok()?,
            denominator: i32::try_from(denominator).ok()?,
        })
    }

    pub(crate) fn partial_cmp_f64(self, value: f64) -> Option<std::cmp::Ordering> {
        let approximate = f64::from(self).partial_cmp(&value)?;
        if approximate != std::cmp::Ordering::Equal {
            return Some(approximate);
        }

        let numerator = i64::from(self.numerator);
        if value == 0.0 {
            return Some(numerator.cmp(&0));
        }

        let value_is_negative = value.is_sign_negative();
        if (numerator < 0) != value_is_negative {
            return Some(if numerator < 0 {
                std::cmp::Ordering::Less
            } else {
                std::cmp::Ordering::Greater
            });
        }

        let bits = value.to_bits();
        let exponent_bits = ((bits >> 52) & 0x7ff) as i32;
        let significand = bits & ((1_u64 << 52) - 1);
        let (significand, exponent) = if exponent_bits == 0 {
            (significand, -1074)
        } else {
            (significand | (1_u64 << 52), exponent_bits - 1023 - 52)
        };

        // A fraction in this type's range cannot round to a float with a nonnegative
        // significand exponent, so this branch is only a defensive fallback.
        if exponent >= 0 {
            return Some(approximate);
        }

        let shift = u32::try_from(-exponent).ok()?;
        let left = u128::from(numerator.unsigned_abs()).checked_shl(shift)?;
        let denominator = u128::try_from(self.denominator).ok()?;
        let right = denominator.checked_mul(u128::from(significand))?;
        let ordering = left.cmp(&right);
        Some(if numerator < 0 {
            ordering.reverse()
        } else {
            ordering
        })
    }

    pub fn to_f64(&self) -> f64 {
        self.numerator as f64 / self.denominator as f64
    }
}

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

impl Ord for Fraction {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let left = i64::from(self.numerator) * i64::from(other.denominator);
        let right = i64::from(other.numerator) * i64::from(self.denominator);
        left.cmp(&right)
    }
}

impl From<Fraction> for f32 {
    fn from(value: Fraction) -> Self {
        value.numerator as Self / value.denominator as Self
    }
}

impl From<Fraction> for f64 {
    fn from(value: Fraction) -> Self {
        value.numerator as Self / value.denominator as Self
    }
}

impl std::ops::Add for Fraction {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        self.checked_add(rhs).expect("attempt to add with overflow")
    }
}

impl std::ops::AddAssign for Fraction {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl std::ops::Sub for Fraction {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        self.checked_sub(rhs)
            .expect("attempt to subtract with overflow")
    }
}

impl std::ops::SubAssign for Fraction {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl std::ops::Mul for Fraction {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        self.checked_mul(rhs)
            .expect("attempt to multiply with overflow")
    }
}

impl std::ops::MulAssign for Fraction {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl std::ops::Div for Fraction {
    type Output = Self;

    fn div(self, rhs: Self) -> Self::Output {
        self.checked_div(rhs)
            .expect("attempt to divide by zero fraction or with overflow")
    }
}

impl std::ops::Neg for Fraction {
    type Output = Self;

    fn neg(self) -> Self::Output {
        Self {
            numerator: -self.numerator,
            denominator: self.denominator,
        }
    }
}

impl std::fmt::Display for Fraction {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}/{}", self.numerator, self.denominator)
    }
}

fn gcd_i64(mut a: i64, mut b: i64) -> i64 {
    while b != 0 {
        let remainder = a % b;
        a = b;
        b = remainder;
    }

    a.max(1)
}

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

    #[test]
    fn new_rejects_zero_denominator() {
        assert_eq!(Fraction::new(1, 0), None);
        assert_eq!(Fraction::new(0, 0), None);
    }

    #[test]
    fn new_normalizes_fraction() {
        assert_eq!(Fraction::new(2, 4).unwrap(), Fraction::new(1, 2).unwrap());
        assert_eq!(Fraction::new(1, -2).unwrap(), Fraction::new(-1, 2).unwrap());
        assert_eq!(Fraction::new(-2, -4).unwrap(), Fraction::new(1, 2).unwrap());
    }

    #[test]
    fn new_rejects_normalized_values_outside_i32() {
        assert_eq!(Fraction::new(i32::MIN, -1), None);
    }

    #[test]
    fn converts_to_float() {
        let fraction = Fraction::new(1, 4).unwrap();

        assert_eq!(f32::from(fraction), 0.25);
        assert_eq!(f64::from(fraction), 0.25);
    }

    #[test]
    fn checked_recip_returns_none_for_zero() {
        assert_eq!(Fraction::new(0, 4).unwrap().checked_recip(), None);
    }

    #[test]
    fn recip_inverts_fraction() {
        assert_eq!(
            Fraction::new(2, 3).unwrap().recip(),
            Fraction::new(3, 2).unwrap()
        );
    }

    #[test]
    #[should_panic(expected = "attempt to take the reciprocal of zero")]
    fn recip_panics_for_zero() {
        let _ = Fraction::new(0, 4).unwrap().recip();
    }

    #[test]
    fn checked_add_adds_fractions() {
        assert_eq!(
            Fraction::new(1, 2)
                .unwrap()
                .checked_add(Fraction::new(1, 3).unwrap()),
            Fraction::new(5, 6)
        );
    }

    #[test]
    fn add_adds_fractions() {
        assert_eq!(
            Fraction::new(1, 2).unwrap() + Fraction::new(1, 3).unwrap(),
            Fraction::new(5, 6).unwrap()
        );
    }

    #[test]
    fn add_assign_adds_fractions() {
        let mut fraction = Fraction::new(1, 2).unwrap();
        fraction += Fraction::new(1, 3).unwrap();

        assert_eq!(fraction, Fraction::new(5, 6).unwrap());
    }

    #[test]
    fn checked_sub_subtracts_fractions() {
        assert_eq!(
            Fraction::new(1, 2)
                .unwrap()
                .checked_sub(Fraction::new(1, 3).unwrap()),
            Fraction::new(1, 6)
        );
    }

    #[test]
    fn sub_subtracts_fractions() {
        assert_eq!(
            Fraction::new(1, 2).unwrap() - Fraction::new(1, 3).unwrap(),
            Fraction::new(1, 6).unwrap()
        );
    }

    #[test]
    fn sub_assign_subtracts_fractions() {
        let mut fraction = Fraction::new(1, 2).unwrap();
        fraction -= Fraction::new(1, 3).unwrap();

        assert_eq!(fraction, Fraction::new(1, 6).unwrap());
    }

    #[test]
    fn checked_mul_multiplies_fractions() {
        assert_eq!(
            Fraction::new(2, 3)
                .unwrap()
                .checked_mul(Fraction::new(3, 4).unwrap()),
            Fraction::new(1, 2)
        );
    }

    #[test]
    fn mul_multiplies_fractions() {
        assert_eq!(
            Fraction::new(2, 3).unwrap() * Fraction::new(3, 4).unwrap(),
            Fraction::new(1, 2).unwrap()
        );
    }

    #[test]
    fn mul_assign_multiplies_fractions() {
        let mut fraction = Fraction::new(2, 3).unwrap();
        fraction *= Fraction::new(3, 4).unwrap();

        assert_eq!(fraction, Fraction::new(1, 2).unwrap());
    }

    #[test]
    fn checked_div_returns_none_for_zero_divisor() {
        let lhs = Fraction::new(1, 2).unwrap();
        let rhs = Fraction::new(0, 3).unwrap();

        assert_eq!(lhs.checked_div(rhs), None);
    }

    #[test]
    fn checked_div_divides_fraction() {
        assert_eq!(
            Fraction::new(1, 2)
                .unwrap()
                .checked_div(Fraction::new(3, 4).unwrap()),
            Fraction::new(2, 3)
        );
    }

    #[test]
    fn div_divides_fraction() {
        let lhs = Fraction::new(1, 2).unwrap();
        let rhs = Fraction::new(3, 4).unwrap();

        assert_eq!(lhs / rhs, Fraction::new(2, 3).unwrap());
    }

    #[test]
    #[should_panic(expected = "attempt to divide by zero fraction or with overflow")]
    fn div_panics_for_zero_divisor() {
        let lhs = Fraction::new(1, 2).unwrap();
        let rhs = Fraction::new(0, 3).unwrap();

        let _ = lhs / rhs;
    }

    #[test]
    fn checked_mul_cross_cancels_before_multiplying() {
        let lhs = Fraction::new(i32::MAX, i32::MAX - 1).unwrap();
        let rhs = Fraction::new(i32::MAX - 1, i32::MAX).unwrap();

        assert_eq!(lhs.checked_mul(rhs), Fraction::new(1, 1));
    }

    #[test]
    fn checked_add_uses_reduced_common_denominator() {
        let lhs = Fraction::new(1, i32::MAX).unwrap();
        let rhs = Fraction::new(1, i32::MAX).unwrap();

        assert_eq!(lhs.checked_add(rhs), Fraction::new(2, i32::MAX));
    }
}