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

cairo_lang_utils/
ordered_hash_map.rs
