iddqd/id_ord_map/
trait_defs.rs

1//! Trait definitions for `IdOrdMap`.
2
3use alloc::{boxed::Box, rc::Rc, sync::Arc};
4use core::hash::Hash;
5
6/// An element stored in an [`IdOrdMap`].
7///
8/// This trait is used to define the key type for the map.
9///
10/// # Examples
11///
12/// ```
13/// use iddqd::{IdOrdItem, IdOrdMap, id_upcast};
14///
15/// // Define a struct with a key.
16/// #[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
17/// struct MyItem {
18///     id: String,
19///     value: u32,
20/// }
21///
22/// // Implement IdOrdItem for the struct.
23/// impl IdOrdItem for MyItem {
24///     // Keys can borrow from the item.
25///     type Key<'a> = &'a str;
26///
27///     fn key(&self) -> Self::Key<'_> {
28///         &self.id
29///     }
30///
31///     id_upcast!();
32/// }
33///
34/// // Create an IdOrdMap and insert items.
35/// let mut map = IdOrdMap::new();
36/// map.insert_unique(MyItem { id: "foo".to_string(), value: 42 }).unwrap();
37/// map.insert_unique(MyItem { id: "bar".to_string(), value: 20 }).unwrap();
38/// ```
39///
40/// [`IdOrdMap`]: crate::IdOrdMap
41pub trait IdOrdItem {
42    /// The key type.
43    ///
44    /// The [`Ord`] implementation is used for ordered comparisons, while the
45    /// [`Hash`] implementation is used for [`RefMut`]'s change detection.
46    /// Ideally [`Hash`] would only be required on the methods that need it, but
47    /// we require it here due to limitations in current versions of Rust.
48    ///
49    /// As required by Rust, the [`Hash`] and [`Ord`] (and [`Eq`], which is
50    /// required by [`Ord`]) implementations must agree with each other. In
51    /// particular, if two keys A and B return
52    /// [`Ordering::Equal`](std::cmp::Ordering::Equal), then [`Hash::hash`] must
53    /// return the same value for both A and B. (Strictly speaking, the converse
54    /// is not required, but it's always best to try and match the two up to
55    /// hash collisions.)
56    ///
57    /// [`RefMut`]: crate::id_ord_map::RefMut
58    type Key<'a>: Ord + Hash
59    where
60        Self: 'a;
61
62    /// Retrieves the key.
63    fn key(&self) -> Self::Key<'_>;
64
65    /// Upcasts the key to a shorter lifetime, in effect asserting that the
66    /// lifetime `'a` on [`IdOrdItem::Key`] is covariant.
67    ///
68    /// Typically implemented via the [`id_upcast`] macro.
69    ///
70    /// [`id_upcast`]: crate::id_upcast
71    fn upcast_key<'short, 'long: 'short>(
72        long: Self::Key<'long>,
73    ) -> Self::Key<'short>;
74}
75
76macro_rules! impl_for_ref {
77    ($type:ty) => {
78        impl<'b, T: 'b + ?Sized + IdOrdItem> IdOrdItem for $type {
79            type Key<'a>
80                = T::Key<'a>
81            where
82                Self: 'a;
83
84            fn key(&self) -> Self::Key<'_> {
85                (**self).key()
86            }
87
88            fn upcast_key<'short, 'long: 'short>(
89                long: Self::Key<'long>,
90            ) -> Self::Key<'short>
91            where
92                Self: 'long,
93            {
94                T::upcast_key(long)
95            }
96        }
97    };
98}
99
100impl_for_ref!(&'b T);
101impl_for_ref!(&'b mut T);
102
103macro_rules! impl_for_box {
104    ($type:ty) => {
105        impl<T: ?Sized + IdOrdItem> IdOrdItem for $type {
106            type Key<'a>
107                = T::Key<'a>
108            where
109                Self: 'a;
110
111            fn key(&self) -> Self::Key<'_> {
112                (**self).key()
113            }
114
115            fn upcast_key<'short, 'long: 'short>(
116                long: Self::Key<'long>,
117            ) -> Self::Key<'short> {
118                T::upcast_key(long)
119            }
120        }
121    };
122}
123
124impl_for_box!(Box<T>);
125impl_for_box!(Rc<T>);
126impl_for_box!(Arc<T>);
iddqd/id_ord_map/trait_defs.rs

iddqd/id_ord_map/
trait_defs.rs
