1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! [`Equivalent`] and [`Comparable`] are traits for key comparison in maps.
//!
//! These may be used in the implementation of maps where the lookup type `Q`
//! may be different than the stored key type `K`.
//!
//! * `Q: Equivalent<K>` checks for equality, similar to the `HashMap<K, V>`
//!   constraint `K: Borrow<Q>, Q: Eq`.
//! * `Q: Comparable<K>` checks the ordering, similar to the `BTreeMap<K, V>`
//!   constraint `K: Borrow<Q>, Q: Ord`.
//!
//! These traits are not used by the maps in the standard library, but they may
//! add more flexibility in third-party map implementations, especially in
//! situations where a strict `K: Borrow<Q>` relationship is not available.
//!
//! # Examples
//!
//! ```
//! use equivalent::*;
//! use std::cmp::Ordering;
//!
//! pub struct Pair<A, B>(pub A, pub B);
//!
//! impl<'a, A: ?Sized, B: ?Sized, C, D> Equivalent<(C, D)> for Pair<&'a A, &'a B>
//! where
//!     A: Equivalent<C>,
//!     B: Equivalent<D>,
//! {
//!     fn equivalent(&self, key: &(C, D)) -> bool {
//!         self.0.equivalent(&key.0) && self.1.equivalent(&key.1)
//!     }
//! }
//!
//! impl<'a, A: ?Sized, B: ?Sized, C, D> Comparable<(C, D)> for Pair<&'a A, &'a B>
//! where
//!     A: Comparable<C>,
//!     B: Comparable<D>,
//! {
//!     fn compare(&self, key: &(C, D)) -> Ordering {
//!         match self.0.compare(&key.0) {
//!             Ordering::Equal => self.1.compare(&key.1),
//!             not_equal => not_equal,
//!         }
//!     }
//! }
//!
//! fn main() {
//!     let key = (String::from("foo"), String::from("bar"));
//!     let q1 = Pair("foo", "bar");
//!     let q2 = Pair("boo", "bar");
//!     let q3 = Pair("foo", "baz");
//!
//!     assert!(q1.equivalent(&key));
//!     assert!(!q2.equivalent(&key));
//!     assert!(!q3.equivalent(&key));
//!
//!     assert_eq!(q1.compare(&key), Ordering::Equal);
//!     assert_eq!(q2.compare(&key), Ordering::Less);
//!     assert_eq!(q3.compare(&key), Ordering::Greater);
//! }
//! ```

#![no_std]

use core::borrow::Borrow;
use core::cmp::Ordering;

/// Key equivalence trait.
///
/// This trait allows hash table lookup to be customized. It has one blanket
/// implementation that uses the regular solution with `Borrow` and `Eq`, just
/// like `HashMap` does, so that you can pass `&str` to lookup into a map with
/// `String` keys and so on.
///
/// # Contract
///
/// The implementor **must** hash like `K`, if it is hashable.
pub trait Equivalent<K: ?Sized> {
    /// Compare self to `key` and return `true` if they are equal.
    fn equivalent(&self, key: &K) -> bool;
}

impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
where
    Q: Eq,
    K: Borrow<Q>,
{
    #[inline]
    fn equivalent(&self, key: &K) -> bool {
        PartialEq::eq(self, key.borrow())
    }
}

/// Key ordering trait.
///
/// This trait allows ordered map lookup to be customized. It has one blanket
/// implementation that uses the regular solution with `Borrow` and `Ord`, just
/// like `BTreeMap` does, so that you can pass `&str` to lookup into a map with
/// `String` keys and so on.
pub trait Comparable<K: ?Sized>: Equivalent<K> {
    /// Compare self to `key` and return their ordering.
    fn compare(&self, key: &K) -> Ordering;
}

impl<Q: ?Sized, K: ?Sized> Comparable<K> for Q
where
    Q: Ord,
    K: Borrow<Q>,
{
    #[inline]
    fn compare(&self, key: &K) -> Ordering {
        Ord::cmp(self, key.borrow())
    }
}