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 super::RunLength;
75
76    #[test]
77    fn test() {
78        let a = vec![3, 1, 1, 4, 1, 5, 5, 5, 9, 9, 9, 2, 2];
79        let mut iter = RunLength::new(&a);
80        assert_eq!(iter.next(), Some((&3, 1)));
81        assert_eq!(iter.next(), Some((&1, 2)));
82        assert_eq!(iter.next(), Some((&4, 1)));
83        assert_eq!(iter.next(), Some((&1, 1)));
84        assert_eq!(iter.next(), Some((&5, 3)));
85        assert_eq!(iter.next_back(), Some((&2, 2)));
86        assert_eq!(iter.next_back(), Some((&9, 3)));
87        assert_eq!(iter.next(), None);
88        assert_eq!(iter.next_back(), None);
89    }
90
91    #[test]
92    fn test_all() {
93        let a = vec![7, 7, 7];
94        let mut iter = RunLength::new(&a);
95        assert_eq!(iter.next(), Some((&7, 3)));
96        assert_eq!(iter.next(), None);
97    }
98
99    #[test]
100    fn empty() {
101        let a = Vec::<i32>::new();
102        let mut iter = RunLength::new(&a);
103        assert_eq!(iter.next(), None);
104    }
105}
run_length/lib.rs

run_length/
lib.rs
