tini/
ordered_hashmap.rs

1//! Ordered Hashmap
2//!
3//! Needs to iterate over items in predictable order
4//! e.g. for save ini sections and items in the same order as loaded or added
5
6use std::borrow::Borrow;
7use std::collections::hash_map::{self, Entry};
8use std::collections::HashMap;
9use std::hash::Hash;
10use std::iter::FromIterator;
11use std::iter::IntoIterator;
12
13/// Ordered hashmap built on top of std::collections::HashMap
14/// Keys are stored in the field `keys` in the order they were added
15#[derive(Debug)]
16pub struct OrderedHashMap<K, V> {
17    #[doc(hidden)]
18    base: HashMap<K, V>,
19    keys: Vec<K>,
20}
21
22impl<K, V> OrderedHashMap<K, V>
23where
24    K: Eq + Hash + Clone,
25{
26    /// Creates an empty `OrderedHashMap`.
27    ///
28    /// # Examples
29    ///
30    /// ```ignore
31    /// let mut map: OrderedHashMap<&str, i32> = HashMap::new();
32    /// ```
33    pub fn new() -> OrderedHashMap<K, V> {
34        OrderedHashMap { base: HashMap::<K, V>::new(), keys: Vec::<K>::new() }
35    }
36
37    /// Returns a reference to the value corresponding to the key.
38    ///
39    /// The key may be any borrowed form of the map's key type, but
40    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
41    /// the key type.
42    ///
43    /// # Examples
44    ///
45    /// ```ignore
46    /// let mut map = OrderedHashMap::new();
47    /// map.insert(1, "a");
48    /// assert_eq!(map.get(&1), Some(&"a"));
49    /// assert_eq!(map.get(&2), None);
50    /// ```
51    pub fn get<Q>(&self, k: &Q) -> Option<&V>
52    where
53        K: Borrow<Q>,
54        Q: Hash + Eq + ?Sized,
55    {
56        self.base.get(k)
57    }
58
59    /// Returns a mutable reference to the value corresponding to the key.
60    ///
61    /// The key may be any borrowed form of the map's key type, but
62    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
63    /// the key type.
64    ///
65    /// # Examples
66    ///
67    /// ```ignore
68    /// use ordered_hashmap::OrderedHashMap;
69    ///
70    /// let mut map = OrderedHashMap::new();
71    /// map.insert(1, "a");
72    /// if let Some(x) = map.get_mut(&1) {
73    ///     *x = "b";
74    /// }
75    /// assert_eq!(map[&1], "b");
76    /// ```
77    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
78    where
79        K: Borrow<Q>,
80        Q: Hash + Eq + ?Sized,
81    {
82        self.base.get_mut(k)
83    }
84
85    pub fn contains_key<Q>(&self, k: &Q) -> bool
86    where
87        K: Borrow<Q>,
88        Q: Hash + Eq + ?Sized,
89    {
90        self.base.contains_key(k)
91    }
92
93    /// Inserts a key-value pair into the map.
94    ///
95    /// If the map did not have this key present, [`None`] is returned.
96    ///
97    /// If the map did have this key present, the value is updated, and the old
98    /// value is returned. The key is not updated, though; this matters for
99    /// types that can be `==` without being identical.
100    ///
101    /// # Examples
102    ///
103    /// ```ignore
104    /// let mut map = OrderedHashMap::new();
105    /// assert_eq!(map.insert(37, "a"), None);
106    /// assert_eq!(map.is_empty(), false);
107    ///
108    /// map.insert(37, "b");
109    /// assert_eq!(map.insert(37, "c"), Some("b"));
110    /// assert_eq!(map[&37], "c");
111    /// ```
112    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
113        if !self.base.contains_key(&k) {
114            self.keys.push(k.clone());
115        }
116        self.base.insert(k, v)
117    }
118
119    /// Removes a key from the map, returning the value at the key if the key
120    /// was previously in the map.
121    ///
122    /// # Examples
123    ///
124    /// ```ignore
125    /// let mut map = OrderedHashMap::new();
126    /// map.insert(1, "a");
127    /// assert_eq!(map.remove(&1), Some("a"));
128    /// assert_eq!(map.remove(&1), None);
129    /// ```
130    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
131    where
132        K: Borrow<Q> + PartialEq<Q>,
133        Q: Hash + Eq + ?Sized,
134    {
135        match self.keys.iter().position(|x| x == k) {
136            Some(index) => {
137                self.keys.swap_remove(index);
138                self.base.remove(k)
139            }
140            None => None,
141        }
142    }
143
144    /// An iterator visiting all key-value pairs in the order they were added.
145    /// The iterator element type is `(&'a K, &'a V)`.
146    ///
147    /// # Examples
148    ///
149    /// ```ignore
150    /// let mut map = OrderedHashMap::new();
151    /// map.insert("a", 1);
152    /// map.insert("b", 2);
153    /// map.insert("c", 3);
154    ///
155    /// for (key, val) in map.iter() {
156    ///     println!("key: {} val: {}", key, val);
157    /// }
158    /// ```
159    pub fn iter(&self) -> Iter<'_, K, V> {
160        Iter { base: &self.base, keys_iterator: self.keys.iter() }
161    }
162
163    /// An iterator visiting all key-value pairs in the order they were added,
164    /// with mutable references to the values.
165    /// The iterator element type is `(&'a K, &'a mut V)`.
166    ///
167    /// # Examples
168    ///
169    /// ```ignore
170    /// let mut map = OrderedHashMap::new();
171    /// map.insert("a", 1);
172    /// map.insert("b", 2);
173    /// map.insert("c", 3);
174    ///
175    /// // Update all values
176    /// for (_, val) in map.iter_mut() {
177    ///     *val *= 2;
178    /// }
179    ///
180    /// for (key, val) in &map {
181    ///     println!("key: {} val: {}", key, val);
182    /// }
183    /// ```
184    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
185        self.base.iter_mut()
186    }
187
188    /// An iterator visiting all keys in the order they were added.
189    /// The iterator element type is `&'a K`.
190    ///
191    /// # Examples
192    ///
193    /// ```ignore
194    /// let mut map = OrderedHashMap::new();
195    /// map.insert("a", 1);
196    /// map.insert("b", 2);
197    /// map.insert("c", 3);
198    ///
199    /// for key in map.keys() {
200    ///     println!("{}", key);
201    /// }
202    /// ```
203    pub fn keys(&self) -> std::slice::Iter<K> {
204        self.keys.iter()
205    }
206
207    /// Gets the given key's corresponding entry in the map for in-place manipulation.
208    ///
209    /// # Examples
210    ///
211    /// ```ignore
212    /// let mut letters = OrderedHashMap::new();
213    ///
214    /// for ch in "a short treatise on fungi".chars() {
215    ///     let counter = letters.entry(ch).or_insert(0);
216    ///     *counter += 1;
217    /// }
218    ///
219    /// assert_eq!(letters[&'s'], 2);
220    /// assert_eq!(letters[&'t'], 3);
221    /// assert_eq!(letters[&'u'], 1);
222    /// assert_eq!(letters.get(&'y'), None);
223    /// ```
224    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
225        if !self.base.contains_key(&key) {
226            self.keys.push(key.clone());
227        }
228        self.base.entry(key)
229    }
230}
231
232impl<K, V> Default for OrderedHashMap<K, V>
233where
234    K: Eq + Hash + Clone,
235{
236    fn default() -> Self {
237        Self::new()
238    }
239}
240
241impl<'a, K, V> IntoIterator for &'a OrderedHashMap<K, V>
242where
243    K: Eq + Hash,
244{
245    type Item = (&'a K, &'a V);
246    type IntoIter = Iter<'a, K, V>;
247
248    fn into_iter(self) -> Self::IntoIter {
249        Iter { base: &self.base, keys_iterator: self.keys.iter() }
250    }
251}
252
253impl<K, V> FromIterator<(K, V)> for OrderedHashMap<K, V>
254where
255    K: Eq + Hash + Clone,
256{
257    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
258        let mut map = OrderedHashMap::new();
259
260        for (k, v) in iter {
261            map.insert(k, v);
262        }
263
264        map
265    }
266}
267/// An iterator over the entries of a `OrderedHashMap`.
268///
269/// This `struct` is created by the `iter` method on `OrderedHashMap`.
270///
271/// # Example
272///
273/// ```ignore
274/// let mut map = OrderedHashMap::new();
275/// map.insert("a", 1);
276/// let iter = map.iter();
277/// ```
278pub struct Iter<'a, K, V> {
279    #[doc(hidden)]
280    base: &'a HashMap<K, V>,
281    keys_iterator: std::slice::Iter<'a, K>,
282}
283
284impl<'a, K, V> Iterator for Iter<'a, K, V>
285where
286    K: Eq + Hash,
287{
288    type Item = (&'a K, &'a V);
289    fn next(&mut self) -> Option<Self::Item> {
290        match self.keys_iterator.next() {
291            Some(k) => self.base.get_key_value(&k),
292            None => None,
293        }
294    }
295}
296
297/// An owning iterator over the entries of a `OrderedHashMap`.
298///
299/// This `struct` is created by the `into_iter` method on `OrderedHashMap`
300/// (provided by the `IntoIterator` trait)
301///
302/// # Example
303///
304/// ```ignore
305/// let mut map = OrderedHashMap::new();
306/// map.insert("a", 1);
307/// let iter = map.into_iter();
308/// ```
309pub struct IntoIter<K, V> {
310    #[doc(hidden)]
311    base: HashMap<K, V>,
312    keys_iterator: std::vec::IntoIter<K>,
313}
314
315impl<K, V> Iterator for IntoIter<K, V>
316where
317    K: Eq + Hash,
318{
319    type Item = (K, V);
320    fn next(&mut self) -> Option<Self::Item> {
321        match self.keys_iterator.next() {
322            Some(k) => self.base.remove_entry(&k),
323            None => None,
324        }
325    }
326}
327
328/// A mutable iterator over the entries of a `OrderedHashMap`.
329/// Note that it iterates in arbitrary order.
330pub type IterMut<'a, K, V> = hash_map::IterMut<'a, K, V>;
331
332#[cfg(test)]
333mod library_test {
334    use super::*;
335
336    #[test]
337    fn get() {
338        let mut map = OrderedHashMap::new();
339        map.insert("a", 1);
340        assert_eq!(map.get("a"), Some(&1));
341        assert_eq!(map.get("b"), None);
342    }
343}
tini/ordered_hashmap.rs

tini/
ordered_hashmap.rs
