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, 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.
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, other:key.borrow())
112 }
113}
114