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

use std::collections::{HashMap, HashSet};

pub struct Sorter {
    dependencies: HashMap<String, HashSet<String>>,
}

impl Sorter {
    pub fn new() -> Self {
        Self {
            dependencies: HashMap::new(),
        }
    }
    pub fn insert(&mut self, dep: String) {
        self.dependencies.insert(dep, HashSet::new());
    }
    pub fn add_dependency(&mut self, dep: String, name: String) {
        if let Some(deps) = self.dependencies.get_mut(&name) {
            deps.insert(dep);
        } else {
            self.dependencies.insert(dep, HashSet::new());
        }
    }

    pub fn remove_unregistered_depedencies(&mut self) {
        let mut deps = HashSet::new();

        for (_, v) in &self.dependencies {
            deps.extend(v);
        }
        deps.retain(|dep| !self.dependencies.contains_key(*dep));
        let deps: HashSet<_> = deps.into_iter().cloned().collect();
        for dep in deps {
            self.remove_dep(&dep.clone());
        }
    }

    fn remove_dep(&mut self, dep: &str) {
        for (_k, v) in &mut self.dependencies {
            v.remove(dep);
        }
    }
    pub fn pop(&mut self) -> Option<String> {
        let indep = self.find_independent()?;
        self.remove_dep(&indep);
        Some(indep)
    }

    fn find_independent(&mut self) -> Option<String> {
        let mut out = None;
        for (k, v) in &self.dependencies {
            if v.is_empty() {
                let key = &k.clone();
                out = self.dependencies.remove_entry(key).map(|x| x.0);
                break;
            }
        }
        let out = out?;
        self.dependencies.remove(&out);
        Some(out)
    }
}