graco 0.1.3

Generalized Rust Ant Colony Optimization
Documentation 
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

use std::cmp::PartialEq;

#[test]
fn cycle_tests() {
    // Simple cycles
    assert_eq!(brent_cycle(&[1, 2, 4, 5, 6, 5, 4, 3, 1]), vec![1]);
    assert_eq!(brent_cycle(&[1, 2, 4, 5, 6, 5, 4, 3, 2, 1]), vec![1]);
    assert_eq!(brent_cycle(&[1, 2, 4, 5, 6, 5, 4, 3, 1, 2]), vec![1, 2]);
    assert_eq!(brent_cycle(&[1, 2]), vec![1, 2]);
    assert_eq!(brent_cycle(&[1, 1]), vec![1]);

    let expectd = vec![1, 2, 4, 3];

    let rtn = brent_cycle(&expectd);
    assert_eq!(rtn, expectd);

    let rtn = brent_cycle(&[1, 2, 4, 3, 5, 6, 7, 7, 6, 5, 3]);
    assert_eq!(rtn, expectd);
}

pub fn brent_cycle<T: PartialEq + Clone>(mcyc: &[T]) -> Vec<T> {
    let mut lambda: usize = 1;
    let mut power: usize = 1;
    let mut tortoise: &T;
    let mut hare: &T;

    if mcyc.len() < 2 {
        // Cannot have a cycle here
        return mcyc.to_vec();
    }

    // Main phase: search successive powers of two.
    tortoise = &mcyc[0]; // Start at the begining of the loop
    hare = &mcyc[1];

    let mut it: usize = 2;

    while tortoise != hare {
        if power == lambda {
            // Time to start a new power of two.
            tortoise = hare;
            power *= 2;
            lambda = 0;
        }
        // Hare might cycle to catch up to the tortoise.
        hare = &mcyc[it % mcyc.len()];
        lambda += 1;
        it += 1;
    }

    // No cycle found, let's return here.
    if lambda == mcyc.len() {
        return mcyc.to_vec();
    }

    // Find the position of the first repetition of length lambda.
    tortoise = &mcyc[0];
    hare = &mcyc[lambda];

    // The distance between hare and tortoise is now lambda.
    it = 1; // Reset iterator
    while tortoise != hare {
        tortoise = &mcyc[it];
        hare = &mcyc[(lambda + it) % mcyc.len()];
        it += 1;
    }

    if it == mcyc.len() {
        // This is a full cycle
        mcyc[0..1].to_vec()
    } else {
        // Cycle found, let's remove it.
        let mut new_vec = Vec::from(&mcyc[0..it]);

        let mut second_part = Vec::from(&mcyc[it + lambda..mcyc.len()]);
        new_vec.append(&mut second_part);
        brent_cycle(&new_vec.to_vec())
    }
}