ringmap/set/
iter.rs

1use crate::map::{ExtractCore, RingMapCore};
2
3use super::{Bucket, RingSet};
4use crate::map::Buckets;
5
6use alloc::collections::vec_deque::{self, VecDeque};
7use core::fmt;
8use core::hash::{BuildHasher, Hash};
9use core::iter::{Chain, FusedIterator};
10use core::ops::RangeBounds;
11
12impl<'a, T, S> IntoIterator for &'a RingSet<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 RingSet<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 [`RingSet`].
31///
32/// This `struct` is created by the [`RingSet::iter`] method.
33/// See its documentation for more.
34pub struct Iter<'a, T> {
35    iter: Buckets<'a, T, ()>,
36}
37
38impl<'a, T> Iter<'a, T> {
39    pub(super) fn new(entries: &'a VecDeque<Bucket<T>>) -> Self {
40        Self {
41            iter: Buckets::new(entries),
42        }
43    }
44
45    pub(super) fn from_slice(slice: &'a [Bucket<T>]) -> Self {
46        Self {
47            iter: Buckets::from_slice(slice),
48        }
49    }
50}
51
52impl<'a, T> Iterator for Iter<'a, T> {
53    type Item = &'a T;
54
55    iterator_methods!(Bucket::key_ref);
56}
57
58impl<T> DoubleEndedIterator for Iter<'_, T> {
59    double_ended_iterator_methods!(Bucket::key_ref);
60}
61
62impl<T> ExactSizeIterator for Iter<'_, T> {
63    fn len(&self) -> usize {
64        self.iter.len()
65    }
66}
67
68impl<T> FusedIterator for Iter<'_, T> {}
69
70impl<T> Clone for Iter<'_, T> {
71    fn clone(&self) -> Self {
72        Iter {
73            iter: self.iter.clone(),
74        }
75    }
76}
77
78impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
79    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80        f.debug_list().entries(self.clone()).finish()
81    }
82}
83
84impl<T> Default for Iter<'_, T> {
85    fn default() -> Self {
86        Self {
87            iter: Default::default(),
88        }
89    }
90}
91
92/// An owning iterator over the items of an [`RingSet`].
93///
94/// This `struct` is created by the [`RingSet::into_iter`] method
95/// (provided by the [`IntoIterator`] trait). See its documentation for more.
96#[derive(Clone)]
97pub struct IntoIter<T> {
98    iter: vec_deque::IntoIter<Bucket<T>>,
99}
100
101impl<T> IntoIter<T> {
102    pub(super) fn new(entries: VecDeque<Bucket<T>>) -> Self {
103        Self {
104            iter: entries.into_iter(),
105        }
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        // FIXME
130        // let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
131        // f.debug_list().entries(iter).finish()
132        f.debug_struct("IntoIter").finish_non_exhaustive()
133    }
134}
135
136impl<T> Default for IntoIter<T> {
137    fn default() -> Self {
138        Self {
139            iter: VecDeque::new().into_iter(),
140        }
141    }
142}
143
144/// A draining iterator over the items of an [`RingSet`].
145///
146/// This `struct` is created by the [`RingSet::drain`] method.
147/// See its documentation for more.
148pub struct Drain<'a, T> {
149    iter: vec_deque::Drain<'a, Bucket<T>>,
150}
151
152impl<'a, T> Drain<'a, T> {
153    pub(super) fn new(iter: vec_deque::Drain<'a, Bucket<T>>) -> Self {
154        Self { iter }
155    }
156}
157
158impl<T> Iterator for Drain<'_, T> {
159    type Item = T;
160
161    iterator_methods!(Bucket::key);
162}
163
164impl<T> DoubleEndedIterator for Drain<'_, T> {
165    double_ended_iterator_methods!(Bucket::key);
166}
167
168impl<T> ExactSizeIterator for Drain<'_, T> {
169    fn len(&self) -> usize {
170        self.iter.len()
171    }
172}
173
174impl<T> FusedIterator for Drain<'_, T> {}
175
176impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
177    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178        // FIXME
179        // let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
180        // f.debug_list().entries(iter).finish()
181        f.debug_struct("Drain").finish_non_exhaustive()
182    }
183}
184
185/// A lazy iterator producing elements in the difference of [`RingSet`]s.
186///
187/// This `struct` is created by the [`RingSet::difference`] method.
188/// See its documentation for more.
189pub struct Difference<'a, T, S> {
190    iter: Iter<'a, T>,
191    other: &'a RingSet<T, S>,
192}
193
194impl<'a, T, S> Difference<'a, T, S> {
195    pub(super) fn new<S1>(set: &'a RingSet<T, S1>, other: &'a RingSet<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 [`RingSet`]s.
266///
267/// This `struct` is created by the [`RingSet::intersection`] method.
268/// See its documentation for more.
269pub struct Intersection<'a, T, S> {
270    iter: Iter<'a, T>,
271    other: &'a RingSet<T, S>,
272}
273
274impl<'a, T, S> Intersection<'a, T, S> {
275    pub(super) fn new<S1>(set: &'a RingSet<T, S1>, other: &'a RingSet<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 [`RingSet`]s.
346///
347/// This `struct` is created by the [`RingSet::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 RingSet<T, S1>, set2: &'a RingSet<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 [`RingSet`]s.
438///
439/// This `struct` is created by the [`RingSet::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 RingSet<T, S>, set2: &'a RingSet<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 `RingSet`.
526///
527/// This `struct` is created by [`RingSet::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    #[track_caller]
545    pub(super) fn new<R>(set: &'a mut RingSet<T, S>, range: R, replace_with: I) -> Self
546    where
547        R: RangeBounds<usize>,
548    {
549        Self {
550            iter: set.map.splice(range, UnitValue(replace_with)),
551        }
552    }
553}
554
555impl<I, T, S> Iterator for Splice<'_, I, T, S>
556where
557    I: Iterator<Item = T>,
558    T: Hash + Eq,
559    S: BuildHasher,
560{
561    type Item = T;
562
563    fn next(&mut self) -> Option<Self::Item> {
564        Some(self.iter.next()?.0)
565    }
566
567    fn size_hint(&self) -> (usize, Option<usize>) {
568        self.iter.size_hint()
569    }
570}
571
572impl<I, T, S> DoubleEndedIterator for Splice<'_, I, T, S>
573where
574    I: Iterator<Item = T>,
575    T: Hash + Eq,
576    S: BuildHasher,
577{
578    fn next_back(&mut self) -> Option<Self::Item> {
579        Some(self.iter.next_back()?.0)
580    }
581}
582
583impl<I, T, S> ExactSizeIterator for Splice<'_, I, T, S>
584where
585    I: Iterator<Item = T>,
586    T: Hash + Eq,
587    S: BuildHasher,
588{
589    fn len(&self) -> usize {
590        self.iter.len()
591    }
592}
593
594impl<I, T, S> FusedIterator for Splice<'_, I, T, S>
595where
596    I: Iterator<Item = T>,
597    T: Hash + Eq,
598    S: BuildHasher,
599{
600}
601
602struct UnitValue<I>(I);
603
604impl<I: Iterator> Iterator for UnitValue<I> {
605    type Item = (I::Item, ());
606
607    fn next(&mut self) -> Option<Self::Item> {
608        self.0.next().map(|x| (x, ()))
609    }
610}
611
612impl<I, T, S> fmt::Debug for Splice<'_, I, T, S>
613where
614    I: fmt::Debug + Iterator<Item = T>,
615    T: fmt::Debug + Hash + Eq,
616    S: BuildHasher,
617{
618    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
619        fmt::Debug::fmt(&self.iter, f)
620    }
621}
622
623impl<I: fmt::Debug> fmt::Debug for UnitValue<I> {
624    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
625        fmt::Debug::fmt(&self.0, f)
626    }
627}
628
629/// An extracting iterator for `RingSet`.
630///
631/// This `struct` is created by [`RingSet::extract_if()`].
632/// See its documentation for more.
633pub struct ExtractIf<'a, T, F> {
634    inner: ExtractCore<'a, T, ()>,
635    pred: F,
636}
637
638impl<T, F> ExtractIf<'_, T, F> {
639    #[track_caller]
640    pub(super) fn new<R>(core: &mut RingMapCore<T, ()>, range: R, pred: F) -> ExtractIf<'_, T, F>
641    where
642        R: RangeBounds<usize>,
643        F: FnMut(&T) -> bool,
644    {
645        ExtractIf {
646            inner: core.extract(range),
647            pred,
648        }
649    }
650}
651
652impl<T, F> Iterator for ExtractIf<'_, T, F>
653where
654    F: FnMut(&T) -> bool,
655{
656    type Item = T;
657
658    fn next(&mut self) -> Option<Self::Item> {
659        self.inner
660            .extract_if(|bucket| (self.pred)(bucket.key_ref()))
661            .map(Bucket::key)
662    }
663
664    fn size_hint(&self) -> (usize, Option<usize>) {
665        (0, Some(self.inner.remaining()))
666    }
667}
668
669impl<T, F> FusedIterator for ExtractIf<'_, T, F> where F: FnMut(&T) -> bool {}
670
671impl<T, F> fmt::Debug for ExtractIf<'_, T, F>
672where
673    T: fmt::Debug,
674{
675    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
676        f.debug_struct("ExtractIf").finish_non_exhaustive()
677    }
678}
ringmap/set/iter.rs

ringmap/set/
iter.rs
