malachite_q/comparison/
partial_cmp_primitive_int.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, UnsignedAbs};
12use malachite_base::num::basic::traits::One;
13use malachite_base::num::conversion::traits::ExactFrom;
14use malachite_base::num::logic::traits::SignificantBits;
15use malachite_nz::natural::Natural;
16
17#[allow(clippy::unnecessary_wraps)]
18fn partial_cmp_unsigned<T: Copy + One + Ord + Sign + SignificantBits>(
19    x: &Rational,
20    other: &T,
21) -> Option<Ordering>
22where
23    Natural: From<T> + PartialOrd<T>,
24{
25    // First check signs
26    let self_sign = x.sign();
27    let other_sign = other.sign();
28    let sign_cmp = self_sign.cmp(&other_sign);
29    if sign_cmp != Equal || self_sign == Equal {
30        return Some(sign_cmp);
31    }
32    // Then check if one is < 1 and the other is > 1
33    let self_cmp_one = x.numerator.cmp(&x.denominator);
34    let other_cmp_one = other.cmp(&T::ONE);
35    let one_cmp = self_cmp_one.cmp(&other_cmp_one);
36    if one_cmp != Equal {
37        return Some(one_cmp);
38    }
39    // Then compare numerators and denominators
40    let n_cmp = x.numerator.partial_cmp(other).unwrap();
41    let d_cmp = x.denominator.cmp(&Natural::ONE);
42    if n_cmp == Equal && d_cmp == Equal {
43        return Some(Equal);
44    }
45    let nd_cmp = n_cmp.cmp(&d_cmp);
46    if nd_cmp != Equal {
47        return Some(nd_cmp);
48    }
49    // Then compare floor ∘ log_2 ∘ abs
50    let log_cmp = x
51        .floor_log_base_2_abs()
52        .cmp(&i64::exact_from(other.significant_bits() - 1));
53    if log_cmp != Equal {
54        return Some(if x.sign { log_cmp } else { log_cmp.reverse() });
55    }
56    // Finally, cross-multiply.
57    Some(x.numerator.cmp(&(&x.denominator * Natural::from(*other))))
58}
59
60macro_rules! impl_unsigned {
61    ($t: ident) => {
62        impl PartialOrd<$t> for Rational {
63            /// Compares a [`Rational`] to an unsigned primitive integer.
64            ///
65            /// # Worst-case complexity
66            /// $T(n) = O(n \log n \log\log n)$
67            ///
68            /// $M(n) = O(n \log n)$
69            ///
70            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
71            ///
72            /// # Examples
73            /// See [here](super::partial_cmp_primitive_int#partial_cmp).
74            #[inline]
75            fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
76                partial_cmp_unsigned(self, other)
77            }
78        }
79
80        impl PartialOrd<Rational> for $t {
81            /// Compares an unsigned primitive integer to a [`Rational`].
82            ///
83            /// # Worst-case complexity
84            /// $T(n) = O(n \log n \log\log n)$
85            ///
86            /// $M(n) = O(n \log n)$
87            ///
88            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
89            ///
90            /// # Examples
91            /// See [here](super::partial_cmp_primitive_int#partial_cmp).
92            #[inline]
93            fn partial_cmp(&self, other: &Rational) -> Option<Ordering> {
94                other.partial_cmp(self).map(Ordering::reverse)
95            }
96        }
97    };
98}
99apply_to_unsigneds!(impl_unsigned);
100
101#[allow(clippy::unnecessary_wraps)]
102fn partial_cmp_signed<
103    U: Copy + One + Ord + SignificantBits,
104    S: Copy + Sign + SignificantBits + UnsignedAbs<Output = U>,
105>(
106    x: &Rational,
107    other: &S,
108) -> Option<Ordering>
109where
110    Natural: From<U> + PartialOrd<U>,
111{
112    // First check signs
113    let self_sign = x.sign();
114    let other_sign = other.sign();
115    let sign_cmp = self_sign.cmp(&other_sign);
116    if sign_cmp != Equal || self_sign == Equal {
117        return Some(sign_cmp);
118    }
119    let other_abs = other.unsigned_abs();
120    // Then check if one is < 1 and the other is > 1
121    let self_cmp_one = x.numerator.cmp(&x.denominator);
122    let other_cmp_one = other_abs.cmp(&U::ONE);
123    let one_cmp = self_cmp_one.cmp(&other_cmp_one);
124    if one_cmp != Equal {
125        return Some(if x.sign { one_cmp } else { one_cmp.reverse() });
126    }
127    // Then compare numerators and denominators
128    let n_cmp = x.numerator.partial_cmp(&other_abs).unwrap();
129    let d_cmp = x.denominator.cmp(&Natural::ONE);
130    if n_cmp == Equal && d_cmp == Equal {
131        return Some(Equal);
132    }
133    let nd_cmp = n_cmp.cmp(&d_cmp);
134    if nd_cmp != Equal {
135        return Some(if x.sign { nd_cmp } else { nd_cmp.reverse() });
136    }
137    // Then compare floor ∘ log_2 ∘ abs
138    let log_cmp = x
139        .floor_log_base_2_abs()
140        .cmp(&i64::exact_from(other.significant_bits() - 1));
141    if log_cmp != Equal {
142        return Some(if x.sign { log_cmp } else { log_cmp.reverse() });
143    }
144    // Finally, cross-multiply.
145    let prod_cmp = x
146        .numerator
147        .cmp(&(&x.denominator * Natural::from(other_abs)));
148    Some(if x.sign { prod_cmp } else { prod_cmp.reverse() })
149}
150
151macro_rules! impl_signed {
152    ($t: ident) => {
153        impl PartialOrd<$t> for Rational {
154            /// Compares a [`Rational`] to a signed primitive integer.
155            ///
156            /// # Worst-case complexity
157            /// $T(n) = O(n \log n \log\log n)$
158            ///
159            /// $M(n) = O(n \log n)$
160            ///
161            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
162            ///
163            /// # Examples
164            /// See [here](super::partial_cmp_primitive_int#partial_cmp).
165            #[inline]
166            fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
167                partial_cmp_signed(self, other)
168            }
169        }
170
171        impl PartialOrd<Rational> for $t {
172            /// Compares a signed primitive integer to a [`Rational`].
173            ///
174            /// # Worst-case complexity
175            /// $T(n) = O(n \log n \log\log n)$
176            ///
177            /// $M(n) = O(n \log n)$
178            ///
179            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
180            ///
181            /// # Examples
182            /// See [here](super::partial_cmp_primitive_int#partial_cmp).
183            #[inline]
184            fn partial_cmp(&self, other: &Rational) -> Option<Ordering> {
185                other.partial_cmp(self).map(Ordering::reverse)
186            }
187        }
188    };
189}
190apply_to_signeds!(impl_signed);
malachite_q/comparison/partial_cmp_primitive_int.rs

malachite_q/comparison/
partial_cmp_primitive_int.rs
