deepwoken_reqparse/util/
reqtree.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2
3use crate::req::Requirement;
4
5pub struct ReqTree {
6    // Keyed by name
7    reqs: HashMap<String, Requirement>,
8    // Stores a set of reqs that depend on the key
9    dependents: HashMap<String, HashSet<String>>,
10}
11
12impl ReqTree {
13    pub fn new() -> Self {
14        Self {
15            reqs: HashMap::new(),
16            dependents: HashMap::new(),
17        }
18    }
19
20    /// Insert a requirement 
21    pub fn insert(&mut self, req: Requirement) {
22        let name = req.name_or_default();
23
24        for prereq in &req.prereqs {
25            self.dependents
26                .entry(prereq.clone())
27                .or_default()
28                .insert(name.clone());
29        }
30
31        self.reqs.insert(name, req);
32    }
33
34    pub fn get(&self, name: &str) -> Option<&Requirement> {
35        self.reqs.get(name)
36    }
37
38    /// Retrieve direct prereqs as names
39    pub fn prereqs(&self, name: &str) -> Option<&[String]> {
40        self.reqs.get(name).map(|r| r.prereqs.as_slice())
41    }
42
43    /// Retrieve direct dependents as names
44    pub fn dependents(&self, name: &str) -> Option<&HashSet<String>> {
45        self.dependents.get(name)
46    }
47
48    /// All transitive prereqs via BFS
49    pub fn all_prereqs(&self, name: &str) -> HashSet<String> {
50        let mut visited = HashSet::new();
51        let mut queue = VecDeque::new();
52
53        if let Some(req) = self.reqs.get(name) {
54            queue.extend(req.prereqs.iter().cloned());
55        }
56
57        while let Some(current) = queue.pop_front() {
58            if visited.insert(current.clone()) {
59                if let Some(req) = self.reqs.get(&current) {
60                    queue.extend(req.prereqs.iter().cloned());
61                }
62            }
63        }
64
65        visited
66    }
67
68    /// All transitive dependents via BFS
69    pub fn all_dependents(&self, name: &str) -> HashSet<String> {
70        let mut visited = HashSet::new();
71        let mut queue = VecDeque::new();
72
73        if let Some(deps) = self.dependents.get(name) {
74            queue.extend(deps.iter().cloned());
75        }
76
77        while let Some(current) = queue.pop_front() {
78            if visited.insert(current.clone()) {
79                if let Some(deps) = self.dependents.get(&current) {
80                    queue.extend(deps.iter().cloned());
81                }
82            }
83        }
84
85        visited
86    }
87
88    /// Check for any cycles (shoudl be invalid for deep anyways)
89    pub fn find_cycle(&self) -> Option<Vec<String>> {
90        let mut visited = HashSet::new();
91        let mut stack = HashSet::new();
92        let mut path = Vec::new();
93
94        for name in self.reqs.keys() {
95            if let Some(cycle) = self.cycle_visit(
96                name, 
97                &mut visited, 
98                &mut stack, 
99                &mut path
100            ) {
101                return Some(cycle);
102            }
103        }
104        None
105    }
106
107    fn cycle_visit(
108        &self,
109        name: &str,
110        visited: &mut HashSet<String>,
111        stack: &mut HashSet<String>,
112        path: &mut Vec<String>,
113    ) -> Option<Vec<String>> {
114        if stack.contains(name) {
115            let idx = path.iter()
116                .position(|n| n == name).unwrap();
117            
118            return Some(path[idx..].to_vec());
119        }
120        if visited.contains(name) {
121            return None;
122        }
123
124        visited.insert(name.to_string());
125        stack.insert(name.to_string());
126        path.push(name.to_string());
127
128        if let Some(req) = self.reqs.get(name) {
129            for prereq in &req.prereqs {
130                if let Some(cycle) = self.cycle_visit(
131                    prereq, 
132                    visited, 
133                    stack, 
134                    path
135                ) {
136                    return Some(cycle);
137                }
138            }
139        }
140
141        stack.remove(name);
142        path.pop();
143        None
144    }
145}
deepwoken_reqparse/util/reqtree.rs

deepwoken_reqparse/util/
reqtree.rs
