topological_sort/
lib.rs

1// Copyright 2016 oauth-client-rs Developers
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://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#![cfg_attr(feature = "cargo-clippy", warn(if_not_else))]
22#![cfg_attr(feature = "cargo-clippy", warn(invalid_upcast_comparisons))]
23#![cfg_attr(feature = "cargo-clippy", warn(items_after_statements))]
24#![cfg_attr(feature = "cargo-clippy", warn(mut_mut))]
25#![cfg_attr(feature = "cargo-clippy", warn(never_loop))]
26#![cfg_attr(feature = "cargo-clippy", warn(nonminimal_bool))]
27#![cfg_attr(feature = "cargo-clippy", warn(option_map_unwrap_or))]
28#![cfg_attr(feature = "cargo-clippy", warn(option_map_unwrap_or_else))]
29#![cfg_attr(feature = "cargo-clippy", warn(option_unwrap_used))]
30#![cfg_attr(feature = "cargo-clippy", warn(result_unwrap_used))]
31#![cfg_attr(feature = "cargo-clippy", warn(used_underscore_binding))]
32
33use std::cmp::Ordering;
34use std::collections::{HashMap, HashSet};
35use std::collections::hash_map::Entry;
36use std::fmt;
37use std::hash::Hash;
38use std::iter::FromIterator;
39
40#[derive(Clone)]
41struct Dependency<T> {
42    num_prec: usize,
43    succ: HashSet<T>,
44}
45
46impl<T: Hash + Eq> Dependency<T> {
47    fn new() -> Dependency<T> {
48        Dependency {
49            num_prec: 0,
50            succ: HashSet::new(),
51        }
52    }
53}
54
55
56
57/// Performs topological sorting.
58#[derive(Clone)]
59pub struct TopologicalSort<T> {
60    top: HashMap<T, Dependency<T>>,
61}
62
63impl<T: Hash + Eq + Clone> TopologicalSort<T> {
64    /// Creates new empty `TopologicalSort`.
65    ///
66    /// ```rust
67    /// # extern crate topological_sort;
68    /// # fn main() {
69    /// use topological_sort::TopologicalSort;
70    /// let mut ts = TopologicalSort::<&str>::new();
71    /// ts.add_dependency("hello_world.o", "hello_world");
72    /// ts.add_dependency("hello_world.c", "hello_world");
73    /// ts.add_dependency("stdio.h", "hello_world.o");
74    /// ts.add_dependency("glibc.so", "hello_world");
75    /// assert_eq!(vec!["glibc.so", "hello_world.c", "stdio.h"],
76    ///            { let mut v = ts.pop_all(); v.sort(); v });
77    /// assert_eq!(vec!["hello_world.o"],
78    ///            { let mut v = ts.pop_all(); v.sort(); v });
79    /// assert_eq!(vec!["hello_world"],
80    ///            { let mut v = ts.pop_all(); v.sort(); v });
81    /// assert!(ts.pop_all().is_empty());
82    /// # }
83    /// ```
84    #[inline]
85    pub fn new() -> TopologicalSort<T> {
86        TopologicalSort {
87            top: HashMap::new(),
88        }
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
180    /// Removes all items that are not depended on by any other items and returns it, or empty
181    /// vector if there are no such items.
182    ///
183    /// If `pop_all` returns an empty vector and `len` is not 0, there is cyclic dependencies.
184    pub fn pop_all(&mut self) -> Vec<T> {
185        let keys = self.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
217    fn remove(&mut self, prec: &T) -> Option<Dependency<T>> {
218        let result = self.top.remove(prec);
219        if let Some(ref p) = result {
220            for s in &p.succ {
221                if let Some(y) = self.top.get_mut(s) {
222                    y.num_prec -= 1;
223                }
224            }
225        }
226        result
227    }
228}
229
230impl<T: PartialOrd + Eq + Hash + Clone> FromIterator<T> for TopologicalSort<T> {
231    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> TopologicalSort<T> {
232        let mut top = TopologicalSort::new();
233        let mut seen = Vec::<T>::default();
234        for item in iter {
235            let _ = top.insert(item.clone());
236            for seen_item in seen.iter().cloned() {
237                match seen_item.partial_cmp(&item) {
238                    Some(Ordering::Less) => {
239                        top.add_dependency(seen_item, item.clone());
240                    }
241                    Some(Ordering::Greater) => {
242                        top.add_dependency(item.clone(), seen_item);
243                    }
244                    _ => (),
245                }
246            }
247            seen.push(item);
248        }
249        top
250    }
251}
252
253/// A link between two items in a sort.
254#[derive(Copy, Clone, Debug)]
255pub struct DependencyLink<T> {
256    /// The element which is depened upon by `succ`.
257    pub prec: T,
258    /// The element which depends on `prec`.
259    pub succ: T,
260}
261
262impl<T> From<(T, T)> for DependencyLink<T> {
263    fn from(tuple: (T, T)) -> Self {
264        DependencyLink {
265            succ: tuple.0,
266            prec: tuple.1,
267        }
268    }
269}
270
271impl<T: Eq + Hash + Clone> FromIterator<DependencyLink<T>> for TopologicalSort<T> {
272    fn from_iter<I: IntoIterator<Item = DependencyLink<T>>>(iter: I) -> TopologicalSort<T> {
273        let mut top = TopologicalSort::new();
274        for link in iter {
275            top.add_link(link);
276        }
277        top
278    }
279}
280
281impl<T: Hash + Eq + Clone> Iterator for TopologicalSort<T> {
282    type Item = T;
283
284    fn next(&mut self) -> Option<T> {
285        self.pop()
286    }
287}
288
289impl<T: fmt::Debug + Hash + Eq> fmt::Debug for Dependency<T> {
290    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
291        write!(f, "prec={}, succ={:?}", self.num_prec, self.succ)
292    }
293}
294
295impl<T: fmt::Debug + Hash + Eq + Clone> fmt::Debug for TopologicalSort<T> {
296    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
297        write!(f, "{:?}", self.top)
298    }
299}
300
301
302#[cfg(test)]
303mod test {
304    use super::TopologicalSort;
305    use std::iter::FromIterator;
306
307    #[test]
308    fn from_iter() {
309        let t = vec![4, 3, 3, 5, 7, 6, 8];
310        let mut ts = TopologicalSort::<i32>::from_iter(t);
311        assert_eq!(Some(3), ts.next());
312        assert_eq!(Some(4), ts.next());
313        assert_eq!(Some(5), ts.next());
314        assert_eq!(Some(6), ts.next());
315        assert_eq!(Some(7), ts.next());
316        assert_eq!(Some(8), ts.next());
317        assert_eq!(None, ts.next());
318    }
319
320    #[test]
321    fn iter() {
322        let mut ts = TopologicalSort::<i32>::new();
323        ts.add_dependency(1, 2);
324        ts.add_dependency(2, 3);
325        ts.add_dependency(3, 4);
326        assert_eq!(Some(1), ts.next());
327        assert_eq!(Some(2), ts.next());
328        assert_eq!(Some(3), ts.next());
329        assert_eq!(Some(4), ts.next());
330        assert_eq!(None, ts.next());
331    }
332
333    #[test]
334    fn pop_all() {
335        fn check(result: &[i32], ts: &mut TopologicalSort<i32>) {
336            let l = ts.len();
337            let mut v = ts.pop_all();
338            v.sort();
339            assert_eq!(result, &v[..]);
340            assert_eq!(l - result.len(), ts.len());
341        }
342
343        let mut ts = TopologicalSort::new();
344        ts.add_dependency(7, 11);
345        assert_eq!(2, ts.len());
346        ts.add_dependency(7, 8);
347        assert_eq!(3, ts.len());
348        ts.add_dependency(5, 11);
349        assert_eq!(4, ts.len());
350        ts.add_dependency(3, 8);
351        assert_eq!(5, ts.len());
352        ts.add_dependency(3, 10);
353        assert_eq!(6, ts.len());
354        ts.add_dependency(11, 2);
355        assert_eq!(7, ts.len());
356        ts.add_dependency(11, 9);
357        assert_eq!(8, ts.len());
358        ts.add_dependency(11, 10);
359        assert_eq!(8, ts.len());
360        ts.add_dependency(8, 9);
361        assert_eq!(8, ts.len());
362
363        check(&[3, 5, 7], &mut ts);
364        check(&[8, 11], &mut ts);
365        check(&[2, 9, 10], &mut ts);
366        check(&[], &mut ts);
367    }
368
369    #[test]
370    fn cyclic_deadlock() {
371        let mut ts = TopologicalSort::new();
372        ts.add_dependency("stone", "sharp");
373
374        ts.add_dependency("bucket", "hole");
375        ts.add_dependency("hole", "straw");
376        ts.add_dependency("straw", "axe");
377        ts.add_dependency("axe", "sharp");
378        ts.add_dependency("sharp", "water");
379        ts.add_dependency("water", "bucket");
380        assert_eq!(ts.pop(), Some("stone"));
381        assert!(ts.pop().is_none());
382        println!("{:?}", ts);
383    }
384}
topological_sort/lib.rs

topological_sort/
lib.rs
