braid_core/vendor/rle/
intersect.rs

1use crate::vendor::rle::{HasRleKey, HasLength, SplitableSpan};
2use crate::vendor::rle::zip::Remainder;
3
4#[derive(Debug, Clone)]
5pub struct RleIntersect<A, B, const FWD: bool = true> where A: Iterator, B: Iterator
6{
7    rem: Remainder<A::Item, B::Item>,
8    a: A,
9    b: B,
10}
11
12impl<A, B> RleIntersect<A, B, true> where A: Iterator, B: Iterator {
13    pub fn new_fwd(a: A, b: B) -> Self {
14        Self {
15            rem: Default::default(),
16            a, b
17        }
18    }
19}
20impl<A, B> RleIntersect<A, B, false> where A: Iterator, B: Iterator {
21    pub fn new_rev(a: A, b: B) -> Self {
22        Self {
23            rem: Default::default(),
24            a, b
25        }
26    }
27}
28
29impl<A, B> Iterator for RleIntersect<A, B, true> where A: Iterator, B: Iterator,
30    A::Item: SplitableSpan + HasLength + HasRleKey,
31    B::Item: SplitableSpan + HasLength + HasRleKey
32{
33    type Item = (A::Item, B::Item);
34
35    fn next(&mut self) -> Option<Self::Item> {
36        // If b is None here, we'll discard the a item, but the iterator will only produce None
37        // from here anyway so its not a big deal.
38        let (mut a, mut b) = self.rem.take_from_iter(&mut self.a, &mut self.b)?;
39
40        loop {
41            let a_key = a.rle_key();
42            let b_key = b.rle_key();
43
44            if a_key >= b_key + b.len() {
45                // This could be further optimized, but its not a big deal here.
46                b = self.b.next()?;
47                continue;
48            }
49            if b_key >= a_key + a.len() {
50                a = self.a.next()?;
51                continue;
52            }
53
54            // Ok, they have some intersection.
55            if a_key > b_key {
56                b.truncate_keeping_right(a_key - b_key);
57            } else if b_key > a_key {
58                a.truncate_keeping_right(b_key - a_key);
59            }
60
61            if b.len() > a.len() {
62                let rem = b.truncate(a.len());
63                self.rem = Remainder::SomeB(rem);
64            } else if a.len() > b.len() {
65                let rem = a.truncate(b.len());
66                self.rem = Remainder::SomeA(rem);
67            } // Else the remainder should be nothing, but that should happen anyway.
68
69            return Some((a, b));
70        }
71    }
72}
73
74// For backwards items.
75impl<A, B> Iterator for RleIntersect<A, B, false> where A: Iterator, B: Iterator,
76    A::Item: SplitableSpan + HasLength + HasRleKey,
77    B::Item: SplitableSpan + HasLength + HasRleKey
78{
79    type Item = (A::Item, B::Item);
80
81    fn next(&mut self) -> Option<Self::Item> {
82        // If b is None here, we'll discard the a item, but the iterator will only produce None
83        // from here anyway so its not a big deal.
84        let (mut a, mut b) = self.rem.take_from_iter(&mut self.a, &mut self.b)?;
85
86        loop {
87            let a_key = a.rle_key();
88            let b_key = b.rle_key();
89
90            if a_key >= b_key + b.len() {
91                a = self.a.next()?;
92                continue;
93            }
94            if b_key >= a_key + a.len() {
95                b = self.b.next()?;
96                continue;
97            }
98
99            // Ok, they have some intersection.
100            if a_key > b_key {
101                let rem = b.truncate_keeping_right(a_key - b_key);
102                self.rem = Remainder::SomeB(rem);
103            } else if b_key > a_key {
104                let rem = a.truncate_keeping_right(b_key - a_key);
105                self.rem = Remainder::SomeA(rem);
106            }
107
108            if b.len() > a.len() {
109                b.truncate(a.len());
110            } else if a.len() > b.len() {
111                a.truncate(b.len());
112            }
113
114            return Some((a, b));
115        }
116    }
117}
118
119pub fn rle_intersect<A, B>(a: A, b: B) -> RleIntersect<A, B>
120    where A: Iterator, B: Iterator,
121          A::Item: SplitableSpan + HasLength + HasRleKey,
122          B::Item: SplitableSpan + HasLength + HasRleKey
123{
124    RleIntersect::new_fwd(a, b)
125}
126
127pub fn rle_intersect_first<A, B>(a: A, b: B) -> impl Iterator<Item = A::Item>
128    where A: Iterator, B: Iterator,
129          A::Item: SplitableSpan + HasLength + HasRleKey,
130          B::Item: SplitableSpan + HasLength + HasRleKey
131{
132    RleIntersect::new_fwd(a, b).map(|(a, _)| a)
133}
134
135pub fn rle_intersect_rev<A, B>(a: A, b: B) -> RleIntersect<A, B, false>
136    where A: Iterator, B: Iterator,
137          A::Item: SplitableSpan + HasLength + HasRleKey,
138          B::Item: SplitableSpan + HasLength + HasRleKey
139{
140    RleIntersect::new_rev(a, b)
141}
142
143pub fn rle_intersect_rev_first<A, B>(a: A, b: B) -> impl Iterator<Item = A::Item>
144    where A: Iterator, B: Iterator,
145          A::Item: SplitableSpan + HasLength + HasRleKey,
146          B::Item: SplitableSpan + HasLength + HasRleKey
147{
148    RleIntersect::new_rev(a, b).map(|(a, _)| a)
149}
150
151#[cfg(test)]
152mod test {
153    use std::ops::Range;
154    use crate::vendor::rle::intersect::*;
155
156    fn dup(a: &[Range<u32>]) -> Vec<(Range<u32>, Range<u32>)> {
157        a.iter().map(|r| (r.clone(), r.clone())).collect::<Vec<_>>()
158    }
159
160    fn test_intersect(a: &[Range<u32>], b: &[Range<u32>], expect: &[Range<u32>]) {
161        let result1: Vec<_> = rle_intersect(a.iter().cloned(), b.iter().cloned()).collect();
162        // Swapped
163        let result2: Vec<_> = rle_intersect(b.iter().cloned(), a.iter().cloned()).collect();
164
165        // The result is repeated here because we get an entry from both a and b.
166        let expect_dup = dup(expect);
167        assert_eq!(result1, expect_dup);
168        assert_eq!(result2, expect_dup);
169
170        // Also an item crossed with itself should produce itself.
171        let cloned_a: Vec<_> = rle_intersect(a.iter().cloned(), a.iter().cloned()).collect();
172        assert_eq!(cloned_a, dup(a));
173        let cloned_b: Vec<_> = rle_intersect(b.iter().cloned(), b.iter().cloned()).collect();
174        assert_eq!(cloned_b, dup(b));
175
176        let mut result_rev1: Vec<_> = rle_intersect_rev(a.iter().rev().cloned(), b.iter().rev().cloned())
177            .collect();
178        result_rev1.reverse();
179        assert_eq!(result_rev1, expect_dup);
180
181        let mut result_rev2: Vec<_> = rle_intersect_rev(b.iter().rev().cloned(), a.iter().rev().cloned())
182            .collect();
183        result_rev2.reverse();
184        assert_eq!(result_rev2, expect_dup);
185    }
186
187    #[test]
188    fn intersect_smoke() {
189        test_intersect(&[0..5, 10..20], &[3..15], &[3..5, 10..15]);
190        test_intersect(&[0..5, 10..20], &[10..20], &[10..20]);
191        test_intersect(&[0..5], &[10..20], &[]);
192        test_intersect(&[0..5], &[5..10], &[]);
193        test_intersect(&[0..20], &[5..10], &[5..10]);
194    }
195
196    #[test]
197    fn intersect_with_empty() {
198        test_intersect(&[], &[0..100], &[]);
199        test_intersect(&[], &[], &[]);
200    }
201}
braid_core/vendor/rle/intersect.rs

braid_core/vendor/rle/
intersect.rs
