seekable_iterator/
comparator.rs

1use core::cmp::Ordering;
2
3#[cfg(feature = "clone-behavior")]
4use clone_behavior::{IndependentClone, MirroredClone, NearInstant, NonRecursive};
5#[cfg(feature = "generic-container")]
6use generic_container::{FragileContainer, GenericContainer};
7
8
9/// Interface for comparing keys (or entries) of a sorted collection.
10///
11/// The comparison function should provide a total order, just as [`Ord`] would.
12///
13/// Note that none of the axioms that define a total order require that two elements which compare
14/// as equal are "*truly*" equal in some more fundamental sense; that is, keys which are distinct
15/// (perhaps according to an [`Eq`] implementation) may compare as equal in the provided total
16/// order and corresponding equivalence relation.
17///
18/// Unsafe code is *not* allowed to rely on the correctness of implementations; that is, an
19/// incorrect `Comparator` implementation may cause severe logic errors, but must not cause
20/// memory unsafety.
21pub trait Comparator<Key: ?Sized> {
22    /// Compare two keys (or entries) in a sorted collection.
23    ///
24    /// This method is analogous to [`Ord::cmp`], and should provide a total order.
25    ///
26    /// Note that none of the axioms that define a total order require that two elements which
27    /// compare as equal are "*truly*" equal in some more fundamental sense; that is, keys which
28    /// are distinct (perhaps according to an [`Eq`] implementation) may compare as equal in
29    /// the provided total order and corresponding equivalence relation.
30    ///
31    /// Unsafe code is *not* allowed to rely on the correctness of implementations; that is, an
32    /// incorrect implementation may cause severe logic errors, but must not cause
33    /// memory unsafety.
34    #[must_use]
35    fn cmp(&self, lhs: &Key, rhs: &Key) -> Ordering;
36}
37
38#[cfg(feature = "generic-container")]
39impl<Key: ?Sized, C: FragileContainer<dyn Comparator<Key>>> Comparator<Key> for C {
40    #[inline]
41    fn cmp(&self, lhs: &Key, rhs: &Key) -> Ordering {
42        // I'm slightly paranoid about the type coercion coercing to the wrong thing,
43        // but doing this line-by-line is probably unnecessary.
44        let inner = self.get_ref();
45        let inner: &dyn Comparator<Key> = &*inner;
46        inner.cmp(lhs, rhs)
47    }
48}
49
50#[cfg(feature = "generic-container")]
51impl<T, C, Key> Comparator<Key> for GenericContainer<T, C>
52where
53    T: ?Sized + Comparator<Key>,
54    C: ?Sized + FragileContainer<T>,
55{
56    #[inline]
57    fn cmp(&self, lhs: &Key, rhs: &Key) -> Ordering {
58        let inner = self.container.get_ref();
59        let inner: &T = &inner;
60        inner.cmp(lhs, rhs)
61    }
62}
63
64/// A [`Comparator`] which uses keys' [`Ord`] implementations.
65#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
66pub struct DefaultComparator;
67
68impl<Key: ?Sized + Ord> Comparator<Key> for DefaultComparator {
69    /// Equivalent to `Ord::cmp(lhs, rhs)`.
70    #[inline]
71    fn cmp(&self, lhs: &Key, rhs: &Key) -> Ordering {
72        Ord::cmp(lhs, rhs)
73    }
74}
75
76#[cfg(feature = "clone-behavior")]
77impl NonRecursive for DefaultComparator {}
78
79#[cfg(feature = "clone-behavior")]
80impl IndependentClone<NearInstant> for DefaultComparator {
81    #[inline]
82    fn independent_clone(&self) -> Self {
83        Self
84    }
85}
86
87#[cfg(feature = "clone-behavior")]
88impl MirroredClone<NearInstant> for DefaultComparator {
89    #[inline]
90    fn mirrored_clone(&self) -> Self {
91        Self
92    }
93}
seekable_iterator/comparator.rs

seekable_iterator/
comparator.rs
