range_set_blaze/
intersection_iter_map.rs

1use core::{
2    cmp::{max, min},
3    iter::FusedIterator,
4    ops::RangeInclusive,
5};
6
7use crate::Integer;
8use crate::{SortedDisjoint, SortedDisjointMap, map::ValueRef};
9
10/// This `struct` is created by the [`intersection`] and [`map_and_set_intersection`] methods on [`SortedDisjointMap`].
11/// See the methods' documentation for more.
12///
13/// [`SortedDisjointMap`]: crate::SortedDisjointMap
14/// [`intersection`]: crate::SortedDisjointMap::intersection
15/// [`map_and_set_intersection`]: crate::SortedDisjointMap::map_and_set_intersection
16#[must_use = "iterators are lazy and do nothing unless consumed"]
17#[derive(Clone, Debug)]
18pub struct IntersectionIterMap<T, VR, IM, IS>
19where
20    T: Integer,
21    VR: ValueRef,
22    IM: SortedDisjointMap<T, VR>,
23    IS: SortedDisjoint<T>,
24{
25    iter_left: IM,
26    iter_right: IS,
27    right: Option<RangeInclusive<T>>,
28    left: Option<(RangeInclusive<T>, VR)>,
29}
30
31impl<T, VR, IM, IS> IntersectionIterMap<T, VR, IM, IS>
32where
33    T: Integer,
34    VR: ValueRef,
35    IM: SortedDisjointMap<T, VR>,
36    IS: SortedDisjoint<T>,
37{
38    pub(crate) const fn new(iter_map: IM, iter_set: IS) -> Self {
39        Self {
40            iter_left: iter_map,
41            iter_right: iter_set,
42            right: None,
43            left: None,
44        }
45    }
46}
47
48impl<T, VR, IM, IS> FusedIterator for IntersectionIterMap<T, VR, IM, IS>
49where
50    T: Integer,
51    VR: ValueRef,
52    IM: SortedDisjointMap<T, VR> + FusedIterator,
53    IS: SortedDisjoint<T> + FusedIterator,
54{
55}
56
57// Note: ExactSizeIterator cannot be safely implemented for IntersectionIterMap
58// because we can't determine the exact number of items that will be produced
59// by the intersection without fully processing both iterators.
60// An upper bound would be min(left.len(), right.len()), but that's not exact.
61
62impl<T, VR, IM, IS> Iterator for IntersectionIterMap<T, VR, IM, IS>
63where
64    T: Integer,
65    VR: ValueRef,
66    IM: SortedDisjointMap<T, VR>,
67    IS: SortedDisjoint<T>,
68{
69    type Item = (RangeInclusive<T>, VR);
70
71    fn next(&mut self) -> Option<(RangeInclusive<T>, VR)> {
72        // println!("begin next");
73        loop {
74            // Be sure both currents are loaded.
75            self.left = self.left.take().or_else(|| self.iter_left.next());
76            self.right = self.right.take().or_else(|| self.iter_right.next());
77
78            // If either is still none, we are done.
79            let (Some(left), Some(right)) = (self.left.take(), self.right.take()) else {
80                return None;
81            };
82            let (left_range, left_value) = left;
83            let (left_start, left_end) = left_range.clone().into_inner();
84            let (right_start, right_end) = right.into_inner();
85            // println!("{:?} {:?}", current_range, current_range_value.0);
86
87            // if current_range ends before current_range_value, clear it and loop for a new value.
88            if right_end < left_start {
89                // println!("getting new range");
90                self.right = None;
91                self.left = Some((left_range, left_value));
92                continue;
93            }
94
95            // if current_range_value ends before current_range, clear it and loop for a new value.
96            if left_end < right_start {
97                // println!("getting new range value");
98                self.right = Some(RangeInclusive::new(right_start, right_end));
99                self.left = None;
100                continue;
101            }
102
103            // Thus, they overlap
104            let start = max(right_start, left_start);
105            let end = min(right_end, left_end);
106
107            // Modified logic: Now prioritize right range boundaries instead of left
108            let value = if left_end != end {
109                // right_end != end, left_end != end is impossible
110                debug_assert!(right_end == end);
111
112                // right_end == end, left_end != end
113                let value = left_value.clone();
114                self.right = None;
115                self.left = Some((left_range, left_value));
116                value
117            } else if right_end == end {
118                // right_end == end, left_end == end
119                self.left = None;
120                self.right = None;
121                left_value
122            } else {
123                // right_end != end, left_end == end
124                self.right = Some(RangeInclusive::new(right_start, right_end));
125                self.left = None;
126                left_value
127            };
128
129            let range_value = (start..=end, value);
130            return Some(range_value);
131        }
132    }
133
134    // TODO: Implement size_hint -- this is similar code from the set version.
135    // // There could be a few as 1 (or 0 if the iter is empty) or as many as the iter.
136    // // Plus, possibly one more if we have a range is in progress.
137    // fn size_hint(&self) -> (usize, Option<usize>) {
138    //     let (low, high) = self.iter.size_hint();
139    //     let low = low.min(1);
140    //     if self.option_range_value.is_some() {
141    //         (low, high.map(|x| x + 1))
142    //     } else {
143    //         (low, high)
144    //     }
145    // }
146}
range_set_blaze/intersection_iter_map.rs

range_set_blaze/
intersection_iter_map.rs
