equivalent/
lib.rs

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
64use core::borrow::Borrow;
65use 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.
77pub 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
82impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
83where
84    Q: Eq,
85    K: Borrow<Q>,
86{
87    #[inline]
88    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.
99pub trait Comparable<K: ?Sized>: Equivalent<K> {
100    /// Compare self to `key` and return their ordering.
101    fn compare(&self, key: &K) -> Ordering;
102}
103
104impl<Q: ?Sized, K: ?Sized> Comparable<K> for Q
105where
106    Q: Ord,
107    K: Borrow<Q>,
108{
109    #[inline]
110    fn compare(&self, key: &K) -> Ordering {
111        Ord::cmp(self, key.borrow())
112    }
113}
equivalent/lib.rs

equivalent/
lib.rs
