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. |
79 | 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 ] |
88 | fn equivalent(&self, key: &K) -> bool { |
89 | PartialEq::eq(self, other: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. |
101 | 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 ] |
110 | fn compare(&self, key: &K) -> Ordering { |
111 | Ord::cmp(self, other:key.borrow()) |
112 | } |
113 | } |
114 | |