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

malachite_base/unsigned_vector/comparison/
shortlex_cmp.rs
