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 may12//! add more flexibility in third-party map implementations, especially in13//! situations where a strict `K: Borrow<Q>` relationship is not available.14//!15//! # Examples16//!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//! where25//! 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//! where35//! 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//! ```6162#![no_std]6364usecore::borrow::Borrow;65usecore::cmp::Ordering;6667/// Key equivalence trait.68///69/// This trait allows hash table lookup to be customized. It has one blanket70/// implementation that uses the regular solution with `Borrow` and `Eq`, just71/// like `HashMap` does, so that you can pass `&str` to lookup into a map with72/// `String` keys and so on.73///74/// # Contract75///76/// The implementor **must** hash like `K`, if it is hashable.77pub traitEquivalent<K:?Sized> {78/// Compare self to `key` and return `true` if they are equal.79fnequivalent(&self, key:&K) -> bool;80}8182impl<Q:?Sized, K:?Sized> Equivalent<K>forQ83where84Q: Eq,85 K: Borrow<Q>,86{87#[inline]88fnequivalent(&self, key:&K) -> bool {89 PartialEq::eq(self, key.borrow())90 }91}9293/// Key ordering trait.94///95/// This trait allows ordered map lookup to be customized. It has one blanket96/// implementation that uses the regular solution with `Borrow` and `Ord`, just97/// like `BTreeMap` does, so that you can pass `&str` to lookup into a map with98/// `String` keys and so on.99pub traitComparable<K:?Sized>: Equivalent<K> {100/// Compare self to `key` and return their ordering.101fncompare(&self, key:&K) -> Ordering;102}103104impl<Q:?Sized, K:?Sized> Comparable<K>forQ105where106Q: Ord,107 K: Borrow<Q>,108{109#[inline]110fncompare(&self, key:&K) -> Ordering {111 Ord::cmp(self, key.borrow())112 }113}