seekable_iterator/
comparator.rs

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

seekable_iterator/
comparator.rs
