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. In other words,
77/// `self.equivalent(key)` implies `hash(self) == hash(key)`.
78pub trait Equivalent<K: ?Sized> {
79    /// Compare self to `key` and return `true` if they are equal.
80    fn equivalent(&self, key: &K) -> bool;
81}
82
83impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
84where
85    Q: Eq,
86    K: Borrow<Q>,
87{
88    #[inline]
89    fn equivalent(&self, key: &K) -> bool {
90        PartialEq::eq(self, key.borrow())
91    }
92}
93
94/// Key ordering trait.
95///
96/// This trait allows ordered map lookup to be customized. It has one blanket
97/// implementation that uses the regular solution with `Borrow` and `Ord`, just
98/// like `BTreeMap` does, so that you can pass `&str` to lookup into a map with
99/// `String` keys and so on.
100///
101/// # Contract
102///
103/// Implementations **must** agree with [`Equivalent`], such that
104/// `self.compare(key).is_eq()` always matches `self.equivalent(key)`.
105pub trait Comparable<K: ?Sized>: Equivalent<K> {
106    /// Compare self to `key` and return their ordering.
107    fn compare(&self, key: &K) -> Ordering;
108}
109
110impl<Q: ?Sized, K: ?Sized> Comparable<K> for Q
111where
112    Q: Ord,
113    K: Borrow<Q>,
114{
115    #[inline]
116    fn compare(&self, key: &K) -> Ordering {
117        Ord::cmp(self, key.borrow())
118    }
119}
equivalent/lib.rs

equivalent/
lib.rs
