1// Copyright 2016 oauth-client-rs Developers
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// https://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// https://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8//! Performs topological sorting.
9
10#![warn(bad_style)]
11#![warn(missing_copy_implementations)]
12#![warn(missing_debug_implementations)]
13#![warn(missing_docs)]
14#![warn(trivial_casts)]
15#![warn(trivial_numeric_casts)]
16#![warn(unused)]
17#![warn(unused_extern_crates)]
18#![warn(unused_import_braces)]
19#![warn(unused_qualifications)]
20#![warn(unused_results)]
21#![warn(clippy::if_not_else)]
22#![warn(clippy::invalid_upcast_comparisons)]
23#![warn(clippy::items_after_statements)]
24#![warn(clippy::mut_mut)]
25#![warn(clippy::never_loop)]
26#![warn(clippy::nonminimal_bool)]
27#![warn(clippy::used_underscore_binding)]
28
29use std::cmp::Ordering;
30use std::collections::hash_map::Entry;
31use std::collections::{HashMap, HashSet};
32use std::fmt;
33use std::hash::Hash;
34use std::iter::FromIterator;
35
36#[derive(Clone)]
37struct Dependency<T> {
38 num_prec: usize,
39 succ: HashSet<T>,
40}
41
42impl<T: Hash + Eq> Dependency<T> {
43 fn new() -> Dependency<T> {
44 Dependency {
45 num_prec: 0,
46 succ: HashSet::new(),
47 }
48 }
49}
50
51/// Performs topological sorting.
52#[derive(Clone)]
53pub struct TopologicalSort<T> {
54 top: HashMap<T, Dependency<T>>,
55}
56
57impl<T> Default for TopologicalSort<T> {
58 fn default() -> TopologicalSort<T> {
59 TopologicalSort {
60 top: HashMap::new(),
61 }
62 }
63}
64
65impl<T: Hash + Eq + Clone> TopologicalSort<T> {
66 /// Creates new empty `TopologicalSort`.
67 ///
68 /// ```rust
69 /// # extern crate topological_sort;
70 /// # fn main() {
71 /// use topological_sort::TopologicalSort;
72 /// let mut ts = TopologicalSort::<&str>::new();
73 /// ts.add_dependency("hello_world.o", "hello_world");
74 /// ts.add_dependency("hello_world.c", "hello_world");
75 /// ts.add_dependency("stdio.h", "hello_world.o");
76 /// ts.add_dependency("glibc.so", "hello_world");
77 /// assert_eq!(vec!["glibc.so", "hello_world.c", "stdio.h"],
78 /// { let mut v = ts.pop_all(); v.sort(); v });
79 /// assert_eq!(vec!["hello_world.o"],
80 /// { let mut v = ts.pop_all(); v.sort(); v });
81 /// assert_eq!(vec!["hello_world"],
82 /// { let mut v = ts.pop_all(); v.sort(); v });
83 /// assert!(ts.pop_all().is_empty());
84 /// # }
85 /// ```
86 #[inline]
87 pub fn new() -> TopologicalSort<T> {
88 Default::default()
89 }
90
91 /// Returns the number of elements in the `TopologicalSort`.
92 #[inline]
93 pub fn len(&self) -> usize {
94 self.top.len()
95 }
96
97 /// Returns true if the `TopologicalSort` contains no elements.
98 #[inline]
99 pub fn is_empty(&self) -> bool {
100 self.top.is_empty()
101 }
102
103 /// Registers the two elements' dependency.
104 ///
105 /// # Arguments
106 ///
107 /// * `prec` - The element appears before `succ`. `prec` is depended on by `succ`.
108 /// * `succ` - The element appears after `prec`. `succ` depends on `prec`.
109 pub fn add_dependency<P, S>(&mut self, prec: P, succ: S)
110 where
111 P: Into<T>,
112 S: Into<T>,
113 {
114 self.add_dependency_impl(prec.into(), succ.into())
115 }
116
117 fn add_dependency_impl(&mut self, prec: T, succ: T) {
118 match self.top.entry(prec) {
119 Entry::Vacant(e) => {
120 let mut dep = Dependency::new();
121 let _ = dep.succ.insert(succ.clone());
122 let _ = e.insert(dep);
123 }
124 Entry::Occupied(e) => {
125 if !e.into_mut().succ.insert(succ.clone()) {
126 // Already registered
127 return;
128 }
129 }
130 }
131
132 match self.top.entry(succ) {
133 Entry::Vacant(e) => {
134 let mut dep = Dependency::new();
135 dep.num_prec += 1;
136 let _ = e.insert(dep);
137 }
138 Entry::Occupied(e) => {
139 e.into_mut().num_prec += 1;
140 }
141 }
142 }
143
144 /// Registers a dependency link.
145 pub fn add_link(&mut self, link: DependencyLink<T>) {
146 self.add_dependency(link.prec, link.succ)
147 }
148
149 /// Inserts an element, without adding any dependencies from or to it.
150 ///
151 /// If the `TopologicalSort` did not have this element present, `true` is returned.
152 ///
153 /// If the `TopologicalSort` already had this element present, `false` is returned.
154 pub fn insert<U>(&mut self, elt: U) -> bool
155 where
156 U: Into<T>,
157 {
158 match self.top.entry(elt.into()) {
159 Entry::Vacant(e) => {
160 let dep = Dependency::new();
161 let _ = e.insert(dep);
162 true
163 }
164 Entry::Occupied(_) => false,
165 }
166 }
167
168 /// Removes the item that is not depended on by any other items and returns it, or `None` if
169 /// there is no such item.
170 ///
171 /// If `pop` returns `None` and `len` is not 0, there is cyclic dependencies.
172 pub fn pop(&mut self) -> Option<T> {
173 self.peek().map(T::clone).map(|key| {
174 let _ = self.remove(&key);
175 key
176 })
177 }
178
179 /// Removes all items that are not depended on by any other items and returns it, or empty
180 /// vector if there are no such items.
181 ///
182 /// If `pop_all` returns an empty vector and `len` is not 0, there is cyclic dependencies.
183 pub fn pop_all(&mut self) -> Vec<T> {
184 let keys = self
185 .top
186 .iter()
187 .filter(|&(_, v)| v.num_prec == 0)
188 .map(|(k, _)| k.clone())
189 .collect::<Vec<_>>();
190 for k in &keys {
191 let _ = self.remove(k);
192 }
193 keys
194 }
195
196 /// Return a reference to the first item that does not depend on any other items, or `None` if
197 /// there is no such item.
198 pub fn peek(&self) -> Option<&T> {
199 self.top
200 .iter()
201 .filter(|&(_, v)| v.num_prec == 0)
202 .map(|(k, _)| k)
203 .next()
204 }
205
206 /// Return a vector of references to all items that do not depend on any other items, or an
207 /// empty vector if there are no such items.
208 pub fn peek_all(&self) -> Vec<&T> {
209 self.top
210 .iter()
211 .filter(|&(_, v)| v.num_prec == 0)
212 .map(|(k, _)| k)
213 .collect::<Vec<_>>()
214 }
215
216 fn remove(&mut self, prec: &T) -> Option<Dependency<T>> {
217 let result = self.top.remove(prec);
218 if let Some(ref p) = result {
219 for s in &p.succ {
220 if let Some(y) = self.top.get_mut(s) {
221 y.num_prec -= 1;
222 }
223 }
224 }
225 result
226 }
227}
228
229impl<T: PartialOrd + Eq + Hash + Clone> FromIterator<T> for TopologicalSort<T> {
230 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> TopologicalSort<T> {
231 let mut top: TopologicalSort = TopologicalSort::new();
232 let mut seen: Vec = Vec::<T>::default();
233 for item: T in iter {
234 let _ = top.insert(elt:item.clone());
235 for seen_item: T in seen.iter().cloned() {
236 match seen_item.partial_cmp(&item) {
237 Some(Ordering::Less) => {
238 top.add_dependency(prec:seen_item, succ:item.clone());
239 }
240 Some(Ordering::Greater) => {
241 top.add_dependency(prec:item.clone(), succ:seen_item);
242 }
243 _ => (),
244 }
245 }
246 seen.push(item);
247 }
248 top
249 }
250}
251
252/// A link between two items in a sort.
253#[derive(Copy, Clone, Debug)]
254pub struct DependencyLink<T> {
255 /// The element which is depened upon by `succ`.
256 pub prec: T,
257 /// The element which depends on `prec`.
258 pub succ: T,
259}
260
261impl<T> From<(T, T)> for DependencyLink<T> {
262 fn from(tuple: (T, T)) -> Self {
263 DependencyLink {
264 succ: tuple.0,
265 prec: tuple.1,
266 }
267 }
268}
269
270impl<T: Eq + Hash + Clone> FromIterator<DependencyLink<T>> for TopologicalSort<T> {
271 fn from_iter<I: IntoIterator<Item = DependencyLink<T>>>(iter: I) -> TopologicalSort<T> {
272 let mut top: TopologicalSort = TopologicalSort::new();
273 for link: DependencyLink in iter {
274 top.add_link(link);
275 }
276 top
277 }
278}
279
280impl<T: Hash + Eq + Clone> Iterator for TopologicalSort<T> {
281 type Item = T;
282
283 fn next(&mut self) -> Option<T> {
284 self.pop()
285 }
286}
287
288impl<T: fmt::Debug + Hash + Eq> fmt::Debug for Dependency<T> {
289 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
290 write!(f, "prec={}, succ={:?}", self.num_prec, self.succ)
291 }
292}
293
294impl<T: fmt::Debug + Hash + Eq + Clone> fmt::Debug for TopologicalSort<T> {
295 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
296 write!(f, "{:?}", self.top)
297 }
298}
299
300#[cfg(test)]
301mod test {
302 use super::TopologicalSort;
303 use quickcheck_macros::quickcheck;
304 use std::iter::FromIterator;
305
306 #[test]
307 fn from_iter() {
308 let t = vec![4, 3, 3, 5, 7, 6, 8];
309 let mut ts = TopologicalSort::<i32>::from_iter(t);
310 assert_eq!(Some(3), ts.next());
311 assert_eq!(Some(4), ts.next());
312 assert_eq!(Some(5), ts.next());
313 assert_eq!(Some(6), ts.next());
314 assert_eq!(Some(7), ts.next());
315 assert_eq!(Some(8), ts.next());
316 assert_eq!(None, ts.next());
317 }
318
319 #[test]
320 fn iter() {
321 let mut ts = TopologicalSort::<i32>::new();
322 ts.add_dependency(1, 2);
323 ts.add_dependency(2, 3);
324 ts.add_dependency(3, 4);
325 assert_eq!(Some(1), ts.next());
326 assert_eq!(Some(2), ts.next());
327 assert_eq!(Some(3), ts.next());
328 assert_eq!(Some(4), ts.next());
329 assert_eq!(None, ts.next());
330 }
331
332 #[test]
333 fn pop_all() {
334 fn check(result: &[i32], ts: &mut TopologicalSort<i32>) {
335 let l = ts.len();
336 let mut v = ts.pop_all();
337 v.sort();
338 assert_eq!(result, &v[..]);
339 assert_eq!(l - result.len(), ts.len());
340 }
341
342 let mut ts = TopologicalSort::new();
343 ts.add_dependency(7, 11);
344 assert_eq!(2, ts.len());
345 ts.add_dependency(7, 8);
346 assert_eq!(3, ts.len());
347 ts.add_dependency(5, 11);
348 assert_eq!(4, ts.len());
349 ts.add_dependency(3, 8);
350 assert_eq!(5, ts.len());
351 ts.add_dependency(3, 10);
352 assert_eq!(6, ts.len());
353 ts.add_dependency(11, 2);
354 assert_eq!(7, ts.len());
355 ts.add_dependency(11, 9);
356 assert_eq!(8, ts.len());
357 ts.add_dependency(11, 10);
358 assert_eq!(8, ts.len());
359 ts.add_dependency(8, 9);
360 assert_eq!(8, ts.len());
361
362 check(&[3, 5, 7], &mut ts);
363 check(&[8, 11], &mut ts);
364 check(&[2, 9, 10], &mut ts);
365 check(&[], &mut ts);
366 }
367
368 #[test]
369 fn cyclic_deadlock() {
370 let mut ts = TopologicalSort::new();
371 ts.add_dependency("stone", "sharp");
372
373 ts.add_dependency("bucket", "hole");
374 ts.add_dependency("hole", "straw");
375 ts.add_dependency("straw", "axe");
376 ts.add_dependency("axe", "sharp");
377 ts.add_dependency("sharp", "water");
378 ts.add_dependency("water", "bucket");
379 assert_eq!(ts.pop(), Some("stone"));
380 assert!(ts.pop().is_none());
381 println!("{:?}", ts);
382 }
383
384 #[quickcheck]
385 fn topo_test_quickcheck(n: usize, edges: Vec<(usize, usize)>) {
386 use std::collections::{HashMap, HashSet};
387
388 let n = n.max(1).min(1000);
389 let mut marked = vec![false; n];
390 let edges = edges
391 .into_iter()
392 .map(|(x, y)| (x % n, y % n))
393 .collect::<Vec<_>>();
394 let mut deps = HashMap::new();
395 let mut toposort = TopologicalSort::<usize>::new();
396
397 for i in 0..n {
398 let _ = deps.insert(i, HashSet::new());
399 assert!(toposort.insert(i));
400 }
401
402 for (op, inp) in edges.iter().map(|(x, y)| (y, x)) {
403 let inps = deps.get_mut(op).unwrap();
404 let _ = inps.insert(*inp);
405 }
406
407 let deps = deps;
408 for (inp, op) in edges {
409 toposort.add_dependency(inp, op);
410 }
411 while let Some(x) = toposort.pop() {
412 for dep in deps.get(&x).unwrap().iter() {
413 assert!(marked[*dep]);
414 }
415 marked[x] = true;
416 }
417
418 if toposort.is_empty() {
419 assert!(marked.into_iter().all(|x| x));
420 } else {
421 let dep_fixed = {
422 let mut ret = (0..n)
423 .map(|i| (i, HashSet::new()))
424 .collect::<HashMap<_, _>>();
425 let mut new_to_add = deps;
426
427 while !new_to_add.is_empty() {
428 for (k, v) in new_to_add.drain() {
429 let inps = ret.get_mut(&k).unwrap();
430 inps.extend(v.into_iter());
431 }
432 for (k, vs) in ret.iter() {
433 for k2 in vs.iter() {
434 for v2 in ret.get(k2).unwrap().iter() {
435 if !vs.contains(v2) {
436 let _ = new_to_add
437 .entry(*k)
438 .or_insert_with(HashSet::new)
439 .insert(*v2);
440 }
441 }
442 }
443 }
444 }
445
446 ret
447 };
448
449 assert!(dep_fixed.into_iter().any(|(op, deps)| deps.contains(&op)));
450 }
451 }
452}
453