indexmap/set/
iter.rs

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

indexmap/set/
iter.rs
