nonempty_collections/
btree_map.rs

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

nonempty_collections/
btree_map.rs
