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::tools::Xorshift;
25    use crate::tools::testutil::{exhaustive_sequences, sample_usize, structured_sequences};
26    use std::iter::repeat_n;
27
28    #[test]
29    fn test_run_length_encoding() {
30        let mut rng = Xorshift::default();
31        let lengths = sample_usize(&mut rng, 16, 0..=100_000, 2);
32        for values in
33            exhaustive_sequences(0..3, 0..=8).chain(structured_sequences(&mut rng, 0..8, lengths))
34        {
35            let runs = run_length_encoding(values.iter().copied());
36            assert!(runs.iter().all(|&(_, len)| len > 0));
37            assert!(runs.windows(2).all(|w| w[0].0 != w[1].0));
38            let restored: Vec<_> = runs
39                .into_iter()
40                .flat_map(|(value, len)| repeat_n(value, len))
41                .collect();
42            assert_eq!(restored, values);
43        }
44    }
45}
competitive/algorithm/other.rs

competitive/algorithm/
other.rs
