1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

use std::cmp::Eq;

/// [run length encoding](https://ja.wikipedia.org/wiki/%E9%80%A3%E9%95%B7%E5%9C%A7%E7%B8%AE) です。
///
/// ```
/// use run_length::RunLength;
///
/// let a = vec![1, 1, 2, 3, 4, 4, 4];
/// let mut iter = RunLength::new(&a);
/// assert_eq!(iter.next(), Some((&1, 2)));
/// assert_eq!(iter.next(), Some((&2, 1)));
/// assert_eq!(iter.next(), Some((&3, 1)));
/// assert_eq!(iter.next(), Some((&4, 3)));
/// assert_eq!(iter.next(), None);
/// ```
pub struct RunLength<'a, T> {
    items: &'a Vec<T>,
    start: usize,
    end: usize,
}

impl<'a, T> RunLength<'a, T> {
    pub fn new(items: &'a Vec<T>) -> Self {
        Self {
            items,
            start: 0,
            end: items.len(),
        }
    }
}

impl<'a, T> Iterator for RunLength<'a, T>
where
    T: Eq,
{
    type Item = (&'a T, usize);

    fn next(&mut self) -> Option<Self::Item> {
        if self.start >= self.end {
            return None;
        }

        let x = &self.items[self.start];
        let mut len = 0;
        while self.start + len < self.end && &self.items[self.start + len] == x {
            len += 1;
        }
        self.start += len;
        Some((x, len))
    }
}

impl<'a, T> DoubleEndedIterator for RunLength<'a, T>
where
    T: Eq,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.start >= self.end {
            return None;
        }

        let x = &self.items[self.end - 1];
        let mut len = 0;
        while self.start < self.end - len && &self.items[self.end - len - 1] == x {
            len += 1;
        }
        self.end -= len;
        Some((x, len))
    }
}

#[cfg(test)]
mod tests {
    use super::RunLength;

    #[test]
    fn test() {
        let a = vec![3, 1, 1, 4, 1, 5, 5, 5, 9, 9, 9, 2, 2];
        let mut iter = RunLength::new(&a);
        assert_eq!(iter.next(), Some((&3, 1)));
        assert_eq!(iter.next(), Some((&1, 2)));
        assert_eq!(iter.next(), Some((&4, 1)));
        assert_eq!(iter.next(), Some((&1, 1)));
        assert_eq!(iter.next(), Some((&5, 3)));
        assert_eq!(iter.next_back(), Some((&2, 2)));
        assert_eq!(iter.next_back(), Some((&9, 3)));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }

    #[test]
    fn test_all() {
        let a = vec![7, 7, 7];
        let mut iter = RunLength::new(&a);
        assert_eq!(iter.next(), Some((&7, 3)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn empty() {
        let a = Vec::<i32>::new();
        let mut iter = RunLength::new(&a);
        assert_eq!(iter.next(), None);
    }
}