haar_lib/algo/
rle.rs

1//! Run Length Encoding
2
3/// **Time complexity** $O(|a|)$
4pub fn rle<T: PartialEq>(a: &[T]) -> Vec<(&T, usize)> {
5    let mut ret = vec![];
6
7    for x in a {
8        match ret.last_mut() {
9            Some((y, c)) if x == *y => *c += 1,
10            _ => ret.push((x, 1)),
11        }
12    }
13
14    ret
15}
16
17#[cfg(test)]
18mod tests {
19    use super::*;
20
21    #[test]
22    fn test_vec() {
23        let a = vec![1, 1, 2, 1, 3, 4, 5, 5, 4];
24        assert_eq!(
25            rle(&a),
26            [
27                (&1, 2),
28                (&2, 1),
29                (&1, 1),
30                (&3, 1),
31                (&4, 1),
32                (&5, 2),
33                (&4, 1)
34            ]
35        );
36    }
37
38    #[test]
39    fn test_str() {
40        let a = "aabbccd";
41        assert_eq!(
42            rle(&a.chars().collect::<Vec<_>>()),
43            [(&'a', 2), (&'b', 2), (&'c', 2), (&'d', 1)]
44        );
45    }
46}
haar_lib/algo/rle.rs

haar_lib/algo/
rle.rs
