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

hashlink/
linked_hash_set.rs
