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}
competitive/algorithm/rho_path.rs

competitive/algorithm/
rho_path.rs
