malachite_q/comparison/
partial_cmp_abs_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::comparison::traits::PartialOrdAbs;
14use malachite_base::num::conversion::traits::ExactFrom;
15use malachite_base::num::logic::traits::SignificantBits;
16use malachite_nz::natural::Natural;
17
18#[allow(clippy::unnecessary_wraps)]
19fn partial_cmp_abs_unsigned<T: Copy + One + Ord + Sign + SignificantBits>(
20    x: &Rational,
21    other: &T,
22) -> Option<Ordering>
23where
24    Natural: From<T> + PartialOrd<T>,
25{
26    // First check if either value is zero
27    let self_sign = x.numerator_ref().sign();
28    let other_sign = other.sign();
29    let sign_cmp = self_sign.cmp(&other_sign);
30    if sign_cmp != Equal || self_sign == Equal {
31        return Some(sign_cmp);
32    }
33    // Then check if one is < 1 and the other is > 1
34    let self_cmp_one = x.numerator.cmp(&x.denominator);
35    let other_cmp_one = other.cmp(&T::ONE);
36    let one_cmp = self_cmp_one.cmp(&other_cmp_one);
37    if one_cmp != Equal {
38        return Some(one_cmp);
39    }
40    // Then compare numerators and denominators
41    let n_cmp = x.numerator.partial_cmp(other).unwrap();
42    let d_cmp = x.denominator.cmp(&Natural::ONE);
43    if n_cmp == Equal && d_cmp == Equal {
44        return Some(Equal);
45    }
46    let nd_cmp = n_cmp.cmp(&d_cmp);
47    if nd_cmp != Equal {
48        return Some(nd_cmp);
49    }
50    // Then compare floor ∘ log_2 ∘ abs
51    let log_cmp = x
52        .floor_log_base_2_abs()
53        .cmp(&i64::exact_from(other.significant_bits() - 1));
54    if log_cmp != Equal {
55        return Some(log_cmp);
56    }
57    // Finally, cross-multiply.
58    Some(x.numerator.cmp(&(&x.denominator * Natural::from(*other))))
59}
60
61macro_rules! impl_unsigned {
62    ($t: ident) => {
63        impl PartialOrdAbs<$t> for Rational {
64            /// Compares the absolute values of a [`Rational`] and an unsigned primitive integer.
65            ///
66            /// # Worst-case complexity
67            /// $T(n) = O(n \log n \log\log n)$
68            ///
69            /// $M(n) = O(n \log n)$
70            ///
71            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
72            ///
73            /// # Examples
74            /// See [here](super::partial_cmp_abs_primitive_int#partial_cmp_abs).
75            #[inline]
76            fn partial_cmp_abs(&self, other: &$t) -> Option<Ordering> {
77                partial_cmp_abs_unsigned(self, other)
78            }
79        }
80
81        impl PartialOrdAbs<Rational> for $t {
82            /// Compares the absolute values of an unsigned primitive integer and a [`Rational`].
83            ///
84            /// # Worst-case complexity
85            /// $T(n) = O(n \log n \log\log n)$
86            ///
87            /// $M(n) = O(n \log n)$
88            ///
89            /// where $T$ is time, $M$ is additional memory, and $n$ is `other.significant_bits()`.
90            ///
91            /// See [here](super::partial_cmp_abs_primitive_int#partial_cmp_abs).
92            #[inline]
93            fn partial_cmp_abs(&self, other: &Rational) -> Option<Ordering> {
94                other.partial_cmp_abs(self).map(Ordering::reverse)
95            }
96        }
97    };
98}
99apply_to_unsigneds!(impl_unsigned);
100
101#[allow(clippy::unnecessary_wraps)]
102fn partial_cmp_abs_signed<
103    U: Copy + One + Ord + Sign + 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 if either value is zero
113    let self_sign = x.numerator_ref().sign();
114    let other_abs = other.unsigned_abs();
115    let other_sign = other_abs.sign();
116    let sign_cmp = self_sign.cmp(&other_sign);
117    if sign_cmp != Equal || self_sign == Equal {
118        return Some(sign_cmp);
119    }
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(one_cmp);
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(nd_cmp);
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(log_cmp);
143    }
144    // Finally, cross-multiply.
145    Some(
146        x.numerator
147            .cmp(&(&x.denominator * Natural::from(other_abs))),
148    )
149}
150
151macro_rules! impl_signed {
152    ($t: ident) => {
153        impl PartialOrdAbs<$t> for Rational {
154            /// Compares the absolute values of a [`Rational`] and 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_abs_primitive_int#partial_cmp_abs).
165            #[inline]
166            fn partial_cmp_abs(&self, other: &$t) -> Option<Ordering> {
167                partial_cmp_abs_signed(self, other)
168            }
169        }
170
171        impl PartialOrdAbs<Rational> for $t {
172            /// Compares the absolute values of a signed primitive integer and 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 `other.significant_bits()`.
180            ///
181            /// See [here](super::partial_cmp_abs_primitive_int#partial_cmp_abs).
182            #[inline]
183            fn partial_cmp_abs(&self, other: &Rational) -> Option<Ordering> {
184                other.partial_cmp_abs(self).map(Ordering::reverse)
185            }
186        }
187    };
188}
189apply_to_signeds!(impl_signed);
malachite_q/comparison/partial_cmp_abs_primitive_int.rs

malachite_q/comparison/
partial_cmp_abs_primitive_int.rs
