run_length/
lib.rs

1use std::cmp::Eq;
2
3/// [run length encoding](https://ja.wikipedia.org/wiki/%E9%80%A3%E9%95%B7%E5%9C%A7%E7%B8%AE) です。
4///
5/// ```
6/// use run_length::RunLength;
7///
8/// let a = vec![1, 1, 2, 3, 4, 4, 4];
9/// let mut iter = RunLength::new(&a);
10/// assert_eq!(iter.next(), Some((&1, 2)));
11/// assert_eq!(iter.next(), Some((&2, 1)));
12/// assert_eq!(iter.next(), Some((&3, 1)));
13/// assert_eq!(iter.next(), Some((&4, 3)));
14/// assert_eq!(iter.next(), None);
15/// ```
16pub struct RunLength<'a, T> {
17    items: &'a Vec<T>,
18    start: usize,
19    end: usize,
20}
21
22impl<'a, T> RunLength<'a, T> {
23    pub fn new(items: &'a Vec<T>) -> Self {
24        Self {
25            items,
26            start: 0,
27            end: items.len(),
28        }
29    }
30}
31
32impl<'a, T> Iterator for RunLength<'a, T>
33where
34    T: Eq,
35{
36    type Item = (&'a T, usize);
37
38    fn next(&mut self) -> Option<Self::Item> {
39        if self.start >= self.end {
40            return None;
41        }
42
43        let x = &self.items[self.start];
44        let mut len = 0;
45        while self.start + len < self.end && &self.items[self.start + len] == x {
46            len += 1;
47        }
48        self.start += len;
49        Some((x, len))
50    }
51}
52
53impl<'a, T> DoubleEndedIterator for RunLength<'a, T>
54where
55    T: Eq,
56{
57    fn next_back(&mut self) -> Option<Self::Item> {
58        if self.start >= self.end {
59            return None;
60        }
61
62        let x = &self.items[self.end - 1];
63        let mut len = 0;
64        while self.start < self.end - len && &self.items[self.end - len - 1] == x {
65            len += 1;
66        }
67        self.end -= len;
68        Some((x, len))
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use ::proptest::{collection, prelude::*};
75
76    use super::RunLength;
77
78    #[test]
79    fn test() {
80        let a = vec![3, 1, 1, 4, 1, 5, 5, 5, 9, 9, 9, 2, 2];
81        let mut iter = RunLength::new(&a);
82        assert_eq!(iter.next(), Some((&3, 1)));
83        assert_eq!(iter.next(), Some((&1, 2)));
84        assert_eq!(iter.next(), Some((&4, 1)));
85        assert_eq!(iter.next(), Some((&1, 1)));
86        assert_eq!(iter.next(), Some((&5, 3)));
87        assert_eq!(iter.next_back(), Some((&2, 2)));
88        assert_eq!(iter.next_back(), Some((&9, 3)));
89        assert_eq!(iter.next(), None);
90        assert_eq!(iter.next_back(), None);
91    }
92
93    #[test]
94    fn test_all() {
95        let a = vec![7, 7, 7];
96        let mut iter = RunLength::new(&a);
97        assert_eq!(iter.next(), Some((&7, 3)));
98        assert_eq!(iter.next(), None);
99    }
100
101    #[test]
102    fn empty() {
103        let a = Vec::<i32>::new();
104        let mut iter = RunLength::new(&a);
105        assert_eq!(iter.next(), None);
106    }
107
108    proptest! {
109        #[test]
110        fn round_trip(items in collection::vec(proptest::char::range('a', 'z'), 0..=20)) {
111            let rle = RunLength::new(&items);
112
113            let concat = rle.fold(Vec::new(), |mut acc, (&c, l)| {
114                acc.append(&mut vec![c; l]);
115                acc
116            });
117
118            prop_assert_eq!(items, concat);
119        }
120
121        #[test]
122        fn adjacent_runs_differ(items in collection::vec(proptest::num::i32::ANY, 0..=20)) {
123            let rle = RunLength::new(&items).collect::<Vec<_>>();
124
125            for w in rle.windows(2) {
126                let (c0, _) = w[0];
127                let (c1, _) = w[1];
128                prop_assert_ne!(c0, c1);
129            }
130        }
131    }
132}
run_length/lib.rs

run_length/
lib.rs
