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

range_set_blaze/
unsorted_disjoint.rs
