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 /// Local Android change: Use std to allow building as a dylib. 65 #[cfg(android_dylib)] 66 extern crate std; 67 68 use core::borrow::Borrow; 69 use core::cmp::Ordering; 70 71 /// Key equivalence trait. 72 /// 73 /// This trait allows hash table lookup to be customized. It has one blanket 74 /// implementation that uses the regular solution with `Borrow` and `Eq`, just 75 /// like `HashMap` does, so that you can pass `&str` to lookup into a map with 76 /// `String` keys and so on. 77 /// 78 /// # Contract 79 /// 80 /// The implementor **must** hash like `K`, if it is hashable. 81 pub trait Equivalent<K: ?Sized> { 82 /// Compare self to `key` and return `true` if they are equal. equivalent(&self, key: &K) -> bool83 fn equivalent(&self, key: &K) -> bool; 84 } 85 86 impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q 87 where 88 Q: Eq, 89 K: Borrow<Q>, 90 { 91 #[inline] equivalent(&self, key: &K) -> bool92 fn equivalent(&self, key: &K) -> bool { 93 PartialEq::eq(self, key.borrow()) 94 } 95 } 96 97 /// Key ordering trait. 98 /// 99 /// This trait allows ordered map lookup to be customized. It has one blanket 100 /// implementation that uses the regular solution with `Borrow` and `Ord`, just 101 /// like `BTreeMap` does, so that you can pass `&str` to lookup into a map with 102 /// `String` keys and so on. 103 pub trait Comparable<K: ?Sized>: Equivalent<K> { 104 /// Compare self to `key` and return their ordering. compare(&self, key: &K) -> Ordering105 fn compare(&self, key: &K) -> Ordering; 106 } 107 108 impl<Q: ?Sized, K: ?Sized> Comparable<K> for Q 109 where 110 Q: Ord, 111 K: Borrow<Q>, 112 { 113 #[inline] compare(&self, key: &K) -> Ordering114 fn compare(&self, key: &K) -> Ordering { 115 Ord::cmp(self, key.borrow()) 116 } 117 } 118