vecmap/set/
iter.rs

1use super::{Entries, Slot, VecSet};
2use crate::map;
3use alloc::vec::{self, Vec};
4use core::fmt;
5use core::iter::{Chain, FusedIterator};
6use core::ops::RangeBounds;
7use core::slice;
8
9macro_rules! impl_iterator {
10    ($ty:ident<$($lt:lifetime,)*$($gen:ident),+>, $item:ty, $map:expr) => {
11        impl_iterator!($ty<$($lt,)*$($gen),+>, $item, $map, $map);
12    };
13    ($ty:ident<$($lt:lifetime,)*$($gen:ident),+>, $item:ty, $map:expr, $debug_map:expr) => {
14        impl<$($lt,)*$($gen),+> Iterator for $ty<$($lt,)*$($gen),+> {
15            type Item = $item;
16
17            fn next(&mut self) -> Option<Self::Item> {
18                self.iter.next().map($map)
19            }
20
21            fn size_hint(&self) -> (usize, Option<usize>) {
22                self.iter.size_hint()
23            }
24        }
25
26        impl<$($lt,)*$($gen),+> DoubleEndedIterator for $ty<$($lt,)*$($gen),+> {
27            fn next_back(&mut self) -> Option<Self::Item> {
28                self.iter.next_back().map($map)
29            }
30        }
31
32        impl<$($lt,)*$($gen),+> ExactSizeIterator for $ty<$($lt,)*$($gen),+> {
33            fn len(&self) -> usize {
34                self.iter.len()
35            }
36        }
37
38        impl<$($lt,)*$($gen),+> FusedIterator for $ty<$($lt,)*$($gen),+> {}
39
40        impl<$($lt,)*$($gen),+> fmt::Debug for $ty<$($lt,)*$($gen),+>
41        where
42            T: fmt::Debug,
43        {
44            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
45                let iter = self.iter.as_slice().iter().map($debug_map);
46                f.debug_list().entries(iter).finish()
47            }
48        }
49    };
50}
51
52impl<T> IntoIterator for VecSet<T> {
53    type Item = T;
54
55    type IntoIter = IntoIter<T>;
56
57    fn into_iter(self) -> Self::IntoIter {
58        IntoIter::new(self.into_entries())
59    }
60}
61
62impl<'a, T> IntoIterator for &'a VecSet<T> {
63    type Item = &'a T;
64
65    type IntoIter = Iter<'a, T>;
66
67    fn into_iter(self) -> Self::IntoIter {
68        self.iter()
69    }
70}
71
72/// An iterator over the elements of a `VecSet`.
73///
74/// This `struct` is created by the [`iter`] method on [`VecSet`]. See its documentation for more.
75///
76/// [`iter`]: VecSet::iter
77pub struct Iter<'a, T> {
78    iter: slice::Iter<'a, Slot<T, ()>>,
79}
80
81impl<'a, T> Iter<'a, T> {
82    pub(super) fn new(entries: &'a [Slot<T, ()>]) -> Iter<'a, T> {
83        Iter {
84            iter: entries.iter(),
85        }
86    }
87}
88
89impl<T> Clone for Iter<'_, T> {
90    fn clone(&self) -> Self {
91        Iter {
92            iter: self.iter.clone(),
93        }
94    }
95}
96
97impl_iterator!(Iter<'a, T>, &'a T, Slot::key);
98
99/// An owning iterator over the elements of a `VecSet`.
100///
101/// This `struct` is created by the [`into_iter`] method on [`VecSet`] (provided by the
102/// [`IntoIterator`] trait). See its documentation for more.
103///
104/// [`into_iter`]: IntoIterator::into_iter
105/// [`IntoIterator`]: core::iter::IntoIterator
106pub struct IntoIter<T> {
107    iter: vec::IntoIter<Slot<T, ()>>,
108}
109
110impl<T> IntoIter<T> {
111    pub(super) fn new(entries: Vec<Slot<T, ()>>) -> IntoIter<T> {
112        IntoIter {
113            iter: entries.into_iter(),
114        }
115    }
116}
117
118impl<T> Clone for IntoIter<T>
119where
120    T: Clone,
121{
122    fn clone(&self) -> Self {
123        IntoIter {
124            iter: self.iter.clone(),
125        }
126    }
127}
128
129impl_iterator!(IntoIter<T>, T, Slot::into_key, Slot::key);
130
131/// A lazy iterator producing elements in the difference of `VecSet`s.
132///
133/// This `struct` is created by the [`difference`] method on [`VecSet`]. See its documentation for
134/// more.
135///
136/// [`VecSet`]: struct.VecSet.html
137/// [`difference`]: struct.VecSet.html#method.difference
138pub struct Difference<'a, T> {
139    iter: Iter<'a, T>,
140    other: &'a VecSet<T>,
141}
142
143impl<'a, T> Difference<'a, T> {
144    pub(super) fn new(set: &'a VecSet<T>, other: &'a VecSet<T>) -> Difference<'a, T> {
145        Difference {
146            iter: set.iter(),
147            other,
148        }
149    }
150}
151
152impl<'a, T> Iterator for Difference<'a, T>
153where
154    T: Eq,
155{
156    type Item = &'a T;
157
158    fn next(&mut self) -> Option<Self::Item> {
159        loop {
160            let item = self.iter.next()?;
161
162            if !self.other.contains(item) {
163                return Some(item);
164            }
165        }
166    }
167
168    fn size_hint(&self) -> (usize, Option<usize>) {
169        (0, self.iter.size_hint().1)
170    }
171}
172
173impl<T> DoubleEndedIterator for Difference<'_, T>
174where
175    T: Eq,
176{
177    fn next_back(&mut self) -> Option<Self::Item> {
178        loop {
179            let item = self.iter.next_back()?;
180
181            if !self.other.contains(item) {
182                return Some(item);
183            }
184        }
185    }
186}
187
188impl<T> FusedIterator for Difference<'_, T> where T: Eq {}
189
190impl<T> Clone for Difference<'_, T> {
191    fn clone(&self) -> Self {
192        Difference {
193            iter: self.iter.clone(),
194            ..*self
195        }
196    }
197}
198
199impl<T> fmt::Debug for Difference<'_, T>
200where
201    T: fmt::Debug + Eq,
202{
203    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
204        f.debug_list().entries(self.clone()).finish()
205    }
206}
207
208/// A lazy iterator producing elements in the intersection of `VecSet`s.
209///
210/// This `struct` is created by the [`intersection`] method on [`VecSet`]. See its documentation
211/// for more.
212///
213/// [`VecSet`]: struct.VecSet.html
214/// [`intersection`]: struct.VecSet.html#method.intersection
215pub struct Intersection<'a, T> {
216    iter: Iter<'a, T>,
217    other: &'a VecSet<T>,
218}
219
220impl<'a, T> Intersection<'a, T> {
221    pub(super) fn new(set: &'a VecSet<T>, other: &'a VecSet<T>) -> Intersection<'a, T> {
222        Intersection {
223            iter: set.iter(),
224            other,
225        }
226    }
227}
228
229impl<'a, T> Iterator for Intersection<'a, T>
230where
231    T: Eq,
232{
233    type Item = &'a T;
234
235    fn next(&mut self) -> Option<Self::Item> {
236        loop {
237            let item = self.iter.next()?;
238
239            if self.other.contains(item) {
240                return Some(item);
241            }
242        }
243    }
244
245    fn size_hint(&self) -> (usize, Option<usize>) {
246        (0, self.iter.size_hint().1)
247    }
248}
249
250impl<T> DoubleEndedIterator for Intersection<'_, T>
251where
252    T: Eq,
253{
254    fn next_back(&mut self) -> Option<Self::Item> {
255        loop {
256            let item = self.iter.next_back()?;
257
258            if self.other.contains(item) {
259                return Some(item);
260            }
261        }
262    }
263}
264
265impl<T> FusedIterator for Intersection<'_, T> where T: Eq {}
266
267impl<T> Clone for Intersection<'_, T> {
268    fn clone(&self) -> Self {
269        Intersection {
270            iter: self.iter.clone(),
271            ..*self
272        }
273    }
274}
275
276impl<T> fmt::Debug for Intersection<'_, T>
277where
278    T: fmt::Debug + Eq,
279{
280    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
281        f.debug_list().entries(self.clone()).finish()
282    }
283}
284
285/// A lazy iterator producing elements in the symmetric difference of `VecSet`s.
286///
287/// This `struct` is created by the [`symmetric_difference`] method on [`VecSet`]. See its
288/// documentation for more.
289///
290/// [`VecSet`]: struct.VecSet.html
291/// [`symmetric_difference`]: struct.VecSet.html#method.symmetric_difference
292pub struct SymmetricDifference<'a, T> {
293    iter: Chain<Difference<'a, T>, Difference<'a, T>>,
294}
295
296impl<'a, T> SymmetricDifference<'a, T>
297where
298    T: Eq,
299{
300    pub(super) fn new(set: &'a VecSet<T>, other: &'a VecSet<T>) -> SymmetricDifference<'a, T> {
301        SymmetricDifference {
302            iter: set.difference(other).chain(other.difference(set)),
303        }
304    }
305}
306
307impl<'a, T> Iterator for SymmetricDifference<'a, T>
308where
309    T: Eq,
310{
311    type Item = &'a T;
312
313    fn next(&mut self) -> Option<Self::Item> {
314        self.iter.next()
315    }
316
317    fn size_hint(&self) -> (usize, Option<usize>) {
318        self.iter.size_hint()
319    }
320}
321
322impl<T> DoubleEndedIterator for SymmetricDifference<'_, T>
323where
324    T: Eq,
325{
326    fn next_back(&mut self) -> Option<Self::Item> {
327        self.iter.next_back()
328    }
329}
330
331impl<T> FusedIterator for SymmetricDifference<'_, T> where T: Eq {}
332
333impl<T> Clone for SymmetricDifference<'_, T> {
334    fn clone(&self) -> Self {
335        SymmetricDifference {
336            iter: self.iter.clone(),
337        }
338    }
339}
340
341impl<T> fmt::Debug for SymmetricDifference<'_, T>
342where
343    T: fmt::Debug + Eq,
344{
345    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
346        f.debug_list().entries(self.clone()).finish()
347    }
348}
349
350/// A lazy iterator producing elements in the union of `VecSet`s.
351///
352/// This `struct` is created by the [`union`] method on [`VecSet`]. See its documentation for more.
353///
354/// [`VecSet`]: struct.VecSet.html
355/// [`union`]: struct.VecSet.html#method.union
356pub struct Union<'a, T> {
357    iter: Chain<Iter<'a, T>, Difference<'a, T>>,
358}
359
360impl<'a, T> Union<'a, T>
361where
362    T: Eq,
363{
364    pub(super) fn new(set: &'a VecSet<T>, other: &'a VecSet<T>) -> Union<'a, T> {
365        Union {
366            iter: set.iter().chain(other.difference(set)),
367        }
368    }
369}
370
371impl<'a, T> Iterator for Union<'a, T>
372where
373    T: Eq,
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
386impl<T> DoubleEndedIterator for Union<'_, T>
387where
388    T: Eq,
389{
390    fn next_back(&mut self) -> Option<Self::Item> {
391        self.iter.next_back()
392    }
393}
394
395impl<T> FusedIterator for Union<'_, T> where T: Eq {}
396
397impl<T> Clone for Union<'_, T> {
398    fn clone(&self) -> Self {
399        Union {
400            iter: self.iter.clone(),
401        }
402    }
403}
404
405impl<T> fmt::Debug for Union<'_, T>
406where
407    T: fmt::Debug + Eq,
408{
409    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
410        f.debug_list().entries(self.clone()).finish()
411    }
412}
413
414/// A draining iterator for `VecSet`.
415///
416/// This `struct` is created by the [`drain`] method on [`VecSet`]. See its documentation for
417/// more.
418///
419/// [`drain`]: VecSet::drain
420pub struct Drain<'a, T> {
421    iter: map::Drain<'a, T, ()>,
422}
423
424impl<'a, T> Drain<'a, T> {
425    pub(super) fn new<R>(set: &'a mut VecSet<T>, range: R) -> Drain<'a, T>
426    where
427        R: RangeBounds<usize>,
428    {
429        Drain {
430            iter: set.base.drain(range),
431        }
432    }
433}
434
435impl_iterator!(Drain<'a, T>, T, |(k, ())| k, Slot::key);
vecmap/set/iter.rs

vecmap/set/
iter.rs
