tortoise_hare/
lib.rs

1pub trait CycleMuLambda: Eq {
2    fn cycle_mu_lambda<F: Fn(&Self) -> Self>(self, f: F) -> (usize, usize);
3}
4
5impl<T: Eq> CycleMuLambda for T {
6    fn cycle_mu_lambda<F: Fn(&T) -> T>(self, f: F) -> (usize, usize) {
7        let mut tor = f(&self);
8        let mut har = f(&tor);
9
10        while tor != har {
11            tor = f(&tor);
12            har = f(&f(&har));
13        }
14
15        let mut tor = self;
16        let mut mu = 0;
17        while tor != har {
18            tor = f(&tor);
19            har = f(&har);
20            mu += 1;
21        }
22
23        let mut lambda = 1;
24        har = f(&tor);
25        while tor != har {
26            har = f(&har);
27            lambda += 1;
28        }
29
30        (mu, lambda)
31    }
32}
33
34#[test]
35fn sanity_check() {
36    let x0 = 879_u32;
37    let f = |&x: &u32| x % 104 * 10;
38    // 879/104 = 8.451(923076...)
39    assert_eq!(x0.cycle_mu_lambda(f), (4, 6));
40
41    assert_eq!('.'.cycle_mu_lambda(|&x| x), (0, 1));
42}
tortoise_hare/lib.rs

tortoise_hare/
lib.rs
