1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//! Identify a cycle in an infinite sequence.

/// Identify a cycle in an infinite sequence using Floyd's algorithm.
/// Return the cycle size, the first element, and the index of first element.
///
/// # Warning
///
/// If no cycle exist, this function loops forever.
pub fn floyd<T, FS>(start: T, successor: FS) -> (usize, T, usize)
where
    T: Clone + PartialEq,
    FS: Fn(T) -> T,
{
    let mut tortoise = successor(start.clone());
    let mut hare = successor(successor(start.clone()));
    while tortoise != hare {
        (tortoise, hare) = (successor(tortoise), successor(successor(hare)));
    }
    let mut mu = 0;
    tortoise = start;
    while tortoise != hare {
        (tortoise, hare, mu) = (successor(tortoise), successor(hare), mu + 1);
    }
    let mut lam = 1;
    hare = successor(tortoise.clone());
    while tortoise != hare {
        (hare, lam) = (successor(hare), lam + 1);
    }
    (lam, tortoise, mu)
}

/// Identify a cycle in an infinite sequence using Brent's algorithm.
/// Return the cycle size, the first element, and the index of first element.
///
/// # Warning
///
/// If no cycle exist, this function loops forever.
pub fn brent<T, FS>(start: T, successor: FS) -> (usize, T, usize)
where
    T: Clone + PartialEq,
    FS: Fn(T) -> T,
{
    let mut power = 1;
    let mut lam = 1;
    let mut tortoise = start.clone();
    let mut hare = successor(start.clone());
    while tortoise != hare {
        if power == lam {
            (tortoise, power, lam) = (hare.clone(), power * 2, 0);
        }
        (hare, lam) = (successor(hare), lam + 1);
    }
    let mut mu = 0;
    (tortoise, hare) = (start.clone(), (0..lam).fold(start, |x, _| successor(x)));
    while tortoise != hare {
        (tortoise, hare, mu) = (successor(tortoise), successor(hare), mu + 1);
    }
    (lam, hare, mu)
}