hashlink/
linked_hash_set.rs

1use core::{
2    borrow::Borrow,
3    fmt,
4    hash::{BuildHasher, Hash, Hasher},
5    iter::{Chain, FromIterator},
6    ops::{BitAnd, BitOr, BitXor, Sub},
7};
8
9use hashbrown::hash_map::DefaultHashBuilder;
10
11use crate::linked_hash_map::{self, LinkedHashMap, TryReserveError};
12
13pub struct LinkedHashSet<T, S = DefaultHashBuilder> {
14    map: LinkedHashMap<T, (), S>,
15}
16
17impl<T: Hash + Eq> LinkedHashSet<T, DefaultHashBuilder> {
18    #[inline]
19    pub fn new() -> LinkedHashSet<T, DefaultHashBuilder> {
20        LinkedHashSet {
21            map: LinkedHashMap::new(),
22        }
23    }
24
25    #[inline]
26    pub fn with_capacity(capacity: usize) -> LinkedHashSet<T, DefaultHashBuilder> {
27        LinkedHashSet {
28            map: LinkedHashMap::with_capacity(capacity),
29        }
30    }
31}
32
33impl<T, S> LinkedHashSet<T, S> {
34    #[inline]
35    pub fn capacity(&self) -> usize {
36        self.map.capacity()
37    }
38
39    #[inline]
40    pub fn iter(&self) -> Iter<'_, T> {
41        Iter {
42            iter: self.map.keys(),
43        }
44    }
45
46    #[inline]
47    pub fn len(&self) -> usize {
48        self.map.len()
49    }
50
51    #[inline]
52    pub fn is_empty(&self) -> bool {
53        self.map.is_empty()
54    }
55
56    #[inline]
57    pub fn drain(&mut self) -> Drain<T> {
58        Drain {
59            iter: self.map.drain(),
60        }
61    }
62
63    #[inline]
64    pub fn clear(&mut self) {
65        self.map.clear()
66    }
67
68    #[inline]
69    pub fn retain<F>(&mut self, mut f: F)
70    where
71        F: FnMut(&T) -> bool,
72    {
73        self.map.retain(|k, _| f(k));
74    }
75}
76
77impl<T, S> LinkedHashSet<T, S>
78where
79    T: Eq + Hash,
80    S: BuildHasher,
81{
82    #[inline]
83    pub fn with_hasher(hasher: S) -> LinkedHashSet<T, S> {
84        LinkedHashSet {
85            map: LinkedHashMap::with_hasher(hasher),
86        }
87    }
88
89    #[inline]
90    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> LinkedHashSet<T, S> {
91        LinkedHashSet {
92            map: LinkedHashMap::with_capacity_and_hasher(capacity, hasher),
93        }
94    }
95
96    #[inline]
97    pub fn hasher(&self) -> &S {
98        self.map.hasher()
99    }
100
101    #[inline]
102    pub fn reserve(&mut self, additional: usize) {
103        self.map.reserve(additional)
104    }
105
106    #[inline]
107    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
108        self.map.try_reserve(additional)
109    }
110
111    #[inline]
112    pub fn shrink_to_fit(&mut self) {
113        self.map.shrink_to_fit()
114    }
115
116    #[inline]
117    pub fn difference<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Difference<'a, T, S> {
118        Difference {
119            iter: self.iter(),
120            other,
121        }
122    }
123
124    #[inline]
125    pub fn symmetric_difference<'a>(
126        &'a self,
127        other: &'a LinkedHashSet<T, S>,
128    ) -> SymmetricDifference<'a, T, S> {
129        SymmetricDifference {
130            iter: self.difference(other).chain(other.difference(self)),
131        }
132    }
133
134    #[inline]
135    pub fn intersection<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Intersection<'a, T, S> {
136        Intersection {
137            iter: self.iter(),
138            other,
139        }
140    }
141
142    #[inline]
143    pub fn union<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Union<'a, T, S> {
144        Union {
145            iter: self.iter().chain(other.difference(self)),
146        }
147    }
148
149    #[inline]
150    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
151    where
152        T: Borrow<Q>,
153        Q: Hash + Eq,
154    {
155        self.map.contains_key(value)
156    }
157
158    #[inline]
159    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
160    where
161        T: Borrow<Q>,
162        Q: Hash + Eq,
163    {
164        self.map.raw_entry().from_key(value).map(|p| p.0)
165    }
166
167    #[inline]
168    pub fn get_or_insert(&mut self, value: T) -> &T {
169        self.map
170            .raw_entry_mut()
171            .from_key(&value)
172            .or_insert(value, ())
173            .0
174    }
175
176    #[inline]
177    pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
178    where
179        T: Borrow<Q>,
180        Q: Hash + Eq,
181        F: FnOnce(&Q) -> T,
182    {
183        self.map
184            .raw_entry_mut()
185            .from_key(value)
186            .or_insert_with(|| (f(value), ()))
187            .0
188    }
189
190    #[inline]
191    pub fn is_disjoint(&self, other: &LinkedHashSet<T, S>) -> bool {
192        self.iter().all(|v| !other.contains(v))
193    }
194
195    #[inline]
196    pub fn is_subset(&self, other: &LinkedHashSet<T, S>) -> bool {
197        self.iter().all(|v| other.contains(v))
198    }
199
200    #[inline]
201    pub fn is_superset(&self, other: &LinkedHashSet<T, S>) -> bool {
202        other.is_subset(self)
203    }
204
205    /// Inserts the given value into the set.
206    ///
207    /// If the set did not have this value present, inserts it at the *back* of the internal linked
208    /// list and returns true, otherwise it moves the existing value to the *back* of the internal
209    /// linked list and returns false.
210    #[inline]
211    pub fn insert(&mut self, value: T) -> bool {
212        self.map.insert(value, ()).is_none()
213    }
214
215    /// Adds the given value to the set, replacing the existing value.
216    ///
217    /// If a previous value existed, returns the replaced value.  In this case, the value's position
218    /// in the internal linked list is *not* changed.
219    #[inline]
220    pub fn replace(&mut self, value: T) -> Option<T> {
221        match self.map.entry(value) {
222            linked_hash_map::Entry::Occupied(occupied) => Some(occupied.replace_key()),
223            linked_hash_map::Entry::Vacant(vacant) => {
224                vacant.insert(());
225                None
226            }
227        }
228    }
229
230    #[inline]
231    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
232    where
233        T: Borrow<Q>,
234        Q: Hash + Eq,
235    {
236        self.map.remove(value).is_some()
237    }
238
239    #[inline]
240    pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
241    where
242        T: Borrow<Q>,
243        Q: Hash + Eq,
244    {
245        match self.map.raw_entry_mut().from_key(value) {
246            linked_hash_map::RawEntryMut::Occupied(occupied) => Some(occupied.remove_entry().0),
247            linked_hash_map::RawEntryMut::Vacant(_) => None,
248        }
249    }
250
251    #[inline]
252    pub fn front(&self) -> Option<&T> {
253        self.map.front().map(|(k, _)| k)
254    }
255
256    #[inline]
257    pub fn pop_front(&mut self) -> Option<T> {
258        self.map.pop_front().map(|(k, _)| k)
259    }
260
261    #[inline]
262    pub fn back(&self) -> Option<&T> {
263        self.map.back().map(|(k, _)| k)
264    }
265
266    #[inline]
267    pub fn pop_back(&mut self) -> Option<T> {
268        self.map.pop_back().map(|(k, _)| k)
269    }
270
271    #[inline]
272    pub fn to_front<Q: ?Sized>(&mut self, value: &Q) -> bool
273    where
274        T: Borrow<Q>,
275        Q: Hash + Eq,
276    {
277        match self.map.raw_entry_mut().from_key(value) {
278            linked_hash_map::RawEntryMut::Occupied(mut occupied) => {
279                occupied.to_front();
280                true
281            }
282            linked_hash_map::RawEntryMut::Vacant(_) => false,
283        }
284    }
285
286    #[inline]
287    pub fn to_back<Q: ?Sized>(&mut self, value: &Q) -> bool
288    where
289        T: Borrow<Q>,
290        Q: Hash + Eq,
291    {
292        match self.map.raw_entry_mut().from_key(value) {
293            linked_hash_map::RawEntryMut::Occupied(mut occupied) => {
294                occupied.to_back();
295                true
296            }
297            linked_hash_map::RawEntryMut::Vacant(_) => false,
298        }
299    }
300
301    #[inline]
302    pub fn retain_with_order<F>(&mut self, mut f: F)
303    where
304        F: FnMut(&T) -> bool,
305    {
306        self.map.retain_with_order(|k, _| f(k));
307    }
308}
309
310impl<T: Hash + Eq + Clone, S: BuildHasher + Clone> Clone for LinkedHashSet<T, S> {
311    #[inline]
312    fn clone(&self) -> Self {
313        let map = self.map.clone();
314        Self { map }
315    }
316}
317
318impl<T, S> PartialEq for LinkedHashSet<T, S>
319where
320    T: Eq + Hash,
321    S: BuildHasher,
322{
323    #[inline]
324    fn eq(&self, other: &Self) -> bool {
325        self.len() == other.len() && self.iter().eq(other)
326    }
327}
328
329impl<T, S> Hash for LinkedHashSet<T, S>
330where
331    T: Eq + Hash,
332    S: BuildHasher,
333{
334    #[inline]
335    fn hash<H: Hasher>(&self, state: &mut H) {
336        for e in self {
337            e.hash(state);
338        }
339    }
340}
341
342impl<T, S> Eq for LinkedHashSet<T, S>
343where
344    T: Eq + Hash,
345    S: BuildHasher,
346{
347}
348
349impl<T, S> fmt::Debug for LinkedHashSet<T, S>
350where
351    T: fmt::Debug,
352{
353    #[inline]
354    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
355        f.debug_set().entries(self.iter()).finish()
356    }
357}
358
359impl<T, S> FromIterator<T> for LinkedHashSet<T, S>
360where
361    T: Eq + Hash,
362    S: BuildHasher + Default,
363{
364    #[inline]
365    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> LinkedHashSet<T, S> {
366        let mut set = LinkedHashSet::with_hasher(Default::default());
367        set.extend(iter);
368        set
369    }
370}
371
372impl<T, S> Extend<T> for LinkedHashSet<T, S>
373where
374    T: Eq + Hash,
375    S: BuildHasher,
376{
377    #[inline]
378    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
379        self.map.extend(iter.into_iter().map(|k| (k, ())));
380    }
381}
382
383impl<'a, T, S> Extend<&'a T> for LinkedHashSet<T, S>
384where
385    T: 'a + Eq + Hash + Copy,
386    S: BuildHasher,
387{
388    #[inline]
389    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
390        self.extend(iter.into_iter().cloned());
391    }
392}
393
394impl<T, S> Default for LinkedHashSet<T, S>
395where
396    S: Default,
397{
398    #[inline]
399    fn default() -> LinkedHashSet<T, S> {
400        LinkedHashSet {
401            map: LinkedHashMap::default(),
402        }
403    }
404}
405
406impl<'a, 'b, T, S> BitOr<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
407where
408    T: Eq + Hash + Clone,
409    S: BuildHasher + Default,
410{
411    type Output = LinkedHashSet<T, S>;
412
413    #[inline]
414    fn bitor(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
415        self.union(rhs).cloned().collect()
416    }
417}
418
419impl<'a, 'b, T, S> BitAnd<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
420where
421    T: Eq + Hash + Clone,
422    S: BuildHasher + Default,
423{
424    type Output = LinkedHashSet<T, S>;
425
426    #[inline]
427    fn bitand(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
428        self.intersection(rhs).cloned().collect()
429    }
430}
431
432impl<'a, 'b, T, S> BitXor<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
433where
434    T: Eq + Hash + Clone,
435    S: BuildHasher + Default,
436{
437    type Output = LinkedHashSet<T, S>;
438
439    #[inline]
440    fn bitxor(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
441        self.symmetric_difference(rhs).cloned().collect()
442    }
443}
444
445impl<'a, 'b, T, S> Sub<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
446where
447    T: Eq + Hash + Clone,
448    S: BuildHasher + Default,
449{
450    type Output = LinkedHashSet<T, S>;
451
452    #[inline]
453    fn sub(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
454        self.difference(rhs).cloned().collect()
455    }
456}
457
458pub struct Iter<'a, K> {
459    iter: linked_hash_map::Keys<'a, K, ()>,
460}
461
462pub struct IntoIter<K> {
463    iter: linked_hash_map::IntoIter<K, ()>,
464}
465
466pub struct Drain<'a, K: 'a> {
467    iter: linked_hash_map::Drain<'a, K, ()>,
468}
469
470pub struct Intersection<'a, T, S> {
471    iter: Iter<'a, T>,
472    other: &'a LinkedHashSet<T, S>,
473}
474
475pub struct Difference<'a, T, S> {
476    iter: Iter<'a, T>,
477    other: &'a LinkedHashSet<T, S>,
478}
479
480pub struct SymmetricDifference<'a, T, S> {
481    iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
482}
483
484pub struct Union<'a, T, S> {
485    iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
486}
487
488impl<'a, T, S> IntoIterator for &'a LinkedHashSet<T, S> {
489    type Item = &'a T;
490    type IntoIter = Iter<'a, T>;
491
492    #[inline]
493    fn into_iter(self) -> Iter<'a, T> {
494        self.iter()
495    }
496}
497
498impl<T, S> IntoIterator for LinkedHashSet<T, S> {
499    type Item = T;
500    type IntoIter = IntoIter<T>;
501
502    #[inline]
503    fn into_iter(self) -> IntoIter<T> {
504        IntoIter {
505            iter: self.map.into_iter(),
506        }
507    }
508}
509
510impl<'a, K> Clone for Iter<'a, K> {
511    #[inline]
512    fn clone(&self) -> Iter<'a, K> {
513        Iter {
514            iter: self.iter.clone(),
515        }
516    }
517}
518impl<'a, K> Iterator for Iter<'a, K> {
519    type Item = &'a K;
520
521    #[inline]
522    fn next(&mut self) -> Option<&'a K> {
523        self.iter.next()
524    }
525
526    #[inline]
527    fn size_hint(&self) -> (usize, Option<usize>) {
528        self.iter.size_hint()
529    }
530}
531
532impl<'a, K> ExactSizeIterator for Iter<'a, K> {}
533
534impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
535    #[inline]
536    fn next_back(&mut self) -> Option<&'a T> {
537        self.iter.next_back()
538    }
539}
540
541impl<'a, K: fmt::Debug> fmt::Debug for Iter<'a, K> {
542    #[inline]
543    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
544        f.debug_list().entries(self.clone()).finish()
545    }
546}
547
548impl<K> Iterator for IntoIter<K> {
549    type Item = K;
550
551    #[inline]
552    fn next(&mut self) -> Option<K> {
553        self.iter.next().map(|(k, _)| k)
554    }
555
556    #[inline]
557    fn size_hint(&self) -> (usize, Option<usize>) {
558        self.iter.size_hint()
559    }
560}
561
562impl<K> ExactSizeIterator for IntoIter<K> {}
563
564impl<K> DoubleEndedIterator for IntoIter<K> {
565    #[inline]
566    fn next_back(&mut self) -> Option<K> {
567        self.iter.next_back().map(|(k, _)| k)
568    }
569}
570
571impl<'a, K> Iterator for Drain<'a, K> {
572    type Item = K;
573
574    #[inline]
575    fn next(&mut self) -> Option<K> {
576        self.iter.next().map(|(k, _)| k)
577    }
578
579    #[inline]
580    fn size_hint(&self) -> (usize, Option<usize>) {
581        self.iter.size_hint()
582    }
583}
584
585impl<'a, K> DoubleEndedIterator for Drain<'a, K> {
586    #[inline]
587    fn next_back(&mut self) -> Option<K> {
588        self.iter.next_back().map(|(k, _)| k)
589    }
590}
591
592impl<'a, K> ExactSizeIterator for Drain<'a, K> {}
593
594impl<'a, T, S> Clone for Intersection<'a, T, S> {
595    #[inline]
596    fn clone(&self) -> Intersection<'a, T, S> {
597        Intersection {
598            iter: self.iter.clone(),
599            ..*self
600        }
601    }
602}
603
604impl<'a, T, S> Iterator for Intersection<'a, T, S>
605where
606    T: Eq + Hash,
607    S: BuildHasher,
608{
609    type Item = &'a T;
610
611    #[inline]
612    fn next(&mut self) -> Option<&'a T> {
613        loop {
614            match self.iter.next() {
615                None => return None,
616                Some(elt) => {
617                    if self.other.contains(elt) {
618                        return Some(elt);
619                    }
620                }
621            }
622        }
623    }
624
625    #[inline]
626    fn size_hint(&self) -> (usize, Option<usize>) {
627        let (_, upper) = self.iter.size_hint();
628        (0, upper)
629    }
630}
631
632impl<'a, T, S> fmt::Debug for Intersection<'a, T, S>
633where
634    T: fmt::Debug + Eq + Hash,
635    S: BuildHasher,
636{
637    #[inline]
638    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
639        f.debug_list().entries(self.clone()).finish()
640    }
641}
642
643impl<'a, T, S> Clone for Difference<'a, T, S> {
644    #[inline]
645    fn clone(&self) -> Difference<'a, T, S> {
646        Difference {
647            iter: self.iter.clone(),
648            ..*self
649        }
650    }
651}
652
653impl<'a, T, S> Iterator for Difference<'a, T, S>
654where
655    T: Eq + Hash,
656    S: BuildHasher,
657{
658    type Item = &'a T;
659
660    #[inline]
661    fn next(&mut self) -> Option<&'a T> {
662        loop {
663            match self.iter.next() {
664                None => return None,
665                Some(elt) => {
666                    if !self.other.contains(elt) {
667                        return Some(elt);
668                    }
669                }
670            }
671        }
672    }
673
674    #[inline]
675    fn size_hint(&self) -> (usize, Option<usize>) {
676        let (_, upper) = self.iter.size_hint();
677        (0, upper)
678    }
679}
680
681impl<'a, T, S> fmt::Debug for Difference<'a, T, S>
682where
683    T: fmt::Debug + Eq + Hash,
684    S: BuildHasher,
685{
686    #[inline]
687    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
688        f.debug_list().entries(self.clone()).finish()
689    }
690}
691
692impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
693    #[inline]
694    fn clone(&self) -> SymmetricDifference<'a, T, S> {
695        SymmetricDifference {
696            iter: self.iter.clone(),
697        }
698    }
699}
700
701impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
702where
703    T: Eq + Hash,
704    S: BuildHasher,
705{
706    type Item = &'a T;
707
708    #[inline]
709    fn next(&mut self) -> Option<&'a T> {
710        self.iter.next()
711    }
712
713    #[inline]
714    fn size_hint(&self) -> (usize, Option<usize>) {
715        self.iter.size_hint()
716    }
717}
718
719impl<'a, T, S> fmt::Debug for SymmetricDifference<'a, T, S>
720where
721    T: fmt::Debug + Eq + Hash,
722    S: BuildHasher,
723{
724    #[inline]
725    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
726        f.debug_list().entries(self.clone()).finish()
727    }
728}
729
730impl<'a, T, S> Clone for Union<'a, T, S> {
731    #[inline]
732    fn clone(&self) -> Union<'a, T, S> {
733        Union {
734            iter: self.iter.clone(),
735        }
736    }
737}
738
739impl<'a, T, S> fmt::Debug for Union<'a, T, S>
740where
741    T: fmt::Debug + Eq + Hash,
742    S: BuildHasher,
743{
744    #[inline]
745    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
746        f.debug_list().entries(self.clone()).finish()
747    }
748}
749
750impl<'a, T, S> Iterator for Union<'a, T, S>
751where
752    T: Eq + Hash,
753    S: BuildHasher,
754{
755    type Item = &'a T;
756
757    #[inline]
758    fn next(&mut self) -> Option<&'a T> {
759        self.iter.next()
760    }
761
762    #[inline]
763    fn size_hint(&self) -> (usize, Option<usize>) {
764        self.iter.size_hint()
765    }
766}
hashlink/linked_hash_set.rs

hashlink/
linked_hash_set.rs
