cairo_lang_utils/
ordered_hash_map.rs

1use core::hash::{BuildHasher, Hash};
2use core::ops::{Index, IndexMut};
3#[cfg(feature = "std")]
4use std::collections::hash_map::RandomState;
5
6use indexmap::{Equivalent, IndexMap};
7use itertools::zip_eq;
8
9#[cfg(feature = "std")]
10#[derive(Clone, Debug)]
11pub struct OrderedHashMap<Key, Value, BH = RandomState>(IndexMap<Key, Value, BH>);
12#[cfg(not(feature = "std"))]
13#[derive(Clone, Debug)]
14pub struct OrderedHashMap<Key, Value, BH = hashbrown::DefaultHashBuilder>(IndexMap<Key, Value, BH>);
15
16impl<Key, Value, BH: Default> Default for OrderedHashMap<Key, Value, BH> {
17    #[cfg(feature = "std")]
18    fn default() -> Self {
19        Self(Default::default())
20    }
21    #[cfg(not(feature = "std"))]
22    fn default() -> Self {
23        Self(IndexMap::with_hasher(Default::default()))
24    }
25}
26
27impl<Key, Value, BH> OrderedHashMap<Key, Value, BH> {
28    /// Returns an iterator over the key-value pairs of the map, in their order.
29    pub fn iter(&self) -> indexmap::map::Iter<'_, Key, Value> {
30        self.0.iter()
31    }
32
33    /// Returns a mutable iterator over the key-value pairs of the map, in their order.
34    pub fn iter_mut(&mut self) -> indexmap::map::IterMut<'_, Key, Value> {
35        self.0.iter_mut()
36    }
37
38    /// Returns an iterator over the keys of the map, in their order.
39    pub fn keys(&self) -> indexmap::map::Keys<'_, Key, Value> {
40        self.0.keys()
41    }
42
43    /// Returns a consuming iterator over the keys of the map, in their order.
44    pub fn into_keys(self) -> indexmap::map::IntoKeys<Key, Value> {
45        self.0.into_keys()
46    }
47
48    /// Returns an iterator over the values of the map, in their order.
49    pub fn values(&self) -> indexmap::map::Values<'_, Key, Value> {
50        self.0.values()
51    }
52
53    /// Returns the number of key-value pairs in the map.
54    pub fn len(&self) -> usize {
55        self.0.len()
56    }
57
58    /// Returns true if the map contains no elements.
59    pub fn is_empty(&self) -> bool {
60        self.0.is_empty()
61    }
62
63    /// Removes all the entries for the map.
64    pub fn clear(&mut self) {
65        self.0.clear()
66    }
67
68    /// Removes the entry at the given index.
69    ///
70    /// Returns the key-value pair at the given index (if present).
71    pub fn shift_remove_index(&mut self, index: usize) -> Option<(Key, Value)> {
72        self.0.shift_remove_index(index)
73    }
74}
75
76impl<Key: Eq + Hash, Value, BH: BuildHasher> OrderedHashMap<Key, Value, BH> {
77    /// Returns a reference to the value stored for key, if it is present, else None.
78    ///
79    /// Computes in O(1) time (average).
80    pub fn get<Q: ?Sized + Hash + Equivalent<Key>>(&self, key: &Q) -> Option<&Value> {
81        self.0.get(key)
82    }
83
84    /// Returns a mutable reference to the value stored for key, if it is present, else None.
85    ///
86    /// Computes in O(1) time (average).
87    pub fn get_mut<Q: ?Sized + Hash + Equivalent<Key>>(&mut self, key: &Q) -> Option<&mut Value> {
88        self.0.get_mut(key)
89    }
90
91    /// Gets the given key’s corresponding entry in the map for insertion and/or in-place
92    /// manipulation.
93    ///
94    /// Computes in O(1) time (amortized average).
95    pub fn entry(&mut self, key: Key) -> Entry<'_, Key, Value> {
96        self.0.entry(key)
97    }
98
99    /// Insert a key-value pair in the map.
100    ///
101    /// If an equivalent key already exists in the map: the key remains and retains in its place in
102    /// the order, its corresponding value is updated with value and the older value is returned
103    /// inside Some(_).
104    ///
105    /// If no equivalent key existed in the map: the new key-value pair is inserted, last in order,
106    /// and None is returned.
107    ///
108    /// Computes in O(1) time (amortized average).
109    ///
110    /// See also entry if you want to insert or modify or if you need to get the index of the
111    /// corresponding key-value pair.
112    pub fn insert(&mut self, key: Key, value: Value) -> Option<Value> {
113        self.0.insert(key, value)
114    }
115
116    /// Extends the map with the content of the given iterator.
117    pub fn extend<I: IntoIterator<Item = (Key, Value)>>(&mut self, iter: I) {
118        self.0.extend(iter)
119    }
120
121    /// Returns true if an equivalent to key exists in the map.
122    pub fn contains_key<Q: ?Sized + Hash + Equivalent<Key>>(&self, key: &Q) -> bool {
123        self.0.contains_key(key)
124    }
125
126    /// Removes the entry for the given key, preserving the order of entries.
127    ///
128    /// Returns the value associated with the key (if present).
129    pub fn shift_remove<Q: ?Sized + Hash + Equivalent<Key>>(&mut self, key: &Q) -> Option<Value> {
130        self.0.shift_remove(key)
131    }
132
133    /// Removes the entry for the given key by swapping it with the last element.
134    /// Thus the order of elements is not preserved, but the resulting order is still deterministic.
135    ///
136    /// Returns the value associated with the key (if present).
137    pub fn swap_remove<Q: ?Sized + Hash + Equivalent<Key>>(&mut self, key: &Q) -> Option<Value> {
138        self.0.swap_remove(key)
139    }
140
141    /// Scan through each key-value pair in the map and keep those where the
142    /// closure `keep` returns `true`.
143    ///
144    /// The elements are visited in order, and remaining elements keep their
145    /// order.
146    ///
147    /// Computes in **O(n)** time (average).
148    pub fn retain(&mut self, keep: impl FnMut(&Key, &mut Value) -> bool) {
149        self.0.retain(keep);
150    }
151
152    /// Returns true if the maps are equal, ignoring the order of the entries.
153    pub fn eq_unordered(&self, other: &Self) -> bool
154    where
155        Value: Eq,
156    {
157        if self.0.len() != other.0.len() {
158            return false;
159        };
160        self.0.iter().all(|(k, v)| other.0.get(k) == Some(v))
161    }
162}
163
164/// Entry for an existing key-value pair or a vacant location to insert one.
165pub type Entry<'a, Key, Value> = indexmap::map::Entry<'a, Key, Value>;
166
167impl<Key, Value, BH> IntoIterator for OrderedHashMap<Key, Value, BH> {
168    type Item = (Key, Value);
169    type IntoIter = indexmap::map::IntoIter<Key, Value>;
170    fn into_iter(self) -> Self::IntoIter {
171        let OrderedHashMap(inner) = self;
172        inner.into_iter()
173    }
174}
175
176impl<Key, Value, Q: ?Sized, BH> Index<&Q> for OrderedHashMap<Key, Value, BH>
177where
178    Q: Hash + Equivalent<Key>,
179    Key: Hash + Eq,
180    BH: BuildHasher,
181{
182    type Output = Value;
183
184    fn index(&self, index: &Q) -> &Self::Output {
185        self.0.index(index)
186    }
187}
188
189impl<Key, Value, Q: ?Sized, BH> IndexMut<&Q> for OrderedHashMap<Key, Value, BH>
190where
191    Q: Hash + Equivalent<Key>,
192    Key: Hash + Eq,
193    BH: BuildHasher,
194{
195    fn index_mut(&mut self, index: &Q) -> &mut Value {
196        self.0.index_mut(index)
197    }
198}
199
200impl<Key: Eq, Value: Eq, BH> PartialEq for OrderedHashMap<Key, Value, BH> {
201    fn eq(&self, other: &Self) -> bool {
202        if self.0.len() != other.0.len() {
203            return false;
204        };
205
206        zip_eq(self.0.iter(), other.0.iter()).all(|(a, b)| a == b)
207    }
208}
209
210impl<Key: Hash + Eq, Value: Eq, BH: BuildHasher> Eq for OrderedHashMap<Key, Value, BH> {}
211
212impl<Key: Hash + Eq, Value, BH: BuildHasher + Default> FromIterator<(Key, Value)>
213    for OrderedHashMap<Key, Value, BH>
214{
215    fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
216        Self(iter.into_iter().collect())
217    }
218}
219
220impl<Key: Hash + Eq, Value, BH: BuildHasher + Default, const N: usize> From<[(Key, Value); N]>
221    for OrderedHashMap<Key, Value, BH>
222{
223    fn from(init_map: [(Key, Value); N]) -> Self {
224        Self(IndexMap::from_iter(init_map))
225    }
226}
227
228#[cfg(feature = "serde")]
229mod impl_serde {
230    #[cfg(not(feature = "std"))]
231    use alloc::vec::Vec;
232
233    use itertools::Itertools;
234    use serde::{Deserialize, Deserializer, Serialize, Serializer};
235
236    use super::*;
237
238    impl<K: Hash + Eq + Serialize, V: Serialize, BH: BuildHasher> Serialize
239        for OrderedHashMap<K, V, BH>
240    {
241        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
242        where
243            S: Serializer,
244        {
245            self.0.serialize(serializer)
246        }
247    }
248
249    impl<'de, K: Hash + Eq + Deserialize<'de>, V: Deserialize<'de>, BH: BuildHasher + Default>
250        Deserialize<'de> for OrderedHashMap<K, V, BH>
251    {
252        fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
253            IndexMap::<K, V, BH>::deserialize(deserializer).map(|s| OrderedHashMap(s))
254        }
255    }
256
257    pub fn serialize_ordered_hashmap_vec<'de, K, V, BH, S>(
258        v: &OrderedHashMap<K, V, BH>,
259        serializer: S,
260    ) -> Result<S::Ok, S::Error>
261    where
262        S: Serializer,
263        K: Serialize + Deserialize<'de> + Hash + Eq,
264        V: Serialize + Deserialize<'de>,
265    {
266        v.iter().collect_vec().serialize(serializer)
267    }
268
269    pub fn deserialize_ordered_hashmap_vec<'de, K, V, BH: BuildHasher + Default, D>(
270        deserializer: D,
271    ) -> Result<OrderedHashMap<K, V, BH>, D::Error>
272    where
273        D: Deserializer<'de>,
274        K: Serialize + Deserialize<'de> + Hash + Eq,
275        V: Serialize + Deserialize<'de>,
276    {
277        Ok(Vec::<(K, V)>::deserialize(deserializer)?.into_iter().collect())
278    }
279}
280#[cfg(feature = "serde")]
281pub use impl_serde::*;
cairo_lang_utils/ordered_hash_map.rs

cairo_lang_utils/
ordered_hash_map.rs
