malachite_q/comparison/
partial_cmp_abs_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::comparison::traits::PartialOrdAbs;
14use malachite_base::num::conversion::traits::ExactFrom;
15use malachite_base::num::logic::traits::SignificantBits;
16use malachite_nz::integer::Integer;
17use malachite_nz::natural::Natural;
18
19impl PartialOrdAbs<Integer> for Rational {
20    /// Compares the absolute values of a [`Rational`] and an [`Integer`].
21    ///
22    /// # Worst-case complexity
23    /// $T(n) = O(n \log n \log\log n)$
24    ///
25    /// $M(n) = O(n \log n)$
26    ///
27    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
28    /// other.significant_bits())`.
29    ///
30    /// # Examples
31    /// ```
32    /// use malachite_base::num::comparison::traits::PartialOrdAbs;
33    /// use malachite_nz::integer::Integer;
34    /// use malachite_q::Rational;
35    /// use std::cmp::Ordering::*;
36    ///
37    /// assert_eq!(
38    ///     Rational::from_signeds(22, 7).partial_cmp_abs(&Integer::from(3)),
39    ///     Some(Greater)
40    /// );
41    /// assert_eq!(
42    ///     Rational::from_signeds(-22, 7).partial_cmp_abs(&Integer::from(-3)),
43    ///     Some(Greater)
44    /// );
45    /// ```
46    fn partial_cmp_abs(&self, other: &Integer) -> Option<Ordering> {
47        // First check whether either value is zero
48        let self_sign = self.numerator_ref().sign();
49        let other_sign = other.unsigned_abs_ref().sign();
50        let sign_cmp = self_sign.cmp(&other_sign);
51        if sign_cmp != Equal || self_sign == Equal {
52            return Some(sign_cmp);
53        }
54        // Then check if one is < 1 and the other is > 1
55        let self_cmp_one = self.numerator.cmp(&self.denominator);
56        let other_cmp_one = other.unsigned_abs_ref().cmp(&Natural::ONE);
57        let one_cmp = self_cmp_one.cmp(&other_cmp_one);
58        if one_cmp != Equal {
59            return Some(one_cmp);
60        }
61        // Then compare numerators and denominators
62        let n_cmp = self.numerator.cmp(other.unsigned_abs_ref());
63        let d_cmp = self.denominator.cmp(&Natural::ONE);
64        if n_cmp == Equal && d_cmp == Equal {
65            return Some(Equal);
66        }
67        let nd_cmp = n_cmp.cmp(&d_cmp);
68        if nd_cmp != Equal {
69            return Some(nd_cmp);
70        }
71        // Then compare floor ∘ log_2 ∘ abs
72        let log_cmp = self
73            .floor_log_base_2_abs()
74            .cmp(&i64::exact_from(other.significant_bits() - 1));
75        if log_cmp != Equal {
76            return Some(log_cmp);
77        }
78        // Finally, cross-multiply.
79        Some(
80            self.numerator
81                .cmp(&(&self.denominator * other.unsigned_abs_ref())),
82        )
83    }
84}
85
86impl PartialOrdAbs<Rational> for Integer {
87    /// Compares the absolute values of an [`Integer`] and a [`Rational`].
88    ///
89    /// # Worst-case complexity
90    /// $T(n) = O(n \log n \log\log n)$
91    ///
92    /// $M(n) = O(n \log n)$
93    ///
94    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
95    /// other.significant_bits())`.
96    ///
97    /// # Examples
98    /// ```
99    /// use malachite_base::num::comparison::traits::PartialOrdAbs;
100    /// use malachite_nz::integer::Integer;
101    /// use malachite_q::Rational;
102    /// use std::cmp::Ordering::*;
103    ///
104    /// assert_eq!(
105    ///     Integer::from(3).partial_cmp_abs(&Rational::from_signeds(22, 7)),
106    ///     Some(Less)
107    /// );
108    /// assert_eq!(
109    ///     Integer::from(-3).partial_cmp_abs(&Rational::from_signeds(-22, 7)),
110    ///     Some(Less)
111    /// );
112    /// ```
113    #[inline]
114    fn partial_cmp_abs(&self, other: &Rational) -> Option<Ordering> {
115        other.partial_cmp_abs(self).map(Ordering::reverse)
116    }
117}
malachite_q/comparison/partial_cmp_abs_integer.rs

malachite_q/comparison/
partial_cmp_abs_integer.rs
