range_set_blaze/
not_iter.rs

1use core::{iter::FusedIterator, ops::RangeInclusive};
2
3use crate::{Integer, SortedDisjoint};
4
5/// The output of [`SortedDisjoint::complement`] and [`SortedDisjointMap::complement_with`].
6///
7/// [`SortedDisjointMap::complement_with`]: trait.SortedDisjointMap.html#method.complement_with
8#[derive(Clone, Debug)]
9#[must_use = "iterators are lazy and do nothing unless consumed"]
10pub struct NotIter<T, I>
11where
12    T: Integer,
13    I: SortedDisjoint<T>,
14{
15    iter: I,
16    start_not: T,
17    next_time_return_none: bool,
18}
19
20impl<T, I> NotIter<T, I>
21where
22    T: Integer,
23    I: SortedDisjoint<T>,
24{
25    #[inline]
26    pub(crate) fn new<J>(iter: J) -> Self
27    where
28        J: IntoIterator<Item = RangeInclusive<T>, IntoIter = I>,
29    {
30        Self {
31            iter: iter.into_iter(),
32            start_not: T::min_value(),
33            next_time_return_none: false,
34        }
35    }
36}
37
38impl<T, I> FusedIterator for NotIter<T, I>
39where
40    T: Integer,
41    I: SortedDisjoint<T> + FusedIterator,
42{
43}
44
45// Note: DoubleEndedIterator is not easily implementable for NotIter because
46// it would require complex tracking of the "flipped" nature of the NotIter
47// in reverse order.
48
49impl<T, I> Iterator for NotIter<T, I>
50where
51    T: Integer,
52    I: SortedDisjoint<T>,
53{
54    type Item = RangeInclusive<T>;
55    fn next(&mut self) -> Option<RangeInclusive<T>> {
56        debug_assert!(T::min_value() <= T::max_value()); // real assert
57        if self.next_time_return_none {
58            return None;
59        }
60        let next_item = self.iter.next();
61        if let Some(range) = next_item {
62            let (start, end) = range.into_inner();
63            debug_assert!(start <= end);
64            if self.start_not < start {
65                // We can subtract with underflow worry because
66                // we know that start > start_not and so not min_value
67                let result = Some(self.start_not..=start.sub_one());
68                if end < T::max_value() {
69                    self.start_not = end.add_one();
70                } else {
71                    self.next_time_return_none = true;
72                }
73                result
74            } else if end < T::max_value() {
75                self.start_not = end.add_one();
76                self.next() // will recurse at most once
77            } else {
78                self.next_time_return_none = true;
79                None
80            }
81        } else {
82            self.next_time_return_none = true;
83            Some(self.start_not..=T::max_value())
84        }
85    }
86
87    // We could have one less or one more than the iter.
88    fn size_hint(&self) -> (usize, Option<usize>) {
89        let (low, high) = self.iter.size_hint();
90        let low = low.saturating_sub(1);
91        let high = high.map(|high| high.saturating_add(1));
92        (low, high)
93    }
94}
95
96// FUTURE define Not, etc on DynSortedDisjoint
range_set_blaze/not_iter.rs

range_set_blaze/
not_iter.rs
