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(iter:iterable.into_iter().map(|k: T| (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(iter: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 = 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: &'a T, _)| 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: &'a T = 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: &'a T = self.iter.next()?;
653 if self.other.contains(elt) {
654 return Some(elt);
655 }
656 }
657 }
658}
659