range_set_blaze/
unsorted_disjoint.rs

1use crate::{Integer, RangeSetBlaze, 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"]
10pub(crate) struct UnsortedDisjoint<T, I>
11where
12    T: Integer,
13    I: Iterator<Item = RangeInclusive<T>>,
14{
15    iter: I,
16    option_range: Option<RangeInclusive<T>>,
17    min_value_plus_2: T,
18    two: T,
19}
20
21impl<T, I> From<I> for UnsortedDisjoint<T, I::IntoIter>
22where
23    T: Integer,
24    I: IntoIterator<Item = RangeInclusive<T>>, // Any iterator is fine
25{
26    fn from(into_iter: I) -> Self {
27        UnsortedDisjoint {
28            iter: into_iter.into_iter(),
29            option_range: None,
30            min_value_plus_2: T::min_value() + T::one() + T::one(),
31            two: T::one() + T::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 range = match self.iter.next() {
53                Some(r) => r,
54                None => return self.option_range.take(),
55            };
56
57            let (next_start, next_end) = range.into_inner();
58            if next_start > next_end {
59                continue;
60            }
61            assert!(
62                next_end <= T::safe_max_value(),
63                "end must be <= T::safe_max_value()"
64            );
65
66            let Some(self_range) = self.option_range.clone() else {
67                self.option_range = Some(next_start..=next_end);
68                continue;
69            };
70
71            let (self_start, self_end) = self_range.into_inner();
72            if (next_start >= self.min_value_plus_2 && self_end <= next_start - self.two)
73                || (self_start >= self.min_value_plus_2 && next_end <= self_start - self.two)
74            {
75                let result = Some(self_start..=self_end);
76                self.option_range = Some(next_start..=next_end);
77                return result;
78            } else {
79                self.option_range = Some(min(self_start, next_start)..=max(self_end, next_end));
80                continue;
81            }
82        }
83    }
84
85    // As few as one (or zero if iter is empty) and as many as iter.len()
86    // There could be one extra if option_range is Some.
87    fn size_hint(&self) -> (usize, Option<usize>) {
88        let (lower, upper) = self.iter.size_hint();
89        let lower = if lower == 0 { 0 } else { 1 };
90        if self.option_range.is_some() {
91            (lower, upper.map(|x| x + 1))
92        } else {
93            (lower, upper)
94        }
95    }
96}
97
98#[must_use = "iterators are lazy and do nothing unless consumed"]
99pub(crate) struct SortedDisjointWithLenSoFar<T, I>
100where
101    T: Integer,
102    I: SortedDisjoint<T>,
103{
104    iter: I,
105    len: <T as Integer>::SafeLen,
106}
107
108impl<T: Integer, I> From<I> for SortedDisjointWithLenSoFar<T, I::IntoIter>
109where
110    I: IntoIterator<Item = RangeInclusive<T>>,
111    I::IntoIter: SortedDisjoint<T>,
112{
113    fn from(into_iter: I) -> Self {
114        SortedDisjointWithLenSoFar {
115            iter: into_iter.into_iter(),
116            len: <T as Integer>::SafeLen::zero(),
117        }
118    }
119}
120
121impl<T: Integer, I> SortedDisjointWithLenSoFar<T, I>
122where
123    I: SortedDisjoint<T>,
124{
125    pub fn len_so_far(&self) -> <T as Integer>::SafeLen {
126        self.len
127    }
128}
129
130impl<T: Integer, I> FusedIterator for SortedDisjointWithLenSoFar<T, I> where
131    I: SortedDisjoint<T> + FusedIterator
132{
133}
134
135impl<T: Integer, I> Iterator for SortedDisjointWithLenSoFar<T, I>
136where
137    I: SortedDisjoint<T>,
138{
139    type Item = (T, T);
140
141    fn next(&mut self) -> Option<Self::Item> {
142        if let Some(range) = self.iter.next() {
143            let (start, end) = range.clone().into_inner();
144            debug_assert!(start <= end && end <= T::safe_max_value());
145            self.len += T::safe_len(&range);
146            Some((start, end))
147        } else {
148            None
149        }
150    }
151    fn size_hint(&self) -> (usize, Option<usize>) {
152        self.iter.size_hint()
153    }
154}
155
156#[derive(Clone, Debug)]
157#[must_use = "iterators are lazy and do nothing unless consumed"]
158
159/// Gives any iterator of ranges the [`SortedStarts`] trait without any checking.
160pub struct AssumeSortedStarts<T, I>
161where
162    T: Integer,
163    I: Iterator<Item = RangeInclusive<T>>,
164{
165    pub(crate) iter: I,
166}
167
168impl<T: Integer, I> SortedStarts<T> for AssumeSortedStarts<T, I> where
169    I: Iterator<Item = RangeInclusive<T>>
170{
171}
172
173impl<T, I> AssumeSortedStarts<T, I>
174where
175    T: Integer,
176    I: Iterator<Item = RangeInclusive<T>>,
177{
178    /// Construct [`AssumeSortedStarts`] from a range iterator.
179    pub fn new<J: IntoIterator<IntoIter = I>>(iter: J) -> Self {
180        AssumeSortedStarts {
181            iter: iter.into_iter(),
182        }
183    }
184
185    /// Create a [`RangeSetBlaze`] from an [`AssumeSortedStarts`] iterator.
186    ///
187    /// *For more about constructors and performance, see [`RangeSetBlaze` Constructors](struct.RangeSetBlaze.html#constructors).*
188    ///
189    /// # Examples
190    ///
191    /// ```
192    /// use range_set_blaze::prelude::*;
193    ///
194    /// let a0 = RangeSetBlaze::from_sorted_starts(AssumeSortedStarts::new([-10..=-5, -7..=2]));
195    /// let a1: RangeSetBlaze<i32> = AssumeSortedStarts::new([-10..=-5, -7..=2]).into_range_set_blaze();
196    /// assert!(a0 == a1 && a0.to_string() == "-10..=2");
197    /// ```
198    pub fn into_range_set_blaze(self) -> RangeSetBlaze<T>
199    where
200        Self: Sized,
201    {
202        RangeSetBlaze::from_sorted_starts(self)
203    }
204}
205
206impl<T, I> FusedIterator for AssumeSortedStarts<T, I>
207where
208    T: Integer,
209    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
210{
211}
212
213impl<T, I> Iterator for AssumeSortedStarts<T, I>
214where
215    T: Integer,
216    I: Iterator<Item = RangeInclusive<T>>,
217{
218    type Item = RangeInclusive<T>;
219
220    fn next(&mut self) -> Option<Self::Item> {
221        self.iter.next()
222    }
223
224    fn size_hint(&self) -> (usize, Option<usize>) {
225        self.iter.size_hint()
226    }
227}
range_set_blaze/unsorted_disjoint.rs

range_set_blaze/
unsorted_disjoint.rs
