dsalgo/
functional_graph_doubling_table.rs

1/// able to compute (k <= 2^max_exp)-th from any node in O(max_exp) time
2
3pub fn doubling_table(
4    f: &[usize],
5    n_bits: usize,
6) -> Vec<Vec<usize>> {
7    assert!(n_bits > 0);
8
9    let n = f.len();
10
11    let mut a = Vec::with_capacity(n_bits);
12
13    a.push(f.to_owned());
14
15    for i in 0..n_bits - 1 {
16        let row = &a[i];
17
18        a.push((0..n).map(|j| row[row[j]]).collect());
19    }
20
21    a
22}
23
24#[cfg(test)]
25
26mod tests {
27
28    #[test]
29
30    fn test() {}
31}