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

range_set_blaze/
not_iter.rs
