malachite_nz/integer_vector/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_vector::{ShortlexIntegerVector, ShortlexIntegerVectorRef};
10use core::cmp::Ordering;
11
12impl Ord for ShortlexIntegerVectorRef<'_> {
13    /// Compares two [`ShortlexIntegerVectorRef`]s.
14    ///
15    /// The order is shortlex: the vectors are compared first by dimension, and then, in case of a
16    /// tie, lexicographically, by their elements from first to last. The 0-dimensional vector comes
17    /// first. This is a total order, and its equality agrees with
18    /// [`IntegerVector`](crate::integer_vector::IntegerVector) equality.
19    ///
20    /// Where the dimensions differ this parts company with the lexicographic order of [`Vec`]s:
21    /// here dimension decides outright, so $(5) < (0, 0)$, where lexicographic order has $(5) > (0,
22    /// 0)$.
23    ///
24    /// # Worst-case complexity
25    /// $T(n) = O(n)$
26    ///
27    /// $M(n) = O(1)$
28    ///
29    /// where $T$ is time, $M$ is additional memory, and $n$ is the smaller of the two vectors'
30    /// total number of bits, summed over their elements. Vectors of different dimensions are
31    /// compared in constant time.
32    ///
33    /// # Examples
34    /// ```
35    /// use core::str::FromStr;
36    /// use malachite_nz::integer_vector::{IntegerVector, ShortlexIntegerVectorRef};
37    ///
38    /// let empty = IntegerVector::from_str("()").unwrap();
39    /// let five = IntegerVector::from_str("(5)").unwrap();
40    /// let zero_zero = IntegerVector::from_str("(0, 0)").unwrap();
41    /// let zero_one = IntegerVector::from_str("(0, 1)").unwrap();
42    ///
43    /// // The 0-dimensional vector comes first.
44    /// assert!(ShortlexIntegerVectorRef(&empty) < ShortlexIntegerVectorRef(&five));
45    /// // Dimension decides, whatever the elements.
46    /// assert!(ShortlexIntegerVectorRef(&five) < ShortlexIntegerVectorRef(&zero_zero));
47    /// // At equal dimensions, the first differing element decides.
48    /// assert!(ShortlexIntegerVectorRef(&zero_zero) < ShortlexIntegerVectorRef(&zero_one));
49    /// ```
50    #[inline]
51    fn cmp(&self, other: &Self) -> Ordering {
52        // Once the lengths agree, comparing the `Vec`s is the comparison at the first element where
53        // the two differ.
54        self.0
55            .elements
56            .len()
57            .cmp(&other.0.elements.len())
58            .then_with(|| self.0.elements.cmp(&other.0.elements))
59    }
60}
61
62impl PartialOrd for ShortlexIntegerVectorRef<'_> {
63    /// Compares two [`ShortlexIntegerVectorRef`]s.
64    ///
65    /// See the documentation for the [`Ord`] implementation.
66    #[inline]
67    fn partial_cmp(&self, other: &ShortlexIntegerVectorRef) -> Option<Ordering> {
68        Some(self.cmp(other))
69    }
70}
71
72impl Ord for ShortlexIntegerVector {
73    /// Compares two [`ShortlexIntegerVector`]s.
74    ///
75    /// The order is shortlex: the vectors are compared first by dimension, and then, in case of a
76    /// tie, lexicographically. See the [`Ord`] implementation for [`ShortlexIntegerVectorRef`] for
77    /// details.
78    ///
79    /// # Worst-case complexity
80    /// $T(n) = O(n)$
81    ///
82    /// $M(n) = O(1)$
83    ///
84    /// where $T$ is time, $M$ is additional memory, and $n$ is the smaller of the two vectors'
85    /// total number of bits, summed over their elements. Vectors of different dimensions are
86    /// compared in constant time.
87    ///
88    /// # Examples
89    /// ```
90    /// use core::str::FromStr;
91    /// use malachite_nz::integer_vector::{IntegerVector, ShortlexIntegerVector};
92    /// use std::collections::BTreeSet;
93    ///
94    /// let five = IntegerVector::from_str("(5)").unwrap();
95    /// let zero_zero = IntegerVector::from_str("(0, 0)").unwrap();
96    ///
97    /// // Dimension decides, whatever the elements.
98    /// assert!(ShortlexIntegerVector(five.clone()) < ShortlexIntegerVector(zero_zero.clone()));
99    ///
100    /// // The wrapper makes vectors usable in ordered collections.
101    /// let set: BTreeSet<_> = [zero_zero, five]
102    ///     .into_iter()
103    ///     .map(ShortlexIntegerVector)
104    ///     .collect();
105    /// assert_eq!(
106    ///     set.iter().map(|v| v.to_string()).collect::<Vec<_>>(),
107    ///     ["(5)", "(0, 0)"]
108    /// );
109    /// ```
110    #[inline]
111    fn cmp(&self, other: &Self) -> Ordering {
112        self.as_ref().cmp(&other.as_ref())
113    }
114}
115
116impl PartialOrd for ShortlexIntegerVector {
117    /// Compares two [`ShortlexIntegerVector`]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_vector/comparison/shortlex_cmp.rs

malachite_nz/integer_vector/comparison/
shortlex_cmp.rs
