Struct DependencyQueue

pub struct DependencyQueue<N: Hash + Eq, E: Hash + Eq, V> {
    dep_map: HashMap<N, (HashSet<(N, E)>, V)>,
    reverse_dep_map: HashMap<N, HashMap<E, HashSet<N>>>,
    priority: HashMap<N, usize>,
    cost: HashMap<N, usize>,
}

Fields

dep_map: HashMap<N, (HashSet<(N, E)>, V)>

A list of all known keys to build.

The value of the hash map is list of dependencies which still need to be built before the package can be built. Note that the set is dynamically updated as more dependencies are built.

reverse_dep_map: HashMap<N, HashMap<E, HashSet<N>>>

A reverse mapping of a package to all packages that depend on that package.

This map is statically known and does not get updated throughout the lifecycle of the DependencyQueue.

This is sort of like a HashMap<(N, E), HashSet<N>> map, but more easily indexable with just an N

priority: HashMap<N, usize>

The relative priority of this package. Higher values should be scheduled sooner.

cost: HashMap<N, usize>

An expected cost for building this package. Used to determine priority.

Implementations

impl<N: Hash + Eq, E: Hash + Eq, V> DependencyQueue<N, E, V>

pub fn new() -> DependencyQueue<N, E, V>

Creates a new dependency queue with 0 packages.

impl<N: Hash + Eq + Clone, E: Eq + Hash + Clone, V> DependencyQueue<N, E, V>

pub fn queue( &mut self, key: N, value: V, dependencies: impl IntoIterator<Item = (N, E)>, cost: usize, )

Adds a new node and its dependencies to this queue.

The key specified is a new node in the dependency graph, and the node depend on all the dependencies iterated by dependencies. Each dependency is a node/edge pair, where edges can be thought of as productions from nodes (aka if it’s just () it’s just waiting for the node to finish).

An optional value can also be associated with key which is reclaimed when the node is ready to go.

The cost parameter can be used to hint at the relative cost of building this node. This implementation does not care about the units of this value, so the calling code is free to use whatever they’d like. In general, higher cost nodes are expected to take longer to build.

pub fn queue_finished(&mut self)

All nodes have been added, calculate some internal metadata and prepare for dequeue.

pub fn dequeue(&mut self) -> Option<(N, V, usize)>

Dequeues a package that is ready to be built.

A package is ready to be built when it has 0 un-built dependencies. If None is returned then no packages are ready to be built.

pub fn is_empty(&self) -> bool

Returns true if there are remaining packages to be built.

pub fn len(&self) -> usize

Returns the number of remaining packages to be built.

pub fn finish(&mut self, node: &N, edge: &E) -> Vec<&N>

Indicate that something has finished.

Calling this function indicates that the node has produced edge. All remaining work items which only depend on this node/edge pair are now candidates to start their job.

Returns the nodes that are now allowed to be dequeued as a result of finishing this node.

Trait Implementations

impl<N: Debug + Hash + Eq, E: Debug + Hash + Eq, V: Debug> Debug for DependencyQueue<N, E, V>

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

Formats the value using the given formatter.

impl<N: Hash + Eq, E: Hash + Eq, V> Default for DependencyQueue<N, E, V>

fn default() -> DependencyQueue<N, E, V>

Returns the “default value” for a type.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 192 bytes