cp_library_rs/utils/
run_length.rs

1//! ランレングス圧縮
2
3/// ## ランレングス圧縮
4/// - スライスからエンコードを行う
5pub fn run_length_encode<T>(arr: &[T]) -> Vec<(T, usize)>
6where
7    T: PartialEq + Copy,
8{
9    let mut res = vec![];
10    let mut cur = arr[0];
11    let mut cnt = 1;
12    for &val in &arr[1..] {
13        if val == cur {
14            cnt += 1;
15        } else {
16            res.push((cur, cnt));
17            cur = val;
18            cnt = 1;
19        }
20    }
21    let last_elem = *arr.last().unwrap();
22    res.push((last_elem, cnt));
23
24    res
25}
26
27/// ## RunLength
28/// - イテレータに対してランレングス圧縮を実装する
29pub trait RunLength: Iterator {
30    /// ## ランレングス圧縮 (from Iterator)
31    /// - イテレータからエンコードを行う
32    fn run_length_encode(&mut self) -> Vec<(Self::Item, usize)>
33    where
34        Self::Item: PartialEq,
35    {
36        let mut res = vec![];
37        let mut cur = self.next().unwrap();
38        let mut cnt = 1;
39        for val in self {
40            if val == cur {
41                cnt += 1;
42            } else {
43                res.push((cur, cnt));
44                cur = val;
45                cnt = 1;
46            }
47        }
48        res.push((cur, cnt));
49
50        res
51    }
52}
53
54impl<I: Iterator> RunLength for I {}
cp_library_rs/utils/run_length.rs

cp_library_rs/utils/
run_length.rs
