Struct TopologicalSort 

pub struct TopologicalSort<T> { /* private fields */ }

A data structure for topological sorting.

See the crate-level documentation for examples.

Implementations

impl<T> TopologicalSort<T>

where T: Clone + Eq + Hash,

pub fn new() -> Self

Creates a new empty TopologicalSort.

See the crate-level documentation for examples.

pub fn len(&self) -> usize

Returns the number of remaining items in the TopologicalSort.

This counts all remaining items, including those that are not yet ready to pop.

pub fn is_empty(&self) -> bool

Returns true if the TopologicalSort contains no remaining items.

pub fn add_dependency<P, S>(&mut self, prec: P, succ: S) -> bool

where P: Into<T>, S: Into<T>,

Registers a dependency from prec to succ.

This means that succ depends on prec, so prec must be popped or removed before succ becomes ready.

Returns true if this dependency link was newly added, or false if it was already present.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::new();
assert!(ts.add_dependency("compile", "link"));

assert_eq!(ts.pop(), Some("compile"));
assert_eq!(ts.pop(), Some("link"));

pub fn add_link(&mut self, link: DependencyLink<T>) -> bool

Registers a dependency link.

This means that link.succ depends on link.prec, so link.prec must be popped or removed before link.succ becomes ready.

Returns true if this dependency link was newly added, or false if it was already present.

use topological_sort::{DependencyLink, TopologicalSort};

let mut ts = TopologicalSort::new();
assert!(ts.add_link(DependencyLink {
    prec: "compile",
    succ: "link"
}));

assert_eq!(ts.pop(), Some("compile"));
assert_eq!(ts.pop(), Some("link"));

pub fn insert<U>(&mut self, item: U) -> bool

where U: Into<T>,

Inserts an item, without adding any dependencies from or to it.

Returns true if the item was not already present, or false otherwise.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::new();
assert!(ts.insert("standalone"));
assert!(!ts.insert("standalone"));

assert_eq!(ts.pop(), Some("standalone"));

pub fn pop(&mut self) -> Option<T>

Removes one item that does not depend on any other remaining item and returns it, or None if there is no such item.

If pop returns None and len is not 0, the remaining items contain a cycle.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::new();
ts.add_dependency("a", "b");

assert_eq!(ts.pop(), Some("a"));
assert_eq!(ts.pop(), Some("b"));
assert_eq!(ts.pop(), None);

pub fn pop_iter(&mut self) -> PopIter<'_, T>

Returns an iterator that repeatedly calls pop.

Each call to Iterator::next removes one item from the sort.

The iterator ends when the sort becomes empty or when no item can be popped because the remaining items contain a cycle.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::new();
ts.add_dependency(1, 2);
ts.add_dependency(2, 3);

let mut it = ts.pop_iter();
assert_eq!(Some(1), it.next());
assert_eq!(Some(2), it.next());
drop(it);

assert_eq!(Some(3), ts.pop());

pub fn pop_all(&mut self) -> Vec<T>

👎Deprecated since 0.3.0:

Use pop_batch instead, which returns an arbitrary collection containing all ready items.

Removes all items that do not depend on any other remaining item at the time of the call and returns them, or an empty vector if there are no such items.

The returned items are in arbitrary order.

If pop_all returns an empty vector and the sort is not empty, the remaining items contain a cycle.

pub fn pop_batch<R>(&mut self) -> R

where R: Default + Extend<T>,

Removes all items that do not depend on any other remaining item at the time of the call and returns them, or an empty collection if there are no such items.

Unlike pop_iter, this removes only the current batch of ready items. If removing those items makes more items ready, they are returned by the next call to pop_batch, not the current one.

The returned items are in arbitrary order.

If pop_batch returns an empty collection and the sort is not empty, the remaining items contain a cycle.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::<i32>::new();
ts.add_dependency(1, 3);
ts.add_dependency(2, 3);

let mut ready = ts.pop_batch::<Vec<_>>();
ready.sort_unstable();
assert_eq!(ready, [1, 2]);

assert_eq!(ts.pop_batch::<Vec<_>>(), [3]);

pub fn peek(&self) -> Option<&T>

Returns a reference to one item that does not depend on any other remaining item, or None if there is no such item.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::new();
ts.add_dependency("a", "b");

assert_eq!(ts.peek(), Some(&"a"));
assert_eq!(ts.len(), 2);
assert_eq!(ts.pop(), Some("a"));

pub fn peek_all(&self) -> Vec<&T>

👎Deprecated since 0.3.0:

Use peek_batch instead, which returns an iterator over all ready items.

Returns a vector of references to all items that do not depend on any other remaining item at the time of the call.

The returned items are in arbitrary order.

pub fn peek_batch(&self) -> PeekBatch<'_, T>

Returns an iterator over references to all items that do not depend on any other remaining item at the time of the call.

The iterator yields no items if there are no such items. This inspects only the current batch of ready items.

The returned items are in arbitrary order.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::<i32>::new();
ts.add_dependency(1, 3);
ts.add_dependency(2, 3);

let mut ready = ts.peek_batch().copied().collect::<Vec<_>>();
ready.sort_unstable();
assert_eq!(ready, [1, 2]);
assert_eq!(ts.len(), 3);

pub fn items(&self) -> Items<'_, T>

Returns an iterator visiting all remaining items in arbitrary order.

This includes items that are not yet ready because they are blocked by unresolved dependencies or cycles.

pub fn into_items(self) -> IntoItems<T>

Returns a consuming iterator visiting all remaining items in arbitrary order.

This includes items that are not yet ready because they are blocked by unresolved dependencies or cycles.

pub fn remove<Q>(&mut self, item: &Q) -> Option<T>

where T: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes the specified item if it does not depend on any other remaining item and returns it.

Returns None if the item is not present or if it still depends on another remaining item.

Removing the item also removes its outgoing dependency links, which may make some successor items ready.

use topological_sort::TopologicalSort;

let mut ts = TopologicalSort::new();
ts.add_dependency("a", "b");

assert_eq!(ts.remove("b"), None);
assert_eq!(ts.remove("a"), Some("a"));
assert_eq!(ts.remove("b"), Some("b"));

Trait Implementations

impl<T: Clone> Clone for TopologicalSort<T>

fn clone(&self) -> TopologicalSort<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for TopologicalSort<T>

where T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for TopologicalSort<T>

fn default() -> TopologicalSort<T>

Returns the “default value” for a type.

impl<T> Extend<DependencyLink<T>> for TopologicalSort<T>

where T: Clone + Eq + Hash,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = DependencyLink<T>>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<DependencyLink<T>> for TopologicalSort<T>

where T: Clone + Eq + Hash,

fn from_iter<I>(iter: I) -> TopologicalSort<T>

where I: IntoIterator<Item = DependencyLink<T>>,

Creates a value from an iterator.