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

range_set_blaze/
intersection_iter_map.rs
