rle/
merge_iter.rs

1use crate::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> {
8    next: Option<I::Item>,
9    iter: I
10}
11
12pub fn merge_items<I: Iterator>(iter: I) -> MergeIter<I> {
13    MergeIter::new(iter)
14}
15
16impl<I: Iterator> MergeIter<I> {
17    pub fn new(iter: I) -> Self {
18        Self {
19            next: None,
20            iter
21        }
22    }
23}
24
25impl<I, X> Iterator for MergeIter<I>
26where
27    I: Iterator<Item = X>,
28    X: MergableSpan
29{
30    type Item = X;
31
32    fn next(&mut self) -> Option<Self::Item> {
33        let mut this_val = match self.next.take() {
34            Some(val) => val,
35            None => {
36                match self.iter.next() {
37                    Some(val) => val,
38                    None => { return None; }
39                }
40            }
41        };
42
43        for val in &mut self.iter {
44            if this_val.can_append(&val) {
45                this_val.append(val);
46            } else {
47                self.next = Some(val);
48                break;
49            }
50        }
51
52        Some(this_val)
53    }
54
55    fn size_hint(&self) -> (usize, Option<usize>) {
56        let (lower, upper) = self.iter.size_hint();
57        (lower.min(1), upper)
58    }
59}
60
61pub trait MergeableIterator<X: MergableSpan>: Iterator<Item = X> where Self: Sized {
62    fn merge_spans(self) -> MergeIter<Self>;
63}
64
65impl<X, I> MergeableIterator<X> for I
66where I: Iterator<Item=X>, X: MergableSpan, Self: Sized
67{
68    fn merge_spans(self) -> MergeIter<Self> {
69        MergeIter::new(self)
70    }
71}
72
73#[cfg(test)]
74mod test {
75    use super::merge_items;
76    use crate::RleRun;
77
78    #[test]
79    fn test_merge_iter() {
80        let empty: Vec<RleRun<u32>> = vec![];
81        assert_eq!(merge_items(empty.into_iter()).collect::<Vec<_>>(), vec![]);
82
83        let one = vec![RleRun { val: 5, len: 1 }];
84        assert_eq!(merge_items(one.into_iter()).collect::<Vec<_>>(), vec![RleRun { val: 5, len: 1 }]);
85
86        let two_split = vec![RleRun { val: 5, len: 1 }, RleRun { val: 15, len: 1 }];
87        assert_eq!(merge_items(two_split.iter().copied()).collect::<Vec<_>>(), two_split);
88
89        let two_merged = vec![RleRun { val: 5, len: 1 }, RleRun { val: 5, len: 2 }];
90        assert_eq!(merge_items(two_merged.iter().copied()).collect::<Vec<_>>(), vec![RleRun { val: 5, len: 3 }]);
91    }
92}
rle/merge_iter.rs

rle/
merge_iter.rs
