range_set_blaze/
unsorted_priority_map.rs

1use crate::map::ValueRef;
2use crate::range_values::ExpectDebugUnwrapRelease;
3use crate::sorted_disjoint_map::{Priority, PrioritySortedStartsMap};
4use crate::{Integer, map::EndValue, sorted_disjoint_map::SortedDisjointMap};
5use core::ops::RangeInclusive;
6use core::{
7    cmp::{max, min},
8    iter::FusedIterator,
9    marker::PhantomData,
10};
11use num_traits::Zero;
12
13#[must_use = "iterators are lazy and do nothing unless consumed"]
14#[allow(clippy::redundant_pub_crate)]
15pub(crate) struct UnsortedPriorityMap<T, VR, I>
16where
17    T: Integer,
18    VR: ValueRef,
19    I: Iterator<Item = (RangeInclusive<T>, VR)>,
20{
21    iter: I,
22    option_priority: Option<Priority<T, VR>>,
23    min_value_plus_2: T,
24    priority_number: usize,
25}
26
27impl<T, VR, I> UnsortedPriorityMap<T, VR, I>
28where
29    T: Integer,
30    VR: ValueRef,
31    I: Iterator<Item = (RangeInclusive<T>, VR)>, // Any iterator is fine
32{
33    #[inline]
34    pub(crate) fn new(into_iter: I) -> Self {
35        Self {
36            iter: into_iter,
37            option_priority: None,
38            min_value_plus_2: T::min_value().add_one().add_one(),
39            priority_number: 0,
40        }
41    }
42}
43
44impl<T, VR, I> FusedIterator for UnsortedPriorityMap<T, VR, I>
45where
46    T: Integer,
47    VR: ValueRef,
48    I: Iterator<Item = (RangeInclusive<T>, VR)>,
49{
50}
51
52impl<T, VR, I> Iterator for UnsortedPriorityMap<T, VR, I>
53where
54    T: Integer,
55    VR: ValueRef,
56    I: Iterator<Item = (RangeInclusive<T>, VR)>,
57{
58    type Item = Priority<T, VR>;
59
60    fn next(&mut self) -> Option<Self::Item> {
61        loop {
62            // Get the next range_value, if none, return the current range_value
63            let Some(next_range_value) = self.iter.next() else {
64                return self.option_priority.take();
65            };
66            let next_priority = Priority::new(next_range_value, self.priority_number);
67            self.priority_number = self
68                .priority_number
69                .checked_add(1)
70                .expect_debug_unwrap_release("underflow");
71
72            // check the next range is valid and non-empty
73            let (next_start, next_end) = next_priority.start_and_end();
74            if next_start > next_end {
75                continue;
76            }
77
78            // get the current range (if none, set the current range to the next range and loop)
79            let Some(mut current_priority) = self.option_priority.take() else {
80                self.option_priority = Some(next_priority);
81                continue;
82            };
83
84            // If the values are different or the ranges do not touch or overlap,
85            // return the current range and set the current range to the next range
86            let (current_start, current_end) = current_priority.start_and_end();
87            if current_priority.value().borrow() != next_priority.value().borrow()
88                || (next_start >= self.min_value_plus_2
89                    && current_end <= next_start.sub_one().sub_one())
90                || (current_start >= self.min_value_plus_2
91                    && next_end <= current_start.sub_one().sub_one())
92            {
93                self.option_priority = Some(next_priority);
94                return Some(current_priority);
95            }
96
97            // They touch or overlap and have the same value, so merge
98            current_priority.set_range(min(current_start, next_start)..=max(current_end, next_end));
99            self.option_priority = Some(current_priority);
100
101            // return to the top of the loop
102        }
103    }
104
105    // As few as one (or zero if iter is empty) and as many as iter.len()
106    // There could be one extra if option_range is Some.
107    fn size_hint(&self) -> (usize, Option<usize>) {
108        let (lower, upper) = self.iter.size_hint();
109        let lower = min(lower, 1);
110        if self.option_priority.is_some() {
111            (lower, upper.map(|x| x + 1))
112        } else {
113            (lower, upper)
114        }
115    }
116}
117
118#[must_use = "iterators are lazy and do nothing unless consumed"]
119#[allow(clippy::redundant_pub_crate)]
120pub(crate) struct SortedDisjointMapWithLenSoFar<T, VR, I>
121where
122    T: Integer,
123    VR: ValueRef,
124    I: SortedDisjointMap<T, VR>,
125{
126    iter: I,
127    len: <T as Integer>::SafeLen,
128    phantom: PhantomData<VR>,
129}
130
131impl<T, VR, I> SortedDisjointMapWithLenSoFar<T, VR, I>
132where
133    T: Integer,
134    VR: ValueRef,
135    I: SortedDisjointMap<T, VR>,
136{
137    pub(crate) const fn len_so_far(&self) -> <T as Integer>::SafeLen {
138        self.len
139    }
140
141    pub(crate) fn new(iter: I) -> Self {
142        Self {
143            iter,
144            len: <T as Integer>::SafeLen::zero(),
145            phantom: PhantomData,
146        }
147    }
148}
149
150impl<T, VR, I> FusedIterator for SortedDisjointMapWithLenSoFar<T, VR, I>
151where
152    T: Integer,
153    VR: ValueRef,
154    I: SortedDisjointMap<T, VR>,
155{
156}
157
158impl<T, VR, I> Iterator for SortedDisjointMapWithLenSoFar<T, VR, I>
159where
160    T: Integer,
161    VR: ValueRef,
162    I: SortedDisjointMap<T, VR>,
163{
164    type Item = (T, EndValue<T, VR::Target>);
165
166    fn next(&mut self) -> Option<Self::Item> {
167        if let Some((range, value)) = self.iter.next() {
168            let (start, end) = range.clone().into_inner();
169            debug_assert!(start <= end);
170            self.len += T::safe_len(&range);
171            let end_value = EndValue {
172                end,
173                value: value.into_value(),
174            };
175            Some((start, end_value))
176        } else {
177            None
178        }
179    }
180    fn size_hint(&self) -> (usize, Option<usize>) {
181        self.iter.size_hint()
182    }
183}
184
185#[derive(Clone, Debug)]
186#[must_use = "iterators are lazy and do nothing unless consumed"]
187/// Used internally by [`UnionIterMap`] and [`SymDiffIterMap`].
188///
189/// [`UnionIterMap`]: crate::UnionIterMap
190/// [`SymDiffIterMap`]: crate::SymDiffIterMap
191pub struct AssumePrioritySortedStartsMap<T, VR, I>
192where
193    T: Integer,
194    VR: ValueRef,
195    I: Iterator<Item = Priority<T, VR>> + FusedIterator,
196{
197    iter: I,
198}
199
200impl<T, VR, I> PrioritySortedStartsMap<T, VR> for AssumePrioritySortedStartsMap<T, VR, I>
201where
202    T: Integer,
203    VR: ValueRef,
204    I: Iterator<Item = Priority<T, VR>> + FusedIterator,
205{
206}
207
208impl<T, VR, I> AssumePrioritySortedStartsMap<T, VR, I>
209where
210    T: Integer,
211    VR: ValueRef,
212    I: Iterator<Item = Priority<T, VR>> + FusedIterator,
213{
214    pub(crate) const fn new(iter: I) -> Self {
215        Self { iter }
216    }
217}
218
219impl<T, VR, I> FusedIterator for AssumePrioritySortedStartsMap<T, VR, I>
220where
221    T: Integer,
222    VR: ValueRef,
223    I: Iterator<Item = Priority<T, VR>> + FusedIterator,
224{
225}
226
227impl<T, VR, I> Iterator for AssumePrioritySortedStartsMap<T, VR, I>
228where
229    T: Integer,
230    VR: ValueRef,
231    I: Iterator<Item = Priority<T, VR>> + FusedIterator,
232{
233    type Item = Priority<T, VR>;
234
235    fn next(&mut self) -> Option<Self::Item> {
236        self.iter.next()
237    }
238
239    fn size_hint(&self) -> (usize, Option<usize>) {
240        self.iter.size_hint()
241    }
242}
range_set_blaze/unsorted_priority_map.rs

range_set_blaze/
unsorted_priority_map.rs
