protobuf_support/
toposort.rs

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
use std::collections::HashSet;
use std::hash::Hash;

#[derive(Debug, thiserror::Error)]
#[error("Cycle detected")]
pub struct TopoSortCycle;

pub fn toposort<K, I>(
    input: impl IntoIterator<Item = K>,
    deps: impl Fn(&K) -> I,
) -> Result<Vec<K>, TopoSortCycle>
where
    K: Eq + Hash + Clone,
    I: Iterator<Item = K>,
{
    struct Ts<K, D, I>
    where
        K: Eq + Hash + Clone,
        I: Iterator<Item = K>,
        D: Fn(&K) -> I,
    {
        result_set: HashSet<K>,
        result: Vec<K>,
        deps: D,
        stack: HashSet<K>,
    }

    impl<K, D, I> Ts<K, D, I>
    where
        K: Eq + Hash + Clone,
        I: Iterator<Item = K>,
        D: Fn(&K) -> I,
    {
        fn visit(&mut self, i: &K) -> Result<(), TopoSortCycle> {
            if self.result_set.contains(i) {
                return Ok(());
            }

            if !self.stack.insert(i.clone()) {
                return Err(TopoSortCycle);
            }
            for dep in (self.deps)(i) {
                self.visit(&dep)?;
            }

            let removed = self.stack.remove(i);
            assert!(removed);

            self.result.push(i.clone());
            self.result_set.insert(i.clone());

            Ok(())
        }
    }

    let mut ts = Ts {
        result: Vec::new(),
        result_set: HashSet::new(),
        deps,
        stack: HashSet::new(),
    };

    for i in input {
        ts.visit(&i)?;
    }

    Ok(ts.result)
}

#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    use crate::toposort::toposort;
    use crate::toposort::TopoSortCycle;

    fn test_toposort(input: &str) -> Result<Vec<&str>, TopoSortCycle> {
        let mut keys: Vec<&str> = Vec::new();
        let mut edges: HashMap<&str, Vec<&str>> = HashMap::new();
        for part in input.split(" ") {
            match part.split_once("->") {
                Some((k, vs)) => {
                    keys.push(k);
                    edges.insert(k, vs.split(",").collect());
                }
                None => keys.push(part),
            };
        }

        toposort(keys, |k| {
            edges
                .get(k)
                .map(|v| v.as_slice())
                .unwrap_or_default()
                .into_iter()
                .copied()
        })
    }

    fn test_toposort_check(input: &str, expected: &str) {
        let sorted = test_toposort(input).unwrap();
        let expected = expected.split(" ").collect::<Vec<_>>();
        assert_eq!(expected, sorted);
    }

    #[test]
    fn test() {
        test_toposort_check("1 2 3", "1 2 3");
        test_toposort_check("1->2 2->3 3", "3 2 1");
        test_toposort_check("1 2->1 3->2", "1 2 3");
        test_toposort_check("1->2,3 2->3 3", "3 2 1");
    }

    #[test]
    fn cycle() {
        assert!(test_toposort("1->1").is_err());
        assert!(test_toposort("1->2 2->1").is_err());
    }
}