competitive/algorithm/
rho_path.rs

1use std::{collections::HashMap, hash::Hash};
2
3/// $P_0 =$ `init`, $P_{i+1} = next(P_i)$
4///
5/// if |T| is finite then P = f, g, g, ...
6#[derive(Debug)]
7pub struct RhoPath<T> {
8    pub f: Vec<T>,
9    pub g: Vec<T>,
10}
11impl<T> RhoPath<T> {
12    /// build rho path
13    pub fn build<F>(init: T, next: F) -> Self
14    where
15        T: Clone + Eq + Hash,
16        F: Fn(&T) -> T,
17    {
18        let mut path = vec![init.clone()];
19        let mut visited = HashMap::new();
20        visited.insert(init, 0);
21        let loop_start = loop {
22            let next_val = next(path.last().unwrap());
23            if let Some(&idx) = visited.get(&next_val) {
24                break idx;
25            }
26            let cnt = path.len();
27            path.push(next_val.clone());
28            visited.insert(next_val, cnt);
29        };
30        let looped = path.split_off(loop_start);
31        Self { f: path, g: looped }
32    }
33    /// rho path that index of rho path
34    pub fn build_rho<F>(&self, init: usize, next: F) -> RhoPath<usize>
35    where
36        F: Fn(&usize) -> usize,
37    {
38        let (n, m) = (self.f.len(), self.g.len());
39        RhoPath::build(init, |x| {
40            let y = next(x);
41            if y < n { y } else { (y - n) % m + n }
42        })
43    }
44    /// get i-th value of rho path
45    pub fn get(&self, index: usize) -> &T {
46        if index < self.f.len() {
47            &self.f[index]
48        } else {
49            &self.g[(index - self.f.len()) % self.g.len()]
50        }
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57    use crate::tools::Xorshift;
58
59    #[test]
60    fn test_rho_path() {
61        let mut rng = Xorshift::default();
62        for _ in 0..100 {
63            let n = rng.random(1..100);
64            let a: Vec<usize> = rng.random_iter(0..n).take(n).collect();
65            let rp = RhoPath::build(0, |&x| a[x]);
66            let mut x = 0;
67            for i in 0..n * 2 {
68                assert_eq!(rp.get(i), &x);
69                x = a[x];
70            }
71
72            let rp2 = rp.build_rho(0, |&x| x + a[*rp.get(x)]);
73            let mut x = 0;
74            for i in 0..n * 2 {
75                assert_eq!(rp.get(*rp2.get(i)), rp.get(x));
76                x += a[*rp.get(x)];
77            }
78        }
79    }
80}
competitive/algorithm/rho_path.rs

competitive/algorithm/
rho_path.rs
