qfall-math 0.1.1

// Copyright © 2023 Sven Moog, Niklas Siemer, Marcel Luca Schmidt
//
// This file is part of qFALL-math.
//
// qFALL-math is free software: you can redistribute it and/or modify it under
// the terms of the Mozilla Public License Version 2.0 as published by the
// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.

//! Implementations to compare [`Q`] with other values.
//! This uses the traits from [`std::cmp`].

use super::Q;
use crate::{
    integer::Z,
    integer_mod_q::Modulus,
    macros::for_others::{implement_for_others, implement_trait_reverse},
};
use flint_sys::{
    fmpq::{fmpq_cmp, fmpq_equal},
    fmpz::{fmpz, fmpz_equal},
};
use std::cmp::Ordering;

impl PartialEq for Q {
    /// Checks if two rationals are equal. Used by the `==` and `!=` operators.
    ///
    /// Parameters:
    /// - `other`: the other value that is used to compare the elements
    ///
    /// Returns `true` if the elements are equal, otherwise `false`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::rational::Q;
    /// use std::str::FromStr;
    /// let a: Q = Q::from((42, 24));
    /// let b: Q = Q::from((24, 42));
    ///
    /// // These are all equivalent and return false.
    /// let compared: bool = (a == b);
    /// # assert!(!compared);
    /// let compared: bool = (&a == &b);
    /// # assert!(!compared);
    /// let compared: bool = (a.eq(&b));
    /// # assert!(!compared);
    /// let compared: bool = (Q::eq(&a, &b));
    /// # assert!(!compared);
    /// ```
    fn eq(&self, other: &Self) -> bool {
        unsafe { 1 == fmpq_equal(&self.value, &other.value) }
    }
}

// With the [`Eq`] trait, `a == a` is always true.
// This is not guaranteed by the [`PartialEq`] trait.
// We do not allow division by zero, therefore, this is the case.
impl Eq for Q {}

impl PartialEq<Z> for Q {
    /// Checks if an integer and a rational are equal. Used by the `==` and `!=` operators.
    /// [`PartialEq`] is also implemented for [`Z`] using [`Q`].
    ///
    /// Parameters:
    /// - `other`: the other value that is used to compare the elements
    ///
    /// Returns `true` if the elements are equal, otherwise `false`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer::Z;
    /// use qfall_math::rational::Q;
    /// let a: Q = Q::from(42);
    /// let b: Z = Z::from(42);
    ///
    /// // These are all equivalent and return true.
    /// let compared: bool = (a == b);
    /// # assert!(compared);
    /// let compared: bool = (b == a);
    /// # assert!(compared);
    /// let compared: bool = (&a == &b);
    /// # assert!(compared);
    /// let compared: bool = (&b == &a);
    /// # assert!(compared);
    /// let compared: bool = (a.eq(&b));
    /// # assert!(compared);
    /// let compared: bool = (b.eq(&a));
    /// # assert!(compared);
    /// let compared: bool = (Q::eq(&a, &b));
    /// # assert!(compared);
    /// let compared: bool = (Z::eq(&b, &a));
    /// # assert!(compared);
    /// ```
    fn eq(&self, other: &Z) -> bool {
        unsafe {
            (1 == fmpz_equal(&self.value.den, &fmpz(1)))
                && (1 == fmpz_equal(&self.value.num, &other.value))
        }
    }
}

implement_trait_reverse!(PartialEq, eq, Z, Q, bool);

impl PartialEq<Modulus> for Q {
    /// Checks if an integer and a rational are equal. Used by the `==` and `!=` operators.
    /// [`PartialEq`] is also implemented for [`Modulus`] using [`Q`].
    ///
    /// Parameters:
    /// - `other`: the other value that is used to compare the elements
    ///
    /// Returns `true` if the elements are equal, otherwise `false`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::Modulus;
    /// use qfall_math::rational::Q;
    /// let a: Q = Q::from(42);
    /// let b: Modulus = Modulus::from(42);
    ///
    /// // These are all equivalent and return true.
    /// let compared: bool = (a == b);
    /// # assert!(compared);
    /// let compared: bool = (b == a);
    /// # assert!(compared);
    /// let compared: bool = (&a == &b);
    /// # assert!(compared);
    /// let compared: bool = (&b == &a);
    /// # assert!(compared);
    /// let compared: bool = (a.eq(&b));
    /// # assert!(compared);
    /// let compared: bool = (b.eq(&a));
    /// # assert!(compared);
    /// let compared: bool = (Q::eq(&a, &b));
    /// # assert!(compared);
    /// let compared: bool = (Modulus::eq(&b, &a));
    /// # assert!(compared);
    /// ```
    fn eq(&self, other: &Modulus) -> bool {
        unsafe {
            (1 == fmpz_equal(&self.value.den, &fmpz(1)))
                && (1 == fmpz_equal(&self.value.num, &other.modulus.n[0]))
        }
    }
}

implement_trait_reverse!(PartialEq, eq, Modulus, Q, bool);

implement_for_others!(Z, Q, PartialEq for fmpz i8 i16 i32 i64 u8 u16 u32 u64);

impl PartialOrd for Q {
    /// Compares two [`Q`] values. Used by the `<`, `<=`, `>`, and `>=` operators.
    ///
    /// Parameters:
    /// - `other`: the other value that is used to compare the elements
    ///
    /// Returns the [`Ordering`] of the elements.
    ///
    /// # Examples
    /// ```
    /// # use qfall_math::error::MathError;
    /// use qfall_math::rational::Q;
    ///
    /// let a: Q = Q::from((1, 10));
    /// let b: Q = Q::from((2, 10));
    ///
    /// assert!(a < b);
    /// assert!(a <= b);
    /// assert!(b > a);
    /// assert!(b >= a);
    ///
    /// assert!(&a < &b);
    /// # Ok::<(), MathError>(())
    /// ```
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Q {
    //! Enables the usage of `max`, `min`, and `clamp`.
    //!
    //! # Examples
    //! ```
    //! use qfall_math::rational::Q;
    //! use std::cmp::{max, min};
    //!
    //! let a: Q = Q::from(10);
    //! let b: Q = Q::from(42);
    //!
    //! assert_eq!(b, max(a.clone(), b.clone()));
    //! assert_eq!(a, min(a.clone(), b.clone()));
    //! assert_eq!(a, Q::ZERO.clamp(a.clone(), b.clone()));
    //! ```

    /// Compares two [`Q`] values. Used by the `<`, `<=`, `>`, and `>=` operators.
    ///
    /// Parameters:
    /// - `other`: the other value that is used to compare the elements
    ///
    /// Returns the [`Ordering`] of the elements.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::rational::Q;
    ///
    /// let a: Q = Q::from(10);
    /// let b: Q = Q::from(42);
    ///
    /// assert!(a < b);
    /// assert!(a <= b);
    /// assert!(b > a);
    /// assert!(b >= a);
    /// ```
    fn cmp(&self, other: &Self) -> Ordering {
        unsafe { fmpq_cmp(&self.value, &other.value).cmp(&0) }
    }
}

implement_for_others!(Q, Q, PartialOrd for Modulus Z fmpz i8 i16 i32 i64 u8 u16 u32 u64);

/// Test that the [`PartialEq`] trait is correctly implemented.
#[cfg(test)]
mod test_partial_eq_q {
    /// Test case structure:
    /// 1. Different ways to use equal and not equal.
    /// 2. Test different combinations of equal and not equal with different
    ///    parameter length combinations.
    ///    Not equal test are inverted equal tests.
    use super::Q;
    use std::str::FromStr;

    // Ensure that the function can be called between owned and borrowed values
    #[test]
    #[allow(clippy::op_ref)]
    fn availability() {
        let q = Q::ONE;

        assert!(q == q);
        assert!(&q == &q);
    }

    /// Demonstrate the different ways to use equal.
    /// We assume that they behave the same in the other tests.
    #[test]
    #[allow(clippy::op_ref)]
    fn equal_call_methods() {
        let one_1 = Q::ONE;
        let one_2 = Q::ONE;

        assert!(one_1 == one_2);
        assert!(&one_1 == &one_2);
        assert!(one_1.eq(&one_2));
        assert!(Q::eq(&one_1, &one_2));
        assert_eq!(one_1, one_2);
    }

    /// Demonstrate the different ways to use not equal.
    /// We assume that they behave the same in the other tests.
    #[test]
    #[allow(clippy::op_ref)]
    fn not_equal_call_methods() {
        let one = Q::ONE;
        let two = Q::from(2);

        assert!(one != two);
        assert!(&one != &two);
        assert!(one.ne(&two));
        assert!(Q::ne(&one, &two));
        assert_ne!(one, two);
    }

    /// Test equal with small positive and negative numbers.
    #[test]
    fn equal_small() {
        let small_1 = Q::from(10);
        let small_2 = Q::from(10);

        assert!(small_1 == small_2);
        assert!(small_2 == small_1);
        assert!(small_1 == small_1);
    }

    /// Test not equal with small positive and negative numbers.
    #[test]
    fn not_equal_small() {
        let small_1 = Q::from(10);
        let negative = Q::MINUS_ONE;

        assert!(small_1 != negative);
        assert!(negative != small_1);
    }

    /// Test equal with a large [`Q`]
    /// (uses FLINT's pointer representation)
    #[test]
    fn equal_large() {
        let max_1 = Q::from_str(&"1".repeat(65)).unwrap();
        let max_2 = Q::from_str(&"1".repeat(65)).unwrap();
        let large_negative_str = format!("-{:1<65}", "1");
        let min = Q::from_str(&large_negative_str).unwrap();

        assert!(max_1 == max_2);
        assert!(max_2 == max_1);
        assert!(max_1 == max_1);
        assert!(min == min);
    }

    /// Test not equal with a large [`Q`]
    /// (uses FLINT's pointer representation)
    #[test]
    fn not_equal_large() {
        let max_1 = Q::from_str(&"1".repeat(65)).unwrap();
        let large_negative_str = format!("-{:1<65}", "1");
        let min = Q::from_str(&large_negative_str).unwrap();

        assert!(max_1 != min);
        assert!(min != max_1);
    }

    /// Test not equal with a large [`Q`] (uses FLINT's pointer representation)
    /// and small [`Q`] (no pointer representation).
    #[test]
    fn not_equal_large_small() {
        let max = Q::from_str(&"1".repeat(65)).unwrap();
        let small_positive = Q::ONE;
        let small_negative = Q::MINUS_ONE;
        let large_negative_str = format!("-{:1<65}", "1");
        let min = Q::from_str(&large_negative_str).unwrap();

        assert!(max != small_negative);
        assert!(small_negative != max);
        assert!(max != small_positive);
        assert!(small_positive != max);

        assert!(min != small_negative);
        assert!(small_negative != min);
        assert!(min != small_positive);
        assert!(small_positive != min);
    }

    /// Test equal with small [`Q`] that have a large denominator
    /// (uses FLINT's pointer representation)
    #[test]
    fn equal_large_denominator() {
        let large_denominator_str = format!("1/{:1<200}", "1");
        let large_denominator_less_str = format!("1/{:1<201}", "1");

        let small_1 = Q::from_str(&large_denominator_str).unwrap();
        let small_2 = Q::from_str(&large_denominator_str).unwrap();
        let less = Q::from_str(&large_denominator_less_str).unwrap();

        assert!(small_1 == small_2);
        assert!(small_2 == small_1);
        assert!(small_1 == small_1);

        assert!(less == less);
    }

    /// Test equal for [`Q`] with large numerator and denominator
    /// (uses FLINT's pointer representation)
    #[test]
    fn equal_large_numerator_denominator() {
        // The greatest common divisor of numerator and denominator is 1
        // => also large after canonicalization
        let large_denominator_str = format!("{:5<200}/{:4<200}", "1", "1");
        let large_denominator_less_str = format!("{:5<201}/{:4<201}", "1", "1");

        let small_1 = Q::from_str(&large_denominator_str).unwrap();
        let small_2 = Q::from_str(&large_denominator_str).unwrap();
        let less = Q::from_str(&large_denominator_less_str).unwrap();

        assert!(small_1 == small_2);
        assert!(small_2 == small_1);
        assert!(small_1 == small_1);

        assert!(less == less);
    }

    /// Ensure that two elements are equal
    #[test]
    fn equal_rational() {
        let a = Q::from((1, 2));
        let b = Q::from((2, 4));

        assert_eq!(a, b);
    }

    /// assert not equal when denominator is different
    #[test]
    fn not_equal_different_denominator() {
        let a = Q::from((1, 2));
        let b = Q::from((1, 4));

        assert_ne!(a, b);
    }

    /// assert equal for `0` when denominator is different
    #[test]
    fn zero_equal_different_denominator() {
        let a = Q::from((0, 2));
        let b = Q::from((0, 4));

        assert_eq!(a, b);
    }
}

/// Test that the [`PartialEq`] trait is correctly implemented.
#[cfg(test)]
mod test_partial_eq_q_other {
    use super::Q;
    use crate::{integer::Z, integer_mod_q::Modulus};

    // Ensure that the function can be called with several types
    #[test]
    #[allow(clippy::op_ref)]
    fn availability() {
        let q = Q::from((2, 1));
        let z = Z::from(2);
        let modulus = Modulus::from(2);

        assert!(q == z);
        assert!(q == modulus);
        assert!(q == z.value);
        assert!(q == 2i8);
        assert!(q == 2u8);
        assert!(q == 2i16);
        assert!(q == 2u16);
        assert!(q == 2i32);
        assert!(q == 2u32);
        assert!(q == 2i64);
        assert!(q == 2u64);

        assert!(z == q);
        assert!(modulus == q);
        assert!(z.value == q);
        assert!(2i8 == q);
        assert!(2u8 == q);
        assert!(2i16 == q);
        assert!(2u16 == q);
        assert!(2i32 == q);
        assert!(2u32 == q);
        assert!(2i64 == q);
        assert!(2u64 == q);

        assert!(&q == &z);
        assert!(&z == &q);
        assert!(&q == &modulus);
        assert!(&modulus == &q);
        assert!(&q == &2i8);
        assert!(&2i8 == &q);
    }

    // Ensure that large values are compared correctly
    #[test]
    fn equal_large() {
        let q = Q::from((u64::MAX, 1));
        let z = Z::from(u64::MAX);
        let modulus1 = Modulus::from(u64::MAX);
        let modulus2 = Modulus::from(u64::MAX - 1);

        assert!(q == z);
        assert!(q == modulus1);
        assert!(q != z + 1);
        assert!(q != modulus2);
    }
}

/// Test the [`PartialOrd`] trait implementation for [`Q`]
#[cfg(test)]
#[allow(clippy::neg_cmp_op_on_partial_ord)]
mod test_partial_ord {
    use super::Q;

    /// Different ways to compare [`Q`] elements with each other
    #[test]
    fn call_methods() {
        let one = Q::ONE;
        let zero = Q::ZERO;

        assert!(one >= zero);
        assert!(one > zero);
    }

    /// Test less (<) comparison between small positive and negative [`Q`]
    /// (FLINT is not using pointers)
    #[test]
    fn less_small() {
        let one_1 = Q::ONE;
        let small_negative = Q::MINUS_ONE;
        let one_half = Q::from((1, 2));

        assert!(small_negative < one_1);

        assert!(one_half < one_1);
        assert!(small_negative < one_half);
    }

    /// Test less (<) comparison between large [`Q`] (FLINT uses pointers)
    /// and small [`Q`] (not using pointers).
    #[test]
    fn less_large_small() {
        let large = Q::from((u64::MAX, 2));
        let small_positive = Q::ONE;
        let small_negative = Q::from((i64::MIN + 1, i64::MAX));
        let large_negative = Q::from(i64::MIN);

        // Comparisons with max
        assert!(small_positive < large);
        assert!(small_negative < large);

        // Comparisons with max_negative
        assert!(large_negative < small_positive);
        assert!(large_negative < small_negative);
    }

    /// Test less (<) comparison between large positive and negative [`Q`]
    /// (FLINT uses pointers)
    #[test]
    fn less_large() {
        let max_1 = Q::from(u64::MAX);
        let max_negative = Q::from(i64::MIN);

        assert!(max_negative < max_1);
    }

    /// Test less or equal (<=) comparison between small positive and negative [`Q`]
    /// (FLINT is not using pointers)
    #[test]
    fn less_equal_small() {
        let small_positive_1 = Q::ONE;
        let small_positive_2 = Q::ONE;
        let small_negative = Q::MINUS_ONE;

        assert!(small_positive_1 <= small_positive_2);
        assert!(small_positive_2 <= small_positive_1);
        assert!(small_positive_1 <= small_positive_1);

        assert!(small_negative <= small_positive_1);
        assert!(small_negative <= small_negative);
    }

    /// Test less or equal (<=) comparison between large [`Q`] (FLINT uses pointers)
    /// and small [`Q`] (not using pointers).
    #[test]
    fn less_equal_large_small() {
        let max = Q::from(u64::MAX);
        let small_positive = Q::ONE;
        let small_negative = Q::MINUS_ONE;
        let max_negative = Q::from(i64::MIN);

        // Comparisons with max
        assert!(small_positive <= max);
        assert!(small_negative <= max);

        // Comparisons with max_negative
        assert!(max_negative <= small_positive);
        assert!(max_negative <= small_negative);
    }

    /// Test less or equal (<=) comparison between large positive and negative [`Q`]
    /// (FLINT uses pointers)
    #[test]
    fn less_equal_large() {
        let max_1 = Q::from(u64::MAX);
        let max_2 = Q::from(u64::MAX);
        let max_negative = Q::from(i64::MIN);

        assert!(max_1 <= max_2);
        assert!(max_2 <= max_1);
        assert!(max_1 <= max_1);

        assert!(max_negative <= max_1);
        assert!(max_negative <= max_negative);
    }

    /// Test greater (>) comparison between small positive and negative [`Q`]
    /// (FLINT is not using pointers)
    #[test]
    fn greater_small() {
        let small_positive_1 = Q::ONE;
        let small_negative = Q::MINUS_ONE;

        assert!(small_positive_1 > small_negative);
    }

    /// Test greater (>) comparison between large [`Q`] (FLINT uses pointers)
    /// and small [`Q`] (not using pointers).
    #[test]
    fn greater_large_small() {
        let max = Q::from(u64::MAX);
        let small_positive = Q::ONE;
        let small_negative = Q::MINUS_ONE;
        let max_negative = Q::from(i64::MIN);

        // Comparisons with max
        assert!(max > small_positive);
        assert!(max > small_negative);

        // Comparisons with max_negative
        assert!(small_positive > max_negative);
        assert!(small_negative > max_negative);
    }

    /// Test greater (>) comparison between large positive and negative [`Q`]
    /// (FLINT uses pointers)
    #[test]
    fn greater_large() {
        let max_1 = Q::from(u64::MAX);
        let max_negative = Q::from(i64::MIN);

        assert!(max_1 > max_negative);
    }

    /// Test greater or equal (>=) comparison between small positive and negative [`Q`]
    /// (FLINT is not using pointers)
    #[test]
    fn greater_equal_small() {
        let small_positive_1 = Q::ONE;
        let small_positive_2 = Q::ONE;
        let small_negative = Q::MINUS_ONE;

        assert!(small_positive_1 >= small_positive_2);
        assert!(small_positive_2 >= small_positive_1);
        assert!(small_positive_1 >= small_positive_1);

        assert!(small_positive_1 >= small_negative);
        assert!(small_negative >= small_negative);
    }

    /// Test greater or equal (>=) comparison between large [`Q`] (FLINT uses pointers)
    /// and small [`Q`] (not using pointers).
    #[test]
    fn greater_equal_large_small() {
        let max = Q::from(u64::MAX);
        let small_positive = Q::ONE;
        let small_negative = Q::MINUS_ONE;
        let max_negative = Q::from(i64::MIN);

        // Comparisons with max
        assert!(max >= small_positive);
        assert!(max >= small_negative);

        // Comparisons with max_negative
        assert!(small_positive >= max_negative);
        assert!(small_negative >= max_negative);
    }

    /// Test greater or equal (>=) comparison between large positive and negative [`Q`]
    /// (FLINT uses pointers)
    #[test]
    fn greater_equal_large() {
        let max_1 = Q::from(u64::MAX);
        let max_2 = Q::from(u64::MAX);
        let max_negative = Q::from(i64::MIN);

        assert!(max_1 >= max_2);
        assert!(max_2 >= max_1);
        assert!(max_1 >= max_1);

        assert!(max_1 >= max_negative);
        assert!(max_negative >= max_negative);
    }

    /// Compare a number close to `0` with `0`
    #[test]
    fn close_to_zero() {
        let small = Q::from((1, u64::MAX));
        let zero = Q::ZERO;

        assert!(small > zero);
        assert!(small >= zero);
    }
}

/// Test that the [`PartialOrd`] trait is correctly implemented.
#[cfg(test)]
mod test_partial_ord_q_other {
    use super::Q;
    use crate::{integer::Z, integer_mod_q::Modulus};

    /// Ensure that the function can be called with several types
    #[test]
    #[allow(clippy::op_ref)]
    fn availability() {
        let q = Q::from((2, 1));
        let z = Z::from(2);
        let modulus = Modulus::from(2);

        assert!(q <= z);
        assert!(q <= modulus);
        assert!(q <= z.value);
        assert!(q <= 2i8);
        assert!(q <= 2u8);
        assert!(q <= 2i16);
        assert!(q <= 2u16);
        assert!(q <= 2i32);
        assert!(q <= 2u32);
        assert!(q <= 2i64);
        assert!(q <= 2u64);

        assert!(z >= q);
        assert!(modulus >= q);
        assert!(z.value >= q);
        assert!(2i8 >= q);
        assert!(2u8 >= q);
        assert!(2i16 >= q);
        assert!(2u16 >= q);
        assert!(2i32 >= q);
        assert!(2u32 >= q);
        assert!(2i64 >= q);
        assert!(2u64 >= q);

        assert!(&q <= &z);
        assert!(&z >= &q);
        assert!(&q <= &modulus);
        assert!(&modulus >= &q);
        assert!(&q <= &2i8);
        assert!(&2i8 >= &q);
    }
}

#[cfg(test)]
mod test_ord {
    use super::Q;
    use std::cmp::{max, min};

    // `cmp` is extensively tested in module `test_partial_eq`, hence omitted here

    /// Check whether default implementations `max`, `min`, `clamp`
    /// work properly for small numbers
    #[test]
    fn default_implementations_small() {
        let a: Q = Q::from((10, 3));
        let b: Q = Q::from((42, 4));

        assert_eq!(b, max(a.clone(), b.clone()));
        assert_eq!(a, min(a.clone(), b.clone()));

        assert_eq!(a, Q::ZERO.clamp(a.clone(), b.clone()));
        assert_eq!(a, a.clone().clamp(Q::ZERO, b.clone()));
        assert_eq!(a, b.clamp(Q::ZERO, a.clone()));
    }

    /// Check whether default implementations `max`, `min`, `clamp`
    /// work properly for large numbers
    #[test]
    fn default_implementations_large() {
        let a: Q = Q::from(i64::MAX);
        let b: Q = Q::from(u64::MAX);

        assert_eq!(b, max(a.clone(), b.clone()));
        assert_eq!(a, min(a.clone(), b.clone()));

        assert_eq!(a, Q::ZERO.clamp(a.clone(), b.clone()));
        assert_eq!(a, a.clone().clamp(Q::ZERO, b.clone()));
        assert_eq!(a, b.clamp(Q::ZERO, a.clone()));
    }
}