range_set_blaze/
range_values.rs

1use crate::{
2    Integer,
3    map::ValueRef,
4    sorted_disjoint_map::{Priority, PrioritySortedStartsMap},
5};
6use alloc::{collections::btree_map, rc::Rc};
7use core::{iter::FusedIterator, marker::PhantomData, ops::RangeInclusive};
8
9use crate::{map::EndValue, sorted_disjoint_map::SortedDisjointMap};
10
11/// This `struct` is created by the [`range_values`] method on [`RangeMapBlaze`]. See [`range_values`]'s
12/// documentation for more. Double-ended.
13///
14/// [`RangeMapBlaze`]: crate::RangeMapBlaze
15/// [`range_values`]: crate::RangeMapBlaze::range_values
16#[derive(Clone, Debug)]
17#[must_use = "iterators are lazy and do nothing unless consumed"]
18#[allow(clippy::module_name_repetitions)]
19pub struct RangeValuesIter<'a, T: Integer, V: Eq + Clone> {
20    iter: btree_map::Iter<'a, T, EndValue<T, V>>,
21}
22
23impl<'a, T: Integer, V: Eq + Clone> RangeValuesIter<'a, T, V> {
24    #[inline]
25    pub(crate) fn new(map: &'a btree_map::BTreeMap<T, EndValue<T, V>>) -> Self {
26        Self { iter: map.iter() }
27    }
28}
29
30impl<T: Integer, V: Eq + Clone> ExactSizeIterator for RangeValuesIter<'_, T, V> {
31    fn len(&self) -> usize {
32        self.iter.len()
33    }
34}
35
36impl<T: Integer, V: Eq + Clone> FusedIterator for RangeValuesIter<'_, T, V> {}
37
38// Range's iterator is just the inside BTreeMap iterator as values
39impl<'a, T, V> Iterator for RangeValuesIter<'a, T, V>
40where
41    T: Integer,
42    V: Eq + Clone + 'a,
43{
44    type Item = (RangeInclusive<T>, &'a V); // Assuming VR is always &'a V for next
45
46    fn next(&mut self) -> Option<Self::Item> {
47        self.iter
48            .next()
49            .map(|(start, end_value)| (*start..=end_value.end, &end_value.value))
50    }
51
52    fn size_hint(&self) -> (usize, Option<usize>) {
53        self.iter.size_hint()
54    }
55}
56
57impl<'a, T, V> DoubleEndedIterator for RangeValuesIter<'a, T, V>
58where
59    T: Integer,
60    V: Eq + Clone + 'a,
61{
62    fn next_back(&mut self) -> Option<Self::Item> {
63        self.iter
64            .next_back()
65            .map(|(start, end_value)| (*start..=end_value.end, &end_value.value))
66    }
67}
68
69/// This `struct` is created by the [`into_range_values`] method on [`RangeMapBlaze`]. See [`into_range_values`]'s
70/// documentation for more. Double-ended.
71///
72/// Not clonable because `btree_map::IntoIter` is not clonable.
73///
74/// [`RangeMapBlaze`]: crate::RangeMapBlaze
75/// [`into_range_values`]: crate::RangeMapBlaze::into_range_values
76#[must_use = "iterators are lazy and do nothing unless consumed"]
77#[derive(Debug)]
78pub struct IntoRangeValuesIter<T: Integer, V: Eq + Clone> {
79    iter: btree_map::IntoIter<T, EndValue<T, V>>,
80}
81
82impl<T: Integer, V: Eq + Clone> IntoRangeValuesIter<T, V> {
83    #[inline]
84    pub(crate) fn new(map: btree_map::BTreeMap<T, EndValue<T, V>>) -> Self {
85        Self {
86            iter: map.into_iter(),
87        }
88    }
89}
90
91impl<T: Integer, V: Eq + Clone> ExactSizeIterator for IntoRangeValuesIter<T, V> {
92    fn len(&self) -> usize {
93        self.iter.len()
94    }
95}
96
97impl<T: Integer, V: Eq + Clone> FusedIterator for IntoRangeValuesIter<T, V> {}
98
99impl<T: Integer, V: Eq + Clone> Iterator for IntoRangeValuesIter<T, V> {
100    type Item = (RangeInclusive<T>, Rc<V>);
101
102    fn next(&mut self) -> Option<Self::Item> {
103        self.iter.next().map(|(start, end_value)| {
104            let range = start..=end_value.end;
105            let value = Rc::new(end_value.value);
106            (range, value)
107        })
108    }
109
110    fn size_hint(&self) -> (usize, Option<usize>) {
111        self.iter.size_hint()
112    }
113}
114
115impl<T: Integer, V: Eq + Clone> DoubleEndedIterator for IntoRangeValuesIter<T, V> {
116    fn next_back(&mut self) -> Option<Self::Item> {
117        self.iter.next_back().map(|(start, end_value)| {
118            let range = start..=end_value.end;
119            let value = Rc::new(end_value.value);
120            (range, value)
121        })
122    }
123}
124
125/// This `struct` is created by the [`ranges`] method on [`RangeMapBlaze`]. See [`ranges`]'s
126/// documentation for more.
127///
128/// [`RangeMapBlaze`]: crate::RangeMapBlaze
129/// [`ranges`]: crate::RangeMapBlaze::ranges
130#[derive(Clone, Debug)]
131#[must_use = "iterators are lazy and do nothing unless consumed"]
132pub struct MapRangesIter<'a, T: Integer, V: Eq + Clone> {
133    iter: btree_map::Iter<'a, T, EndValue<T, V>>,
134    gather: Option<RangeInclusive<T>>,
135}
136
137impl<'a, T: Integer, V: Eq + Clone> MapRangesIter<'a, T, V> {
138    pub(crate) const fn new(iter: btree_map::Iter<'a, T, EndValue<T, V>>) -> Self {
139        MapRangesIter { iter, gather: None }
140    }
141}
142
143impl<T: Integer, V: Eq + Clone> FusedIterator for MapRangesIter<'_, T, V> {}
144
145// Range's iterator is just the inside BTreeMap iterator as values
146impl<'a, T, V> Iterator for MapRangesIter<'a, T, V>
147where
148    T: Integer,
149    V: Eq + Clone + 'a,
150{
151    type Item = RangeInclusive<T>;
152
153    fn next(&mut self) -> Option<Self::Item> {
154        loop {
155            // If no next, return gather, if any.
156            let Some((start, end_value)) = self.iter.next() else {
157                return self.gather.take();
158            };
159
160            let (start_next, end_next) = (*start, end_value.end);
161            debug_assert!(start_next <= end_next); // real assert
162
163            // if not gather, start a new gather.
164            let Some(gather) = self.gather.take() else {
165                self.gather = Some(start_next..=end_next);
166                continue;
167            };
168
169            let (gather_start, gather_end) = gather.into_inner();
170
171            // if next is just touching gather, extend gather.
172            if gather_end.add_one() == start_next {
173                self.gather = Some(gather_start..=end_next);
174                continue;
175            }
176
177            // they are disjoint, return gather and start a new gather.
178            self.gather = Some(start_next..=end_next);
179            return Some(gather_start..=gather_end);
180        }
181    }
182
183    fn size_hint(&self) -> (usize, Option<usize>) {
184        // 'Low' could be 0 if empty or 1 if fully merged.
185        (0, self.iter.size_hint().1)
186    }
187}
188
189/// This `struct` is created by the [`into_ranges`] method on [`RangeMapBlaze`]. See [`into_ranges`]'s
190/// documentation for more.
191///
192/// [`RangeMapBlaze`]: crate::RangeMapBlaze
193/// [`into_ranges`]: crate::RangeMapBlaze::into_ranges
194#[must_use = "iterators are lazy and do nothing unless consumed"]
195#[derive(Debug)]
196pub struct MapIntoRangesIter<T: Integer, V: Eq + Clone> {
197    iter: btree_map::IntoIter<T, EndValue<T, V>>,
198    gather: Option<RangeInclusive<T>>,
199}
200
201impl<T: Integer, V: Eq + Clone> MapIntoRangesIter<T, V> {
202    pub(crate) const fn new(iter: btree_map::IntoIter<T, EndValue<T, V>>) -> Self {
203        Self { iter, gather: None }
204    }
205}
206
207impl<T: Integer, V: Eq + Clone> FusedIterator for MapIntoRangesIter<T, V> {}
208
209impl<T: Integer, V: Eq + Clone> Iterator for MapIntoRangesIter<T, V> {
210    type Item = RangeInclusive<T>;
211
212    fn next(&mut self) -> Option<Self::Item> {
213        loop {
214            // If no next, return gather, if any.
215            let Some((start_next, end_value)) = self.iter.next() else {
216                return self.gather.take();
217            };
218
219            let end_next = end_value.end;
220            debug_assert!(start_next <= end_next); // real assert
221
222            // if not gather, start a new gather.
223            let Some(gather) = self.gather.take() else {
224                self.gather = Some(start_next..=end_next);
225                continue;
226            };
227
228            let (gather_start, gather_end) = gather.into_inner();
229
230            // if next is just touching gather, extend gather.
231            if gather_end.add_one() == start_next {
232                self.gather = Some(gather_start..=end_next);
233                continue;
234            }
235
236            // they are disjoint, return gather and start a new gather.
237            self.gather = Some(start_next..=end_next);
238            return Some(gather_start..=gather_end);
239        }
240    }
241
242    fn size_hint(&self) -> (usize, Option<usize>) {
243        // 'Low' could be 0 if empty or 1 if fully merged.
244        (0, self.iter.size_hint().1)
245    }
246}
247
248/// This `struct` is used internally.
249#[derive(Debug, Clone)]
250#[must_use = "iterators are lazy and do nothing unless consumed"]
251#[allow(clippy::module_name_repetitions)]
252pub struct RangeValuesToRangesIter<T, VR, I>
253where
254    T: Integer,
255    VR: ValueRef,
256    I: SortedDisjointMap<T, VR>,
257{
258    iter: I,
259    gather: Option<RangeInclusive<T>>,
260    phantom: PhantomData<VR>,
261}
262
263impl<T, VR, I> FusedIterator for RangeValuesToRangesIter<T, VR, I>
264where
265    T: Integer,
266    VR: ValueRef,
267    I: SortedDisjointMap<T, VR>,
268{
269}
270
271impl<T, VR, I> RangeValuesToRangesIter<T, VR, I>
272where
273    T: Integer,
274    VR: ValueRef,
275    I: SortedDisjointMap<T, VR>,
276{
277    /// Creates a new `RangeValuesToRangesIter` from an existing sorted disjoint map iterator.
278    /// `option_ranges` is initialized as `None` by default.
279    pub(crate) const fn new(iter: I) -> Self {
280        Self {
281            iter,
282            gather: None,
283            phantom: PhantomData,
284        }
285    }
286}
287
288impl<T, VR, I> Iterator for RangeValuesToRangesIter<T, VR, I>
289where
290    T: Integer,
291    VR: ValueRef,
292    I: SortedDisjointMap<T, VR>,
293{
294    type Item = RangeInclusive<T>;
295
296    fn next(&mut self) -> Option<Self::Item> {
297        loop {
298            // If no next value, return gather, if any.
299            let Some(next_range_value) = self.iter.next() else {
300                return self.gather.take();
301            };
302            let (next_start, next_end) = next_range_value.0.into_inner();
303
304            // If there is no gather, start a new gather.
305            let Some(gather) = self.gather.take() else {
306                self.gather = Some(next_start..=next_end);
307                continue;
308            };
309            let (gather_start, gather_end) = gather.into_inner();
310
311            // If next is just touching gather, extend gather.
312            if gather_end.add_one() == next_start {
313                self.gather = Some(gather_start..=next_end);
314                continue;
315            }
316
317            // They are disjoint, return gather and start a new gather.
318            self.gather = Some(next_start..=next_end);
319            return Some(gather_start..=gather_end);
320        }
321    }
322}
323
324#[allow(clippy::redundant_pub_crate)]
325pub(crate) trait ExpectDebugUnwrapRelease<T> {
326    fn expect_debug_unwrap_release(self, msg: &str) -> T;
327}
328
329#[allow(unused_variables)]
330impl<T> ExpectDebugUnwrapRelease<T> for Option<T> {
331    fn expect_debug_unwrap_release(self, msg: &str) -> T {
332        #[cfg(debug_assertions)]
333        {
334            self.expect(msg)
335        }
336        #[cfg(not(debug_assertions))]
337        {
338            self.unwrap()
339        }
340    }
341}
342
343#[expect(clippy::redundant_pub_crate)]
344#[must_use = "iterators are lazy and do nothing unless consumed"]
345#[derive(Clone, Debug)]
346pub(crate) struct SetPriorityMap<T, VR, I>
347where
348    T: Integer,
349    VR: ValueRef,
350    I: SortedDisjointMap<T, VR>,
351{
352    iter: I,
353    priority_number: usize,
354    phantom: PhantomData<(T, VR)>,
355}
356
357impl<T, VR, I> FusedIterator for SetPriorityMap<T, VR, I>
358where
359    T: Integer,
360    VR: ValueRef,
361    I: SortedDisjointMap<T, VR>,
362{
363}
364
365impl<T, VR, I> Iterator for SetPriorityMap<T, VR, I>
366where
367    T: Integer,
368    VR: ValueRef,
369    I: SortedDisjointMap<T, VR>,
370{
371    type Item = Priority<T, VR>;
372
373    fn next(&mut self) -> Option<Self::Item> {
374        self.iter
375            .next()
376            .map(|range_value| Priority::new(range_value, self.priority_number))
377    }
378}
379
380impl<T, VR, I> SetPriorityMap<T, VR, I>
381where
382    T: Integer,
383    VR: ValueRef,
384    I: SortedDisjointMap<T, VR>,
385{
386    pub(crate) const fn new(iter: I, priority: usize) -> Self {
387        Self {
388            iter,
389            priority_number: priority,
390            phantom: PhantomData,
391        }
392    }
393}
394
395impl<T, VR, I> PrioritySortedStartsMap<T, VR> for SetPriorityMap<T, VR, I>
396where
397    T: Integer,
398    VR: ValueRef,
399    I: SortedDisjointMap<T, VR>,
400{
401}
range_set_blaze/range_values.rs

range_set_blaze/
range_values.rs
