cairo_lang_utils/
unordered_hash_map.rs

1#[cfg(test)]
2#[path = "unordered_hash_map_test.rs"]
3mod test;
4
5#[cfg(not(feature = "std"))]
6use alloc::vec;
7use core::borrow::Borrow;
8use core::hash::{BuildHasher, Hash};
9use core::ops::Index;
10#[cfg(feature = "std")]
11use std::collections::HashMap;
12#[cfg(feature = "std")]
13pub use std::collections::hash_map::Entry;
14#[cfg(feature = "std")]
15use std::collections::hash_map::OccupiedEntry;
16#[cfg(feature = "std")]
17use std::collections::hash_map::RandomState;
18#[cfg(feature = "std")]
19use std::vec;
20
21#[cfg(not(feature = "std"))]
22use hashbrown::HashMap;
23#[cfg(not(feature = "std"))]
24pub use hashbrown::hash_map::Entry;
25use itertools::Itertools;
26
27/// A hash map that does not care about the order of insertion.
28///
29/// In particular, it does not support iterating, in order to guarantee deterministic compilation.
30/// It does support aggregation which can be used in intermediate computations (see `aggregate_by`).
31/// For an iterable version see [OrderedHashMap](crate::ordered_hash_map::OrderedHashMap).
32#[cfg(feature = "std")]
33#[derive(Clone, Debug)]
34pub struct UnorderedHashMap<Key, Value, BH = RandomState>(HashMap<Key, Value, BH>);
35#[cfg(not(feature = "std"))]
36#[derive(Clone, Debug)]
37pub struct UnorderedHashMap<Key, Value, BH = hashbrown::hash_map::DefaultHashBuilder>(
38    HashMap<Key, Value, BH>,
39);
40
41impl<Key, Value, BH> UnorderedHashMap<Key, Value, BH> {
42    fn with_hasher(hash_builder: BH) -> Self {
43        Self(HashMap::<Key, Value, BH>::with_hasher(hash_builder))
44    }
45}
46
47impl<Key, Value, BH> PartialEq for UnorderedHashMap<Key, Value, BH>
48where
49    Key: Eq + Hash,
50    Value: PartialEq,
51    BH: BuildHasher,
52{
53    fn eq(&self, other: &Self) -> bool {
54        self.0 == other.0
55    }
56}
57
58impl<Key, Value, BH> Eq for UnorderedHashMap<Key, Value, BH>
59where
60    Key: Eq + Hash,
61    Value: Eq,
62    BH: BuildHasher,
63{
64}
65
66impl<Key, Value, BH> UnorderedHashMap<Key, Value, BH> {
67    /// Returns the number of elements in the map.
68    pub fn len(&self) -> usize {
69        self.0.len()
70    }
71
72    /// Returns true if the map contains no elements.
73    pub fn is_empty(&self) -> bool {
74        self.0.is_empty()
75    }
76}
77
78impl<Key: Eq + Hash, Value, BH: BuildHasher> UnorderedHashMap<Key, Value, BH> {
79    /// Returns a reference to the value corresponding to the key.
80    ///
81    /// The key may be any borrowed form of the map's key type, but [`Hash`] and [`Eq`] on the
82    /// borrowed form *must* match those for the key type.
83    pub fn get<Q>(&self, key: &Q) -> Option<&Value>
84    where
85        Key: Borrow<Q>,
86        Q: Hash + Eq + ?Sized,
87    {
88        self.0.get(key)
89    }
90
91    /// Returns a mutable reference to the value corresponding to the key.
92    ///
93    /// The key may be any borrowed form of the map's key type, but [`Hash`] and [`Eq`] on the
94    /// borrowed form *must* match those for the key type.
95    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut Value>
96    where
97        Key: Borrow<Q>,
98        Q: Hash + Eq + ?Sized,
99    {
100        self.0.get_mut(key)
101    }
102
103    /// Inserts a key-value pair into the map.
104    ///
105    /// If the map did not have this key present, None is returned.
106    ///
107    /// If the map did have this key present, the value is updated, and the old value is returned.
108    /// The key is not updated, though; this matters for types that can be == without being
109    /// identical.
110    pub fn insert(&mut self, key: Key, value: Value) -> Option<Value> {
111        self.0.insert(key, value)
112    }
113
114    /// Removes a key from the map, returning the value at the key if the key was previously in the
115    /// map.
116    ///
117    /// The key may be any borrowed form of the map's key type, but Hash and Eq on the borrowed form
118    /// must match those for the key type.
119    pub fn remove<Q>(&mut self, key: &Q) -> Option<Value>
120    where
121        Key: Borrow<Q>,
122        Q: Hash + Eq + ?Sized,
123    {
124        self.0.remove(key)
125    }
126
127    #[cfg(feature = "std")]
128    /// Gets the given key's corresponding entry in the map for in-place manipulation.
129    pub fn entry(&mut self, key: Key) -> Entry<'_, Key, Value> {
130        self.0.entry(key)
131    }
132
133    #[cfg(not(feature = "std"))]
134    /// Gets the given key's corresponding entry in the map for in-place manipulation.
135    pub fn entry(&mut self, key: Key) -> Entry<'_, Key, Value, BH> {
136        self.0.entry(key)
137    }
138
139    /// Returns true if the map contains a value for the specified key.
140    pub fn contains_key<Q>(&self, key: &Q) -> bool
141    where
142        Q: ?Sized,
143        Key: Borrow<Q>,
144        Q: Hash + Eq,
145    {
146        self.0.contains_key(key)
147    }
148
149    /// Maps the values of the map to new values using the given function.
150    pub fn map<TargetValue>(
151        &self,
152        mapper: impl Fn(&Value) -> TargetValue,
153    ) -> UnorderedHashMap<Key, TargetValue, BH>
154    where
155        Key: Clone,
156        BH: Clone,
157    {
158        self.0.iter().fold(
159            UnorderedHashMap::<_, _, _>::with_hasher(self.0.hasher().clone()),
160            |mut acc, (key, value)| {
161                match acc.entry(key.clone()) {
162                    Entry::Occupied(_) => {
163                        unreachable!("The original map should not contain duplicate keys.");
164                    }
165                    Entry::Vacant(vacant) => {
166                        vacant.insert(mapper(value));
167                    }
168                };
169                acc
170            },
171        )
172    }
173
174    /// Aggregates values of the map using the given functions.
175    /// `mapping_function` maps each key to a new key, possibly mapping multiple original keys to
176    /// the same target key.
177    /// `reduce_function` dictates how to aggregate any two values of the same target key.
178    /// `default_value` is the initial value for each target key.
179    /// Note! as the map is unordered, `reduce_function` should be commutative. Otherwise, the
180    /// result is undefined (nondeterministic).
181    pub fn aggregate_by<TargetKey: Eq + Hash, TargetValue>(
182        &self,
183        mapping_function: impl Fn(&Key) -> TargetKey,
184        reduce_function: impl Fn(&TargetValue, &Value) -> TargetValue,
185        default_value: &TargetValue,
186    ) -> UnorderedHashMap<TargetKey, TargetValue, BH>
187    where
188        BH: Clone,
189    {
190        self.0.iter().fold(
191            UnorderedHashMap::<_, _, _>::with_hasher(self.0.hasher().clone()),
192            |mut acc, (key, value)| {
193                let target_key = mapping_function(key);
194                match acc.entry(target_key) {
195                    Entry::Occupied(occupied) => {
196                        let old_target_value = occupied.into_mut();
197                        let new_target_value = reduce_function(old_target_value, value);
198                        *old_target_value = new_target_value;
199                    }
200                    Entry::Vacant(vacant) => {
201                        let new_value = reduce_function(default_value, value);
202                        vacant.insert(new_value);
203                    }
204                };
205                acc
206            },
207        )
208    }
209
210    /// Iterates the map in an ascending order applied by the `Ord` implementation of `Key`.
211    /// NOTE! To guarantee a deterministic output, the `Ord` implementation must apply a strict
212    /// ordering. That is, `a <= b` and `b <= a`, then `a == b`. If `Ord` is derived (in all
213    /// hierarchy levels), this is probably the case. If the ordering is not strict, the order of
214    /// the output OrderedHashMap is undefined (nondeterministic).
215    /// This can be used to convert an unordered map to an ordered map (mostly when the unordered
216    /// map was used for intermediate processing).
217    pub fn iter_sorted(&self) -> impl Iterator<Item = (&Key, &Value)>
218    where
219        Key: Ord,
220    {
221        self.0.iter().sorted_by_key(|(key, _)| *key)
222    }
223
224    /// A consuming version of `iter_sorted`.
225    pub fn into_iter_sorted(self) -> impl Iterator<Item = (Key, Value)>
226    where
227        Key: Ord + Clone,
228    {
229        self.0.into_iter().sorted_by_key(|(key, _)| (*key).clone())
230    }
231
232    /// Iterates the map in an ascending order of the keys produced by the given function `f`.
233    /// NOTE! To guarantee a deterministic output, `f`'s implementation must apply a strict
234    /// ordering of the (Key, Value) pairs. That is, for any given pair of entries `a=(k_a, v_a)`
235    /// and `b=(k_b, v_b)`, if `a <= b` and `b <= a`, then `a == b`. If the ordering is not strict,
236    /// the order of the output OrderedHashMap is undefined (nondeterministic).
237    /// This can be used to convert an unordered map to an ordered map (mostly when the unordered
238    /// map was used for intermediate processing).
239    pub fn iter_sorted_by_key<TargetKey, F>(&self, f: F) -> vec::IntoIter<(&Key, &Value)>
240    where
241        TargetKey: Ord,
242        F: FnMut(&(&Key, &Value)) -> TargetKey,
243    {
244        self.0.iter().sorted_by_key(f)
245    }
246
247    /// A consuming version of `iter_sorted_by_key`.
248    pub fn into_iter_sorted_by_key<TargetKey, F>(self, f: F) -> vec::IntoIter<(Key, Value)>
249    where
250        TargetKey: Ord,
251        F: FnMut(&(Key, Value)) -> TargetKey,
252    {
253        self.0.into_iter().sorted_by_key(f)
254    }
255
256    /// Creates a new map with only the elements from the original map for which the given predicate
257    /// returns `true`. Consuming.
258    pub fn filter<P>(self, mut p: P) -> Self
259    where
260        BH: Default,
261        P: FnMut(&Key, &Value) -> bool,
262    {
263        Self(self.0.into_iter().filter(|(key, value)| p(key, value)).collect())
264    }
265
266    /// Non consuming version of `filter`. Only clones the filtered entries. Requires `Key` and
267    /// `Value` to implement `Clone`.
268    pub fn filter_cloned<P>(&self, mut p: P) -> Self
269    where
270        BH: Default,
271        P: FnMut(&Key, &Value) -> bool,
272        Key: Clone,
273        Value: Clone,
274    {
275        Self(
276            self.0
277                .iter()
278                .filter_map(
279                    |(key, value)| {
280                        if p(key, value) { Some((key.clone(), value.clone())) } else { None }
281                    },
282                )
283                .collect(),
284        )
285    }
286
287    #[cfg(feature = "std")]
288    /// Merges the map with another map. If a key is present in both maps, the given handler
289    /// function is used to combine the values.
290    pub fn merge<HandleDuplicate>(&mut self, other: &Self, handle_duplicate: HandleDuplicate)
291    where
292        BH: Clone,
293        HandleDuplicate: Fn(OccupiedEntry<'_, Key, Value>, &Value),
294        Key: Clone,
295        Value: Clone,
296    {
297        for (key, value) in &other.0 {
298            match self.0.entry(key.clone()) {
299                Entry::Occupied(e) => {
300                    handle_duplicate(e, value);
301                }
302                Entry::Vacant(e) => {
303                    e.insert(value.clone());
304                }
305            }
306        }
307    }
308}
309
310impl<Key, Q: ?Sized, Value, BH: BuildHasher> Index<&Q> for UnorderedHashMap<Key, Value, BH>
311where
312    Key: Eq + Hash + Borrow<Q>,
313    Q: Eq + Hash,
314{
315    type Output = Value;
316
317    fn index(&self, key: &Q) -> &Self::Output {
318        self.0.index(key)
319    }
320}
321
322impl<Key, Value, BH: Default> Default for UnorderedHashMap<Key, Value, BH> {
323    #[cfg(feature = "std")]
324    fn default() -> Self {
325        Self(Default::default())
326    }
327    #[cfg(not(feature = "std"))]
328    fn default() -> Self {
329        Self(HashMap::with_hasher(Default::default()))
330    }
331}
332
333impl<Key: Hash + Eq, Value, BH: BuildHasher + Default> FromIterator<(Key, Value)>
334    for UnorderedHashMap<Key, Value, BH>
335{
336    fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
337        Self(iter.into_iter().collect())
338    }
339}
340
341impl<Key: Hash + Eq, Value, const N: usize, BH: BuildHasher + Default> From<[(Key, Value); N]>
342    for UnorderedHashMap<Key, Value, BH>
343{
344    fn from(items: [(Key, Value); N]) -> Self {
345        Self(HashMap::from_iter(items))
346    }
347}
cairo_lang_utils/unordered_hash_map.rs

cairo_lang_utils/
unordered_hash_map.rs
