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_start, left_end) = left.0.clone().into_inner();
83            let (right_start, right_end) = right.into_inner();
84            // println!("{:?} {:?}", current_range, current_range_value.0);
85
86            // if current_range ends before current_range_value, clear it and loop for a new value.
87            if right_end < left_start {
88                // println!("getting new range");
89                self.right = None;
90                self.left = Some(left);
91                continue;
92            }
93
94            // if current_range_value ends before current_range, clear it and loop for a new value.
95            if left_end < right_start {
96                // println!("getting new range value");
97                self.right = Some(RangeInclusive::new(right_start, right_end));
98                self.left = None;
99                continue;
100            }
101
102            // Thus, they overlap
103            let start = max(right_start, left_start);
104            let end = min(right_end, left_end);
105
106            // remove any ranges that match "end" and set them None
107            let value = if right_end != end {
108                // left_end != end, right_end != end is impossible{
109                debug_assert!(left_end == end);
110
111                // left_end == end, right_end != end
112                self.left = None;
113                self.right = Some(RangeInclusive::new(right_start, right_end));
114                left.1
115            } else if left_end == end {
116                // left_end == end, right_end == end
117                self.left = None;
118                self.right = None;
119                left.1
120            } else {
121                // left_end != end, right_end == end
122                let value = left.1.clone();
123                self.left = Some(left);
124                self.right = None;
125                value
126            };
127
128            let range_value = (start..=end, value);
129            return Some(range_value);
130        }
131    }
132
133    // TODO: Implement size_hint -- this is similar code from the set version.
134    // // There could be a few as 1 (or 0 if the iter is empty) or as many as the iter.
135    // // Plus, possibly one more if we have a range is in progress.
136    // fn size_hint(&self) -> (usize, Option<usize>) {
137    //     let (low, high) = self.iter.size_hint();
138    //     let low = low.min(1);
139    //     if self.option_range_value.is_some() {
140    //         (low, high.map(|x| x + 1))
141    //     } else {
142    //         (low, high)
143    //     }
144    // }
145}
range_set_blaze/intersection_iter_map.rs

range_set_blaze/
intersection_iter_map.rs
