indexmap/set/
iter.rs

1use alloc::vec::{self, Vec};
2use core::{
3    fmt,
4    hash::{BuildHasher, Hash},
5    iter::{Chain, FusedIterator},
6    ops::RangeBounds,
7    slice::Iter as SliceIter,
8};
9
10use super::{Bucket, IndexSet, Slice};
11use crate::inner::{Core, ExtractCore};
12
13impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> {
14    type Item = &'a T;
15    type IntoIter = Iter<'a, T>;
16
17    fn into_iter(self) -> Self::IntoIter {
18        self.iter()
19    }
20}
21
22impl<T, S> IntoIterator for IndexSet<T, S> {
23    type Item = T;
24    type IntoIter = IntoIter<T>;
25
26    fn into_iter(self) -> Self::IntoIter {
27        IntoIter::new(self.into_entries())
28    }
29}
30
31/// An iterator over the items of an [`IndexSet`].
32///
33/// This `struct` is created by the [`IndexSet::iter`] method.
34/// See its documentation for more.
35pub struct Iter<'a, T> {
36    iter: SliceIter<'a, Bucket<T>>,
37}
38
39impl<'a, T> Iter<'a, T> {
40    pub(super) fn new(entries: &'a [Bucket<T>]) -> Self {
41        Self {
42            iter: entries.iter(),
43        }
44    }
45
46    /// Returns a slice of the remaining entries in the iterator.
47    pub fn as_slice(&self) -> &'a Slice<T> {
48        Slice::from_slice(self.iter.as_slice())
49    }
50}
51
52impl<'a, T> Iterator for Iter<'a, T> {
53    type Item = &'a T;
54
55    iterator_methods!(Bucket::key_ref);
56}
57
58impl<T> DoubleEndedIterator for Iter<'_, T> {
59    double_ended_iterator_methods!(Bucket::key_ref);
60}
61
62impl<T> ExactSizeIterator for Iter<'_, T> {
63    fn len(&self) -> usize {
64        self.iter.len()
65    }
66}
67
68impl<T> FusedIterator for Iter<'_, T> {}
69
70impl<T> Clone for Iter<'_, T> {
71    fn clone(&self) -> Self {
72        Iter {
73            iter: self.iter.clone(),
74        }
75    }
76}
77
78impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
79    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80        f.debug_list().entries(self.clone()).finish()
81    }
82}
83
84impl<T> Default for Iter<'_, T> {
85    fn default() -> Self {
86        Self {
87            iter: [].iter(),
88        }
89    }
90}
91
92/// An owning iterator over the items of an [`IndexSet`].
93///
94/// This `struct` is created by the [`IndexSet::into_iter`] method
95/// (provided by the [`IntoIterator`] trait). See its documentation for more.
96#[derive(Clone)]
97pub struct IntoIter<T> {
98    iter: vec::IntoIter<Bucket<T>>,
99}
100
101impl<T> IntoIter<T> {
102    pub(super) fn new(entries: Vec<Bucket<T>>) -> Self {
103        Self {
104            iter: entries.into_iter(),
105        }
106    }
107
108    /// Returns a slice of the remaining entries in the iterator.
109    pub fn as_slice(&self) -> &Slice<T> {
110        Slice::from_slice(self.iter.as_slice())
111    }
112}
113
114impl<T> Iterator for IntoIter<T> {
115    type Item = T;
116
117    iterator_methods!(Bucket::key);
118}
119
120impl<T> DoubleEndedIterator for IntoIter<T> {
121    double_ended_iterator_methods!(Bucket::key);
122}
123
124impl<T> ExactSizeIterator for IntoIter<T> {
125    fn len(&self) -> usize {
126        self.iter.len()
127    }
128}
129
130impl<T> FusedIterator for IntoIter<T> {}
131
132impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
133    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
134        let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
135        f.debug_list().entries(iter).finish()
136    }
137}
138
139impl<T> Default for IntoIter<T> {
140    fn default() -> Self {
141        Self {
142            iter: Vec::new().into_iter(),
143        }
144    }
145}
146
147/// A draining iterator over the items of an [`IndexSet`].
148///
149/// This `struct` is created by the [`IndexSet::drain`] method.
150/// See its documentation for more.
151pub struct Drain<'a, T> {
152    iter: vec::Drain<'a, Bucket<T>>,
153}
154
155impl<'a, T> Drain<'a, T> {
156    pub(super) fn new(iter: vec::Drain<'a, Bucket<T>>) -> Self {
157        Self {
158            iter,
159        }
160    }
161
162    /// Returns a slice of the remaining entries in the iterator.
163    pub fn as_slice(&self) -> &Slice<T> {
164        Slice::from_slice(self.iter.as_slice())
165    }
166}
167
168impl<T> Iterator for Drain<'_, T> {
169    type Item = T;
170
171    iterator_methods!(Bucket::key);
172}
173
174impl<T> DoubleEndedIterator for Drain<'_, T> {
175    double_ended_iterator_methods!(Bucket::key);
176}
177
178impl<T> ExactSizeIterator for Drain<'_, T> {
179    fn len(&self) -> usize {
180        self.iter.len()
181    }
182}
183
184impl<T> FusedIterator for Drain<'_, T> {}
185
186impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
187    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
188        let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
189        f.debug_list().entries(iter).finish()
190    }
191}
192
193/// A lazy iterator producing elements in the difference of [`IndexSet`]s.
194///
195/// This `struct` is created by the [`IndexSet::difference`] method.
196/// See its documentation for more.
197pub struct Difference<'a, T, S> {
198    iter: Iter<'a, T>,
199    other: &'a IndexSet<T, S>,
200}
201
202impl<'a, T, S> Difference<'a, T, S> {
203    pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
204        Self {
205            iter: set.iter(),
206            other,
207        }
208    }
209}
210
211impl<'a, T, S> Iterator for Difference<'a, T, S>
212where
213    T: Eq + Hash,
214    S: BuildHasher,
215{
216    type Item = &'a T;
217
218    fn next(&mut self) -> Option<Self::Item> {
219        while let Some(item) = self.iter.next() {
220            if !self.other.contains(item) {
221                return Some(item);
222            }
223        }
224        None
225    }
226
227    fn size_hint(&self) -> (usize, Option<usize>) {
228        (0, self.iter.size_hint().1)
229    }
230}
231
232impl<T, S> DoubleEndedIterator for Difference<'_, T, S>
233where
234    T: Eq + Hash,
235    S: BuildHasher,
236{
237    fn next_back(&mut self) -> Option<Self::Item> {
238        while let Some(item) = self.iter.next_back() {
239            if !self.other.contains(item) {
240                return Some(item);
241            }
242        }
243        None
244    }
245}
246
247impl<T, S> FusedIterator for Difference<'_, T, S>
248where
249    T: Eq + Hash,
250    S: BuildHasher,
251{
252}
253
254impl<T, S> Clone for Difference<'_, T, S> {
255    fn clone(&self) -> Self {
256        Difference {
257            iter: self.iter.clone(),
258            ..*self
259        }
260    }
261}
262
263impl<T, S> fmt::Debug for Difference<'_, T, S>
264where
265    T: fmt::Debug + Eq + Hash,
266    S: BuildHasher,
267{
268    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
269        f.debug_list().entries(self.clone()).finish()
270    }
271}
272
273/// A lazy iterator producing elements in the intersection of [`IndexSet`]s.
274///
275/// This `struct` is created by the [`IndexSet::intersection`] method.
276/// See its documentation for more.
277pub struct Intersection<'a, T, S> {
278    iter: Iter<'a, T>,
279    other: &'a IndexSet<T, S>,
280}
281
282impl<'a, T, S> Intersection<'a, T, S> {
283    pub(super) fn new<S1>(set: &'a IndexSet<T, S1>, other: &'a IndexSet<T, S>) -> Self {
284        Self {
285            iter: set.iter(),
286            other,
287        }
288    }
289}
290
291impl<'a, T, S> Iterator for Intersection<'a, T, S>
292where
293    T: Eq + Hash,
294    S: BuildHasher,
295{
296    type Item = &'a T;
297
298    fn next(&mut self) -> Option<Self::Item> {
299        while let Some(item) = self.iter.next() {
300            if self.other.contains(item) {
301                return Some(item);
302            }
303        }
304        None
305    }
306
307    fn size_hint(&self) -> (usize, Option<usize>) {
308        (0, self.iter.size_hint().1)
309    }
310}
311
312impl<T, S> DoubleEndedIterator for Intersection<'_, T, S>
313where
314    T: Eq + Hash,
315    S: BuildHasher,
316{
317    fn next_back(&mut self) -> Option<Self::Item> {
318        while let Some(item) = self.iter.next_back() {
319            if self.other.contains(item) {
320                return Some(item);
321            }
322        }
323        None
324    }
325}
326
327impl<T, S> FusedIterator for Intersection<'_, T, S>
328where
329    T: Eq + Hash,
330    S: BuildHasher,
331{
332}
333
334impl<T, S> Clone for Intersection<'_, T, S> {
335    fn clone(&self) -> Self {
336        Intersection {
337            iter: self.iter.clone(),
338            ..*self
339        }
340    }
341}
342
343impl<T, S> fmt::Debug for Intersection<'_, T, S>
344where
345    T: fmt::Debug + Eq + Hash,
346    S: BuildHasher,
347{
348    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
349        f.debug_list().entries(self.clone()).finish()
350    }
351}
352
353/// A lazy iterator producing elements in the symmetric difference of [`IndexSet`]s.
354///
355/// This `struct` is created by the [`IndexSet::symmetric_difference`] method.
356/// See its documentation for more.
357pub struct SymmetricDifference<'a, T, S1, S2> {
358    iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>,
359}
360
361impl<'a, T, S1, S2> SymmetricDifference<'a, T, S1, S2>
362where
363    T: Eq + Hash,
364    S1: BuildHasher,
365    S2: BuildHasher,
366{
367    pub(super) fn new(set1: &'a IndexSet<T, S1>, set2: &'a IndexSet<T, S2>) -> Self {
368        let diff1 = set1.difference(set2);
369        let diff2 = set2.difference(set1);
370        Self {
371            iter: diff1.chain(diff2),
372        }
373    }
374}
375
376impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2>
377where
378    T: Eq + Hash,
379    S1: BuildHasher,
380    S2: BuildHasher,
381{
382    type Item = &'a T;
383
384    fn next(&mut self) -> Option<Self::Item> {
385        self.iter.next()
386    }
387
388    fn size_hint(&self) -> (usize, Option<usize>) {
389        self.iter.size_hint()
390    }
391
392    fn fold<B, F>(self, init: B, f: F) -> B
393    where
394        F: FnMut(B, Self::Item) -> B,
395    {
396        self.iter.fold(init, f)
397    }
398}
399
400impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2>
401where
402    T: Eq + Hash,
403    S1: BuildHasher,
404    S2: BuildHasher,
405{
406    fn next_back(&mut self) -> Option<Self::Item> {
407        self.iter.next_back()
408    }
409
410    fn rfold<B, F>(self, init: B, f: F) -> B
411    where
412        F: FnMut(B, Self::Item) -> B,
413    {
414        self.iter.rfold(init, f)
415    }
416}
417
418impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2>
419where
420    T: Eq + Hash,
421    S1: BuildHasher,
422    S2: BuildHasher,
423{
424}
425
426impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> {
427    fn clone(&self) -> Self {
428        SymmetricDifference {
429            iter: self.iter.clone(),
430        }
431    }
432}
433
434impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2>
435where
436    T: fmt::Debug + Eq + Hash,
437    S1: BuildHasher,
438    S2: BuildHasher,
439{
440    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
441        f.debug_list().entries(self.clone()).finish()
442    }
443}
444
445/// A lazy iterator producing elements in the union of [`IndexSet`]s.
446///
447/// This `struct` is created by the [`IndexSet::union`] method.
448/// See its documentation for more.
449pub struct Union<'a, T, S> {
450    iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
451}
452
453impl<'a, T, S> Union<'a, T, S>
454where
455    T: Eq + Hash,
456    S: BuildHasher,
457{
458    pub(super) fn new<S2>(set1: &'a IndexSet<T, S>, set2: &'a IndexSet<T, S2>) -> Self
459    where
460        S2: BuildHasher,
461    {
462        Self {
463            iter: set1.iter().chain(set2.difference(set1)),
464        }
465    }
466}
467
468impl<'a, T, S> Iterator for Union<'a, T, S>
469where
470    T: Eq + Hash,
471    S: BuildHasher,
472{
473    type Item = &'a T;
474
475    fn next(&mut self) -> Option<Self::Item> {
476        self.iter.next()
477    }
478
479    fn size_hint(&self) -> (usize, Option<usize>) {
480        self.iter.size_hint()
481    }
482
483    fn fold<B, F>(self, init: B, f: F) -> B
484    where
485        F: FnMut(B, Self::Item) -> B,
486    {
487        self.iter.fold(init, f)
488    }
489}
490
491impl<T, S> DoubleEndedIterator for Union<'_, T, S>
492where
493    T: Eq + Hash,
494    S: BuildHasher,
495{
496    fn next_back(&mut self) -> Option<Self::Item> {
497        self.iter.next_back()
498    }
499
500    fn rfold<B, F>(self, init: B, f: F) -> B
501    where
502        F: FnMut(B, Self::Item) -> B,
503    {
504        self.iter.rfold(init, f)
505    }
506}
507
508impl<T, S> FusedIterator for Union<'_, T, S>
509where
510    T: Eq + Hash,
511    S: BuildHasher,
512{
513}
514
515impl<T, S> Clone for Union<'_, T, S> {
516    fn clone(&self) -> Self {
517        Union {
518            iter: self.iter.clone(),
519        }
520    }
521}
522
523impl<T, S> fmt::Debug for Union<'_, T, S>
524where
525    T: fmt::Debug + Eq + Hash,
526    S: BuildHasher,
527{
528    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
529        f.debug_list().entries(self.clone()).finish()
530    }
531}
532
533/// A splicing iterator for `IndexSet`.
534///
535/// This `struct` is created by [`IndexSet::splice()`].
536/// See its documentation for more.
537pub struct Splice<'a, I, T, S>
538where
539    I: Iterator<Item = T>,
540    T: Hash + Eq,
541    S: BuildHasher,
542{
543    iter: crate::map::Splice<'a, UnitValue<I>, T, (), S>,
544}
545
546impl<'a, I, T, S> Splice<'a, I, T, S>
547where
548    I: Iterator<Item = T>,
549    T: Hash + Eq,
550    S: BuildHasher,
551{
552    #[track_caller]
553    pub(super) fn new<R>(set: &'a mut IndexSet<T, S>, range: R, replace_with: I) -> Self
554    where
555        R: RangeBounds<usize>,
556    {
557        Self {
558            iter: set.map.splice(range, UnitValue(replace_with)),
559        }
560    }
561}
562
563impl<I, T, S> Iterator for Splice<'_, I, T, S>
564where
565    I: Iterator<Item = T>,
566    T: Hash + Eq,
567    S: BuildHasher,
568{
569    type Item = T;
570
571    fn next(&mut self) -> Option<Self::Item> {
572        Some(self.iter.next()?.0)
573    }
574
575    fn size_hint(&self) -> (usize, Option<usize>) {
576        self.iter.size_hint()
577    }
578}
579
580impl<I, T, S> DoubleEndedIterator for Splice<'_, I, T, S>
581where
582    I: Iterator<Item = T>,
583    T: Hash + Eq,
584    S: BuildHasher,
585{
586    fn next_back(&mut self) -> Option<Self::Item> {
587        Some(self.iter.next_back()?.0)
588    }
589}
590
591impl<I, T, S> ExactSizeIterator for Splice<'_, I, T, S>
592where
593    I: Iterator<Item = T>,
594    T: Hash + Eq,
595    S: BuildHasher,
596{
597    fn len(&self) -> usize {
598        self.iter.len()
599    }
600}
601
602impl<I, T, S> FusedIterator for Splice<'_, I, T, S>
603where
604    I: Iterator<Item = T>,
605    T: Hash + Eq,
606    S: BuildHasher,
607{
608}
609
610struct UnitValue<I>(I);
611
612impl<I: Iterator> Iterator for UnitValue<I> {
613    type Item = (I::Item, ());
614
615    fn next(&mut self) -> Option<Self::Item> {
616        self.0.next().map(|x| (x, ()))
617    }
618}
619
620impl<I, T, S> fmt::Debug for Splice<'_, I, T, S>
621where
622    I: fmt::Debug + Iterator<Item = T>,
623    T: fmt::Debug + Hash + Eq,
624    S: BuildHasher,
625{
626    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
627        fmt::Debug::fmt(&self.iter, f)
628    }
629}
630
631impl<I: fmt::Debug> fmt::Debug for UnitValue<I> {
632    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
633        fmt::Debug::fmt(&self.0, f)
634    }
635}
636
637/// An extracting iterator for `IndexSet`.
638///
639/// This `struct` is created by [`IndexSet::extract_if()`].
640/// See its documentation for more.
641pub struct ExtractIf<'a, T, F> {
642    inner: ExtractCore<'a, T, ()>,
643    pred: F,
644}
645
646impl<T, F> ExtractIf<'_, T, F> {
647    #[track_caller]
648    pub(super) fn new<R>(core: &mut Core<T, ()>, range: R, pred: F) -> ExtractIf<'_, T, F>
649    where
650        R: RangeBounds<usize>,
651        F: FnMut(&T) -> bool,
652    {
653        ExtractIf {
654            inner: core.extract(range),
655            pred,
656        }
657    }
658}
659
660impl<T, F> Iterator for ExtractIf<'_, T, F>
661where
662    F: FnMut(&T) -> bool,
663{
664    type Item = T;
665
666    fn next(&mut self) -> Option<Self::Item> {
667        self.inner
668            .extract_if(|bucket| (self.pred)(bucket.key_ref()))
669            .map(Bucket::key)
670    }
671
672    fn size_hint(&self) -> (usize, Option<usize>) {
673        (0, Some(self.inner.remaining()))
674    }
675}
676
677impl<T, F> FusedIterator for ExtractIf<'_, T, F> where F: FnMut(&T) -> bool {}
678
679impl<T, F> fmt::Debug for ExtractIf<'_, T, F>
680where
681    T: fmt::Debug,
682{
683    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
684        f.debug_struct("ExtractIf").finish_non_exhaustive()
685    }
686}
indexmap/set/iter.rs

indexmap/set/
iter.rs
