scarlet_queen_entrypoint/
find_cycle.rs

1use std::{collections::HashMap, hash::Hash, io::Write};
2
3pub fn find_tail_cycle<T, W>(
4    count_data: &[HashMap<T, usize>],
5    out: &mut W,
6) -> Result<(), std::io::Error>
7where
8    T: Clone + Eq + Hash,
9    W: Write,
10{
11    let data_len: usize = count_data.len();
12    let (header_len, cycle_len) = tail_cycle(count_data);
13    let result: String = if let Some(v) = count_data.last() {
14        let mut last_count: Vec<&usize> = v.values().collect::<Vec<&usize>>();
15        last_count.sort();
16        if last_count
17            .iter()
18            .take(last_count.len() - 1)
19            .all(|&&v| v == 0)
20        {
21            "cycle: Divergence".to_string()
22        } else if header_len == data_len {
23            "cycle: NotEnoughLoop".to_string()
24        } else {
25            format!("cycle: HeaderLen-CycleLen({header_len}-{cycle_len})")
26        }
27    } else {
28        "cycle: NoData".to_string()
29    };
30    writeln!(out, "{result}")
31}
32
33pub fn tail_cycle<T>(data: &[T]) -> (usize, usize)
34where
35    T: Eq,
36{
37    let data_len: usize = data.len();
38    let data_rev: Vec<&T> = data.iter().rev().collect::<Vec<&T>>();
39    let match_table: Vec<usize> = match_table(data_rev);
40    match_table
41        .iter()
42        .copied()
43        .enumerate()
44        .skip(1)
45        .zip(match_table.iter().copied())
46        .filter_map(|((i, u), v)| {
47            if u == v + 1 && (i - u) * 2 <= i {
48                Some((i, i - u))
49            } else {
50                None
51            }
52        })
53        .next_back()
54        .map(|(all_cycle_len, cycle_len)| (data_len - all_cycle_len, cycle_len))
55        .unwrap_or((data_len, 0))
56}
57
58fn match_table<T>(data: Vec<&T>) -> Vec<usize>
59where
60    T: Eq,
61{
62    if data.len() <= 2 {
63        return vec![0; data.len()];
64    }
65    let mut res: Vec<usize> = vec![0; data.len()];
66    'a: for i in 1..(data.len() - 1) {
67        let mut j: usize = i;
68        while data[i] != data[res[j]] {
69            j = res[j];
70            if j == 0 {
71                res[i + 1] = 0;
72                continue 'a;
73            }
74        }
75        res[i + 1] = res[j] + 1;
76    }
77    res
78}
scarlet_queen_entrypoint/find_cycle.rs

scarlet_queen_entrypoint/
find_cycle.rs
