range_set_blaze/
unsorted_disjoint.rs

1use crate::{Integer, SortedDisjoint, SortedStarts};
2use core::{
3    cmp::{max, min},
4    iter::FusedIterator,
5    ops::RangeInclusive,
6};
7use num_traits::Zero;
8
9#[must_use = "iterators are lazy and do nothing unless consumed"]
10#[allow(clippy::redundant_pub_crate)]
11pub(crate) struct UnsortedDisjoint<T, I>
12where
13    T: Integer,
14    I: Iterator<Item = RangeInclusive<T>>,
15{
16    iter: I,
17    option_range: Option<RangeInclusive<T>>,
18    min_value_plus_2: T,
19}
20
21impl<T, I> UnsortedDisjoint<T, I>
22where
23    T: Integer,
24    I: Iterator<Item = RangeInclusive<T>>, // Any iterator is fine
25{
26    #[inline]
27    pub(crate) fn new(iter: I) -> Self {
28        Self {
29            iter,
30            option_range: None,
31            min_value_plus_2: T::min_value().add_one().add_one(),
32        }
33    }
34}
35
36impl<T, I> FusedIterator for UnsortedDisjoint<T, I>
37where
38    T: Integer,
39    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
40{
41}
42
43impl<T, I> Iterator for UnsortedDisjoint<T, I>
44where
45    T: Integer,
46    I: Iterator<Item = RangeInclusive<T>>,
47{
48    type Item = RangeInclusive<T>;
49
50    fn next(&mut self) -> Option<Self::Item> {
51        loop {
52            let Some(range) = self.iter.next() else {
53                return self.option_range.take();
54            };
55            let (next_start, next_end) = range.into_inner();
56            if next_start > next_end {
57                continue;
58            }
59            let Some(self_range) = self.option_range.clone() else {
60                self.option_range = Some(next_start..=next_end);
61                continue;
62            };
63
64            let (self_start, self_end) = self_range.into_inner();
65            if (next_start >= self.min_value_plus_2 && self_end <= next_start.sub_one().sub_one())
66                || (self_start >= self.min_value_plus_2
67                    && next_end <= self_start.sub_one().sub_one())
68            {
69                let result = Some(self_start..=self_end);
70                self.option_range = Some(next_start..=next_end);
71                return result;
72            }
73            self.option_range = Some(min(self_start, next_start)..=max(self_end, next_end));
74            // continue;
75        }
76    }
77
78    // As few as one (or zero if iter is empty) and as many as iter.len()
79    // There could be one extra if option_range is Some.
80    fn size_hint(&self) -> (usize, Option<usize>) {
81        let (lower, upper) = self.iter.size_hint();
82        let lower = min(lower, 1);
83        if self.option_range.is_some() {
84            (lower, upper.map(|x| x + 1))
85        } else {
86            (lower, upper)
87        }
88    }
89}
90
91#[must_use = "iterators are lazy and do nothing unless consumed"]
92#[allow(clippy::redundant_pub_crate)]
93pub(crate) struct SortedDisjointWithLenSoFar<T, I>
94where
95    T: Integer,
96    I: SortedDisjoint<T>,
97{
98    iter: I,
99    len: <T as Integer>::SafeLen,
100}
101
102impl<T, I> SortedDisjointWithLenSoFar<T, I>
103where
104    T: Integer,
105    I: Iterator<Item = RangeInclusive<T>> + SortedDisjoint<T>,
106{
107    #[inline]
108    pub(crate) fn new(iter: I) -> Self {
109        Self {
110            iter,
111            len: T::SafeLen::zero(),
112        }
113    }
114}
115
116impl<T: Integer, I> SortedDisjointWithLenSoFar<T, I>
117where
118    I: SortedDisjoint<T>,
119{
120    pub(crate) const fn len_so_far(&self) -> <T as Integer>::SafeLen {
121        self.len
122    }
123}
124
125impl<T: Integer, I> FusedIterator for SortedDisjointWithLenSoFar<T, I> where
126    I: SortedDisjoint<T> + FusedIterator
127{
128}
129
130impl<T: Integer, I> Iterator for SortedDisjointWithLenSoFar<T, I>
131where
132    I: SortedDisjoint<T>,
133{
134    type Item = (T, T);
135
136    fn next(&mut self) -> Option<Self::Item> {
137        if let Some(range) = self.iter.next() {
138            let (start, end) = range.clone().into_inner();
139            debug_assert!(start <= end);
140            self.len += T::safe_len(&range);
141            Some((start, end))
142        } else {
143            None
144        }
145    }
146    fn size_hint(&self) -> (usize, Option<usize>) {
147        self.iter.size_hint()
148    }
149}
150
151#[derive(Clone, Debug)]
152#[must_use = "iterators are lazy and do nothing unless consumed"]
153/// Gives any iterator of ranges the [`SortedStarts`] trait without any checking.
154pub struct AssumeSortedStarts<T, I>
155where
156    T: Integer,
157    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
158{
159    pub(crate) iter: I,
160}
161
162impl<T, I> FusedIterator for AssumeSortedStarts<T, I>
163where
164    T: Integer,
165    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
166{
167}
168
169impl<T: Integer, I> SortedStarts<T> for AssumeSortedStarts<T, I> where
170    I: Iterator<Item = RangeInclusive<T>> + FusedIterator
171{
172}
173
174impl<T, I> AssumeSortedStarts<T, I>
175where
176    T: Integer,
177    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
178{
179    /// Construct [`AssumeSortedStarts`] from a range iterator.
180    #[inline]
181    pub fn new<J: IntoIterator<IntoIter = I>>(iter: J) -> Self {
182        Self {
183            iter: iter.into_iter(),
184        }
185    }
186}
187
188impl<T, I> Iterator for AssumeSortedStarts<T, I>
189where
190    T: Integer,
191    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
192{
193    type Item = RangeInclusive<T>;
194
195    fn next(&mut self) -> Option<Self::Item> {
196        self.iter.next()
197    }
198
199    fn size_hint(&self) -> (usize, Option<usize>) {
200        self.iter.size_hint()
201    }
202}
range_set_blaze/unsorted_disjoint.rs

range_set_blaze/
unsorted_disjoint.rs
