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

cairo_lang_utils/
ordered_hash_map.rs
