clt_database/skiplist/
comparator.rs

1//! Traits for key comparison in maps.
2
3use core::cmp::Ordering;
4
5use super::equivalent::{Comparable, Equivalent};
6
7/// Key equality trait.
8///
9/// This trait allows for very flexible comparison of objects. You may
10/// borrow/dereference `L` and `R` using `Borrow` or another trait. The trait
11/// takes a `self` parameter, which you can use to change how the operands are
12/// compared. For example, you can toggle string case-sensitivity on and off at
13/// runtime, or you can use `Box<dyn Equivalator<L, R>>` to allow the user of
14/// your code to supply a custom comparison function.
15///
16/// Implementations of `Equivalator` don't affect the inherent `Eq` or `Hash`
17/// implementations for a type. Currently there is no companion trait that
18/// allows for custom hashing the way `Equivalator` allows for custom
19/// comparison.
20///
21/// See also `Comparator`.
22///
23/// ## Example
24/// ```
25/// use turso_core::skiplist::comparator::Equivalator;
26///
27/// struct MyEquivalator {
28///     case_sensitive: bool,
29/// }
30///
31/// impl Equivalator<[u8], [u8]> for MyEquivalator {
32///     fn equivalent(&self, lhs: &[u8], rhs: &[u8]) -> bool {
33///         if self.case_sensitive {
34///             lhs == rhs
35///         } else {
36///             // Case-insensitive ASCII comparison on raw bytes
37///             if lhs.len() != rhs.len() { return false; }
38///             for (&c1, &c2) in lhs.iter().zip(rhs.iter()) {
39///                 let c1 = if c1 >= 0x61 && c1 <= 0x7a { c1 - 32 } else { c1 };
40///                 let c2 = if c2 >= 0x61 && c2 <= 0x7a { c2 - 32 } else { c2 };
41///                 if c1 != c2 { return false; }
42///             }
43///             true
44///         }
45///     }
46/// }
47/// ```
48pub trait Equivalator<L: ?Sized, R: ?Sized = L> {
49    /// Compare `lhs` to `rhs` for equality.
50    fn equivalent(&self, lhs: &L, rhs: &R) -> bool;
51}
52
53/// Key ordering trait.
54///
55/// This trait allows for very flexible comparison of objects. You may
56/// borrow/dereference `L` and `R` using `Borrow` or another trait. The trait
57/// takes a `self` parameter, which you can use to change how the operands are
58/// compared. For example, you can toggle string case-sensitivity on and off,
59/// or you can use `Box<dyn Comparator<L, R>>` to allow the user of your code
60/// to supply a custom comparison function.
61///
62/// The `Comparator` and `Equivalator` implementations for a comparator must
63/// agree on which inputs are equal.
64///
65/// See also `Equivalator`.
66pub trait Comparator<L: ?Sized, R: ?Sized = L>: Equivalator<L, R> {
67    /// Compare `lhs` to `rhs` and return their ordering.
68    fn compare(&self, lhs: &L, rhs: &R) -> Ordering;
69}
70
71/// This comparator uses the `Equivalent` and `Comparable` traits to perform
72/// comparisons, which themselves fall back on the standard library `Borrow`
73/// and `Ord` traits. When used in a map, this results in the same behavior as
74/// the standard `BTreeMap` interface.
75#[derive(Clone, Copy, Debug, Default)]
76pub struct BasicComparator;
77
78impl<K: ?Sized, Q: ?Sized> Equivalator<K, Q> for BasicComparator
79where
80    K: Equivalent<Q>,
81{
82    #[inline]
83    fn equivalent(&self, lhs: &K, rhs: &Q) -> bool {
84        <K as Equivalent<Q>>::equivalent(lhs, rhs)
85    }
86}
87
88impl<K: ?Sized, Q: ?Sized> Comparator<K, Q> for BasicComparator
89where
90    K: Comparable<Q>,
91{
92    #[inline]
93    fn compare(&self, lhs: &K, rhs: &Q) -> Ordering {
94        <K as Comparable<Q>>::compare(lhs, rhs)
95    }
96}
clt_database/skiplist/comparator.rs

clt_database/skiplist/
comparator.rs
