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, 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 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, 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        (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, V> {
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> {
253    iter: I,
254    gather: Option<RangeInclusive<T>>,
255    phantom: PhantomData<VR>,
256}
257
258impl<T, VR, I> FusedIterator for RangeValuesToRangesIter<T, VR, I>
259where
260    T: Integer,
261    VR: ValueRef,
262    I: SortedDisjointMap<T, VR>,
263{
264}
265
266impl<T, VR, I> RangeValuesToRangesIter<T, VR, I>
267where
268    T: Integer,
269    VR: ValueRef,
270    I: SortedDisjointMap<T, VR>,
271{
272    /// Creates a new `RangeValuesToRangesIter` from an existing sorted disjoint map iterator.
273    /// `option_ranges` is initialized as `None` by default.
274    pub(crate) const fn new(iter: I) -> Self {
275        Self {
276            iter,
277            gather: None,
278            phantom: PhantomData,
279        }
280    }
281}
282
283impl<T, VR, I> Iterator for RangeValuesToRangesIter<T, VR, I>
284where
285    T: Integer,
286    VR: ValueRef,
287    I: SortedDisjointMap<T, VR>,
288{
289    type Item = RangeInclusive<T>;
290
291    fn next(&mut self) -> Option<Self::Item> {
292        loop {
293            // If no next value, return gather, if any.
294            let Some(next_range_value) = self.iter.next() else {
295                return self.gather.take();
296            };
297            let (next_start, next_end) = next_range_value.0.into_inner();
298
299            // If there is no gather, start a new gather.
300            let Some(gather) = self.gather.take() else {
301                self.gather = Some(next_start..=next_end);
302                continue;
303            };
304            let (gather_start, gather_end) = gather.into_inner();
305
306            // If next is just touching gather, extend gather.
307            if gather_end.add_one() == next_start {
308                self.gather = Some(gather_start..=next_end);
309                continue;
310            }
311
312            // They are disjoint, return gather and start a new gather.
313            self.gather = Some(next_start..=next_end);
314            return Some(gather_start..=gather_end);
315        }
316    }
317}
318
319#[allow(clippy::redundant_pub_crate)]
320pub(crate) trait ExpectDebugUnwrapRelease<T> {
321    fn expect_debug_unwrap_release(self, msg: &str) -> T;
322}
323
324#[allow(unused_variables)]
325impl<T> ExpectDebugUnwrapRelease<T> for Option<T> {
326    fn expect_debug_unwrap_release(self, msg: &str) -> T {
327        #[cfg(debug_assertions)]
328        {
329            self.expect(msg)
330        }
331        #[cfg(not(debug_assertions))]
332        {
333            self.unwrap()
334        }
335    }
336}
337
338#[expect(clippy::redundant_pub_crate)]
339#[must_use = "iterators are lazy and do nothing unless consumed"]
340#[derive(Clone, Debug)]
341pub(crate) struct SetPriorityMap<T, VR, I> {
342    iter: I,
343    priority_number: usize,
344    phantom: PhantomData<(T, VR)>,
345}
346
347impl<T, VR, I> FusedIterator for SetPriorityMap<T, VR, I>
348where
349    T: Integer,
350    VR: ValueRef,
351    I: SortedDisjointMap<T, VR>,
352{
353}
354
355impl<T, VR, I: Iterator<Item = (RangeInclusive<T>, VR)>> Iterator for SetPriorityMap<T, VR, I> {
356    type Item = Priority<T, VR>;
357
358    fn next(&mut self) -> Option<Self::Item> {
359        self.iter
360            .next()
361            .map(|range_value| Priority::new(range_value, self.priority_number))
362    }
363}
364
365impl<T, VR, I> SetPriorityMap<T, VR, I>
366where
367    T: Integer,
368    VR: ValueRef,
369    I: SortedDisjointMap<T, VR>,
370{
371    pub(crate) const fn new(iter: I, priority: usize) -> Self {
372        Self {
373            iter,
374            priority_number: priority,
375            phantom: PhantomData,
376        }
377    }
378}
379
380impl<T, VR, I> PrioritySortedStartsMap<T, VR> for SetPriorityMap<T, VR, I>
381where
382    T: Integer,
383    VR: ValueRef,
384    I: SortedDisjointMap<T, VR>,
385{
386}
range_set_blaze/range_values.rs

range_set_blaze/
range_values.rs
