nonempty_collections/
index_set.rs

1//! Non-empty IndexSets.
2
3use core::fmt;
4use indexmap::IndexSet;
5use std::borrow::Borrow;
6use std::hash::BuildHasher;
7use std::hash::Hash;
8use std::num::NonZeroUsize;
9
10use crate::iter::NonEmptyIterator;
11use crate::FromNonEmptyIterator;
12use crate::IntoIteratorExt;
13use crate::IntoNonEmptyIterator;
14use crate::Singleton;
15
16/// Like the [`crate::nes!`] macro, but for IndexSets.
17///
18/// ```
19/// use nonempty_collections::neis;
20///
21/// let s = neis![1, 2, 2, 3,];
22/// assert_eq!(3, s.len().get());
23/// ```
24#[macro_export]
25macro_rules! neis {
26    ($h:expr, $( $x:expr ),* $(,)?) => {{
27        let mut set = $crate::NEIndexSet::new($h);
28        $( set.insert($x); )*
29        set
30    }};
31    ($h:expr) => {
32        $crate::NEIndexSet::new($h)
33    }
34}
35
36/// A non-empty, growable `IndexSet`.
37///
38/// # Construction and Access
39///
40/// The [`neis`] macro is the simplest way to construct an `NEIndexSet`:
41///
42/// ```
43/// use nonempty_collections::*;
44///
45/// let s = neis![1, 1, 2, 2, 3, 3, 4, 4];
46/// let mut v: NEVec<_> = s.nonempty_iter().collect();
47/// v.sort();
48/// assert_eq!(nev![&1, &2, &3, &4], v);
49/// ```
50///
51///
52/// ```
53/// use nonempty_collections::neis;
54///
55/// let s = neis!["Fëanor", "Fingolfin", "Finarfin"];
56/// assert!(s.contains(&"Fëanor"));
57/// ```
58///
59/// # Conversion
60///
61/// If you have a [`IndexSet`] but want an `NEIndexSet`, try [`NEIndexSet::try_from_set`].
62/// Naturally, this might not succeed.
63///
64/// If you have an `NEIndexSet` but want a `IndexSet`, try their corresponding
65/// [`From`] instance. This will always succeed.
66///
67/// ```
68/// use indexmap::set::IndexSet;
69///
70/// use nonempty_collections::neis;
71///
72/// let n0 = neis![1, 2, 3];
73/// let s0 = IndexSet::from(n0);
74///
75/// // Or just use `Into`.
76/// let n1 = neis![1, 2, 3];
77/// let s1: IndexSet<_> = n1.into();
78/// ```
79///
80/// # API Differences with [`IndexSet`]
81///
82/// Note that the following methods aren't implemented for `NEIndexSet`:
83///
84/// - `clear`
85/// - `drain`
86/// - `drain_filter`
87/// - `remove`
88/// - `retain`
89/// - `take`
90///
91/// As these methods are all "mutate-in-place" style and are difficult to
92/// reconcile with the non-emptiness guarantee.
93#[derive(Clone)]
94pub struct NEIndexSet<T, S = std::collections::hash_map::RandomState> {
95    inner: IndexSet<T, S>,
96}
97
98impl<T, S> NEIndexSet<T, S> {
99    /// Returns the number of elements the set can hold without reallocating.
100    #[must_use]
101    pub fn capacity(&self) -> NonZeroUsize {
102        unsafe { NonZeroUsize::new_unchecked(self.inner.capacity()) }
103    }
104
105    /// Returns a reference to the set's `BuildHasher`.
106    #[must_use]
107    pub fn hasher(&self) -> &S {
108        self.inner.hasher()
109    }
110
111    /// Returns a regular iterator over the values in this non-empty set.
112    ///
113    /// For a `NonEmptyIterator` see `Self::nonempty_iter()`.
114    pub fn iter(&self) -> indexmap::set::Iter<'_, T> {
115        self.inner.iter()
116    }
117
118    /// An iterator visiting all elements in arbitrary order.
119    pub fn nonempty_iter(&self) -> Iter<'_, T> {
120        Iter {
121            iter: self.inner.iter(),
122        }
123    }
124
125    /// Returns the number of elements in the set. Always 1 or more.
126    ///
127    /// ```
128    /// use nonempty_collections::neis;
129    ///
130    /// let s = neis![1, 2, 3];
131    /// assert_eq!(3, s.len().get());
132    /// ```
133    #[must_use]
134    pub fn len(&self) -> NonZeroUsize {
135        unsafe { NonZeroUsize::new_unchecked(self.inner.len()) }
136    }
137
138    /// A `NEIndexSet` is never empty.
139    #[deprecated(since = "0.1.0", note = "A NEIndexSet is never empty.")]
140    #[must_use]
141    pub const fn is_empty(&self) -> bool {
142        false
143    }
144}
145
146impl<T> NEIndexSet<T>
147where
148    T: Eq + Hash,
149{
150    /// Creates a new `NEIndexSet` with a single element.
151    #[must_use]
152    pub fn new(value: T) -> Self {
153        let mut inner = IndexSet::new();
154        inner.insert(value);
155        Self { inner }
156    }
157
158    /// Creates a new `NEIndexSet` with a single element and specified capacity.
159    ///
160    /// ```
161    /// use std::hash::RandomState;
162    /// use std::num::NonZeroUsize;
163    ///
164    /// use nonempty_collections::*;
165    /// let set = NEIndexSet::with_capacity(NonZeroUsize::MIN, "hello");
166    /// assert_eq!(neis! {"hello"}, set);
167    /// assert!(set.capacity().get() >= 1);
168    /// ```
169    #[must_use]
170    pub fn with_capacity(capacity: NonZeroUsize, value: T) -> NEIndexSet<T> {
171        let mut inner = IndexSet::with_capacity(capacity.get());
172        inner.insert(value);
173        NEIndexSet { inner }
174    }
175}
176
177impl<T, S> NEIndexSet<T, S>
178where
179    T: Eq + Hash,
180    S: BuildHasher,
181{
182    /// Attempt a conversion from a [`IndexSet`], consuming the given `IndexSet`.
183    /// Will return `None` if the `IndexSet` is empty.
184    ///
185    /// ```
186    /// use indexmap::set::IndexSet;
187    ///
188    /// use nonempty_collections::neis;
189    /// use nonempty_collections::NEIndexSet;
190    ///
191    /// let mut s = IndexSet::new();
192    /// s.extend([1, 2, 3]);
193    ///
194    /// let n = NEIndexSet::try_from_set(s);
195    /// assert_eq!(Some(neis![1, 2, 3]), n);
196    /// let s: IndexSet<()> = IndexSet::new();
197    /// assert_eq!(None, NEIndexSet::try_from_set(s));
198    /// ```
199    #[must_use]
200    pub fn try_from_set(set: IndexSet<T, S>) -> Option<NEIndexSet<T, S>> {
201        if set.is_empty() {
202            None
203        } else {
204            Some(NEIndexSet { inner: set })
205        }
206    }
207
208    /// Returns true if the set contains a value.
209    ///
210    /// ```
211    /// use nonempty_collections::neis;
212    ///
213    /// let s = neis![1, 2, 3];
214    /// assert!(s.contains(&3));
215    /// assert!(!s.contains(&10));
216    /// ```
217    #[must_use]
218    pub fn contains<Q>(&self, value: &Q) -> bool
219    where
220        T: Borrow<Q>,
221        Q: Eq + Hash + ?Sized,
222    {
223        self.inner.contains(value)
224    }
225
226    /// Visits the values representing the difference, i.e., the values that are
227    /// in `self` but not in `other`.
228    ///
229    /// ```
230    /// use nonempty_collections::neis;
231    ///
232    /// let s0 = neis![1, 2, 3];
233    /// let s1 = neis![3, 4, 5];
234    /// let mut v: Vec<_> = s0.difference(&s1).collect();
235    /// v.sort();
236    /// assert_eq!(vec![&1, &2], v);
237    /// ```
238    pub fn difference<'a>(
239        &'a self,
240        other: &'a NEIndexSet<T, S>,
241    ) -> indexmap::set::Difference<'a, T, S> {
242        self.inner.difference(&other.inner)
243    }
244
245    /// Returns a reference to the value in the set, if any, that is equal to
246    /// the given value.
247    ///
248    /// The value may be any borrowed form of the set’s value type, but `Hash`
249    /// and `Eq` on the borrowed form must match those for the value type.
250    ///
251    /// ```
252    /// use nonempty_collections::neis;
253    ///
254    /// let s = neis![1, 2, 3];
255    /// assert_eq!(Some(&3), s.get(&3));
256    /// assert_eq!(None, s.get(&10));
257    /// ```
258    #[must_use]
259    pub fn get<Q>(&self, value: &Q) -> Option<&T>
260    where
261        T: Borrow<Q>,
262        Q: Eq + Hash,
263    {
264        self.inner.get(value)
265    }
266
267    /// Adds a value to the set.
268    ///
269    /// If the set did not have this value present, `true` is returned.
270    ///
271    /// If the set did have this value present, `false` is returned.
272    ///
273    /// ```
274    /// use nonempty_collections::neis;
275    ///
276    /// let mut s = neis![1, 2, 3];
277    /// assert_eq!(false, s.insert(2));
278    /// assert_eq!(true, s.insert(4));
279    /// ```
280    pub fn insert(&mut self, value: T) -> bool {
281        self.inner.insert(value)
282    }
283
284    /// Visits the values representing the interesection, i.e., the values that
285    /// are both in `self` and `other`.
286    ///
287    /// ```
288    /// use nonempty_collections::neis;
289    ///
290    /// let s0 = neis![1, 2, 3];
291    /// let s1 = neis![3, 4, 5];
292    /// let mut v: Vec<_> = s0.intersection(&s1).collect();
293    /// v.sort();
294    /// assert_eq!(vec![&3], v);
295    /// ```
296    pub fn intersection<'a>(
297        &'a self,
298        other: &'a NEIndexSet<T, S>,
299    ) -> indexmap::set::Intersection<'a, T, S> {
300        self.inner.intersection(&other.inner)
301    }
302
303    /// Returns `true` if `self` has no elements in common with `other`.
304    /// This is equivalent to checking for an empty intersection.
305    ///
306    /// ```
307    /// use nonempty_collections::neis;
308    ///
309    /// let s0 = neis![1, 2, 3];
310    /// let s1 = neis![4, 5, 6];
311    /// assert!(s0.is_disjoint(&s1));
312    /// ```
313    #[must_use]
314    pub fn is_disjoint(&self, other: &NEIndexSet<T, S>) -> bool {
315        self.inner.is_disjoint(&other.inner)
316    }
317
318    /// Returns `true` if the set is a subset of another, i.e., `other` contains
319    /// at least all the values in `self`.
320    ///
321    /// ```
322    /// use nonempty_collections::neis;
323    ///
324    /// let sub = neis![1, 2, 3];
325    /// let sup = neis![1, 2, 3, 4];
326    ///
327    /// assert!(sub.is_subset(&sup));
328    /// assert!(!sup.is_subset(&sub));
329    /// ```
330    #[must_use]
331    pub fn is_subset(&self, other: &NEIndexSet<T, S>) -> bool {
332        self.inner.is_subset(&other.inner)
333    }
334
335    /// Returns `true` if the set is a superset of another, i.e., `self`
336    /// contains at least all the values in `other`.
337    ///
338    /// ```
339    /// use nonempty_collections::neis;
340    ///
341    /// let sub = neis![1, 2, 3];
342    /// let sup = neis![1, 2, 3, 4];
343    ///
344    /// assert!(sup.is_superset(&sub));
345    /// assert!(!sub.is_superset(&sup));
346    /// ```
347    #[must_use]
348    pub fn is_superset(&self, other: &NEIndexSet<T, S>) -> bool {
349        self.inner.is_superset(&other.inner)
350    }
351
352    /// Adds a value to the set, replacing the existing value, if any, that is
353    /// equal to the given one. Returns the replaced value.
354    pub fn replace(&mut self, value: T) -> Option<T> {
355        self.inner.replace(value)
356    }
357
358    /// Reserves capacity for at least `additional` more elements to be inserted
359    /// in the `NEIndexSet`. The collection may reserve more space to avoid frequent
360    /// reallocations.
361    ///
362    /// # Panics
363    ///
364    /// Panics if the new allocation size overflows `usize`.
365    pub fn reserve(&mut self, additional: usize) {
366        self.inner.reserve(additional);
367    }
368
369    /// Shrinks the capacity of the set as much as possible. It will drop down
370    /// as much as possible while maintaining the internal rules and possibly
371    /// leaving some space in accordance with the resize policy.
372    pub fn shrink_to_fit(&mut self) {
373        self.inner.shrink_to_fit();
374    }
375
376    /// Visits the values representing the union, i.e., all the values in `self`
377    /// or `other`, without duplicates.
378    ///
379    /// Note that a Union is always non-empty.
380    ///
381    /// ```
382    /// use nonempty_collections::*;
383    ///
384    /// let s0 = neis![1, 2, 3];
385    /// let s1 = neis![3, 4, 5];
386    /// let mut v: NEVec<_> = s0.union(&s1).collect();
387    /// v.sort();
388    /// assert_eq!(nev![&1, &2, &3, &4, &5], v);
389    /// ```
390    pub fn union<'a>(&'a self, other: &'a NEIndexSet<T, S>) -> Union<'a, T, S> {
391        Union {
392            inner: self.inner.union(&other.inner),
393        }
394    }
395
396    /// See [`IndexSet::with_capacity_and_hasher`].
397    #[must_use]
398    pub fn with_capacity_and_hasher(
399        capacity: NonZeroUsize,
400        hasher: S,
401        value: T,
402    ) -> NEIndexSet<T, S> {
403        let mut inner = IndexSet::with_capacity_and_hasher(capacity.get(), hasher);
404        inner.insert(value);
405        NEIndexSet { inner }
406    }
407
408    /// See [`IndexSet::with_hasher`].
409    #[must_use]
410    pub fn with_hasher(hasher: S, value: T) -> NEIndexSet<T, S> {
411        let mut inner = IndexSet::with_hasher(hasher);
412        inner.insert(value);
413        NEIndexSet { inner }
414    }
415}
416
417impl<T, S> AsRef<IndexSet<T, S>> for NEIndexSet<T, S> {
418    fn as_ref(&self) -> &IndexSet<T, S> {
419        &self.inner
420    }
421}
422
423impl<T, S> AsMut<IndexSet<T, S>> for NEIndexSet<T, S> {
424    fn as_mut(&mut self) -> &mut IndexSet<T, S> {
425        &mut self.inner
426    }
427}
428
429impl<T, S> PartialEq for NEIndexSet<T, S>
430where
431    T: Eq + Hash,
432    S: BuildHasher,
433{
434    /// ```
435    /// use nonempty_collections::neis;
436    ///
437    /// let s0 = neis![1, 2, 3];
438    /// let s1 = neis![1, 2, 3];
439    /// let s2 = neis![1, 2];
440    /// let s3 = neis![1, 2, 3, 4];
441    ///
442    /// assert!(s0 == s1);
443    /// assert!(s0 != s2);
444    /// assert!(s0 != s3);
445    /// ```
446    fn eq(&self, other: &Self) -> bool {
447        self.len() == other.len() && self.intersection(other).count() == self.len().get()
448    }
449}
450
451impl<T, S> Eq for NEIndexSet<T, S>
452where
453    T: Eq + Hash,
454    S: BuildHasher,
455{
456}
457
458impl<T, S> IntoNonEmptyIterator for NEIndexSet<T, S> {
459    type IntoNEIter = IntoIter<T>;
460
461    fn into_nonempty_iter(self) -> Self::IntoNEIter {
462        IntoIter {
463            iter: self.inner.into_iter(),
464        }
465    }
466}
467
468impl<'a, T, S> IntoNonEmptyIterator for &'a NEIndexSet<T, S> {
469    type IntoNEIter = Iter<'a, T>;
470
471    fn into_nonempty_iter(self) -> Self::IntoNEIter {
472        self.nonempty_iter()
473    }
474}
475
476impl<T, S> IntoIterator for NEIndexSet<T, S> {
477    type Item = T;
478
479    type IntoIter = indexmap::set::IntoIter<T>;
480
481    fn into_iter(self) -> Self::IntoIter {
482        self.inner.into_iter()
483    }
484}
485
486impl<'a, T, S> IntoIterator for &'a NEIndexSet<T, S> {
487    type Item = &'a T;
488
489    type IntoIter = indexmap::set::Iter<'a, T>;
490
491    fn into_iter(self) -> Self::IntoIter {
492        self.iter()
493    }
494}
495
496/// ```
497/// use nonempty_collections::*;
498///
499/// let s0 = neis![1, 2, 3];
500/// let s1: NEIndexSet<_> = s0.nonempty_iter().cloned().collect();
501/// assert_eq!(s0, s1);
502/// ```
503impl<T, S> FromNonEmptyIterator<T> for NEIndexSet<T, S>
504where
505    T: Eq + Hash,
506    S: BuildHasher + Default,
507{
508    /// ```
509    /// use nonempty_collections::*;
510    ///
511    /// let v = nev![1, 1, 2, 3, 2];
512    /// let s = NEIndexSet::from_nonempty_iter(v);
513    ///
514    /// assert_eq!(neis![1, 2, 3], s);
515    /// ```
516    fn from_nonempty_iter<I>(iter: I) -> Self
517    where
518        I: IntoNonEmptyIterator<Item = T>,
519    {
520        NEIndexSet {
521            inner: iter.into_nonempty_iter().into_iter().collect(),
522        }
523    }
524}
525
526/// A non-empty iterator over the values of an [`NEIndexSet`].
527#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
528pub struct Iter<'a, T: 'a> {
529    iter: indexmap::set::Iter<'a, T>,
530}
531
532impl<'a, T: 'a> IntoIterator for Iter<'a, T> {
533    type Item = &'a T;
534
535    type IntoIter = indexmap::set::Iter<'a, T>;
536
537    fn into_iter(self) -> Self::IntoIter {
538        self.iter
539    }
540}
541
542impl<T> NonEmptyIterator for Iter<'_, T> {}
543
544impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
545    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
546        self.iter.fmt(f)
547    }
548}
549
550/// An owned non-empty iterator over the values of an [`NEIndexSet`].
551#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
552pub struct IntoIter<T> {
553    iter: indexmap::set::IntoIter<T>,
554}
555
556impl<T> IntoIterator for IntoIter<T> {
557    type Item = T;
558
559    type IntoIter = indexmap::set::IntoIter<T>;
560
561    fn into_iter(self) -> Self::IntoIter {
562        self.iter
563    }
564}
565
566impl<T> NonEmptyIterator for IntoIter<T> {}
567
568impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
569    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
570        self.iter.fmt(f)
571    }
572}
573
574/// A non-empty iterator producing elements in the union of two [`NEIndexSet`]s.
575#[must_use = "non-empty iterators are lazy and do nothing unless consumed"]
576pub struct Union<'a, T: 'a, S: 'a> {
577    inner: indexmap::set::Union<'a, T, S>,
578}
579
580impl<'a, T, S> IntoIterator for Union<'a, T, S>
581where
582    T: Eq + Hash,
583    S: BuildHasher,
584{
585    type Item = &'a T;
586
587    type IntoIter = indexmap::set::Union<'a, T, S>;
588
589    fn into_iter(self) -> Self::IntoIter {
590        self.inner
591    }
592}
593
594impl<T, S> NonEmptyIterator for Union<'_, T, S>
595where
596    T: Eq + Hash,
597    S: BuildHasher,
598{
599}
600
601impl<T, S> fmt::Debug for Union<'_, T, S>
602where
603    T: fmt::Debug + Eq + Hash,
604    S: BuildHasher,
605{
606    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
607        self.inner.fmt(f)
608    }
609}
610
611impl<T, S> From<NEIndexSet<T, S>> for IndexSet<T, S>
612where
613    T: Eq + Hash,
614    S: BuildHasher,
615{
616    /// ```
617    /// use indexmap::set::IndexSet;
618    ///
619    /// use nonempty_collections::neis;
620    ///
621    /// let s: IndexSet<_> = neis![1, 2, 3].into();
622    /// let mut v: Vec<_> = s.into_iter().collect();
623    /// v.sort();
624    /// assert_eq!(vec![1, 2, 3], v);
625    /// ```
626    fn from(s: NEIndexSet<T, S>) -> Self {
627        s.inner
628    }
629}
630
631impl<T: fmt::Debug, S> fmt::Debug for NEIndexSet<T, S> {
632    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
633        self.inner.fmt(f)
634    }
635}
636
637impl<T, S> TryFrom<IndexSet<T, S>> for NEIndexSet<T, S>
638where
639    T: Eq + Hash,
640    S: BuildHasher + Default,
641{
642    type Error = crate::Error;
643
644    fn try_from(set: IndexSet<T, S>) -> Result<Self, Self::Error> {
645        let ne = set
646            .try_into_nonempty_iter()
647            .ok_or(crate::Error::Empty)?
648            .collect();
649
650        Ok(ne)
651    }
652}
653
654impl<T> Singleton for NEIndexSet<T>
655where
656    T: Eq + Hash,
657{
658    type Item = T;
659
660    /// ```
661    /// use nonempty_collections::{NEIndexSet, Singleton, neis};
662    ///
663    /// let s = NEIndexSet::singleton(1);
664    /// assert_eq!(neis![1], s);
665    /// ```
666    fn singleton(item: Self::Item) -> Self {
667        NEIndexSet::new(item)
668    }
669}
670
671impl<T> Extend<T> for NEIndexSet<T>
672where
673    T: Eq + Hash,
674{
675    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
676        self.inner.extend(iter);
677    }
678}
679
680#[cfg(test)]
681mod test {
682    use maplit::hashset;
683
684    #[test]
685    fn debug_impl() {
686        let expected = format!("{:?}", hashset! {0});
687        let actual = format!("{:?}", neis! {0});
688        assert_eq!(expected, actual);
689    }
690
691    #[test]
692    fn iter_debug_impl() {
693        let expected = format!("{:?}", hashset! {0}.iter());
694        let actual = format!("{:?}", neis! {0}.nonempty_iter());
695        assert_eq!(expected, actual);
696    }
697}
nonempty_collections/index_set.rs

nonempty_collections/
index_set.rs
