range_set_blaze/
range_values.rs

1use crate::{
2    Integer,
3    map::ValueCarrier,
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, V> {
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 VC 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, V> {
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, V> {
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        let (_, upper) = self.iter.size_hint();
186        (0, upper)
187    }
188}
189
190/// This `struct` is created by the [`into_ranges`] method on [`RangeMapBlaze`]. See [`into_ranges`]'s
191/// documentation for more.
192///
193/// [`RangeMapBlaze`]: crate::RangeMapBlaze
194/// [`into_ranges`]: crate::RangeMapBlaze::into_ranges
195#[must_use = "iterators are lazy and do nothing unless consumed"]
196#[derive(Debug)]
197pub struct MapIntoRangesIter<T, V> {
198    iter: btree_map::IntoIter<T, EndValue<T, V>>,
199    gather: Option<RangeInclusive<T>>,
200}
201
202impl<T: Integer, V: Eq + Clone> MapIntoRangesIter<T, V> {
203    pub(crate) const fn new(iter: btree_map::IntoIter<T, EndValue<T, V>>) -> Self {
204        Self { iter, gather: None }
205    }
206}
207
208impl<T: Integer, V: Eq + Clone> FusedIterator for MapIntoRangesIter<T, V> {}
209
210impl<T: Integer, V: Eq + Clone> Iterator for MapIntoRangesIter<T, V> {
211    type Item = RangeInclusive<T>;
212
213    fn next(&mut self) -> Option<Self::Item> {
214        loop {
215            // If no next, return gather, if any.
216            let Some((start_next, end_value)) = self.iter.next() else {
217                return self.gather.take();
218            };
219
220            let end_next = end_value.end;
221            debug_assert!(start_next <= end_next); // real assert
222
223            // if not gather, start a new gather.
224            let Some(gather) = self.gather.take() else {
225                self.gather = Some(start_next..=end_next);
226                continue;
227            };
228
229            let (gather_start, gather_end) = gather.into_inner();
230
231            // if next is just touching gather, extend gather.
232            if gather_end.add_one() == start_next {
233                self.gather = Some(gather_start..=end_next);
234                continue;
235            }
236
237            // they are disjoint, return gather and start a new gather.
238            self.gather = Some(start_next..=end_next);
239            return Some(gather_start..=gather_end);
240        }
241    }
242
243    fn size_hint(&self) -> (usize, Option<usize>) {
244        // 'Low' could be 0 if empty or 1 if fully merged.
245        let (_, upper) = self.iter.size_hint();
246        (0, upper)
247    }
248}
249
250/// This `struct` is used internally.
251#[derive(Debug, Clone)]
252#[must_use = "iterators are lazy and do nothing unless consumed"]
253#[allow(clippy::module_name_repetitions)]
254pub struct RangeValuesToRangesIter<T, VC, I> {
255    iter: I,
256    gather: Option<RangeInclusive<T>>,
257    phantom: PhantomData<VC>,
258}
259
260impl<T, VC, I> FusedIterator for RangeValuesToRangesIter<T, VC, I>
261where
262    T: Integer,
263    VC: ValueCarrier,
264    I: SortedDisjointMap<T, VC>,
265{
266}
267
268impl<T, VC, I> RangeValuesToRangesIter<T, VC, I>
269where
270    T: Integer,
271    VC: ValueCarrier,
272    I: SortedDisjointMap<T, VC>,
273{
274    /// Creates a new `RangeValuesToRangesIter` from an existing sorted disjoint map iterator.
275    /// `option_ranges` is initialized as `None` by default.
276    pub(crate) const fn new(iter: I) -> Self {
277        Self {
278            iter,
279            gather: None,
280            phantom: PhantomData,
281        }
282    }
283}
284
285impl<T, VC, I> Iterator for RangeValuesToRangesIter<T, VC, I>
286where
287    T: Integer,
288    VC: ValueCarrier,
289    I: SortedDisjointMap<T, VC>,
290{
291    type Item = RangeInclusive<T>;
292
293    fn next(&mut self) -> Option<Self::Item> {
294        loop {
295            // If no next value, return gather, if any.
296            let Some(next_range_value) = self.iter.next() else {
297                return self.gather.take();
298            };
299            let (next_range, _) = next_range_value;
300            let (next_start, next_end) = next_range.into_inner();
301
302            // If there is no gather, start a new gather.
303            let Some(gather) = self.gather.take() else {
304                self.gather = Some(next_start..=next_end);
305                continue;
306            };
307            let (gather_start, gather_end) = gather.into_inner();
308
309            // If next is just touching gather, extend gather.
310            if gather_end.add_one() == next_start {
311                self.gather = Some(gather_start..=next_end);
312                continue;
313            }
314
315            // They are disjoint, return gather and start a new gather.
316            self.gather = Some(next_start..=next_end);
317            return Some(gather_start..=gather_end);
318        }
319    }
320}
321
322#[allow(clippy::redundant_pub_crate)]
323pub(crate) trait ExpectDebugUnwrapRelease<T> {
324    fn expect_debug_unwrap_release(self, msg: &str) -> T;
325}
326
327#[allow(unused_variables)]
328impl<T> ExpectDebugUnwrapRelease<T> for Option<T> {
329    fn expect_debug_unwrap_release(self, msg: &str) -> T {
330        #[cfg(debug_assertions)]
331        {
332            self.expect(msg)
333        }
334        #[cfg(not(debug_assertions))]
335        {
336            self.unwrap()
337        }
338    }
339}
340
341#[expect(clippy::redundant_pub_crate)]
342#[must_use = "iterators are lazy and do nothing unless consumed"]
343#[derive(Clone, Debug)]
344pub(crate) struct SetPriorityMap<T, VC, I> {
345    iter: I,
346    priority_number: usize,
347    phantom: PhantomData<(T, VC)>,
348}
349
350impl<T, VC, I> FusedIterator for SetPriorityMap<T, VC, I>
351where
352    T: Integer,
353    VC: ValueCarrier,
354    I: SortedDisjointMap<T, VC>,
355{
356}
357
358impl<T, VC, I: Iterator<Item = (RangeInclusive<T>, VC)>> Iterator for SetPriorityMap<T, VC, I> {
359    type Item = Priority<T, VC>;
360
361    fn next(&mut self) -> Option<Self::Item> {
362        self.iter
363            .next()
364            .map(|range_value| Priority::new(range_value, self.priority_number))
365    }
366}
367
368impl<T, VC, I> SetPriorityMap<T, VC, I>
369where
370    T: Integer,
371    VC: ValueCarrier,
372    I: SortedDisjointMap<T, VC>,
373{
374    pub(crate) const fn new(iter: I, priority: usize) -> Self {
375        Self {
376            iter,
377            priority_number: priority,
378            phantom: PhantomData,
379        }
380    }
381}
382
383impl<T, VC, I> PrioritySortedStartsMap<T, VC> for SetPriorityMap<T, VC, I>
384where
385    T: Integer,
386    VC: ValueCarrier,
387    I: SortedDisjointMap<T, VC>,
388{
389}
range_set_blaze/range_values.rs

range_set_blaze/
range_values.rs
