malachite_q/comparison/
partial_cmp_integer.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::Rational;
10use core::cmp::Ordering::{self, *};
11use malachite_base::num::arithmetic::traits::Sign;
12use malachite_base::num::basic::traits::One;
13use malachite_base::num::conversion::traits::ExactFrom;
14use malachite_base::num::logic::traits::SignificantBits;
15use malachite_nz::integer::Integer;
16use malachite_nz::natural::Natural;
17
18impl PartialOrd<Integer> for Rational {
19    /// Compares a [`Rational`] to an [`Integer`].
20    ///
21    /// # Worst-case complexity
22    /// $T(n) = O(n \log n \log\log n)$
23    ///
24    /// $M(n) = O(n \log n)$
25    ///
26    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
27    /// other.significant_bits())`.
28    ///
29    /// # Examples
30    /// ```
31    /// use malachite_nz::integer::Integer;
32    /// use malachite_q::Rational;
33    ///
34    /// assert!(Rational::from_signeds(22, 7) > Integer::from(3));
35    /// assert!(Rational::from_signeds(22, 7) < Integer::from(4));
36    /// assert!(Rational::from_signeds(-22, 7) < Integer::from(-3));
37    /// assert!(Rational::from_signeds(-22, 7) > Integer::from(-4));
38    /// ```
39    fn partial_cmp(&self, other: &Integer) -> Option<Ordering> {
40        // First check signs
41        let self_sign = self.sign();
42        let other_sign = other.sign();
43        let sign_cmp = self_sign.cmp(&other_sign);
44        if sign_cmp != Equal || self_sign == Equal {
45            return Some(sign_cmp);
46        }
47        // Then check if one is < 1 and the other is > 1
48        let self_cmp_one = self.numerator.cmp(&self.denominator);
49        let other_cmp_one = other.unsigned_abs_ref().cmp(&Natural::ONE);
50        let one_cmp = self_cmp_one.cmp(&other_cmp_one);
51        if one_cmp != Equal {
52            return Some(if self.sign {
53                one_cmp
54            } else {
55                one_cmp.reverse()
56            });
57        }
58        // Then compare numerators and denominators
59        let n_cmp = self.numerator.cmp(other.unsigned_abs_ref());
60        let d_cmp = self.denominator.cmp(&Natural::ONE);
61        if n_cmp == Equal && d_cmp == Equal {
62            return Some(Equal);
63        }
64        let nd_cmp = n_cmp.cmp(&d_cmp);
65        if nd_cmp != Equal {
66            return Some(if self.sign { nd_cmp } else { nd_cmp.reverse() });
67        }
68        let log_cmp = self
69            .floor_log_base_2_abs()
70            .cmp(&i64::exact_from(other.significant_bits() - 1));
71        if log_cmp != Equal {
72            return Some(if self.sign {
73                log_cmp
74            } else {
75                log_cmp.reverse()
76            });
77        }
78        // Finally, cross-multiply.
79        let prod_cmp = self
80            .numerator
81            .cmp(&(&self.denominator * other.unsigned_abs_ref()));
82        Some(if self.sign {
83            prod_cmp
84        } else {
85            prod_cmp.reverse()
86        })
87    }
88}
89
90impl PartialOrd<Rational> for Integer {
91    /// Compares an [`Integer`] to a [`Rational`].
92    ///
93    /// # Worst-case complexity
94    /// $T(n) = O(n \log n \log\log n)$
95    ///
96    /// $M(n) = O(n \log n)$
97    ///
98    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
99    /// other.significant_bits())`.
100    ///
101    /// # Examples
102    /// ```
103    /// use malachite_nz::integer::Integer;
104    /// use malachite_q::Rational;
105    ///
106    /// assert!(Integer::from(3) < Rational::from_signeds(22, 7));
107    /// assert!(Integer::from(4) > Rational::from_signeds(22, 7));
108    /// assert!(Integer::from(-3) > Rational::from_signeds(-22, 7));
109    /// assert!(Integer::from(-4) < Rational::from_signeds(-22, 7));
110    /// ```
111    #[inline]
112    fn partial_cmp(&self, other: &Rational) -> Option<Ordering> {
113        other.partial_cmp(self).map(Ordering::reverse)
114    }
115}
malachite_q/comparison/partial_cmp_integer.rs

malachite_q/comparison/
partial_cmp_integer.rs
