1 //! [`Equivalent`] and [`Comparable`] are traits for key comparison in maps. 2 //! 3 //! These may be used in the implementation of maps where the lookup type `Q` 4 //! may be different than the stored key type `K`. 5 //! 6 //! * `Q: Equivalent<K>` checks for equality, similar to the `HashMap<K, V>` 7 //! constraint `K: Borrow<Q>, Q: Eq`. 8 //! * `Q: Comparable<K>` checks the ordering, similar to the `BTreeMap<K, V>` 9 //! constraint `K: Borrow<Q>, Q: Ord`. 10 //! 11 //! These traits are not used by the maps in the standard library, but they may 12 //! add more flexibility in third-party map implementations, especially in 13 //! situations where a strict `K: Borrow<Q>` relationship is not available. 14 //! 15 //! # Examples 16 //! 17 //! ``` 18 //! use equivalent::*; 19 //! use std::cmp::Ordering; 20 //! 21 //! pub struct Pair<A, B>(pub A, pub B); 22 //! 23 //! impl<'a, A: ?Sized, B: ?Sized, C, D> Equivalent<(C, D)> for Pair<&'a A, &'a B> 24 //! where 25 //! A: Equivalent<C>, 26 //! B: Equivalent<D>, 27 //! { 28 //! fn equivalent(&self, key: &(C, D)) -> bool { 29 //! self.0.equivalent(&key.0) && self.1.equivalent(&key.1) 30 //! } 31 //! } 32 //! 33 //! impl<'a, A: ?Sized, B: ?Sized, C, D> Comparable<(C, D)> for Pair<&'a A, &'a B> 34 //! where 35 //! A: Comparable<C>, 36 //! B: Comparable<D>, 37 //! { 38 //! fn compare(&self, key: &(C, D)) -> Ordering { 39 //! match self.0.compare(&key.0) { 40 //! Ordering::Equal => self.1.compare(&key.1), 41 //! not_equal => not_equal, 42 //! } 43 //! } 44 //! } 45 //! 46 //! fn main() { 47 //! let key = (String::from("foo"), String::from("bar")); 48 //! let q1 = Pair("foo", "bar"); 49 //! let q2 = Pair("boo", "bar"); 50 //! let q3 = Pair("foo", "baz"); 51 //! 52 //! assert!(q1.equivalent(&key)); 53 //! assert!(!q2.equivalent(&key)); 54 //! assert!(!q3.equivalent(&key)); 55 //! 56 //! assert_eq!(q1.compare(&key), Ordering::Equal); 57 //! assert_eq!(q2.compare(&key), Ordering::Less); 58 //! assert_eq!(q3.compare(&key), Ordering::Greater); 59 //! } 60 //! ``` 61 62 #![no_std] 63 64 use core::borrow::Borrow; 65 use core::cmp::Ordering; 66 67 /// Key equivalence trait. 68 /// 69 /// This trait allows hash table lookup to be customized. It has one blanket 70 /// implementation that uses the regular solution with `Borrow` and `Eq`, just 71 /// like `HashMap` does, so that you can pass `&str` to lookup into a map with 72 /// `String` keys and so on. 73 /// 74 /// # Contract 75 /// 76 /// The implementor **must** hash like `K`, if it is hashable. 77 pub trait Equivalent<K: ?Sized> { 78 /// Compare self to `key` and return `true` if they are equal. equivalent(&self, key: &K) -> bool79 fn equivalent(&self, key: &K) -> bool; 80 } 81 82 impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q 83 where 84 Q: Eq, 85 K: Borrow<Q>, 86 { 87 #[inline] equivalent(&self, key: &K) -> bool88 fn equivalent(&self, key: &K) -> bool { 89 PartialEq::eq(self, key.borrow()) 90 } 91 } 92 93 /// Key ordering trait. 94 /// 95 /// This trait allows ordered map lookup to be customized. It has one blanket 96 /// implementation that uses the regular solution with `Borrow` and `Ord`, just 97 /// like `BTreeMap` does, so that you can pass `&str` to lookup into a map with 98 /// `String` keys and so on. 99 pub trait Comparable<K: ?Sized>: Equivalent<K> { 100 /// Compare self to `key` and return their ordering. compare(&self, key: &K) -> Ordering101 fn compare(&self, key: &K) -> Ordering; 102 } 103 104 impl<Q: ?Sized, K: ?Sized> Comparable<K> for Q 105 where 106 Q: Ord, 107 K: Borrow<Q>, 108 { 109 #[inline] compare(&self, key: &K) -> Ordering110 fn compare(&self, key: &K) -> Ordering { 111 Ord::cmp(self, key.borrow()) 112 } 113 } 114