indexmap/set/
iter.rs

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

indexmap/set/
iter.rs
