non_empty_collections/index_map/
mod.rs

1//! Non-empty hash map implementation.
2
3#[cfg(feature = "serde_support")]
4mod deserialize;
5mod entry;
6mod into_iter;
7#[cfg(feature = "serde_support")]
8mod serialize;
9
10pub use self::entry::Entry;
11pub use self::into_iter::IntoIter;
12use indexmap::IndexMap;
13use std::collections::hash_map::RandomState;
14use std::hash::{BuildHasher, Hash};
15use std::iter::Extend;
16use std::mem::replace;
17use std::{borrow, fmt, iter};
18use {estimated_size, Error};
19
20/// A wrapper around [`::indexmap::IndexMap`] that is guaranteed to have at least one element by the
21/// Rust's type system: it consists of a **first** element and an indexed map (which could be
22/// empty) **rest** elements.
23#[derive(Clone)]
24pub struct NonEmptyIndexMap<K, V, S = RandomState> {
25    first: (K, V),
26    rest: IndexMap<K, V, S>,
27}
28
29/// A helper enum to easily obtain indexed entries.
30#[derive(Clone, Copy)]
31enum Index {
32    First,
33    Rest(usize),
34}
35
36impl<K, V> NonEmptyIndexMap<K, V, RandomState> {
37    /// Creates a map with a default hasher.
38    pub fn new(key: K, value: V) -> Self {
39        NonEmptyIndexMap {
40            first: (key, value),
41            rest: IndexMap::new(),
42        }
43    }
44
45    /// Creates a map with a given capacity.
46    pub fn with_capacity(key: K, value: V, capacity: usize) -> Self {
47        NonEmptyIndexMap {
48            first: (key, value),
49            rest: IndexMap::with_capacity(if capacity == 0 { 0 } else { capacity - 1 }),
50        }
51    }
52
53    /// Creates a map from an item (a key and a value pair) standart hash map.
54    pub fn from_item_and_iterator(key: K, value: V, i: impl IntoIterator<Item = (K, V)>) -> Self
55    where
56        K: Hash + Eq,
57    {
58        NonEmptyIndexMap {
59            first: (key, value),
60            rest: i.into_iter().collect(),
61        }
62    }
63
64    /// Creates a map from a given iterator with a default hasher.
65    pub fn from_iterator(i: impl IntoIterator<Item = (K, V)>) -> Result<Self, Error>
66    where
67        K: Hash + Eq,
68    {
69        let mut iter = i.into_iter();
70        let first = iter.next().ok_or(Error::EmptyCollection)?;
71        Ok(NonEmptyIndexMap {
72            first,
73            rest: iter.collect(),
74        })
75    }
76}
77
78impl<K, V, S1, S2> PartialEq<NonEmptyIndexMap<K, V, S1>> for NonEmptyIndexMap<K, V, S2>
79where
80    K: Hash + Eq,
81    V: Eq,
82    S1: BuildHasher,
83    S2: BuildHasher,
84{
85    fn eq(&self, other: &NonEmptyIndexMap<K, V, S1>) -> bool {
86        self.rest.len() == other.rest.len() && self.first == other.first && self.rest == other.rest
87    }
88}
89
90impl<K, V, S> Eq for NonEmptyIndexMap<K, V, S>
91where
92    K: Hash + Eq,
93    V: Eq,
94    S: BuildHasher,
95{
96}
97
98impl<K, V, S> NonEmptyIndexMap<K, V, S>
99where
100    K: Eq + Hash,
101    S: BuildHasher,
102{
103    /// Creates a map with a given hasher.
104    pub fn with_hasher(key: K, value: V, hash_builder: S) -> Self {
105        NonEmptyIndexMap {
106            first: (key, value),
107            rest: IndexMap::with_hasher(hash_builder),
108        }
109    }
110
111    /// Creates a map with a given capacity and a given hasher.
112    pub fn with_capacity_and_hasher(key: K, value: V, capacity: usize, hash_builder: S) -> Self {
113        NonEmptyIndexMap {
114            first: (key, value),
115            rest: IndexMap::with_capacity_and_hasher(
116                if capacity == 0 { 0 } else { capacity - 1 },
117                hash_builder,
118            ),
119        }
120    }
121
122    /// Iterates over key-value pairs of the map in an immutable way.
123    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
124        iter::once((&self.first.0, &self.first.1)).chain(self.rest.iter())
125    }
126
127    /// Iterates over key-value pairs of the map in a mutable way.
128    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
129        iter::once((&self.first.0, &mut self.first.1)).chain(self.rest.iter_mut())
130    }
131
132    /// Creates a map from a given iterator with a given hasher.
133    pub fn from_iter_with_hasher(
134        i: impl IntoIterator<Item = (K, V)>,
135        hasher: S,
136    ) -> Result<Self, Error> {
137        let mut iter = i.into_iter();
138        let first = iter.next().ok_or(Error::EmptyCollection)?;
139        let mut rest = match estimated_size(&iter) {
140            None => IndexMap::with_hasher(hasher),
141            Some(len) => IndexMap::with_capacity_and_hasher(len, hasher),
142        };
143        rest.extend(iter);
144        Ok(NonEmptyIndexMap { first, rest })
145    }
146
147    /// Gets a value associated with a given key, if any.
148    pub fn get<Q>(&self, key: &Q) -> Option<&V>
149    where
150        K: borrow::Borrow<Q>,
151        Q: Eq + Hash + ?Sized,
152    {
153        if self.first.0.borrow() == key {
154            Some(&self.first.1)
155        } else {
156            self.rest.get(key)
157        }
158    }
159
160    /// Checks whether a given key exists in the map.
161    pub fn contains<Q>(&self, key: &Q) -> bool
162    where
163        K: borrow::Borrow<Q>,
164        Q: Eq + Hash + ?Sized,
165    {
166        if self.first.0.borrow() == key {
167            true
168        } else {
169            self.rest.contains_key(key)
170        }
171    }
172
173    /// Gets a value associated with a given key, if any.
174    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
175    where
176        K: borrow::Borrow<Q>,
177        Q: Eq + Hash + ?Sized,
178    {
179        if self.first.0.borrow() == key {
180            Some(&mut self.first.1)
181        } else {
182            self.rest.get_mut(key)
183        }
184    }
185
186    /// Removes and returns an element associated with a given key, if any.
187    ///
188    /// An attempt to remove the last element will cause an [`Error`] to be returned.
189    pub fn remove_entry<Q>(&mut self, key: &Q) -> Result<Option<(K, V)>, Error>
190    where
191        K: borrow::Borrow<Q>,
192        Q: Eq + Hash + ?Sized,
193    {
194        if self.first.0.borrow() == key {
195            let intermediate_element = self.rest.pop().ok_or(Error::EmptyCollection)?;
196            Ok(Some(replace(&mut self.first, intermediate_element)))
197        } else {
198            Ok(self
199                .rest
200                .swap_remove_full(key)
201                .map(|(_index, key, value)| (key, value)))
202        }
203    }
204
205    /// Removes and element associated with a given key and return its value, if any.
206    ///
207    /// An attempt to remove the last element will cause an [`Error`] to be returned.
208    pub fn remove<Q>(&mut self, key: &Q) -> Result<Option<V>, Error>
209    where
210        K: borrow::Borrow<Q>,
211        Q: Eq + Hash + ?Sized,
212    {
213        self.remove_entry(key).map(|x| x.map(|(_key, value)| value))
214    }
215
216    /// Inserts a key-value pair into the map. If the map have already had an element associated
217    /// with a given key, the associated value is updated and the old one is returned.
218    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
219        if self.first.0 == key {
220            Some(replace(&mut self.first.1, value))
221        } else {
222            self.rest.insert(key, value)
223        }
224    }
225
226    /// Returns the number of elements in the map.
227    pub fn len(&self) -> usize {
228        self.rest.len() + 1
229    }
230
231    /// Checks whether or not the map is empty.
232    ///
233    /// As one would expect it always evaluates to `false` :)
234    ///
235    /// ```
236    /// # extern crate non_empty_collections;
237    /// # use non_empty_collections::NonEmptyIndexMap;
238    /// # fn main() {
239    /// assert!(!NonEmptyIndexMap::new("key", "value").is_empty());
240    /// # }
241    /// ```
242    pub fn is_empty(&self) -> bool {
243        false
244    }
245
246    /// Returns an entry that corresponds to a given key.
247    pub fn entry(&mut self, key: K) -> Entry<K, V, S> {
248        match self.get_index(&key) {
249            Some(index) => Entry::Occupied(entry::Occupied {
250                key,
251                index,
252                map: self,
253            }),
254            None => Entry::Vacant(entry::Vacant { key, map: self }),
255        }
256    }
257
258    fn get_entry(&self, index: Index) -> &V {
259        match index {
260            Index::First => &self.first.1,
261            Index::Rest(idx) => {
262                self.rest
263                    .get_index(idx)
264                    .expect("The entry exists for sure")
265                    .1
266            }
267        }
268    }
269
270    fn get_index<Q>(&mut self, key: &Q) -> Option<Index>
271    where
272        K: borrow::Borrow<Q>,
273        Q: Eq + Hash + ?Sized,
274    {
275        if self.first.0.borrow() == key {
276            Some(Index::First)
277        } else {
278            self.rest
279                .get_full(key)
280                .map(|(index, _, _)| Index::Rest(index))
281        }
282    }
283
284    fn get_entry_mut(&mut self, index: Index) -> &mut V {
285        match index {
286            Index::First => &mut self.first.1,
287            Index::Rest(idx) => {
288                self.rest
289                    .get_index_mut(idx)
290                    .expect("The entry exists for sure")
291                    .1
292            }
293        }
294    }
295
296    /// Gets an immutable reference to the **firs** element (only the *value*).
297    pub fn get_first(&self) -> (&K, &V) {
298        (&self.first.0, &self.first.1)
299    }
300
301    /// Gets a mutable reference to the **firs** element (only the *value*).
302    pub fn get_first_mut(&mut self) -> (&mut K, &mut V) {
303        (&mut self.first.0, &mut self.first.1)
304    }
305
306    /// Gets an immutable reference to the **rest** indexed map of elements.
307    pub fn get_rest(&self) -> &IndexMap<K, V, S> {
308        &self.rest
309    }
310
311    /// Gets a mutable reference to the **rest** indexed map of elements.
312    pub fn get_rest_mut(&mut self) -> &mut IndexMap<K, V, S> {
313        &mut self.rest
314    }
315
316    /// Attempts to remove the first element. Will fail if it is the only one element in the map.
317    pub fn remove_first(&mut self) -> Result<(), Error> {
318        let (key, value) = self.rest.pop().ok_or(Error::EmptyCollection)?;
319        self.first = (key, value);
320        Ok(())
321    }
322
323    /// Scans the collection and keeps only the items on which the provided `keep` function
324    /// returns `true`. Will fail if in the end only one element will remain.
325    pub fn retain<F>(&mut self, mut keep: F) -> Result<(), Error>
326    where
327        F: FnMut(&K, &mut V) -> bool,
328    {
329        while !(keep)(&self.first.0, &mut self.first.1) {
330            self.remove_first()?;
331        }
332        self.rest.retain(keep);
333        Ok(())
334    }
335}
336
337impl<K: Eq + Hash, V, S: BuildHasher> Into<IndexMap<K, V, S>> for NonEmptyIndexMap<K, V, S> {
338    fn into(self) -> IndexMap<K, V, S> {
339        let mut map = self.rest;
340        map.insert(self.first.0, self.first.1);
341        map
342    }
343}
344
345impl<K, V, S> fmt::Debug for NonEmptyIndexMap<K, V, S>
346where
347    K: Eq + Hash + fmt::Debug,
348    V: fmt::Debug,
349    S: BuildHasher,
350{
351    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
352        f.debug_map().entries(self.iter()).finish()
353    }
354}
355
356impl<K, V, S> Extend<(K, V)> for NonEmptyIndexMap<K, V, S>
357where
358    K: Eq + Hash,
359    S: BuildHasher,
360{
361    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
362        self.rest.extend(iter)
363    }
364}
365
366impl<K, V, S> IntoIterator for NonEmptyIndexMap<K, V, S>
367where
368    K: Eq + Hash,
369    S: BuildHasher,
370{
371    type Item = (K, V);
372    type IntoIter = IntoIter<K, V>;
373
374    fn into_iter(self) -> Self::IntoIter {
375        IntoIter {
376            iter: iter::once(self.first).chain(self.rest),
377        }
378    }
379}
380
381#[cfg(test)]
382mod tests {
383    use super::*;
384
385    #[test]
386    fn insert_and_get() {
387        let mut map = NonEmptyIndexMap::new(0, 1);
388        assert_eq!(Some(&1), map.get(&0));
389        assert_eq!(None, map.get(&10));
390
391        assert_eq!(None, map.insert(10, 20));
392        assert_eq!(Some(&20), map.get(&10));
393
394        // Key `10` already exists in the map.
395        assert_eq!(Some(20), map.insert(10, 40));
396        assert_eq!(Some(&40), map.get(&10));
397    }
398
399    #[test]
400    fn insert_and_contains() {
401        let mut map = NonEmptyIndexMap::new(0, 1);
402        assert!(map.contains(&0));
403        assert!(!map.contains(&10));
404
405        assert_eq!(None, map.insert(10, 20));
406        assert!(map.contains(&10));
407
408        // Key `10` already exists in the map.
409        assert_eq!(Some(20), map.insert(10, 40));
410        assert!(map.contains(&10));
411    }
412
413    #[test]
414    fn remove_entry() {
415        let mut map = NonEmptyIndexMap::from_iterator(vec![(1, 2), (3, 4), (5, 6)]).unwrap();
416        assert_eq!(Ok(Some((1, 2))), map.remove_entry(&1));
417        assert_eq!(None, map.get(&1));
418
419        assert_eq!(Ok(Some((3, 4))), map.remove_entry(&3));
420        assert_eq!(None, map.get(&3));
421
422        // Entry `&3` doesn't exist anymore.
423        assert_eq!(Ok(None), map.remove_entry(&3));
424
425        // Trying to remove the last element is an error.
426        assert_eq!(Err(Error::EmptyCollection), map.remove_entry(&5));
427    }
428
429    #[test]
430    fn remove_first() {
431        let mut map = NonEmptyIndexMap::from_iterator(vec![(1, 2), (3, 4), (5, 6)]).unwrap();
432        assert_eq!(Ok(()), map.remove_first());
433        assert_eq!(Ok(()), map.remove_first());
434        assert_eq!(Err(Error::EmptyCollection), map.remove_first());
435    }
436
437    #[test]
438    fn into_std_hashmap() {
439        let mut map = NonEmptyIndexMap::new(1, 2);
440        assert_eq!(None, map.insert(3, 4));
441        assert_eq!(None, map.insert(5, 6));
442        assert_eq!(None, map.insert(7, 8));
443
444        let std_map: IndexMap<_, _> = map.into();
445        assert_eq!(4, std_map.len());
446        assert_eq!(Some(&2), std_map.get(&1));
447        assert_eq!(Some(&4), std_map.get(&3));
448        assert_eq!(Some(&6), std_map.get(&5));
449        assert_eq!(Some(&8), std_map.get(&7));
450    }
451
452    #[test]
453    fn from_item_and_iterator() {
454        let original = vec![(1u8, 2u8), (3, 4), (5, 6)];
455        let converted = NonEmptyIndexMap::from_item_and_iterator(7, 8, original);
456        let std_map: IndexMap<_, _> = converted.into();
457        assert_eq!(4, std_map.len());
458        assert_eq!(Some(&2), std_map.get(&1));
459        assert_eq!(Some(&4), std_map.get(&3));
460        assert_eq!(Some(&6), std_map.get(&5));
461        assert_eq!(Some(&8), std_map.get(&7));
462    }
463
464    #[test]
465    fn into_iter() {
466        let original: IndexMap<_, _> = vec![(1u8, 2u8), (3, 4), (10, 12)].into_iter().collect();
467        let map = NonEmptyIndexMap::from_iterator(original.clone())
468            .map_err(|_| ())
469            .unwrap();
470        let converted: IndexMap<_, _> = map.into_iter().collect();
471        assert_eq!(converted, original);
472    }
473
474    #[test]
475    fn len() {
476        let map = NonEmptyIndexMap::new(1, 2);
477        assert_eq!(1, map.len());
478
479        let map = NonEmptyIndexMap::from_iterator(vec![(1, 2), (3, 4), (5, 6)]).unwrap();
480        assert_eq!(3, map.len());
481    }
482
483    #[test]
484    fn get_unsized() {
485        let map = NonEmptyIndexMap::new("Lol".to_string(), "wut");
486        assert_eq!(Some(&"wut"), map.get("Lol"));
487    }
488
489    #[test]
490    fn retain() {
491        let original_map =
492            NonEmptyIndexMap::from_iterator(vec![(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]).unwrap();
493        let mut map = original_map.clone();
494        assert_eq!(Ok(()), map.retain(|key, value| *key < 2 && *value < 'b'));
495        assert_eq!(1, map.len());
496        assert_eq!(Some(&'a'), map.get(&1));
497        assert_eq!(Err(Error::EmptyCollection), map.retain(|_, _| false));
498
499        let mut map = original_map.clone();
500        assert_eq!(Ok(()), map.retain(|key, value| *key > 3 && *value > 'c'));
501        assert_eq!(1, map.len());
502        assert_eq!(Some(&'d'), map.get(&4));
503        assert_eq!(Err(Error::EmptyCollection), map.retain(|_, _| false));
504    }
505
506    #[test]
507    fn comparison() {
508        let original_map =
509            NonEmptyIndexMap::from_iterator(vec![(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]).unwrap();
510        assert_eq!(original_map, original_map);
511        for (key, _) in original_map.iter() {
512            let mut modified_map = original_map.clone();
513            *modified_map.get_mut(&key).unwrap() = 'z';
514            assert_ne!(modified_map, original_map);
515        }
516    }
517}
non_empty_collections/index_map/mod.rs

non_empty_collections/index_map/
mod.rs
