malachite_nz/integer_polynomial/comparison/
shortlex_cmp.rs

1// Copyright © 2026 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::integer_polynomial::{ShortlexIntegerPolynomial, ShortlexIntegerPolynomialRef};
10use core::cmp::Ordering;
11
12impl Ord for ShortlexIntegerPolynomialRef<'_> {
13    /// Compares two [`ShortlexIntegerPolynomialRef`]s.
14    ///
15    /// The order is shortlex: the polynomials are compared first by degree, and then, in case of a
16    /// tie, by their coefficients from highest to lowest. The zero polynomial, having no degree at
17    /// all, comes first. This is a total order, and its equality agrees with
18    /// [`IntegerPolynomial`](crate::integer_polynomial::IntegerPolynomial) equality. It is the
19    /// order FLINT uses for polynomials, the one `fmpq_poly_cmp` implements.
20    ///
21    /// Where the degrees differ this parts company with
22    /// [`IntegerPolynomial`](crate::integer_polynomial::IntegerPolynomial)'s own [`Ord`], which
23    /// compares polynomials by how they behave for large arguments and so lets a negative leading
24    /// coefficient send a high-degree polynomial to the bottom. Here degree decides outright, so
25    /// $-x^3 > x^2$ where the asymptotic order has $-x^3 < x^2$.
26    ///
27    /// # Worst-case complexity
28    /// $T(n) = O(n)$
29    ///
30    /// $M(n) = O(1)$
31    ///
32    /// where $T$ is time, $M$ is additional memory, and $n$ is the smaller of the two polynomials'
33    /// total number of bits, summed over their coefficients. Polynomials of different degrees are
34    /// compared in constant time.
35    ///
36    /// # Examples
37    /// ```
38    /// use core::str::FromStr;
39    /// use malachite_nz::integer_polynomial::{IntegerPolynomial, ShortlexIntegerPolynomialRef};
40    ///
41    /// let zero = IntegerPolynomial::from_str("0").unwrap();
42    /// let x_squared = IntegerPolynomial::from_str("x^2").unwrap();
43    /// let negative_x_cubed = IntegerPolynomial::from_str("-x^3").unwrap();
44    ///
45    /// // The zero polynomial comes first.
46    /// assert!(ShortlexIntegerPolynomialRef(&zero) < ShortlexIntegerPolynomialRef(&x_squared));
47    /// // Degree decides, whatever the sign of the leading coefficient.
48    /// assert!(
49    ///     ShortlexIntegerPolynomialRef(&x_squared)
50    ///         < ShortlexIntegerPolynomialRef(&negative_x_cubed)
51    /// );
52    /// ```
53    #[inline]
54    fn cmp(&self, other: &Self) -> Ordering {
55        // The coefficients are held with no trailing zero, so the length is the degree plus one,
56        // and 0 for the zero polynomial; comparing lengths is comparing degrees. Once the lengths
57        // agree the iterators have the same length, so comparing them from the leading coefficient
58        // down is the comparison at the highest coefficient where the two differ.
59        self.0
60            .coefficients
61            .len()
62            .cmp(&other.0.coefficients.len())
63            .then_with(|| {
64                self.0
65                    .coefficients
66                    .iter()
67                    .rev()
68                    .cmp(other.0.coefficients.iter().rev())
69            })
70    }
71}
72
73impl PartialOrd for ShortlexIntegerPolynomialRef<'_> {
74    /// Compares two [`ShortlexIntegerPolynomialRef`]s.
75    ///
76    /// See the documentation for the [`Ord`] implementation.
77    #[inline]
78    fn partial_cmp(&self, other: &ShortlexIntegerPolynomialRef) -> Option<Ordering> {
79        Some(self.cmp(other))
80    }
81}
82
83impl Ord for ShortlexIntegerPolynomial {
84    /// Compares two [`ShortlexIntegerPolynomial`]s.
85    ///
86    /// The order is shortlex: the polynomials are compared first by degree, and then, in case of a
87    /// tie, by their coefficients from highest to lowest. See the [`Ord`] implementation for
88    /// [`ShortlexIntegerPolynomialRef`] for details.
89    ///
90    /// # Worst-case complexity
91    /// $T(n) = O(n)$
92    ///
93    /// $M(n) = O(1)$
94    ///
95    /// where $T$ is time, $M$ is additional memory, and $n$ is the smaller of the two polynomials'
96    /// total number of bits, summed over their coefficients. Polynomials of different degrees are
97    /// compared in constant time.
98    ///
99    /// # Examples
100    /// ```
101    /// use core::str::FromStr;
102    /// use malachite_nz::integer_polynomial::{IntegerPolynomial, ShortlexIntegerPolynomial};
103    ///
104    /// let x_squared = IntegerPolynomial::from_str("x^2").unwrap();
105    /// let negative_x_cubed = IntegerPolynomial::from_str("-x^3").unwrap();
106    ///
107    /// // Degree decides, whatever the sign of the leading coefficient.
108    /// assert!(ShortlexIntegerPolynomial(x_squared) < ShortlexIntegerPolynomial(negative_x_cubed));
109    /// ```
110    #[inline]
111    fn cmp(&self, other: &Self) -> Ordering {
112        self.as_ref().cmp(&other.as_ref())
113    }
114}
115
116impl PartialOrd for ShortlexIntegerPolynomial {
117    /// Compares two [`ShortlexIntegerPolynomial`]s.
118    ///
119    /// See the documentation for the [`Ord`] implementation.
120    #[inline]
121    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
122        Some(self.cmp(other))
123    }
124}
malachite_nz/integer_polynomial/comparison/shortlex_cmp.rs

malachite_nz/integer_polynomial/comparison/
shortlex_cmp.rs
