closed_interval_set/
intersection_iterator.rs

1//! Computes the union of two normalized iterators.
2use crate::ClosedRange;
3use crate::Endpoint;
4use crate::IntoNormalizedRangeIter;
5use crate::NormalizedRangeIter;
6use crate::RangeVec;
7
8use core::iter::Peekable;
9
10pub struct LinearIntersectionIterator<T, X, Y>
11where
12    T: Endpoint,
13    X: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
14    Y: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
15{
16    left: Peekable<X>,
17    right: Peekable<Y>,
18}
19
20impl<T, X, Y> LinearIntersectionIterator<T, X, Y>
21where
22    T: Endpoint,
23    X: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
24    Y: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
25{
26    pub fn new(left: X, right: Y) -> Self {
27        Self {
28            left: left.peekable(),
29            right: right.peekable(),
30        }
31    }
32}
33
34impl<T, X, Y> Iterator for LinearIntersectionIterator<T, X, Y>
35where
36    T: Endpoint,
37    X: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
38    Y: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
39{
40    type Item = (T, T);
41
42    fn next(&mut self) -> Option<(T, T)> {
43        use core::cmp::Ordering; // Safe because both iterators are normalized
44
45        loop {
46            let (Some(left), Some(right)) = (
47                self.left.peek().map(|x| x.get()),
48                self.right.peek().map(|x| x.get()),
49            ) else {
50                return None;
51            };
52
53            // We always advance the smallest endpoint (or both if equal)
54            match left.1.cmp_end(right.1) {
55                Ordering::Less => {
56                    self.left.next();
57                }
58                Ordering::Equal => {
59                    self.left.next();
60                    self.right.next();
61                }
62                Ordering::Greater => {
63                    self.right.next();
64                }
65            }
66
67            // Find the intersection of left and right.
68            let start = left.0.top_end(right.0);
69            let stop = left.1.bot_end(right.1);
70
71            if start.cmp_end(stop) <= Ordering::Equal {
72                return Some((start, stop));
73            }
74        }
75    }
76
77    #[inline]
78    fn size_hint(&self) -> (usize, Option<usize>) {
79        // The intersection can always be empty, but each output range
80        // consumed (at least) one input range.
81        let (_, left_max) = self.left.size_hint();
82        let (_, right_max) = self.right.size_hint();
83
84        if (left_max == Some(0)) | (right_max == Some(0)) {
85            // Intersection with empty is always empty.
86            (0, Some(0))
87        } else {
88            (
89                0,
90                left_max
91                    .unwrap_or(usize::MAX)
92                    .checked_add(right_max.unwrap_or(usize::MAX)),
93            )
94        }
95    }
96}
97
98impl<T, X, Y> crate::private::Sealed for LinearIntersectionIterator<T, X, Y>
99where
100    T: Endpoint,
101    X: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
102    Y: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
103{
104}
105
106impl<T, X, Y> NormalizedRangeIter for LinearIntersectionIterator<T, X, Y>
107where
108    T: Endpoint,
109    X: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
110    Y: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
111{
112}
113
114// We use `Peekable` internally, so we'll reliably return None after None.
115impl<T, X, Y> core::iter::FusedIterator for LinearIntersectionIterator<T, X, Y>
116where
117    T: Endpoint,
118    X: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
119    Y: Sized + NormalizedRangeIter + Iterator<Item: ClosedRange<EndT = T>>,
120{
121}
122
123impl<T: Endpoint> RangeVec<T> {
124    /// Constructs the intersection of this [`RangeVec`] and any iterator of
125    /// ranges.
126    ///
127    /// This operation takes linear time in the size of the two inputs.
128    ///
129    /// See [`RangeVec::intersect_vec`] when the other argument is
130    /// also a [`RangeVec`].
131    #[inline(always)]
132    pub fn intersect(
133        &self,
134        other: impl IntoNormalizedRangeIter<Item: ClosedRange<EndT = T>>,
135    ) -> Self {
136        #[inline(never)]
137        fn doit<T: Endpoint>(
138            this: &RangeVec<T>,
139            other: impl NormalizedRangeIter<Item: ClosedRange<EndT = T>>,
140        ) -> RangeVec<T> {
141            let iter = this.iter().intersect(other);
142            let size_hint = iter.size_hint();
143            if this.is_empty() {
144                debug_assert_eq!(size_hint, (0, Some(0)));
145            }
146
147            let ret = iter.collect_range_vec();
148
149            debug_assert!(ret.len() >= size_hint.0);
150            debug_assert!(ret.len() <= size_hint.1.unwrap_or(usize::MAX));
151
152            ret
153        }
154
155        doit(self, other.into_iter())
156    }
157}
158
159#[cfg(test)]
160#[cfg_attr(coverage_nightly, coverage(off))]
161mod test {
162    use super::*;
163    use alloc::vec;
164    use alloc::vec::Vec;
165
166    #[test]
167    fn smoke_test() {
168        // empty & empty -> empty.
169        let empty: RangeVec<u8> = RangeVec::default();
170        let other = RangeVec::from_vec(vec![(u8::MIN, u8::MAX)]);
171
172        {
173            let empty_empty = empty.iter().intersect(empty.iter());
174
175            assert_eq!(empty_empty.size_hint(), (0, Some(0)));
176            assert_eq!(&empty_empty.collect_range_vec(), &empty);
177        }
178
179        {
180            let empty_other = empty.iter().intersect(other.iter());
181
182            assert_eq!(empty_other.size_hint(), (0, Some(0)));
183            assert_eq!(&empty_other.collect_range_vec(), &empty);
184        }
185
186        {
187            let other_empty = other.iter().intersect(empty.iter());
188
189            assert_eq!(other_empty.size_hint(), (0, Some(0)));
190            assert_eq!(&other_empty.collect_range_vec(), &empty);
191        }
192
193        // We can pull multiple times and get `None`.
194        {
195            let mut other_empty = other.iter().intersect(other.iter());
196
197            // We can't know it's empty.
198            assert!(other_empty.size_hint() != (0, Some(0)));
199
200            assert!(other_empty.next().is_some());
201            // Should be done
202            assert_eq!(other_empty.next(), None);
203            // And still done.
204            assert_eq!(other_empty.next(), None);
205        }
206    }
207
208    #[cfg(test)]
209    proptest::proptest! {
210        #[test]
211        fn test_intersection_iterator(xs: Vec<(u8, u8)>, ys: Vec<(u8, u8)>)
212        {
213            use crate::ranges_to_bits;
214
215            let bits = {
216                let x_bits = ranges_to_bits(&xs);
217                let y_bits = ranges_to_bits(&ys);
218
219                x_bits.into_iter().zip(y_bits.into_iter()).map(|(x, y)| x & y).collect::<Vec<bool>>()
220            };
221
222            {
223                let out = RangeVec::from_vec(xs.clone()).iter().intersect(
224                    RangeVec::from_vec(ys.clone()).iter()).collect_range_vec();
225                assert_eq!(&bits, &ranges_to_bits(&out));
226            }
227
228            {
229                let out = RangeVec::from_vec(ys.clone()).iter().intersect(&RangeVec::from_vec(xs.clone())).collect_range_vec();
230                assert_eq!(&bits, &ranges_to_bits(&out));
231            }
232        }
233
234        #[test]
235        fn test_intersection_identity(xs: Vec<(u8, u8)>, ys: Vec<(u8, u8)>)
236        {
237            // Increase interesting coverage with valid ranges
238            let xs = RangeVec::from_vec(xs.into_iter().map(|(a, b)| (a.min(b), a.max(b))).collect::<Vec<_>>());
239            let ys = RangeVec::from_vec(ys.into_iter().map(|(a, b)| (a.min(b), a.max(b))).collect::<Vec<_>>());
240
241            //  (X & Y) = -(-x | -y),
242            // or
243            // -(X & Y) =  (-x | -y).
244
245            // Try that with iterators.
246            {
247                let not_and = xs.iter().intersect(&ys).complement().collect_range_vec();
248                let or_not = crate::union_vec(xs.iter().complement().collect_range_vec(),
249                                              ys.iter().complement());
250
251                assert_eq!(not_and, or_not);
252            }
253
254            {
255                let and = xs.iter().intersect(&ys).collect_range_vec();
256                let not_or_not = crate::union_vec(xs.iter().complement().collect_range_vec(),
257                                                  ys.iter().complement()).iter().complement().collect_range_vec();
258
259                assert_eq!(and, not_or_not);
260            }
261        }
262    }
263}
closed_interval_set/intersection_iterator.rs

closed_interval_set/
intersection_iterator.rs
