nonempty_collections/
map.rs

1//! Non-empty [`HashMap`]s.
2
3use core::fmt;
4use std::borrow::Borrow;
5use std::collections::HashMap;
6use std::hash::BuildHasher;
7use std::hash::Hash;
8use std::num::NonZeroUsize;
9
10#[cfg(feature = "serde")]
11use serde::Deserialize;
12#[cfg(feature = "serde")]
13use serde::Serialize;
14
15use crate::FromNonEmptyIterator;
16use crate::IntoIteratorExt;
17use crate::IntoNonEmptyIterator;
18use crate::NonEmptyIterator;
19
20/// Like the [`crate::nev!`] macro, but for Maps. A nice short-hand for
21/// constructing [`NEMap`] values.
22///
23/// ```
24/// use nonempty_collections::nem;
25///
26/// let m = nem! {"elves" => 3000, "orcs" => 10000};
27/// assert_eq!(2, m.len().get());
28/// ```
29#[macro_export]
30macro_rules! nem {
31    ($hk:expr => $hv:expr, $( $xk:expr => $xv:expr ),* $(,)?) => {{
32        let mut map = $crate::NEMap::new($hk, $hv);
33        $( map.insert($xk, $xv); )*
34        map
35    }};
36    ($hk:expr => $hv:expr) => {
37        $crate::NEMap::new($hk, $hv)
38    }
39}
40
41/// A non-empty, growable `HashMap`.
42///
43/// ```
44/// use nonempty_collections::nem;
45///
46/// let m = nem!["elves" => 3000, "orcs" => 10000];
47/// assert_eq!(2, m.len().get());
48/// ```
49#[allow(clippy::unsafe_derive_deserialize)]
50#[cfg_attr(
51    feature = "serde",
52    derive(Deserialize, Serialize),
53    serde(bound(
54        serialize = "K: Eq + Hash + Clone + Serialize, V: Clone + Serialize, S: Clone + BuildHasher",
55        deserialize = "K: Eq + Hash + Clone + Deserialize<'de>, V: Deserialize<'de>, S: Default + BuildHasher"
56    )),
57    serde(into = "HashMap<K, V, S>", try_from = "HashMap<K, V, S>")
58)]
59#[derive(Clone)]
60pub struct NEMap<K, V, S = std::collections::hash_map::RandomState> {
61    inner: HashMap<K, V, S>,
62}
63
64impl<K, V> NEMap<K, V>
65where
66    K: Eq + Hash,
67{
68    /// Creates a new `NEMap` with a single element.
69    #[must_use]
70    pub fn new(k: K, v: V) -> NEMap<K, V> {
71        let mut inner = HashMap::new();
72        inner.insert(k, v);
73        NEMap { inner }
74    }
75
76    /// Creates a new `NEMap` with a single element and specified capacity.
77    /// ```
78    /// use std::num::*;
79    ///
80    /// use nonempty_collections::*;
81    /// let map = NEMap::with_capacity(NonZeroUsize::MIN, 1, 1);
82    /// assert_eq!(nem! { 1 => 1 }, map);
83    /// assert!(map.capacity().get() >= 1);
84    /// ```
85    #[must_use]
86    pub fn with_capacity(capacity: NonZeroUsize, k: K, v: V) -> NEMap<K, V> {
87        let mut inner = HashMap::with_capacity(capacity.get());
88        inner.insert(k, v);
89        NEMap { inner }
90    }
91}
92
93impl<K, V, S> NEMap<K, V, S> {
94    /// Attempt a conversion from [`HashMap`], consuming the given `HashMap`.
95    /// Will return `None` if the `HashMap` is empty.
96    ///
97    /// ```
98    /// use std::collections::*;
99    ///
100    /// use nonempty_collections::*;
101    ///
102    /// let mut map = HashMap::new();
103    /// map.extend([("a", 1), ("b", 2)]);
104    /// assert_eq!(Some(nem! {"a" => 1, "b" => 2}), NEMap::try_from_map(map));
105    /// let map: HashMap<(), ()> = HashMap::new();
106    /// assert_eq!(None, NEMap::try_from_map(map));
107    /// ```
108    #[must_use]
109    pub fn try_from_map(map: HashMap<K, V, S>) -> Option<Self> {
110        if map.is_empty() {
111            None
112        } else {
113            Some(Self { inner: map })
114        }
115    }
116
117    /// Returns the number of elements the map can hold without reallocating.
118    #[must_use]
119    pub fn capacity(&self) -> NonZeroUsize {
120        unsafe { NonZeroUsize::new_unchecked(self.inner.capacity()) }
121    }
122
123    /// Returns a reference to the map's `BuildHasher`.
124    #[must_use]
125    pub fn hasher(&self) -> &S {
126        self.inner.hasher()
127    }
128
129    /// Returns a regular iterator over the values in this non-empty map.
130    ///
131    /// For a `NonEmptyIterator` see `Self::nonempty_iter()`.
132    pub fn iter(&self) -> std::collections::hash_map::Iter<'_, K, V> {
133        self.inner.iter()
134    }
135
136    /// An iterator visiting all elements in arbitrary order. The iterator
137    /// element type is `(&'a K, &'a V)`.
138    pub fn nonempty_iter(&self) -> Iter<'_, K, V> {
139        Iter {
140            iter: self.inner.iter(),
141        }
142    }
143
144    /// An iterator visiting all elements in arbitrary order. The iterator
145    /// element type is `(&'a K, &'a mut V)`.
146    ///
147    /// # Panics
148    ///
149    /// If you manually advance this iterator until empty and then call `first`,
150    /// you're in for a surprise.
151    pub fn nonempty_iter_mut(&mut self) -> IterMut<'_, K, V> {
152        IterMut {
153            iter: self.inner.iter_mut(),
154        }
155    }
156
157    /// An iterator visiting all keys in arbitrary order. The iterator element
158    /// type is `&'a K`.
159    ///
160    /// ```
161    /// use nonempty_collections::*;
162    ///
163    /// let m = nem!["Valmar" => "Vanyar", "Tirion" => "Noldor", "Alqualondë" => "Teleri"];
164    /// let mut v: NEVec<_> = m.keys().collect();
165    /// v.sort();
166    /// assert_eq!(nev![&"Alqualondë", &"Tirion", &"Valmar"], v);
167    /// ```
168    pub fn keys(&self) -> Keys<'_, K, V> {
169        Keys {
170            inner: self.inner.keys(),
171        }
172    }
173
174    /// Returns the number of elements in the map. Always 1 or more.
175    ///
176    /// ```
177    /// use nonempty_collections::nem;
178    ///
179    /// let m = nem!["a" => 1, "b" => 2];
180    /// assert_eq!(2, m.len().get());
181    /// ```
182    #[must_use]
183    pub fn len(&self) -> NonZeroUsize {
184        unsafe { NonZeroUsize::new_unchecked(self.inner.len()) }
185    }
186
187    /// A `NEMap` is never empty.
188    #[deprecated(since = "0.1.0", note = "A NEMap is never empty.")]
189    #[must_use]
190    pub const fn is_empty(&self) -> bool {
191        false
192    }
193
194    /// An iterator visiting all values in arbitrary order. The iterator element
195    /// type is `&'a V`.
196    ///
197    /// ```
198    /// use nonempty_collections::*;
199    ///
200    /// let m = nem!["Valmar" => "Vanyar", "Tirion" => "Noldor", "Alqualondë" => "Teleri"];
201    /// let mut v: NEVec<_> = m.values().collect();
202    /// v.sort();
203    /// assert_eq!(nev![&"Noldor", &"Teleri", &"Vanyar"], v);
204    /// ```
205    pub fn values(&self) -> Values<'_, K, V> {
206        Values {
207            inner: self.inner.values(),
208        }
209    }
210
211    // /// An iterator visiting all values mutably in arbitrary order. The iterator
212    // /// element type is `&'a mut V`.
213    // ///
214    // /// ```
215    // /// use nonempty_collections::nem;
216    // ///
217    // /// let mut m = nem!["Valmar" => 10000, "Tirion" => 10000, "Alqualondë" =>
218    // 10000]; ///
219    // /// for v in m.values_mut() {
220    // ///     *v += 1000;
221    // /// }
222    // /// ```
223    // pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
224    //     ValuesMut {
225    //         inner: self.iter_mut(),
226    //         head_val: todo!(),
227    //     }
228    // }
229}
230
231impl<K, V, S> NEMap<K, V, S>
232where
233    K: Eq + Hash,
234    S: BuildHasher,
235{
236    /// Returns true if the map contains a value.
237    ///
238    /// ```
239    /// use nonempty_collections::nem;
240    ///
241    /// let m = nem!["Jack" => 8];
242    /// assert!(m.contains_key("Jack"));
243    /// assert!(!m.contains_key("Colin"));
244    /// ```
245    #[must_use]
246    pub fn contains_key<Q>(&self, k: &Q) -> bool
247    where
248        K: Borrow<Q>,
249        Q: Eq + Hash + ?Sized,
250    {
251        self.inner.contains_key(k)
252    }
253
254    /// Returns a reference to the value corresponding to the key.
255    ///
256    /// The key may be any borrowed form of the map's value type, but `Hash` and
257    /// `Eq` on the borrowed form must match those for the key type.
258    ///
259    /// ```
260    /// use nonempty_collections::nem;
261    ///
262    /// let m = nem!["silmarils" => 3];
263    /// assert_eq!(Some(&3), m.get("silmarils"));
264    /// assert_eq!(None, m.get("arkenstone"));
265    /// ```
266    #[must_use]
267    pub fn get<Q>(&self, k: &Q) -> Option<&V>
268    where
269        K: Borrow<Q>,
270        Q: Eq + Hash + ?Sized,
271    {
272        self.inner.get(k)
273    }
274
275    /// Returns the key-value pair corresponding to the key.
276    ///
277    /// The key may be any borrowed form of the map's value type, but `Hash` and
278    /// `Eq` on the borrowed form must match those for the key type.
279    ///
280    /// ```
281    /// use nonempty_collections::nem;
282    ///
283    /// let m = nem!["silmarils" => 3];
284    /// assert_eq!(Some((&"silmarils", &3)), m.get_key_value("silmarils"));
285    /// assert_eq!(None, m.get_key_value("arkenstone"));
286    /// ```
287    #[must_use]
288    pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
289    where
290        K: Borrow<Q>,
291        Q: Eq + Hash + ?Sized,
292    {
293        self.inner.get_key_value(k)
294    }
295
296    /// Returns a reference to the value corresponding to the key.
297    ///
298    /// The key may be any borrowed form of the map's value type, but `Hash` and
299    /// `Eq` on the borrowed form must match those for the key type.
300    ///
301    /// ```
302    /// use nonempty_collections::nem;
303    ///
304    /// let mut m = nem!["silmarils" => 3];
305    /// let mut v = m.get_mut("silmarils").unwrap();
306    ///
307    /// // And thus it came to pass that the Silmarils found their long homes:
308    /// // one in the airs of heaven, and one in the fires of the heart of the
309    /// // world, and one in the deep waters.
310    /// *v -= 3;
311    ///
312    /// assert_eq!(Some(&0), m.get("silmarils"));
313    /// ```
314    #[must_use]
315    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
316    where
317        K: Borrow<Q>,
318        Q: Eq + Hash + ?Sized,
319    {
320        self.inner.get_mut(k)
321    }
322
323    /// Insert a key-value pair into the map.
324    ///
325    /// If the map did not have this present, [`None`] is returned.
326    ///
327    /// If the map did have this key present, the value is updated, and the old
328    /// value is returned. The key is not updated, though; this matters for
329    /// types that can be `==` without being identical. See [`HashMap::insert`]
330    /// for more.
331    ///
332    /// ```
333    /// use nonempty_collections::nem;
334    ///
335    /// let mut m = nem!["Vilya" => "Elrond", "Nenya" => "Galadriel"];
336    /// assert_eq!(None, m.insert("Narya", "Cirdan"));
337    ///
338    /// // The Ring of Fire was given to Gandalf upon his arrival in Middle Earth.
339    /// assert_eq!(Some("Cirdan"), m.insert("Narya", "Gandalf"));
340    /// ```
341    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
342        self.inner.insert(k, v)
343    }
344
345    /// Shrinks the capacity of the map as much as possible. It will drop down
346    /// as much as possible while maintaining the internal rules and possibly
347    /// leaving some space in accordance with the resize policy.
348    pub fn shrink_to_fit(&mut self) {
349        self.inner.shrink_to_fit();
350    }
351
352    /// See [`HashMap::with_capacity_and_hasher`].
353    #[must_use]
354    pub fn with_capacity_and_hasher(
355        capacity: NonZeroUsize,
356        hasher: S,
357        k: K,
358        v: V,
359    ) -> NEMap<K, V, S> {
360        let mut inner = HashMap::with_capacity_and_hasher(capacity.get(), hasher);
361        inner.insert(k, v);
362        NEMap { inner }
363    }
364
365    /// See [`HashMap::with_hasher`].
366    #[must_use]
367    pub fn with_hasher(hasher: S, k: K, v: V) -> NEMap<K, V, S> {
368        let mut inner = HashMap::with_hasher(hasher);
369        inner.insert(k, v);
370        NEMap { inner }
371    }
372}
373
374impl<K, V, S> PartialEq for NEMap<K, V, S>
375where
376    K: Eq + Hash,
377    V: Eq,
378    S: BuildHasher,
379{
380    /// This is an `O(n)` comparison of each key/value pair, one by one.
381    /// Short-circuits if any comparison fails.
382    ///
383    /// ```
384    /// use nonempty_collections::*;
385    ///
386    /// let m0 = nem!['a' => 1, 'b' => 2];
387    /// let m1 = nem!['b' => 2, 'a' => 1];
388    /// assert_eq!(m0, m1);
389    /// ```
390    fn eq(&self, other: &Self) -> bool {
391        self.inner.eq(&other.inner)
392    }
393}
394
395impl<K, V, S> Eq for NEMap<K, V, S>
396where
397    K: Eq + Hash,
398    V: Eq,
399    S: BuildHasher,
400{
401}
402
403impl<K, V, S> From<NEMap<K, V, S>> for HashMap<K, V, S>
404where
405    K: Eq + Hash,
406    S: BuildHasher,
407{
408    /// ```
409    /// use nonempty_collections::nem;
410    /// use std::collections::HashMap;
411    ///
412    /// let m: HashMap<&str, usize> = nem!["population" => 1000].into();
413    /// assert!(m.contains_key("population"));
414    /// ```
415    fn from(m: NEMap<K, V, S>) -> Self {
416        m.inner
417    }
418}
419
420impl<K, V, S> TryFrom<HashMap<K, V, S>> for NEMap<K, V, S>
421where
422    K: Eq + Hash,
423    S: BuildHasher + Default,
424{
425    type Error = crate::Error;
426
427    fn try_from(map: HashMap<K, V, S>) -> Result<Self, Self::Error> {
428        map.try_into_nonempty_iter()
429            .map(NonEmptyIterator::collect)
430            .ok_or(crate::Error::Empty)
431    }
432}
433
434impl<K, V, S> IntoNonEmptyIterator for NEMap<K, V, S> {
435    type IntoNEIter = IntoIter<K, V>;
436
437    fn into_nonempty_iter(self) -> Self::IntoNEIter {
438        IntoIter {
439            iter: self.inner.into_iter(),
440        }
441    }
442}
443
444impl<'a, K, V, S> IntoNonEmptyIterator for &'a NEMap<K, V, S> {
445    type IntoNEIter = Iter<'a, K, V>;
446
447    fn into_nonempty_iter(self) -> Self::IntoNEIter {
448        self.nonempty_iter()
449    }
450}
451
452impl<K, V, S> IntoIterator for NEMap<K, V, S> {
453    type Item = (K, V);
454
455    type IntoIter = std::collections::hash_map::IntoIter<K, V>;
456
457    fn into_iter(self) -> Self::IntoIter {
458        self.inner.into_iter()
459    }
460}
461
462impl<'a, K, V, S> IntoIterator for &'a NEMap<K, V, S> {
463    type Item = (&'a K, &'a V);
464
465    type IntoIter = std::collections::hash_map::Iter<'a, K, V>;
466
467    fn into_iter(self) -> Self::IntoIter {
468        self.iter()
469    }
470}
471
472/// ```
473/// use nonempty_collections::*;
474///
475/// let v = nev![('a', 1), ('b', 2), ('c', 3), ('a', 4)];
476/// let m0: NEMap<_, _> = v.into_nonempty_iter().collect();
477/// let m1: NEMap<_, _> = nem!['a' => 4, 'b' => 2, 'c' => 3];
478/// assert_eq!(m0, m1);
479/// ```
480impl<K, V, S> FromNonEmptyIterator<(K, V)> for NEMap<K, V, S>
481where
482    K: Eq + Hash,
483    S: BuildHasher + Default,
484{
485    fn from_nonempty_iter<I>(iter: I) -> Self
486    where
487        I: IntoNonEmptyIterator<Item = (K, V)>,
488    {
489        NEMap {
490            inner: iter.into_nonempty_iter().into_iter().collect(),
491        }
492    }
493}
494
495/// A non-empty iterator over the entries of an [`NEMap`].
496#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
497pub struct Iter<'a, K: 'a, V: 'a> {
498    iter: std::collections::hash_map::Iter<'a, K, V>,
499}
500
501impl<K, V> NonEmptyIterator for Iter<'_, K, V> {}
502
503impl<'a, K, V> IntoIterator for Iter<'a, K, V> {
504    type Item = (&'a K, &'a V);
505
506    type IntoIter = std::collections::hash_map::Iter<'a, K, V>;
507
508    fn into_iter(self) -> Self::IntoIter {
509        self.iter
510    }
511}
512
513impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
514    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
515        self.iter.fmt(f)
516    }
517}
518
519/// A non-empty iterator over mutable values of an [`NEMap`].
520#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
521pub struct IterMut<'a, K: 'a, V: 'a> {
522    iter: std::collections::hash_map::IterMut<'a, K, V>,
523}
524
525impl<K, V> NonEmptyIterator for IterMut<'_, K, V> {}
526
527impl<'a, K, V> IntoIterator for IterMut<'a, K, V> {
528    type Item = (&'a K, &'a mut V);
529
530    type IntoIter = std::collections::hash_map::IterMut<'a, K, V>;
531
532    fn into_iter(self) -> Self::IntoIter {
533        self.iter
534    }
535}
536
537impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
538    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
539        self.iter.fmt(f)
540    }
541}
542
543/// A non-empty iterator over the entries of an [`NEMap`].
544pub struct IntoIter<K, V> {
545    iter: std::collections::hash_map::IntoIter<K, V>,
546}
547
548impl<K, V> NonEmptyIterator for IntoIter<K, V> {}
549
550impl<K, V> IntoIterator for IntoIter<K, V> {
551    type Item = (K, V);
552
553    type IntoIter = std::collections::hash_map::IntoIter<K, V>;
554
555    fn into_iter(self) -> Self::IntoIter {
556        self.iter
557    }
558}
559
560impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
561    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
562        self.iter.fmt(f)
563    }
564}
565
566/// A non-empty iterator over the keys of an [`NEMap`].
567#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
568pub struct Keys<'a, K: 'a, V: 'a> {
569    inner: std::collections::hash_map::Keys<'a, K, V>,
570}
571
572impl<K, V> NonEmptyIterator for Keys<'_, K, V> {}
573
574impl<'a, K, V> IntoIterator for Keys<'a, K, V> {
575    type Item = &'a K;
576
577    type IntoIter = std::collections::hash_map::Keys<'a, K, V>;
578
579    fn into_iter(self) -> Self::IntoIter {
580        self.inner
581    }
582}
583
584impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Keys<'_, K, V> {
585    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
586        self.inner.fmt(f)
587    }
588}
589
590/// A non-empty iterator over the values of an [`NEMap`].
591#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
592pub struct Values<'a, K: 'a, V: 'a> {
593    inner: std::collections::hash_map::Values<'a, K, V>,
594}
595
596impl<K, V> NonEmptyIterator for Values<'_, K, V> {}
597
598impl<'a, K, V> IntoIterator for Values<'a, K, V> {
599    type Item = &'a V;
600
601    type IntoIter = std::collections::hash_map::Values<'a, K, V>;
602
603    fn into_iter(self) -> Self::IntoIter {
604        self.inner
605    }
606}
607
608impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
609    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
610        self.inner.fmt(f)
611    }
612}
613
614impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for NEMap<K, V, S> {
615    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
616        self.inner.fmt(f)
617    }
618}
619
620// /// A non-empty iterator over mutable values of an [`NEMap`].
621// pub struct ValuesMut<'a, K: 'a, V: 'a> {
622//     inner: IterMut<'a, K, V>,
623// }
624
625// impl<'a, K, V> NonEmptyIterator for ValuesMut<'a, K, V> {
626//     type Item = &'a mut V;
627
628//     type Iter = Skip<Chain<Once<&'a mut V>,
629// std::collections::hash_map::IterMut<'a, K, V>>>;
630
631//     fn first(self) -> (Self::Item, Self::Iter) {
632//         (self.head_val, self.inner.skip(1))
633//     }
634
635//     fn next(&mut self) -> Option<Self::Item> {
636//         self.inner.next().map(|(_, v)| v)
637//     }
638// }
639
640#[cfg(test)]
641mod test {
642    use std::num::NonZeroUsize;
643
644    use maplit::hashmap;
645
646    use crate::nem;
647
648    struct Foo {
649        user: String,
650    }
651
652    #[test]
653    fn debug_impl() {
654        let expected = format!("{:?}", hashmap! {0 => 10});
655        let actual = format!("{:?}", nem! {0 => 10});
656        assert_eq!(expected, actual);
657    }
658
659    #[test]
660    fn macro_usage() {
661        let a = Foo {
662            user: "a".to_string(),
663        };
664        let b = Foo {
665            user: "b".to_string(),
666        };
667
668        let map = nem![1 => a, 2 => b];
669        assert_eq!("a", map.get(&1).unwrap().user);
670        assert_eq!("b", map.get(&2).unwrap().user);
671    }
672
673    #[test]
674    fn macro_length() {
675        let map = nem![1 => 'a', 2 => 'b', 1 => 'c'];
676        assert_eq!(unsafe { NonZeroUsize::new_unchecked(2) }, map.len());
677        assert_eq!('c', *map.get(&1).unwrap());
678        assert_eq!('b', *map.get(&2).unwrap());
679    }
680}
681
682#[cfg(feature = "serde")]
683#[cfg(test)]
684mod serde_tests {
685    use std::collections::HashMap;
686
687    use crate::nem;
688    use crate::NEMap;
689
690    #[test]
691    fn json() {
692        let map0 = nem![1 => 'a', 2 => 'b', 1 => 'c'];
693        let j = serde_json::to_string(&map0).unwrap();
694        let map1 = serde_json::from_str(&j).unwrap();
695        assert_eq!(map0, map1);
696
697        let empty: HashMap<usize, char> = HashMap::new();
698        let j = serde_json::to_string(&empty).unwrap();
699        let bad = serde_json::from_str::<NEMap<usize, char>>(&j);
700        assert!(bad.is_err());
701    }
702}
nonempty_collections/map.rs

nonempty_collections/
map.rs
