competitive/algorithm/
other.rs

1#[codesnip::entry]
2/// return: \[(elem, length)\]
3pub fn run_length_encoding<T, I>(iter: I) -> Vec<(T, usize)>
4where
5    T: Clone + PartialEq,
6    I: IntoIterator<Item = T>,
7{
8    let mut res = Vec::new();
9    for a in iter.into_iter() {
10        if let Some((p, len)) = res.last_mut()
11            && p == &a
12        {
13            *len += 1;
14            continue;
15        }
16        res.push((a, 1));
17    }
18    res
19}
20
21#[cfg(test)]
22mod tests {
23    use super::*;
24    use crate::{rand, tools::Xorshift};
25
26    #[test]
27    fn test_run_length_encoding() {
28        let mut rng = Xorshift::default();
29        const N: usize = 100_000;
30        rand!(rng, v: [0u8..8u8; N]);
31        let r = run_length_encoding(v.iter());
32        let mut s = 0;
33        for (a, l) in r {
34            for v in &v[s..s + l] {
35                assert_eq!(a, v);
36            }
37            s += l;
38        }
39    }
40}
competitive/algorithm/other.rs

competitive/algorithm/
other.rs
