1//! Type definitions for a default set.
2
3use core::{
4 borrow::Borrow,
5 fmt::{self, Debug},
6 hash::Hash,
7 iter::FusedIterator,
8 ops::{BitAnd, BitOr, BitXor, Sub},
9};
10
11#[cfg(all(
12 feature = "hash-collections",
13 not(feature = "prefer-btree-collections")
14))]
15mod detail {
16 use crate::collections::hash;
17 use hashbrown::hash_set;
18
19 pub type SetImpl<T> = hash_set::HashSet<T, hash::RandomState>;
20 pub type IterImpl<'a, T> = hash_set::Iter<'a, T>;
21 pub type IntoIterImpl<T> = hash_set::IntoIter<T>;
22 pub type DifferenceImpl<'a, T> = hash_set::Difference<'a, T, hash::RandomState>;
23 pub type IntersectionImpl<'a, T> = hash_set::Intersection<'a, T, hash::RandomState>;
24 pub type SymmetricDifferenceImpl<'a, T> =
25 hash_set::SymmetricDifference<'a, T, hash::RandomState>;
26 pub type UnionImpl<'a, T> = hash_set::Union<'a, T, hash::RandomState>;
27}
28
29#[cfg(any(
30 not(feature = "hash-collections"),
31 feature = "prefer-btree-collections"
32))]
33mod detail {
34 use alloc::collections::btree_set;
35
36 pub type SetImpl<T> = btree_set::BTreeSet<T>;
37 pub type IterImpl<'a, T> = btree_set::Iter<'a, T>;
38 pub type IntoIterImpl<T> = btree_set::IntoIter<T>;
39 pub type DifferenceImpl<'a, T> = btree_set::Difference<'a, T>;
40 pub type IntersectionImpl<'a, T> = btree_set::Intersection<'a, T>;
41 pub type SymmetricDifferenceImpl<'a, T> = btree_set::SymmetricDifference<'a, T>;
42 pub type UnionImpl<'a, T> = btree_set::Union<'a, T>;
43}
44
45/// A default set of values.
46///
47/// Provides an API compatible with both [`HashSet`] and [`BTreeSet`].
48///
49/// [`HashSet`]: hashbrown::HashSet
50/// [`BTreeSet`]: alloc::collections::BTreeSet
51#[derive(Debug, Clone)]
52pub struct Set<T> {
53 /// The underlying hash-set or btree-set data structure used.
54 inner: detail::SetImpl<T>,
55}
56
57impl<T> Default for Set<T> {
58 #[inline]
59 fn default() -> Self {
60 Self {
61 inner: detail::SetImpl::default(),
62 }
63 }
64}
65
66impl<T> Set<T> {
67 /// Clears the [`Set`], removing all elements.
68 #[inline]
69 pub fn clear(&mut self) {
70 self.inner.clear()
71 }
72
73 /// Retains only the elements specified by the predicate.
74 ///
75 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
76 /// The elements are visited in unsorted (and unspecified) order.
77 #[inline]
78 pub fn retain<F>(&mut self, f: F)
79 where
80 T: Ord,
81 F: FnMut(&T) -> bool,
82 {
83 self.inner.retain(f)
84 }
85
86 /// Returns the number of elements in the [`Set`].
87 #[inline]
88 pub fn len(&self) -> usize {
89 self.inner.len()
90 }
91
92 /// Returns `true` if the [`Set`] contains no elements.
93 #[inline]
94 pub fn is_empty(&self) -> bool {
95 self.inner.is_empty()
96 }
97
98 /// Returns an iterator that yields the items in the [`Set`].
99 #[inline]
100 pub fn iter(&self) -> Iter<'_, T> {
101 Iter {
102 inner: self.inner.iter(),
103 }
104 }
105}
106
107impl<T> Set<T>
108where
109 T: Eq + Hash + Ord,
110{
111 /// Reserves capacity for at least `additional` more elements to be inserted in the [`Set`].
112 #[inline]
113 pub fn reserve(&mut self, additional: usize) {
114 #[cfg(all(
115 feature = "hash-collections",
116 not(feature = "prefer-btree-collections")
117 ))]
118 self.inner.reserve(additional);
119 #[cfg(any(
120 not(feature = "hash-collections"),
121 feature = "prefer-btree-collections"
122 ))]
123 let _ = additional;
124 }
125
126 /// Returns true if the [`Set`] contains an element equal to the `value`.
127 #[inline]
128 pub fn contains<Q>(&self, value: &Q) -> bool
129 where
130 T: Borrow<Q>,
131 Q: ?Sized + Hash + Eq + Ord,
132 {
133 self.inner.contains(value)
134 }
135
136 /// Returns a reference to the element in the [`Set`], if any, that is equal to the `value`.
137 #[inline]
138 pub fn get<Q>(&self, value: &Q) -> Option<&T>
139 where
140 T: Borrow<Q>,
141 Q: ?Sized + Hash + Eq + Ord,
142 {
143 self.inner.get(value)
144 }
145
146 /// Adds `value` to the [`Set`].
147 ///
148 /// Returns whether the value was newly inserted:
149 ///
150 /// - Returns `true` if the set did not previously contain an equal value.
151 /// - Returns `false` otherwise and the entry is not updated.
152 #[inline]
153 pub fn insert(&mut self, value: T) -> bool {
154 self.inner.insert(value)
155 }
156
157 /// If the set contains an element equal to the value, removes it from the [`Set`] and drops it.
158 ///
159 /// Returns `true` if such an element was present, otherwise `false`.
160 #[inline]
161 pub fn remove<Q>(&mut self, value: &Q) -> bool
162 where
163 T: Borrow<Q>,
164 Q: ?Sized + Hash + Eq + Ord,
165 {
166 self.inner.remove(value)
167 }
168
169 /// Removes and returns the element in the [`Set`], if any, that is equal to
170 /// the value.
171 ///
172 /// The value may be any borrowed form of the set's element type,
173 /// but the ordering on the borrowed form *must* match the
174 /// ordering on the element type.
175 #[inline]
176 pub fn take<Q>(&mut self, value: &Q) -> Option<T>
177 where
178 T: Borrow<Q>,
179 Q: ?Sized + Hash + Ord,
180 {
181 self.inner.take(value)
182 }
183
184 /// Adds a value to the [`Set`], replacing the existing value, if any, that is equal to the given
185 /// one. Returns the replaced value.
186 #[inline]
187 pub fn replace(&mut self, value: T) -> Option<T> {
188 self.inner.replace(value)
189 }
190
191 /// Returns `true` if `self` has no elements in common with `other`.
192 /// This is equivalent to checking for an empty intersection.
193 #[inline]
194 pub fn is_disjoint(&self, other: &Self) -> bool {
195 self.inner.is_disjoint(&other.inner)
196 }
197
198 /// Returns `true` if the [`Set`] is a subset of another,
199 /// i.e., `other` contains at least all the values in `self`.
200 #[inline]
201 pub fn is_subset(&self, other: &Self) -> bool {
202 self.inner.is_subset(&other.inner)
203 }
204
205 /// Returns `true` if the [`Set`] is a superset of another,
206 /// i.e., `self` contains at least all the values in `other`.
207 #[inline]
208 pub fn is_superset(&self, other: &Self) -> bool {
209 self.inner.is_superset(&other.inner)
210 }
211
212 /// Visits the values representing the difference,
213 /// i.e., the values that are in `self` but not in `other`.
214 #[inline]
215 pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T> {
216 Difference {
217 inner: self.inner.difference(&other.inner),
218 }
219 }
220
221 /// Visits the values representing the symmetric difference,
222 /// i.e., the values that are in `self` or in `other` but not in both.
223 #[inline]
224 pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T> {
225 SymmetricDifference {
226 inner: self.inner.symmetric_difference(&other.inner),
227 }
228 }
229
230 /// Visits the values representing the intersection,
231 /// i.e., the values that are both in `self` and `other`.
232 ///
233 /// When an equal element is present in `self` and `other`
234 /// then the resulting `Intersection` may yield references to
235 /// one or the other. This can be relevant if `T` contains fields which
236 /// are not compared by its `Eq` implementation, and may hold different
237 /// value between the two equal copies of `T` in the two sets.
238 #[inline]
239 pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
240 Intersection {
241 inner: self.inner.intersection(&other.inner),
242 }
243 }
244
245 /// Visits the values representing the union,
246 /// i.e., all the values in `self` or `other`, without duplicates.
247 #[inline]
248 pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
249 Union {
250 inner: self.inner.union(&other.inner),
251 }
252 }
253}
254
255impl<T> PartialEq for Set<T>
256where
257 T: Eq + Hash,
258{
259 #[inline]
260 fn eq(&self, other: &Self) -> bool {
261 self.inner == other.inner
262 }
263}
264
265impl<T> Eq for Set<T> where T: Eq + Hash {}
266
267impl<T> FromIterator<T> for Set<T>
268where
269 T: Hash + Eq + Ord,
270{
271 #[inline]
272 fn from_iter<I>(iter: I) -> Self
273 where
274 I: IntoIterator<Item = T>,
275 {
276 Self {
277 inner: <detail::SetImpl<T>>::from_iter(iter),
278 }
279 }
280}
281
282impl<'a, T> IntoIterator for &'a Set<T> {
283 type Item = &'a T;
284 type IntoIter = Iter<'a, T>;
285
286 #[inline]
287 fn into_iter(self) -> Self::IntoIter {
288 self.iter()
289 }
290}
291
292impl<'a, T> Extend<&'a T> for Set<T>
293where
294 T: Hash + Eq + Ord + Copy + 'a,
295{
296 #[inline]
297 fn extend<Iter: IntoIterator<Item = &'a T>>(&mut self, iter: Iter) {
298 self.inner.extend(iter)
299 }
300}
301
302impl<T> Extend<T> for Set<T>
303where
304 T: Hash + Eq + Ord,
305{
306 #[inline]
307 fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
308 self.inner.extend(iter)
309 }
310}
311
312impl<'a, T> BitAnd<Self> for &'a Set<T>
313where
314 T: Eq + Hash + Ord + Clone + 'a,
315{
316 type Output = Set<T>;
317
318 #[inline]
319 fn bitand(self, rhs: Self) -> Set<T> {
320 Set {
321 inner: BitAnd::bitand(&self.inner, &rhs.inner),
322 }
323 }
324}
325
326impl<'a, T> BitOr<Self> for &'a Set<T>
327where
328 T: Eq + Hash + Ord + Clone + 'a,
329{
330 type Output = Set<T>;
331
332 #[inline]
333 fn bitor(self, rhs: Self) -> Set<T> {
334 Set {
335 inner: BitOr::bitor(&self.inner, &rhs.inner),
336 }
337 }
338}
339
340impl<'a, T> BitXor<Self> for &'a Set<T>
341where
342 T: Eq + Hash + Ord + Clone + 'a,
343{
344 type Output = Set<T>;
345
346 #[inline]
347 fn bitxor(self, rhs: Self) -> Set<T> {
348 Set {
349 inner: BitXor::bitxor(&self.inner, &rhs.inner),
350 }
351 }
352}
353
354impl<'a, T> Sub<Self> for &'a Set<T>
355where
356 T: Eq + Hash + Ord + Clone + 'a,
357{
358 type Output = Set<T>;
359
360 #[inline]
361 fn sub(self, rhs: Self) -> Set<T> {
362 Set {
363 inner: Sub::sub(&self.inner, &rhs.inner),
364 }
365 }
366}
367
368/// An iterator over the items of a [`Set`].
369#[derive(Debug, Clone)]
370pub struct Iter<'a, T> {
371 inner: detail::IterImpl<'a, T>,
372}
373
374impl<'a, T: 'a> Iterator for Iter<'a, T> {
375 type Item = &'a T;
376
377 #[inline]
378 fn size_hint(&self) -> (usize, Option<usize>) {
379 self.inner.size_hint()
380 }
381
382 #[inline]
383 fn next(&mut self) -> Option<Self::Item> {
384 self.inner.next()
385 }
386}
387
388impl<'a, T: 'a> ExactSizeIterator for Iter<'a, T> {
389 #[inline]
390 fn len(&self) -> usize {
391 self.inner.len()
392 }
393}
394
395impl<'a, T: 'a> FusedIterator for Iter<'a, T> where detail::IterImpl<'a, T>: FusedIterator {}
396
397impl<T> IntoIterator for Set<T> {
398 type Item = T;
399 type IntoIter = IntoIter<T>;
400
401 #[inline]
402 fn into_iter(self) -> Self::IntoIter {
403 IntoIter {
404 inner: self.inner.into_iter(),
405 }
406 }
407}
408
409/// An iterator over the owned items of an [`Set`].
410#[derive(Debug)]
411pub struct IntoIter<T> {
412 inner: detail::IntoIterImpl<T>,
413}
414
415impl<T> Iterator for IntoIter<T> {
416 type Item = T;
417
418 #[inline]
419 fn size_hint(&self) -> (usize, Option<usize>) {
420 self.inner.size_hint()
421 }
422
423 #[inline]
424 fn next(&mut self) -> Option<Self::Item> {
425 self.inner.next()
426 }
427}
428
429impl<T> ExactSizeIterator for IntoIter<T> {
430 #[inline]
431 fn len(&self) -> usize {
432 self.inner.len()
433 }
434}
435
436impl<T> FusedIterator for IntoIter<T> where detail::IntoIterImpl<T>: FusedIterator {}
437
438/// A lazy iterator producing elements in the difference of [`Set`]s.
439///
440/// This `struct` is created by the [`difference`] method on [`Set`].
441/// See its documentation for more.
442///
443/// [`difference`]: Set::difference
444pub struct Difference<'a, T: 'a> {
445 inner: detail::DifferenceImpl<'a, T>,
446}
447
448impl<T> Debug for Difference<'_, T>
449where
450 T: Debug + Hash + Eq,
451{
452 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
453 self.inner.fmt(f)
454 }
455}
456
457impl<T> Clone for Difference<'_, T> {
458 #[inline]
459 fn clone(&self) -> Self {
460 Self {
461 inner: self.inner.clone(),
462 }
463 }
464}
465
466impl<'a, T> Iterator for Difference<'a, T>
467where
468 T: Hash + Eq + Ord,
469{
470 type Item = &'a T;
471
472 #[inline]
473 fn next(&mut self) -> Option<Self::Item> {
474 self.inner.next()
475 }
476
477 #[inline]
478 fn size_hint(&self) -> (usize, Option<usize>) {
479 self.inner.size_hint()
480 }
481}
482
483impl<'a, T> FusedIterator for Difference<'a, T>
484where
485 T: Hash + Eq + Ord,
486 detail::DifferenceImpl<'a, T>: FusedIterator,
487{
488}
489
490/// A lazy iterator producing elements in the intersection of [`Set`]s.
491///
492/// This `struct` is created by the [`intersection`] method on [`Set`].
493/// See its documentation for more.
494///
495/// [`intersection`]: Set::intersection
496pub struct Intersection<'a, T: 'a> {
497 inner: detail::IntersectionImpl<'a, T>,
498}
499
500impl<T> Debug for Intersection<'_, T>
501where
502 T: Debug + Hash + Eq,
503{
504 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
505 self.inner.fmt(f)
506 }
507}
508
509impl<T> Clone for Intersection<'_, T> {
510 #[inline]
511 fn clone(&self) -> Self {
512 Self {
513 inner: self.inner.clone(),
514 }
515 }
516}
517
518impl<'a, T> Iterator for Intersection<'a, T>
519where
520 T: Hash + Eq + Ord,
521{
522 type Item = &'a T;
523
524 #[inline]
525 fn next(&mut self) -> Option<Self::Item> {
526 self.inner.next()
527 }
528
529 #[inline]
530 fn size_hint(&self) -> (usize, Option<usize>) {
531 self.inner.size_hint()
532 }
533}
534
535impl<'a, T> FusedIterator for Intersection<'a, T>
536where
537 T: Hash + Eq + Ord,
538 detail::IntersectionImpl<'a, T>: FusedIterator,
539{
540}
541
542/// A lazy iterator producing elements in the symmetric difference of [`Set`]s.
543///
544/// This `struct` is created by the [`symmetric_difference`] method on
545/// [`Set`]. See its documentation for more.
546///
547/// [`symmetric_difference`]: Set::symmetric_difference
548pub struct SymmetricDifference<'a, T: 'a> {
549 inner: detail::SymmetricDifferenceImpl<'a, T>,
550}
551
552impl<T> Debug for SymmetricDifference<'_, T>
553where
554 T: Debug + Hash + Eq,
555{
556 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
557 self.inner.fmt(f)
558 }
559}
560
561impl<T> Clone for SymmetricDifference<'_, T> {
562 #[inline]
563 fn clone(&self) -> Self {
564 Self {
565 inner: self.inner.clone(),
566 }
567 }
568}
569
570impl<'a, T> Iterator for SymmetricDifference<'a, T>
571where
572 T: Hash + Eq + Ord,
573{
574 type Item = &'a T;
575
576 #[inline]
577 fn next(&mut self) -> Option<Self::Item> {
578 self.inner.next()
579 }
580
581 #[inline]
582 fn size_hint(&self) -> (usize, Option<usize>) {
583 self.inner.size_hint()
584 }
585}
586
587impl<'a, T> FusedIterator for SymmetricDifference<'a, T>
588where
589 T: Hash + Eq + Ord,
590 detail::SymmetricDifferenceImpl<'a, T>: FusedIterator,
591{
592}
593
594/// A lazy iterator producing elements in the union of [`Set`]s.
595///
596/// This `struct` is created by the [`union`] method on
597/// [`Set`]. See its documentation for more.
598///
599/// [`union`]: Set::union
600pub struct Union<'a, T: 'a> {
601 inner: detail::UnionImpl<'a, T>,
602}
603
604impl<T> Debug for Union<'_, T>
605where
606 T: Debug + Hash + Eq,
607{
608 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
609 self.inner.fmt(f)
610 }
611}
612
613impl<T> Clone for Union<'_, T> {
614 #[inline]
615 fn clone(&self) -> Self {
616 Self {
617 inner: self.inner.clone(),
618 }
619 }
620}
621
622impl<'a, T> Iterator for Union<'a, T>
623where
624 T: Hash + Eq + Ord,
625{
626 type Item = &'a T;
627
628 #[inline]
629 fn next(&mut self) -> Option<Self::Item> {
630 self.inner.next()
631 }
632
633 #[inline]
634 fn size_hint(&self) -> (usize, Option<usize>) {
635 self.inner.size_hint()
636 }
637}
638
639impl<'a, T> FusedIterator for Union<'a, T>
640where
641 T: Hash + Eq + Ord,
642 detail::UnionImpl<'a, T>: FusedIterator,
643{
644}
645
646#[cfg(feature = "serde")]
647impl<T> serde::Serialize for Set<T>
648where
649 T: serde::Serialize + Eq + Hash + Ord,
650{
651 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
652 where
653 S: serde::ser::Serializer,
654 {
655 serde::Serialize::serialize(&self.inner, serializer)
656 }
657}
658
659#[cfg(feature = "serde")]
660impl<'a, T> serde::Deserialize<'a> for Set<T>
661where
662 T: serde::Deserialize<'a> + Eq + Hash + Ord,
663{
664 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
665 where
666 D: serde::de::Deserializer<'a>,
667 {
668 Ok(Set {
669 inner: serde::Deserialize::deserialize(deserializer)?,
670 })
671 }
672}
673