braid_core/vendor/rle/
merge_iter.rs

1use crate::vendor::rle::MergableSpan;
2
3/// This is an iterator composer which wraps any iterator over a SplitableSpan to become an
4/// iterator over those same items in run-length order.
5
6#[derive(Debug, Clone)]
7pub struct MergeIter<I: Iterator, const FWD: bool = true> {
8    next: Option<I::Item>,
9    iter: I
10}
11
12pub fn merge_items<I: Iterator>(iter: I) -> MergeIter<I, true> {
13    MergeIter::new(iter)
14}
15pub fn merge_items_rev<I: Iterator>(iter: I) -> MergeIter<I, false> {
16    MergeIter::new(iter)
17}
18
19impl<I: Iterator, const FWD: bool> MergeIter<I, FWD> {
20    pub fn new(iter: I) -> Self {
21        Self {
22            next: None,
23            iter
24        }
25    }
26
27    pub fn into_inner(self) -> I {
28        self.iter
29    }
30}
31
32impl<I, X, const FWD: bool> Iterator for MergeIter<I, FWD>
33where
34    I: Iterator<Item = X>,
35    X: MergableSpan
36{
37    type Item = X;
38
39    fn next(&mut self) -> Option<Self::Item> {
40        let mut this_val = match self.next.take() {
41            Some(val) => val,
42            None => {
43                self.iter.next()?
44            }
45        };
46
47        for val in &mut self.iter {
48            if FWD && this_val.can_append(&val) {
49                this_val.append(val);
50            } else if !FWD && val.can_append(&this_val) {
51                this_val.prepend(val);
52            } else {
53                self.next = Some(val);
54                break;
55            }
56        }
57
58        Some(this_val)
59    }
60
61    fn size_hint(&self) -> (usize, Option<usize>) {
62        let (lower, upper) = self.iter.size_hint();
63        (lower.min(1), upper)
64    }
65}
66
67pub trait MergeableIterator<X: MergableSpan>: Iterator<Item = X> where Self: Sized {
68    fn merge_spans(self) -> MergeIter<Self, true>;
69    fn merge_spans_rev(self) -> MergeIter<Self, false>;
70}
71
72impl<X, I> MergeableIterator<X> for I
73where I: Iterator<Item=X>, X: MergableSpan, Self: Sized
74{
75    fn merge_spans(self) -> MergeIter<Self> {
76        MergeIter::new(self)
77    }
78    fn merge_spans_rev(self) -> MergeIter<Self, false> {
79        MergeIter::new(self)
80    }
81}
82
83#[cfg(test)]
84mod test {
85    use std::ops::Range;
86    use super::merge_items;
87    use crate::vendor::rle::{merge_items_rev, RleRun};
88
89    #[test]
90    fn test_merge_iter() {
91        let empty: Vec<RleRun<u32>> = vec![];
92        assert_eq!(merge_items(empty.into_iter()).collect::<Vec<_>>(), vec![]);
93
94        let one = vec![RleRun { val: 5, len: 1 }];
95        assert_eq!(merge_items(one.into_iter()).collect::<Vec<_>>(), vec![RleRun { val: 5, len: 1 }]);
96
97        let two_split = vec![2u32..3, 5..10];
98        assert_eq!(merge_items(two_split.iter().cloned()).collect::<Vec<_>>(), two_split);
99
100        let two_merged = vec![2u32..5, 5..10];
101        assert_eq!(merge_items(two_merged.iter().cloned()).collect::<Vec<_>>(), vec![2..10]);
102    }
103
104    #[test]
105    fn test_merge_iter_rev() {
106        // TODO: This is a bit of a crap test because it doesn't actually
107        let empty: Vec<Range<u32>> = vec![];
108        assert_eq!(merge_items_rev(empty.into_iter()).collect::<Vec<_>>(), vec![]);
109
110        let one = vec![5..6];
111        assert_eq!(merge_items_rev(one.into_iter()).collect::<Vec<_>>(), vec![5u32..6]);
112
113        let two_split = vec![5u32..10, 2..3];
114        assert_eq!(merge_items_rev(two_split.iter().cloned()).collect::<Vec<_>>(), two_split);
115
116        let two_merged = vec![5u32..10, 2..5];
117        assert_eq!(merge_items_rev(two_merged.iter().cloned()).collect::<Vec<_>>(), vec![2..10]);
118    }
119}
braid_core/vendor/rle/merge_iter.rs

braid_core/vendor/rle/
merge_iter.rs
