indexmap/set/
iter.rs

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