im_rc/hash/
set.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! An unordered set.
6//!
7//! An immutable hash set using [hash array mapped tries] [1].
8//!
9//! Most operations on this set are O(log<sub>x</sub> n) for a
10//! suitably high *x* that it should be nearly O(1) for most sets.
11//! Because of this, it's a great choice for a generic set as long as
12//! you don't mind that values will need to implement
13//! [`Hash`][std::hash::Hash] and [`Eq`][std::cmp::Eq].
14//!
15//! Values will have a predictable order based on the hasher
16//! being used. Unless otherwise specified, this will be the standard
17//! [`RandomState`][std::collections::hash_map::RandomState] hasher.
18//!
19//! [1]: https://en.wikipedia.org/wiki/Hash_array_mapped_trie
20//! [std::cmp::Eq]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
21//! [std::hash::Hash]: https://doc.rust-lang.org/std/hash/trait.Hash.html
22//! [std::collections::hash_map::RandomState]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
23
24use std::borrow::Borrow;
25use std::cmp::Ordering;
26use std::collections::hash_map::RandomState;
27use std::collections::{self, BTreeSet};
28use std::fmt::{Debug, Error, Formatter};
29use std::hash::{BuildHasher, Hash, Hasher};
30use std::iter::FusedIterator;
31use std::iter::{FromIterator, IntoIterator, Sum};
32use std::ops::{Add, Deref, Mul};
33
34use crate::nodes::hamt::{hash_key, Drain as NodeDrain, HashValue, Iter as NodeIter, Node};
35use crate::ordset::OrdSet;
36use crate::util::{Pool, PoolRef, Ref};
37use crate::Vector;
38
39/// Construct a set from a sequence of values.
40///
41/// # Examples
42///
43/// ```
44/// # #[macro_use] extern crate im_rc as im;
45/// # use im::hashset::HashSet;
46/// # fn main() {
47/// assert_eq!(
48///   hashset![1, 2, 3],
49///   HashSet::from(vec![1, 2, 3])
50/// );
51/// # }
52/// ```
53#[macro_export]
54macro_rules! hashset {
55    () => { $crate::hashset::HashSet::new() };
56
57    ( $($x:expr),* ) => {{
58        let mut l = $crate::hashset::HashSet::new();
59        $(
60            l.insert($x);
61        )*
62            l
63    }};
64
65    ( $($x:expr ,)* ) => {{
66        let mut l = $crate::hashset::HashSet::new();
67        $(
68            l.insert($x);
69        )*
70            l
71    }};
72}
73
74def_pool!(HashSetPool<A>, Node<Value<A>>);
75
76/// An unordered set.
77///
78/// An immutable hash set using [hash array mapped tries] [1].
79///
80/// Most operations on this set are O(log<sub>x</sub> n) for a
81/// suitably high *x* that it should be nearly O(1) for most sets.
82/// Because of this, it's a great choice for a generic set as long as
83/// you don't mind that values will need to implement
84/// [`Hash`][std::hash::Hash] and [`Eq`][std::cmp::Eq].
85///
86/// Values will have a predictable order based on the hasher
87/// being used. Unless otherwise specified, this will be the standard
88/// [`RandomState`][std::collections::hash_map::RandomState] hasher.
89///
90/// [1]: https://en.wikipedia.org/wiki/Hash_array_mapped_trie
91/// [std::cmp::Eq]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
92/// [std::hash::Hash]: https://doc.rust-lang.org/std/hash/trait.Hash.html
93/// [std::collections::hash_map::RandomState]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
94pub struct HashSet<A, S = RandomState> {
95    hasher: Ref<S>,
96    pool: HashSetPool<A>,
97    root: PoolRef<Node<Value<A>>>,
98    size: usize,
99}
100
101#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
102struct Value<A>(A);
103
104impl<A> Deref for Value<A> {
105    type Target = A;
106    fn deref(&self) -> &Self::Target {
107        &self.0
108    }
109}
110
111// FIXME lacking specialisation, we can't simply implement `HashValue`
112// for `A`, we have to use the `Value<A>` indirection.
113impl<A> HashValue for Value<A>
114where
115    A: Hash + Eq,
116{
117    type Key = A;
118
119    fn extract_key(&self) -> &Self::Key {
120        &self.0
121    }
122
123    fn ptr_eq(&self, _other: &Self) -> bool {
124        false
125    }
126}
127
128impl<A> HashSet<A, RandomState> {
129    /// Construct an empty set.
130    #[must_use]
131    pub fn new() -> Self {
132        Self::default()
133    }
134
135    /// Construct an empty set using a specific memory pool.
136    #[cfg(feature = "pool")]
137    #[must_use]
138    pub fn with_pool(pool: &HashSetPool<A>) -> Self {
139        Self {
140            pool: pool.clone(),
141            hasher: Default::default(),
142            size: 0,
143            root: PoolRef::default(&pool.0),
144        }
145    }
146}
147
148impl<A> HashSet<A, RandomState>
149where
150    A: Hash + Eq + Clone,
151{
152    /// Construct a set with a single value.
153    ///
154    /// # Examples
155    ///
156    /// ```
157    /// # #[macro_use] extern crate im_rc as im;
158    /// # use im::hashset::HashSet;
159    /// # use std::sync::Arc;
160    /// let set = HashSet::unit(123);
161    /// assert!(set.contains(&123));
162    /// ```
163    #[inline]
164    #[must_use]
165    pub fn unit(a: A) -> Self {
166        HashSet::new().update(a)
167    }
168}
169
170impl<A, S> HashSet<A, S> {
171    /// Test whether a set is empty.
172    ///
173    /// Time: O(1)
174    ///
175    /// # Examples
176    ///
177    /// ```
178    /// # #[macro_use] extern crate im_rc as im;
179    /// # use im::hashset::HashSet;
180    /// assert!(
181    ///   !hashset![1, 2, 3].is_empty()
182    /// );
183    /// assert!(
184    ///   HashSet::<i32>::new().is_empty()
185    /// );
186    /// ```
187    #[inline]
188    #[must_use]
189    pub fn is_empty(&self) -> bool {
190        self.len() == 0
191    }
192
193    /// Get the size of a set.
194    ///
195    /// Time: O(1)
196    ///
197    /// # Examples
198    ///
199    /// ```
200    /// # #[macro_use] extern crate im_rc as im;
201    /// # use im::hashset::HashSet;
202    /// assert_eq!(3, hashset![1, 2, 3].len());
203    /// ```
204    #[inline]
205    #[must_use]
206    pub fn len(&self) -> usize {
207        self.size
208    }
209
210    /// Test whether two sets refer to the same content in memory.
211    ///
212    /// This is true if the two sides are references to the same set,
213    /// or if the two sets refer to the same root node.
214    ///
215    /// This would return true if you're comparing a set to itself, or
216    /// if you're comparing a set to a fresh clone of itself.
217    ///
218    /// Time: O(1)
219    pub fn ptr_eq(&self, other: &Self) -> bool {
220        std::ptr::eq(self, other) || PoolRef::ptr_eq(&self.root, &other.root)
221    }
222
223    /// Get a reference to the memory pool used by this set.
224    ///
225    /// Note that if you didn't specifically construct it with a pool, you'll
226    /// get back a reference to a pool of size 0.
227    #[cfg(feature = "pool")]
228    pub fn pool(&self) -> &HashSetPool<A> {
229        &self.pool
230    }
231
232    /// Construct an empty hash set using the provided hasher.
233    #[inline]
234    #[must_use]
235    pub fn with_hasher<RS>(hasher: RS) -> Self
236    where
237        Ref<S>: From<RS>,
238    {
239        let pool = HashSetPool::default();
240        let root = PoolRef::default(&pool.0);
241        HashSet {
242            size: 0,
243            pool,
244            root,
245            hasher: From::from(hasher),
246        }
247    }
248
249    /// Construct an empty hash set using the provided memory pool and hasher.
250    #[cfg(feature = "pool")]
251    #[inline]
252    #[must_use]
253    pub fn with_pool_hasher<RS>(pool: &HashSetPool<A>, hasher: RS) -> Self
254    where
255        Ref<S>: From<RS>,
256    {
257        let root = PoolRef::default(&pool.0);
258        HashSet {
259            size: 0,
260            pool: pool.clone(),
261            root,
262            hasher: From::from(hasher),
263        }
264    }
265
266    /// Get a reference to the set's [`BuildHasher`][BuildHasher].
267    ///
268    /// [BuildHasher]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
269    #[must_use]
270    pub fn hasher(&self) -> &Ref<S> {
271        &self.hasher
272    }
273
274    /// Construct an empty hash set using the same hasher as the current hash set.
275    #[inline]
276    #[must_use]
277    pub fn new_from<A1>(&self) -> HashSet<A1, S>
278    where
279        A1: Hash + Eq + Clone,
280    {
281        let pool = HashSetPool::default();
282        let root = PoolRef::default(&pool.0);
283        HashSet {
284            size: 0,
285            pool,
286            root,
287            hasher: self.hasher.clone(),
288        }
289    }
290
291    /// Discard all elements from the set.
292    ///
293    /// This leaves you with an empty set, and all elements that
294    /// were previously inside it are dropped.
295    ///
296    /// Time: O(n)
297    ///
298    /// # Examples
299    ///
300    /// ```
301    /// # #[macro_use] extern crate im_rc as im;
302    /// # use im::HashSet;
303    /// let mut set = hashset![1, 2, 3];
304    /// set.clear();
305    /// assert!(set.is_empty());
306    /// ```
307    pub fn clear(&mut self) {
308        if !self.is_empty() {
309            self.root = PoolRef::default(&self.pool.0);
310            self.size = 0;
311        }
312    }
313
314    /// Get an iterator over the values in a hash set.
315    ///
316    /// Please note that the order is consistent between sets using
317    /// the same hasher, but no other ordering guarantee is offered.
318    /// Items will not come out in insertion order or sort order.
319    /// They will, however, come out in the same order every time for
320    /// the same set.
321    #[must_use]
322    pub fn iter(&self) -> Iter<'_, A> {
323        Iter {
324            it: NodeIter::new(&self.root, self.size),
325        }
326    }
327}
328
329impl<A, S> HashSet<A, S>
330where
331    A: Hash + Eq,
332    S: BuildHasher,
333{
334    fn test_eq(&self, other: &Self) -> bool {
335        if self.len() != other.len() {
336            return false;
337        }
338        let mut seen = collections::HashSet::new();
339        for value in self.iter() {
340            if !other.contains(value) {
341                return false;
342            }
343            seen.insert(value);
344        }
345        for value in other.iter() {
346            if !seen.contains(&value) {
347                return false;
348            }
349        }
350        true
351    }
352
353    /// Test if a value is part of a set.
354    ///
355    /// Time: O(log n)
356    #[must_use]
357    pub fn contains<BA>(&self, a: &BA) -> bool
358    where
359        BA: Hash + Eq + ?Sized,
360        A: Borrow<BA>,
361    {
362        self.root.get(hash_key(&*self.hasher, a), 0, a).is_some()
363    }
364
365    /// Test whether a set is a subset of another set, meaning that
366    /// all values in our set must also be in the other set.
367    ///
368    /// Time: O(n log n)
369    #[must_use]
370    pub fn is_subset<RS>(&self, other: RS) -> bool
371    where
372        RS: Borrow<Self>,
373    {
374        let o = other.borrow();
375        self.iter().all(|a| o.contains(a))
376    }
377
378    /// Test whether a set is a proper subset of another set, meaning
379    /// that all values in our set must also be in the other set. A
380    /// proper subset must also be smaller than the other set.
381    ///
382    /// Time: O(n log n)
383    #[must_use]
384    pub fn is_proper_subset<RS>(&self, other: RS) -> bool
385    where
386        RS: Borrow<Self>,
387    {
388        self.len() != other.borrow().len() && self.is_subset(other)
389    }
390}
391
392impl<A, S> HashSet<A, S>
393where
394    A: Hash + Eq + Clone,
395    S: BuildHasher,
396{
397    /// Insert a value into a set.
398    ///
399    /// Time: O(log n)
400    #[inline]
401    pub fn insert(&mut self, a: A) -> Option<A> {
402        let hash = hash_key(&*self.hasher, &a);
403        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
404        match root.insert(&self.pool.0, hash, 0, Value(a)) {
405            None => {
406                self.size += 1;
407                None
408            }
409            Some(Value(old_value)) => Some(old_value),
410        }
411    }
412
413    /// Remove a value from a set if it exists.
414    ///
415    /// Time: O(log n)
416    pub fn remove<BA>(&mut self, a: &BA) -> Option<A>
417    where
418        BA: Hash + Eq + ?Sized,
419        A: Borrow<BA>,
420    {
421        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
422        let result = root.remove(&self.pool.0, hash_key(&*self.hasher, a), 0, a);
423        if result.is_some() {
424            self.size -= 1;
425        }
426        result.map(|v| v.0)
427    }
428
429    /// Construct a new set from the current set with the given value
430    /// added.
431    ///
432    /// Time: O(log n)
433    ///
434    /// # Examples
435    ///
436    /// ```
437    /// # #[macro_use] extern crate im_rc as im;
438    /// # use im::hashset::HashSet;
439    /// # use std::sync::Arc;
440    /// let set = hashset![123];
441    /// assert_eq!(
442    ///   set.update(456),
443    ///   hashset![123, 456]
444    /// );
445    /// ```
446    #[must_use]
447    pub fn update(&self, a: A) -> Self {
448        let mut out = self.clone();
449        out.insert(a);
450        out
451    }
452
453    /// Construct a new set with the given value removed if it's in
454    /// the set.
455    ///
456    /// Time: O(log n)
457    #[must_use]
458    pub fn without<BA>(&self, a: &BA) -> Self
459    where
460        BA: Hash + Eq + ?Sized,
461        A: Borrow<BA>,
462    {
463        let mut out = self.clone();
464        out.remove(a);
465        out
466    }
467
468    /// Filter out values from a set which don't satisfy a predicate.
469    ///
470    /// This is slightly more efficient than filtering using an
471    /// iterator, in that it doesn't need to rehash the retained
472    /// values, but it still needs to reconstruct the entire tree
473    /// structure of the set.
474    ///
475    /// Time: O(n log n)
476    ///
477    /// # Examples
478    ///
479    /// ```
480    /// # #[macro_use] extern crate im_rc as im;
481    /// # use im::HashSet;
482    /// let mut set = hashset![1, 2, 3];
483    /// set.retain(|v| *v > 1);
484    /// let expected = hashset![2, 3];
485    /// assert_eq!(expected, set);
486    /// ```
487    pub fn retain<F>(&mut self, mut f: F)
488    where
489        F: FnMut(&A) -> bool,
490    {
491        let old_root = self.root.clone();
492        let root = PoolRef::make_mut(&self.pool.0, &mut self.root);
493        for (value, hash) in NodeIter::new(&old_root, self.size) {
494            if !f(value) && root.remove(&self.pool.0, hash, 0, value).is_some() {
495                self.size -= 1;
496            }
497        }
498    }
499
500    /// Construct the union of two sets.
501    ///
502    /// Time: O(n log n)
503    ///
504    /// # Examples
505    ///
506    /// ```
507    /// # #[macro_use] extern crate im_rc as im;
508    /// # use im::hashset::HashSet;
509    /// let set1 = hashset!{1, 2};
510    /// let set2 = hashset!{2, 3};
511    /// let expected = hashset!{1, 2, 3};
512    /// assert_eq!(expected, set1.union(set2));
513    /// ```
514    #[must_use]
515    pub fn union(self, other: Self) -> Self {
516        let (mut to_mutate, to_consume) = if self.len() >= other.len() {
517            (self, other)
518        } else {
519            (other, self)
520        };
521        for value in to_consume {
522            to_mutate.insert(value);
523        }
524        to_mutate
525    }
526
527    /// Construct the union of multiple sets.
528    ///
529    /// Time: O(n log n)
530    #[must_use]
531    pub fn unions<I>(i: I) -> Self
532    where
533        I: IntoIterator<Item = Self>,
534        S: Default,
535    {
536        i.into_iter().fold(Self::default(), Self::union)
537    }
538
539    /// Construct the symmetric difference between two sets.
540    ///
541    /// This is an alias for the
542    /// [`symmetric_difference`][symmetric_difference] method.
543    ///
544    /// Time: O(n log n)
545    ///
546    /// # Examples
547    ///
548    /// ```
549    /// # #[macro_use] extern crate im_rc as im;
550    /// # use im::hashset::HashSet;
551    /// let set1 = hashset!{1, 2};
552    /// let set2 = hashset!{2, 3};
553    /// let expected = hashset!{1, 3};
554    /// assert_eq!(expected, set1.difference(set2));
555    /// ```
556    ///
557    /// [symmetric_difference]: #method.symmetric_difference
558    #[must_use]
559    pub fn difference(self, other: Self) -> Self {
560        self.symmetric_difference(other)
561    }
562
563    /// Construct the symmetric difference between two sets.
564    ///
565    /// Time: O(n log n)
566    ///
567    /// # Examples
568    ///
569    /// ```
570    /// # #[macro_use] extern crate im_rc as im;
571    /// # use im::hashset::HashSet;
572    /// let set1 = hashset!{1, 2};
573    /// let set2 = hashset!{2, 3};
574    /// let expected = hashset!{1, 3};
575    /// assert_eq!(expected, set1.symmetric_difference(set2));
576    /// ```
577    #[must_use]
578    pub fn symmetric_difference(mut self, other: Self) -> Self {
579        for value in other {
580            if self.remove(&value).is_none() {
581                self.insert(value);
582            }
583        }
584        self
585    }
586
587    /// Construct the relative complement between two sets, that is the set
588    /// of values in `self` that do not occur in `other`.
589    ///
590    /// Time: O(m log n) where m is the size of the other set
591    ///
592    /// # Examples
593    ///
594    /// ```
595    /// # #[macro_use] extern crate im_rc as im;
596    /// # use im::ordset::OrdSet;
597    /// let set1 = ordset!{1, 2};
598    /// let set2 = ordset!{2, 3};
599    /// let expected = ordset!{1};
600    /// assert_eq!(expected, set1.relative_complement(set2));
601    /// ```
602    #[must_use]
603    pub fn relative_complement(mut self, other: Self) -> Self {
604        for value in other {
605            let _ = self.remove(&value);
606        }
607        self
608    }
609
610    /// Construct the intersection of two sets.
611    ///
612    /// Time: O(n log n)
613    ///
614    /// # Examples
615    ///
616    /// ```
617    /// # #[macro_use] extern crate im_rc as im;
618    /// # use im::hashset::HashSet;
619    /// let set1 = hashset!{1, 2};
620    /// let set2 = hashset!{2, 3};
621    /// let expected = hashset!{2};
622    /// assert_eq!(expected, set1.intersection(set2));
623    /// ```
624    #[must_use]
625    pub fn intersection(self, other: Self) -> Self {
626        let mut out = self.new_from();
627        for value in other {
628            if self.contains(&value) {
629                out.insert(value);
630            }
631        }
632        out
633    }
634}
635
636// Core traits
637
638impl<A, S> Clone for HashSet<A, S>
639where
640    A: Clone,
641{
642    /// Clone a set.
643    ///
644    /// Time: O(1)
645    #[inline]
646    fn clone(&self) -> Self {
647        HashSet {
648            hasher: self.hasher.clone(),
649            pool: self.pool.clone(),
650            root: self.root.clone(),
651            size: self.size,
652        }
653    }
654}
655
656impl<A, S> PartialEq for HashSet<A, S>
657where
658    A: Hash + Eq,
659    S: BuildHasher + Default,
660{
661    fn eq(&self, other: &Self) -> bool {
662        self.test_eq(other)
663    }
664}
665
666impl<A, S> Eq for HashSet<A, S>
667where
668    A: Hash + Eq,
669    S: BuildHasher + Default,
670{
671}
672
673impl<A, S> PartialOrd for HashSet<A, S>
674where
675    A: Hash + Eq + Clone + PartialOrd,
676    S: BuildHasher + Default,
677{
678    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
679        if Ref::ptr_eq(&self.hasher, &other.hasher) {
680            return self.iter().partial_cmp(other.iter());
681        }
682        self.iter().partial_cmp(other.iter())
683    }
684}
685
686impl<A, S> Ord for HashSet<A, S>
687where
688    A: Hash + Eq + Clone + Ord,
689    S: BuildHasher + Default,
690{
691    fn cmp(&self, other: &Self) -> Ordering {
692        if Ref::ptr_eq(&self.hasher, &other.hasher) {
693            return self.iter().cmp(other.iter());
694        }
695        self.iter().cmp(other.iter())
696    }
697}
698
699impl<A, S> Hash for HashSet<A, S>
700where
701    A: Hash + Eq,
702    S: BuildHasher + Default,
703{
704    fn hash<H>(&self, state: &mut H)
705    where
706        H: Hasher,
707    {
708        for i in self.iter() {
709            i.hash(state);
710        }
711    }
712}
713
714impl<A, S> Default for HashSet<A, S>
715where
716    S: BuildHasher + Default,
717{
718    fn default() -> Self {
719        let pool = HashSetPool::default();
720        let root = PoolRef::default(&pool.0);
721        HashSet {
722            hasher: Ref::<S>::default(),
723            pool,
724            root,
725            size: 0,
726        }
727    }
728}
729
730impl<A, S> Add for HashSet<A, S>
731where
732    A: Hash + Eq + Clone,
733    S: BuildHasher,
734{
735    type Output = HashSet<A, S>;
736
737    fn add(self, other: Self) -> Self::Output {
738        self.union(other)
739    }
740}
741
742impl<A, S> Mul for HashSet<A, S>
743where
744    A: Hash + Eq + Clone,
745    S: BuildHasher,
746{
747    type Output = HashSet<A, S>;
748
749    fn mul(self, other: Self) -> Self::Output {
750        self.intersection(other)
751    }
752}
753
754impl<'a, A, S> Add for &'a HashSet<A, S>
755where
756    A: Hash + Eq + Clone,
757    S: BuildHasher,
758{
759    type Output = HashSet<A, S>;
760
761    fn add(self, other: Self) -> Self::Output {
762        self.clone().union(other.clone())
763    }
764}
765
766impl<'a, A, S> Mul for &'a HashSet<A, S>
767where
768    A: Hash + Eq + Clone,
769    S: BuildHasher,
770{
771    type Output = HashSet<A, S>;
772
773    fn mul(self, other: Self) -> Self::Output {
774        self.clone().intersection(other.clone())
775    }
776}
777
778impl<A, S> Sum for HashSet<A, S>
779where
780    A: Hash + Eq + Clone,
781    S: BuildHasher + Default,
782{
783    fn sum<I>(it: I) -> Self
784    where
785        I: Iterator<Item = Self>,
786    {
787        it.fold(Self::default(), |a, b| a + b)
788    }
789}
790
791impl<A, S, R> Extend<R> for HashSet<A, S>
792where
793    A: Hash + Eq + Clone + From<R>,
794    S: BuildHasher,
795{
796    fn extend<I>(&mut self, iter: I)
797    where
798        I: IntoIterator<Item = R>,
799    {
800        for value in iter {
801            self.insert(From::from(value));
802        }
803    }
804}
805
806#[cfg(not(has_specialisation))]
807impl<A, S> Debug for HashSet<A, S>
808where
809    A: Hash + Eq + Debug,
810    S: BuildHasher,
811{
812    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
813        f.debug_set().entries(self.iter()).finish()
814    }
815}
816
817#[cfg(has_specialisation)]
818impl<A, S> Debug for HashSet<A, S>
819where
820    A: Hash + Eq + Debug,
821    S: BuildHasher,
822{
823    default fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
824        f.debug_set().entries(self.iter()).finish()
825    }
826}
827
828#[cfg(has_specialisation)]
829impl<A, S> Debug for HashSet<A, S>
830where
831    A: Hash + Eq + Debug + Ord,
832    S: BuildHasher,
833{
834    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
835        f.debug_set().entries(self.iter()).finish()
836    }
837}
838
839// Iterators
840
841/// An iterator over the elements of a set.
842pub struct Iter<'a, A> {
843    it: NodeIter<'a, Value<A>>,
844}
845
846impl<'a, A> Iterator for Iter<'a, A>
847where
848    A: 'a,
849{
850    type Item = &'a A;
851
852    fn next(&mut self) -> Option<Self::Item> {
853        self.it.next().map(|(v, _)| &v.0)
854    }
855
856    fn size_hint(&self) -> (usize, Option<usize>) {
857        self.it.size_hint()
858    }
859}
860
861impl<'a, A> ExactSizeIterator for Iter<'a, A> {}
862
863impl<'a, A> FusedIterator for Iter<'a, A> {}
864
865/// A consuming iterator over the elements of a set.
866pub struct ConsumingIter<A>
867where
868    A: Hash + Eq + Clone,
869{
870    it: NodeDrain<Value<A>>,
871}
872
873impl<A> Iterator for ConsumingIter<A>
874where
875    A: Hash + Eq + Clone,
876{
877    type Item = A;
878
879    fn next(&mut self) -> Option<Self::Item> {
880        self.it.next().map(|(v, _)| v.0)
881    }
882
883    fn size_hint(&self) -> (usize, Option<usize>) {
884        self.it.size_hint()
885    }
886}
887
888impl<A> ExactSizeIterator for ConsumingIter<A> where A: Hash + Eq + Clone {}
889
890impl<A> FusedIterator for ConsumingIter<A> where A: Hash + Eq + Clone {}
891
892// Iterator conversions
893
894impl<A, RA, S> FromIterator<RA> for HashSet<A, S>
895where
896    A: Hash + Eq + Clone + From<RA>,
897    S: BuildHasher + Default,
898{
899    fn from_iter<T>(i: T) -> Self
900    where
901        T: IntoIterator<Item = RA>,
902    {
903        let mut set = Self::default();
904        for value in i {
905            set.insert(From::from(value));
906        }
907        set
908    }
909}
910
911impl<'a, A, S> IntoIterator for &'a HashSet<A, S>
912where
913    A: Hash + Eq,
914    S: BuildHasher,
915{
916    type Item = &'a A;
917    type IntoIter = Iter<'a, A>;
918
919    fn into_iter(self) -> Self::IntoIter {
920        self.iter()
921    }
922}
923
924impl<A, S> IntoIterator for HashSet<A, S>
925where
926    A: Hash + Eq + Clone,
927    S: BuildHasher,
928{
929    type Item = A;
930    type IntoIter = ConsumingIter<Self::Item>;
931
932    fn into_iter(self) -> Self::IntoIter {
933        ConsumingIter {
934            it: NodeDrain::new(&self.pool.0, self.root, self.size),
935        }
936    }
937}
938
939// Conversions
940
941impl<'s, 'a, A, OA, SA, SB> From<&'s HashSet<&'a A, SA>> for HashSet<OA, SB>
942where
943    A: ToOwned<Owned = OA> + Hash + Eq + ?Sized,
944    OA: Borrow<A> + Hash + Eq + Clone,
945    SA: BuildHasher,
946    SB: BuildHasher + Default,
947{
948    fn from(set: &HashSet<&A, SA>) -> Self {
949        set.iter().map(|a| (*a).to_owned()).collect()
950    }
951}
952
953impl<'a, A, S> From<&'a [A]> for HashSet<A, S>
954where
955    A: Hash + Eq + Clone,
956    S: BuildHasher + Default,
957{
958    fn from(slice: &'a [A]) -> Self {
959        slice.iter().cloned().collect()
960    }
961}
962
963impl<A, S> From<Vec<A>> for HashSet<A, S>
964where
965    A: Hash + Eq + Clone,
966    S: BuildHasher + Default,
967{
968    fn from(vec: Vec<A>) -> Self {
969        vec.into_iter().collect()
970    }
971}
972
973impl<'a, A, S> From<&'a Vec<A>> for HashSet<A, S>
974where
975    A: Hash + Eq + Clone,
976    S: BuildHasher + Default,
977{
978    fn from(vec: &Vec<A>) -> Self {
979        vec.iter().cloned().collect()
980    }
981}
982
983impl<A, S> From<Vector<A>> for HashSet<A, S>
984where
985    A: Hash + Eq + Clone,
986    S: BuildHasher + Default,
987{
988    fn from(vector: Vector<A>) -> Self {
989        vector.into_iter().collect()
990    }
991}
992
993impl<'a, A, S> From<&'a Vector<A>> for HashSet<A, S>
994where
995    A: Hash + Eq + Clone,
996    S: BuildHasher + Default,
997{
998    fn from(vector: &Vector<A>) -> Self {
999        vector.iter().cloned().collect()
1000    }
1001}
1002
1003impl<A, S> From<collections::HashSet<A>> for HashSet<A, S>
1004where
1005    A: Eq + Hash + Clone,
1006    S: BuildHasher + Default,
1007{
1008    fn from(hash_set: collections::HashSet<A>) -> Self {
1009        hash_set.into_iter().collect()
1010    }
1011}
1012
1013impl<'a, A, S> From<&'a collections::HashSet<A>> for HashSet<A, S>
1014where
1015    A: Eq + Hash + Clone,
1016    S: BuildHasher + Default,
1017{
1018    fn from(hash_set: &collections::HashSet<A>) -> Self {
1019        hash_set.iter().cloned().collect()
1020    }
1021}
1022
1023impl<'a, A, S> From<&'a BTreeSet<A>> for HashSet<A, S>
1024where
1025    A: Hash + Eq + Clone,
1026    S: BuildHasher + Default,
1027{
1028    fn from(btree_set: &BTreeSet<A>) -> Self {
1029        btree_set.iter().cloned().collect()
1030    }
1031}
1032
1033impl<A, S> From<OrdSet<A>> for HashSet<A, S>
1034where
1035    A: Ord + Hash + Eq + Clone,
1036    S: BuildHasher + Default,
1037{
1038    fn from(ordset: OrdSet<A>) -> Self {
1039        ordset.into_iter().collect()
1040    }
1041}
1042
1043impl<'a, A, S> From<&'a OrdSet<A>> for HashSet<A, S>
1044where
1045    A: Ord + Hash + Eq + Clone,
1046    S: BuildHasher + Default,
1047{
1048    fn from(ordset: &OrdSet<A>) -> Self {
1049        ordset.into_iter().cloned().collect()
1050    }
1051}
1052
1053// Proptest
1054#[cfg(any(test, feature = "proptest"))]
1055#[doc(hidden)]
1056pub mod proptest {
1057    #[deprecated(
1058        since = "14.3.0",
1059        note = "proptest strategies have moved to im::proptest"
1060    )]
1061    pub use crate::proptest::hash_set;
1062}
1063
1064#[cfg(test)]
1065mod test {
1066    use super::proptest::*;
1067    use super::*;
1068    use crate::test::LolHasher;
1069    use ::proptest::num::i16;
1070    use ::proptest::proptest;
1071    use std::hash::BuildHasherDefault;
1072
1073    #[test]
1074    fn insert_failing() {
1075        let mut set: HashSet<i16, BuildHasherDefault<LolHasher>> = Default::default();
1076        set.insert(14658);
1077        assert_eq!(1, set.len());
1078        set.insert(-19198);
1079        assert_eq!(2, set.len());
1080    }
1081
1082    #[test]
1083    fn match_strings_with_string_slices() {
1084        let mut set: HashSet<String> = From::from(&hashset!["foo", "bar"]);
1085        set = set.without("bar");
1086        assert!(!set.contains("bar"));
1087        set.remove("foo");
1088        assert!(!set.contains("foo"));
1089    }
1090
1091    #[test]
1092    fn macro_allows_trailing_comma() {
1093        let set1 = hashset! {"foo", "bar"};
1094        let set2 = hashset! {
1095            "foo",
1096            "bar",
1097        };
1098        assert_eq!(set1, set2);
1099    }
1100
1101    #[test]
1102    fn issue_60_drain_iterator_memory_corruption() {
1103        use crate::test::MetroHashBuilder;
1104        for i in 0..1000 {
1105            let mut lhs = vec![0, 1, 2];
1106            lhs.sort_unstable();
1107
1108            let hasher = Ref::from(MetroHashBuilder::new(i));
1109            let mut iset: HashSet<_, MetroHashBuilder> = HashSet::with_hasher(hasher.clone());
1110            for &i in &lhs {
1111                iset.insert(i);
1112            }
1113
1114            let mut rhs: Vec<_> = iset.clone().into_iter().collect();
1115            rhs.sort_unstable();
1116
1117            if lhs != rhs {
1118                println!("iteration: {}", i);
1119                println!("seed: {}", hasher.seed());
1120                println!("lhs: {}: {:?}", lhs.len(), &lhs);
1121                println!("rhs: {}: {:?}", rhs.len(), &rhs);
1122                panic!();
1123            }
1124        }
1125    }
1126
1127    proptest! {
1128        #[test]
1129        fn proptest_a_set(ref s in hash_set(".*", 10..100)) {
1130            assert!(s.len() < 100);
1131            assert!(s.len() >= 10);
1132        }
1133    }
1134}
im_rc/hash/set.rs

im_rc/hash/
set.rs
