heapless/
indexset.rs

1use crate::indexmap::{self, IndexMap};
2use core::{
3    borrow::Borrow,
4    fmt,
5    hash::{BuildHasher, Hash},
6    iter::FromIterator,
7};
8use hash32::{BuildHasherDefault, FnvHasher};
9
10/// A [`IndexSet`] using the
11/// default FNV hasher.
12/// A list of all Methods and Traits available for `FnvIndexSet` can be found in
13/// the [`IndexSet`] documentation.
14///
15/// # Examples
16/// ```
17/// use heapless::FnvIndexSet;
18///
19/// // A hash set with a capacity of 16 elements allocated on the stack
20/// let mut books = FnvIndexSet::<_, 16>::new();
21///
22/// // Add some books.
23/// books.insert("A Dance With Dragons").unwrap();
24/// books.insert("To Kill a Mockingbird").unwrap();
25/// books.insert("The Odyssey").unwrap();
26/// books.insert("The Great Gatsby").unwrap();
27///
28/// // Check for a specific one.
29/// if !books.contains("The Winds of Winter") {
30///     println!("We have {} books, but The Winds of Winter ain't one.",
31///              books.len());
32/// }
33///
34/// // Remove a book.
35/// books.remove("The Odyssey");
36///
37/// // Iterate over everything.
38/// for book in &books {
39///     println!("{}", book);
40/// }
41/// ```
42pub type FnvIndexSet<T, const N: usize> = IndexSet<T, BuildHasherDefault<FnvHasher>, N>;
43
44/// Fixed capacity [`IndexSet`](https://docs.rs/indexmap/2/indexmap/set/struct.IndexSet.html).
45///
46/// Note that you cannot use `IndexSet` directly, since it is generic around the hashing algorithm
47/// in use. Pick a concrete instantiation like [`FnvIndexSet`] instead
48/// or create your own.
49///
50/// Note that the capacity of the `IndexSet` must be a power of 2.
51///
52/// # Examples
53/// Since `IndexSet` cannot be used directly, we're using its `FnvIndexSet` instantiation
54/// for this example.
55///
56/// ```
57/// use heapless::FnvIndexSet;
58///
59/// // A hash set with a capacity of 16 elements allocated on the stack
60/// let mut books = FnvIndexSet::<_, 16>::new();
61///
62/// // Add some books.
63/// books.insert("A Dance With Dragons").unwrap();
64/// books.insert("To Kill a Mockingbird").unwrap();
65/// books.insert("The Odyssey").unwrap();
66/// books.insert("The Great Gatsby").unwrap();
67///
68/// // Check for a specific one.
69/// if !books.contains("The Winds of Winter") {
70///     println!("We have {} books, but The Winds of Winter ain't one.",
71///              books.len());
72/// }
73///
74/// // Remove a book.
75/// books.remove("The Odyssey");
76///
77/// // Iterate over everything.
78/// for book in &books {
79///     println!("{}", book);
80/// }
81/// ```
82pub struct IndexSet<T, S, const N: usize> {
83    map: IndexMap<T, (), S, N>,
84}
85
86impl<T, S, const N: usize> IndexSet<T, BuildHasherDefault<S>, N> {
87    /// Creates an empty `IndexSet`
88    pub const fn new() -> Self {
89        IndexSet {
90            map: IndexMap::new(),
91        }
92    }
93}
94
95impl<T, S, const N: usize> IndexSet<T, S, N> {
96    /// Returns the number of elements the set can hold
97    ///
98    /// # Examples
99    ///
100    /// ```
101    /// use heapless::FnvIndexSet;
102    ///
103    /// let set = FnvIndexSet::<i32, 16>::new();
104    /// assert_eq!(set.capacity(), 16);
105    /// ```
106    pub fn capacity(&self) -> usize {
107        self.map.capacity()
108    }
109
110    /// Return an iterator over the values of the set, in insertion order
111    ///
112    /// # Examples
113    ///
114    /// ```
115    /// use heapless::FnvIndexSet;
116    ///
117    /// let mut set = FnvIndexSet::<_, 16>::new();
118    /// set.insert("a").unwrap();
119    /// set.insert("b").unwrap();
120    ///
121    /// // Will print in insertion order: a, b
122    /// for x in set.iter() {
123    ///     println!("{}", x);
124    /// }
125    /// ```
126    pub fn iter(&self) -> Iter<'_, T> {
127        Iter {
128            iter: self.map.iter(),
129        }
130    }
131
132    /// Get the first value
133    ///
134    /// Computes in **O(1)** time
135    pub fn first(&self) -> Option<&T> {
136        self.map.first().map(|(k, _v)| k)
137    }
138
139    /// Get the last value
140    ///
141    /// Computes in **O(1)** time
142    pub fn last(&self) -> Option<&T> {
143        self.map.last().map(|(k, _v)| k)
144    }
145
146    /// Returns the number of elements in the set.
147    ///
148    /// # Examples
149    ///
150    /// ```
151    /// use heapless::FnvIndexSet;
152    ///
153    /// let mut v: FnvIndexSet<_, 16> = FnvIndexSet::new();
154    /// assert_eq!(v.len(), 0);
155    /// v.insert(1).unwrap();
156    /// assert_eq!(v.len(), 1);
157    /// ```
158    pub fn len(&self) -> usize {
159        self.map.len()
160    }
161
162    /// Returns `true` if the set contains no elements.
163    ///
164    /// # Examples
165    ///
166    /// ```
167    /// use heapless::FnvIndexSet;
168    ///
169    /// let mut v: FnvIndexSet<_, 16> = FnvIndexSet::new();
170    /// assert!(v.is_empty());
171    /// v.insert(1).unwrap();
172    /// assert!(!v.is_empty());
173    /// ```
174    pub fn is_empty(&self) -> bool {
175        self.map.is_empty()
176    }
177
178    /// Clears the set, removing all values.
179    ///
180    /// # Examples
181    ///
182    /// ```
183    /// use heapless::FnvIndexSet;
184    ///
185    /// let mut v: FnvIndexSet<_, 16> = FnvIndexSet::new();
186    /// v.insert(1).unwrap();
187    /// v.clear();
188    /// assert!(v.is_empty());
189    /// ```
190    pub fn clear(&mut self) {
191        self.map.clear()
192    }
193}
194
195impl<T, S, const N: usize> IndexSet<T, S, N>
196where
197    T: Eq + Hash,
198    S: BuildHasher,
199{
200    /// Visits the values representing the difference, i.e. the values that are in `self` but not in
201    /// `other`.
202    ///
203    /// # Examples
204    ///
205    /// ```
206    /// use heapless::FnvIndexSet;
207    ///
208    /// let mut a: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
209    /// let mut b: FnvIndexSet<_, 16> = [4, 2, 3, 4].iter().cloned().collect();
210    ///
211    /// // Can be seen as `a - b`.
212    /// for x in a.difference(&b) {
213    ///     println!("{}", x); // Print 1
214    /// }
215    ///
216    /// let diff: FnvIndexSet<_, 16> = a.difference(&b).collect();
217    /// assert_eq!(diff, [1].iter().collect::<FnvIndexSet<_, 16>>());
218    ///
219    /// // Note that difference is not symmetric,
220    /// // and `b - a` means something else:
221    /// let diff: FnvIndexSet<_, 16> = b.difference(&a).collect();
222    /// assert_eq!(diff, [4].iter().collect::<FnvIndexSet<_, 16>>());
223    /// ```
224    pub fn difference<'a, S2, const N2: usize>(
225        &'a self,
226        other: &'a IndexSet<T, S2, N2>,
227    ) -> Difference<'a, T, S2, N2>
228    where
229        S2: BuildHasher,
230    {
231        Difference {
232            iter: self.iter(),
233            other,
234        }
235    }
236
237    /// Visits the values representing the symmetric difference, i.e. the values that are in `self`
238    /// or in `other` but not in both.
239    ///
240    /// # Examples
241    ///
242    /// ```
243    /// use heapless::FnvIndexSet;
244    ///
245    /// let mut a: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
246    /// let mut b: FnvIndexSet<_, 16> = [4, 2, 3, 4].iter().cloned().collect();
247    ///
248    /// // Print 1, 4 in that order.
249    /// for x in a.symmetric_difference(&b) {
250    ///     println!("{}", x);
251    /// }
252    ///
253    /// let diff1: FnvIndexSet<_, 16> = a.symmetric_difference(&b).collect();
254    /// let diff2: FnvIndexSet<_, 16> = b.symmetric_difference(&a).collect();
255    ///
256    /// assert_eq!(diff1, diff2);
257    /// assert_eq!(diff1, [1, 4].iter().collect::<FnvIndexSet<_, 16>>());
258    /// ```
259    pub fn symmetric_difference<'a, S2, const N2: usize>(
260        &'a self,
261        other: &'a IndexSet<T, S2, N2>,
262    ) -> impl Iterator<Item = &'a T>
263    where
264        S2: BuildHasher,
265    {
266        self.difference(other).chain(other.difference(self))
267    }
268
269    /// Visits the values representing the intersection, i.e. the values that are both in `self` and
270    /// `other`.
271    ///
272    /// # Examples
273    ///
274    /// ```
275    /// use heapless::FnvIndexSet;
276    ///
277    /// let mut a: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
278    /// let mut b: FnvIndexSet<_, 16> = [4, 2, 3, 4].iter().cloned().collect();
279    ///
280    /// // Print 2, 3 in that order.
281    /// for x in a.intersection(&b) {
282    ///     println!("{}", x);
283    /// }
284    ///
285    /// let intersection: FnvIndexSet<_, 16> = a.intersection(&b).collect();
286    /// assert_eq!(intersection, [2, 3].iter().collect::<FnvIndexSet<_, 16>>());
287    /// ```
288    pub fn intersection<'a, S2, const N2: usize>(
289        &'a self,
290        other: &'a IndexSet<T, S2, N2>,
291    ) -> Intersection<'a, T, S2, N2>
292    where
293        S2: BuildHasher,
294    {
295        Intersection {
296            iter: self.iter(),
297            other,
298        }
299    }
300
301    /// Visits the values representing the union, i.e. all the values in `self` or `other`, without
302    /// duplicates.
303    ///
304    /// # Examples
305    ///
306    /// ```
307    /// use heapless::FnvIndexSet;
308    ///
309    /// let mut a: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
310    /// let mut b: FnvIndexSet<_, 16> = [4, 2, 3, 4].iter().cloned().collect();
311    ///
312    /// // Print 1, 2, 3, 4 in that order.
313    /// for x in a.union(&b) {
314    ///     println!("{}", x);
315    /// }
316    ///
317    /// let union: FnvIndexSet<_, 16> = a.union(&b).collect();
318    /// assert_eq!(union, [1, 2, 3, 4].iter().collect::<FnvIndexSet<_, 16>>());
319    /// ```
320    pub fn union<'a, S2, const N2: usize>(
321        &'a self,
322        other: &'a IndexSet<T, S2, N2>,
323    ) -> impl Iterator<Item = &'a T>
324    where
325        S2: BuildHasher,
326    {
327        self.iter().chain(other.difference(self))
328    }
329
330    /// Returns `true` if the set contains a value.
331    ///
332    /// The value may be any borrowed form of the set's value type, but `Hash` and `Eq` on the
333    /// borrowed form must match those for the value type.
334    ///
335    /// # Examples
336    ///
337    /// ```
338    /// use heapless::FnvIndexSet;
339    ///
340    /// let set: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
341    /// assert_eq!(set.contains(&1), true);
342    /// assert_eq!(set.contains(&4), false);
343    /// ```
344    pub fn contains<Q>(&self, value: &Q) -> bool
345    where
346        T: Borrow<Q>,
347        Q: ?Sized + Eq + Hash,
348    {
349        self.map.contains_key(value)
350    }
351
352    /// Returns `true` if `self` has no elements in common with `other`. This is equivalent to
353    /// checking for an empty intersection.
354    ///
355    /// # Examples
356    ///
357    /// ```
358    /// use heapless::FnvIndexSet;
359    ///
360    /// let a: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
361    /// let mut b = FnvIndexSet::<_, 16>::new();
362    ///
363    /// assert_eq!(a.is_disjoint(&b), true);
364    /// b.insert(4).unwrap();
365    /// assert_eq!(a.is_disjoint(&b), true);
366    /// b.insert(1).unwrap();
367    /// assert_eq!(a.is_disjoint(&b), false);
368    /// ```
369    pub fn is_disjoint<S2, const N2: usize>(&self, other: &IndexSet<T, S2, N2>) -> bool
370    where
371        S2: BuildHasher,
372    {
373        self.iter().all(|v| !other.contains(v))
374    }
375
376    /// Returns `true` if the set is a subset of another, i.e. `other` contains at least all the
377    /// values in `self`.
378    ///
379    /// # Examples
380    ///
381    /// ```
382    /// use heapless::FnvIndexSet;
383    ///
384    /// let sup: FnvIndexSet<_, 16> = [1, 2, 3].iter().cloned().collect();
385    /// let mut set = FnvIndexSet::<_, 16>::new();
386    ///
387    /// assert_eq!(set.is_subset(&sup), true);
388    /// set.insert(2).unwrap();
389    /// assert_eq!(set.is_subset(&sup), true);
390    /// set.insert(4).unwrap();
391    /// assert_eq!(set.is_subset(&sup), false);
392    /// ```
393    pub fn is_subset<S2, const N2: usize>(&self, other: &IndexSet<T, S2, N2>) -> bool
394    where
395        S2: BuildHasher,
396    {
397        self.iter().all(|v| other.contains(v))
398    }
399
400    // Returns `true` if the set is a superset of another, i.e. `self` contains at least all the
401    // values in `other`.
402    ///
403    /// # Examples
404    ///
405    /// ```
406    /// use heapless::FnvIndexSet;
407    ///
408    /// let sub: FnvIndexSet<_, 16> = [1, 2].iter().cloned().collect();
409    /// let mut set = FnvIndexSet::<_, 16>::new();
410    ///
411    /// assert_eq!(set.is_superset(&sub), false);
412    ///
413    /// set.insert(0).unwrap();
414    /// set.insert(1).unwrap();
415    /// assert_eq!(set.is_superset(&sub), false);
416    ///
417    /// set.insert(2).unwrap();
418    /// assert_eq!(set.is_superset(&sub), true);
419    /// ```
420    pub fn is_superset<S2, const N2: usize>(&self, other: &IndexSet<T, S2, N2>) -> bool
421    where
422        S2: BuildHasher,
423    {
424        other.is_subset(self)
425    }
426
427    /// Adds a value to the set.
428    ///
429    /// If the set did not have this value present, `true` is returned.
430    ///
431    /// If the set did have this value present, `false` is returned.
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// use heapless::FnvIndexSet;
437    ///
438    /// let mut set = FnvIndexSet::<_, 16>::new();
439    ///
440    /// assert_eq!(set.insert(2).unwrap(), true);
441    /// assert_eq!(set.insert(2).unwrap(), false);
442    /// assert_eq!(set.len(), 1);
443    /// ```
444    pub fn insert(&mut self, value: T) -> Result<bool, T> {
445        self.map
446            .insert(value, ())
447            .map(|old| old.is_none())
448            .map_err(|(k, _)| k)
449    }
450
451    /// Removes a value from the set. Returns `true` if the value was present in the set.
452    ///
453    /// The value may be any borrowed form of the set's value type, but `Hash` and `Eq` on the
454    /// borrowed form must match those for the value type.
455    ///
456    /// # Examples
457    ///
458    /// ```
459    /// use heapless::FnvIndexSet;
460    ///
461    /// let mut set = FnvIndexSet::<_, 16>::new();
462    ///
463    /// set.insert(2).unwrap();
464    /// assert_eq!(set.remove(&2), true);
465    /// assert_eq!(set.remove(&2), false);
466    /// ```
467    pub fn remove<Q>(&mut self, value: &Q) -> bool
468    where
469        T: Borrow<Q>,
470        Q: ?Sized + Eq + Hash,
471    {
472        self.map.remove(value).is_some()
473    }
474
475    /// Retains only the elements specified by the predicate.
476    ///
477    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
478    pub fn retain<F>(&mut self, mut f: F)
479    where
480        F: FnMut(&T) -> bool,
481    {
482        self.map.retain(move |k, _| f(k));
483    }
484}
485
486impl<T, S, const N: usize> Clone for IndexSet<T, S, N>
487where
488    T: Clone,
489    S: Clone,
490{
491    fn clone(&self) -> Self {
492        Self {
493            map: self.map.clone(),
494        }
495    }
496}
497
498impl<T, S, const N: usize> fmt::Debug for IndexSet<T, S, N>
499where
500    T: fmt::Debug,
501{
502    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
503        f.debug_set().entries(self.iter()).finish()
504    }
505}
506
507impl<T, S, const N: usize> Default for IndexSet<T, S, N>
508where
509    S: Default,
510{
511    fn default() -> Self {
512        IndexSet {
513            map: <_>::default(),
514        }
515    }
516}
517
518impl<T, S1, S2, const N1: usize, const N2: usize> PartialEq<IndexSet<T, S2, N2>>
519    for IndexSet<T, S1, N1>
520where
521    T: Eq + Hash,
522    S1: BuildHasher,
523    S2: BuildHasher,
524{
525    fn eq(&self, other: &IndexSet<T, S2, N2>) -> bool {
526        self.len() == other.len() && self.is_subset(other)
527    }
528}
529
530impl<T, S, const N: usize> Extend<T> for IndexSet<T, S, N>
531where
532    T: Eq + Hash,
533    S: BuildHasher,
534{
535    fn extend<I>(&mut self, iterable: I)
536    where
537        I: IntoIterator<Item = T>,
538    {
539        self.map.extend(iterable.into_iter().map(|k| (k, ())))
540    }
541}
542
543impl<'a, T, S, const N: usize> Extend<&'a T> for IndexSet<T, S, N>
544where
545    T: 'a + Eq + Hash + Copy,
546    S: BuildHasher,
547{
548    fn extend<I>(&mut self, iterable: I)
549    where
550        I: IntoIterator<Item = &'a T>,
551    {
552        self.extend(iterable.into_iter().cloned())
553    }
554}
555
556impl<T, S, const N: usize> FromIterator<T> for IndexSet<T, S, N>
557where
558    T: Eq + Hash,
559    S: BuildHasher + Default,
560{
561    fn from_iter<I>(iter: I) -> Self
562    where
563        I: IntoIterator<Item = T>,
564    {
565        let mut set = IndexSet::default();
566        set.extend(iter);
567        set
568    }
569}
570
571impl<'a, T, S, const N: usize> IntoIterator for &'a IndexSet<T, S, N>
572where
573    T: Eq + Hash,
574    S: BuildHasher,
575{
576    type Item = &'a T;
577    type IntoIter = Iter<'a, T>;
578
579    fn into_iter(self) -> Self::IntoIter {
580        self.iter()
581    }
582}
583
584/// An iterator over the items of a [`IndexSet`].
585///
586/// This `struct` is created by the [`iter`](IndexSet::iter) method on [`IndexSet`]. See its
587/// documentation for more.
588pub struct Iter<'a, T> {
589    iter: indexmap::Iter<'a, T, ()>,
590}
591
592impl<'a, T> Iterator for Iter<'a, T> {
593    type Item = &'a T;
594
595    fn next(&mut self) -> Option<Self::Item> {
596        self.iter.next().map(|(k, _)| k)
597    }
598}
599
600impl<'a, T> Clone for Iter<'a, T> {
601    fn clone(&self) -> Self {
602        Self {
603            iter: self.iter.clone(),
604        }
605    }
606}
607
608pub struct Difference<'a, T, S, const N: usize>
609where
610    S: BuildHasher,
611    T: Eq + Hash,
612{
613    iter: Iter<'a, T>,
614    other: &'a IndexSet<T, S, N>,
615}
616
617impl<'a, T, S, const N: usize> Iterator for Difference<'a, T, S, N>
618where
619    S: BuildHasher,
620    T: Eq + Hash,
621{
622    type Item = &'a T;
623
624    fn next(&mut self) -> Option<Self::Item> {
625        loop {
626            let elt = self.iter.next()?;
627            if !self.other.contains(elt) {
628                return Some(elt);
629            }
630        }
631    }
632}
633
634pub struct Intersection<'a, T, S, const N: usize>
635where
636    S: BuildHasher,
637    T: Eq + Hash,
638{
639    iter: Iter<'a, T>,
640    other: &'a IndexSet<T, S, N>,
641}
642
643impl<'a, T, S, const N: usize> Iterator for Intersection<'a, T, S, N>
644where
645    S: BuildHasher,
646    T: Eq + Hash,
647{
648    type Item = &'a T;
649
650    fn next(&mut self) -> Option<Self::Item> {
651        loop {
652            let elt = self.iter.next()?;
653            if self.other.contains(elt) {
654                return Some(elt);
655            }
656        }
657    }
658}