indexmap/set/
iter.rs

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

indexmap/set/
iter.rs
