range_set_blaze/
sym_diff_iter_map.rs

1use core::{
2    cmp::{self, min},
3    iter::FusedIterator,
4    ops::RangeInclusive,
5};
6
7use alloc::collections::BinaryHeap;
8
9use crate::{
10    Integer, MergeMap, SortedDisjointMap, SymDiffKMergeMap, SymDiffMergeMap,
11    map::ValueRef,
12    merge_map::KMergeMap,
13    sorted_disjoint_map::{Priority, PrioritySortedStartsMap},
14};
15
16/// This `struct` is created by the [`symmetric_difference`] method on [`SortedDisjointMap`]. See [`symmetric_difference`]'s
17/// documentation for more.
18///
19/// [`SortedDisjointMap`]: crate::SortedDisjointMap
20/// [`symmetric_difference`]: crate::SortedDisjointMap::symmetric_difference
21#[derive(Clone, Debug)]
22#[must_use = "iterators are lazy and do nothing unless consumed"]
23pub struct SymDiffIterMap<T, VR, I>
24where
25    T: Integer,
26    VR: ValueRef,
27    I: PrioritySortedStartsMap<T, VR>,
28{
29    iter: I,
30    next_item: Option<Priority<T, VR>>,
31    workspace: BinaryHeap<Priority<T, VR>>,
32    workspace_next_end: Option<T>,
33    gather: Option<(RangeInclusive<T>, VR)>,
34    ready_to_go: Option<(RangeInclusive<T>, VR)>,
35}
36
37#[expect(clippy::ref_option)]
38fn min_next_end<T>(next_end: &Option<T>, next_item_end: T) -> T
39where
40    T: Integer,
41{
42    next_end.map_or_else(
43        || next_item_end,
44        |current_end| cmp::min(current_end, next_item_end),
45    )
46}
47
48impl<T, VR, I> FusedIterator for SymDiffIterMap<T, VR, I>
49where
50    T: Integer,
51    VR: ValueRef,
52    I: PrioritySortedStartsMap<T, VR>,
53{
54}
55
56impl<T, VR, I> Iterator for SymDiffIterMap<T, VR, I>
57where
58    T: Integer,
59    VR: ValueRef,
60    I: PrioritySortedStartsMap<T, VR>,
61{
62    type Item = (RangeInclusive<T>, VR);
63
64    fn next(&mut self) -> Option<(RangeInclusive<T>, VR)> {
65        // Keep doing this until we have something to return.
66        loop {
67            if let Some(value) = self.ready_to_go.take() {
68                // If ready_to_go is Some, return the value immediately.
69                return Some(value);
70            }
71
72            // if self.next_item should go into the workspace, then put it there, get the next, next_item, and loop
73            if let Some(next_item) = self.next_item.take() {
74                let (next_start, next_end) = next_item.start_and_end();
75
76                // If workspace is empty, just push the next item
77                let Some(best) = self.workspace.peek() else {
78                    self.workspace_next_end =
79                        Some(min_next_end(&self.workspace_next_end, next_end));
80                    self.workspace.push(next_item);
81                    self.next_item = self.iter.next();
82                    continue; // return to top of the main processing loop
83                };
84                let best = best.range_value();
85                if next_start == *best.0.start() {
86                    // Always push (this differs from UnionIterMap)
87                    self.workspace_next_end =
88                        Some(min_next_end(&self.workspace_next_end, next_end));
89                    self.workspace.push(next_item);
90                    self.next_item = self.iter.next();
91                    continue; // return to top of the main processing loop
92                }
93
94                // It does not go into the workspace, so just hold it and keep processing.
95                self.next_item = Some(next_item);
96            }
97
98            // If the workspace is empty, we are done.
99            let Some(best) = self.workspace.peek() else {
100                debug_assert!(self.next_item.is_none());
101                debug_assert!(self.ready_to_go.is_none());
102                return self.gather.take();
103            };
104            let best = best.range_value();
105
106            // We buffer for output the best item up to the start of the next item (if any).
107
108            // Find the start of the next item, if any.
109            let mut next_end = self
110                .workspace_next_end
111                .take()
112                .expect("Real Assert: safe because we know the workspace is not empty");
113            if let Some(next_item) = self.next_item.as_ref() {
114                next_end = min(next_item.start().sub_one(), next_end);
115            }
116
117            // Add the front of best to the gather buffer.
118            if let Some(mut gather) = self.gather.take() {
119                if gather.1.borrow() == best.1.borrow()
120                    && (*gather.0.end()).add_one() == *best.0.start()
121                {
122                    if self.workspace.len().is_odd() {
123                        // if the gather is contiguous with the best, then merge them
124                        gather.0 = *gather.0.start()..=next_end;
125                        self.gather = Some(gather);
126                    } else {
127                        // if an even number of items in the workspace, then flush the gather
128                        self.ready_to_go = Some(gather);
129                        debug_assert!(self.gather.is_none());
130                    }
131                } else {
132                    // if the gather is not contiguous with the best, then output the gather and set the gather to the best
133                    self.ready_to_go = Some(gather);
134                    // FYI: this code appear twice # 1 of 2
135                    if self.workspace.len().is_odd() {
136                        self.gather = Some((*best.0.start()..=next_end, best.1.clone()));
137                    } else {
138                        debug_assert!(self.gather.is_none());
139                    }
140                }
141            } else {
142                // if there is no gather, then set the gather to the best
143                // FYI: this code appear twice # 2 of 2
144                if self.workspace.len().is_odd() {
145                    self.gather = Some((*best.0.start()..=next_end, best.1.clone()));
146                } else {
147                    debug_assert!(self.gather.is_none());
148                }
149            }
150
151            // We also update the workspace to removing any items that are completely covered by the new_start.
152            // (Unlike UnionIterMap, we must keep any items that have a lower priority and are shorter than the new best.)
153            self.workspace_next_end = None;
154            self.workspace = self
155                .workspace
156                .drain()
157                .filter(|item| item.end() > next_end)
158                .map(|mut item| {
159                    item.set_range(next_end.add_one()..=item.end());
160                    self.workspace_next_end =
161                        Some(min_next_end(&self.workspace_next_end, item.end()));
162                    item
163                })
164                .collect();
165        } // end of main loop
166    }
167}
168
169impl<T, VR, L, R> SymDiffMergeMap<T, VR, L, R>
170where
171    T: Integer,
172    VR: ValueRef,
173    L: SortedDisjointMap<T, VR>,
174    R: SortedDisjointMap<T, VR>,
175{
176    #[inline]
177    pub(crate) fn new2(left: L, right: R) -> Self {
178        let iter = MergeMap::new(left, right);
179        Self::new(iter)
180    }
181}
182
183impl<T, VR, J> SymDiffKMergeMap<T, VR, J>
184where
185    T: Integer,
186    VR: ValueRef,
187    J: SortedDisjointMap<T, VR>,
188{
189    #[inline]
190    pub(crate) fn new_k<K>(k: K) -> Self
191    where
192        K: IntoIterator<Item = J>,
193    {
194        let iter = KMergeMap::new(k);
195        Self::new(iter)
196    }
197}
198
199impl<T, VR, I> SymDiffIterMap<T, VR, I>
200where
201    T: Integer,
202    VR: ValueRef,
203    I: PrioritySortedStartsMap<T, VR>,
204{
205    #[inline]
206    pub(crate) fn new(mut iter: I) -> Self {
207        let item = iter.next();
208        Self {
209            iter,
210            next_item: item,
211            workspace: BinaryHeap::new(),
212            workspace_next_end: None,
213            gather: None,
214            ready_to_go: None,
215        }
216    }
217}
218
219#[allow(clippy::wrong_self_convention)]
220#[allow(clippy::redundant_pub_crate)]
221pub(crate) trait UsizeExtensions {
222    fn is_odd(self) -> bool;
223}
224
225impl UsizeExtensions for usize {
226    #[inline]
227    fn is_odd(self) -> bool {
228        self & 1 != 0
229    }
230}
range_set_blaze/sym_diff_iter_map.rs

range_set_blaze/
sym_diff_iter_map.rs
