org.eclipse.e4.ui.internal.workbench

Class TopologicalSort<T,ID>

java.lang.Object

org.eclipse.e4.ui.internal.workbench.TopologicalSort<T,ID>

Type Parameters:

T - the type of objects being sorted

ID - the type of the object identifiers; multiple objects of T may correspond to the same ID

Direct Known Subclasses:

ExtensionsSort

public abstract class TopologicalSort<T,ID>
extends java.lang.Object

This class implements a topological sort. The implementation distinguishes between the objects to be sorted from their corresponding dependency identifier, and properly tracks where multiple objects have the same identifier. This is required for sorting Eclipse Extension Registry extensions by their plug-in dependencies, as a plug-in may contribute multiple sets of extensions.

The implementation creates a dependency graph where the vertices represent the object identifiers and the edges represent the required-relation between them. Subclasses must implement of getRequirements(Object) and getDependencies(Object). Although these are normally symmetric operations (i.e., if B is a requirement of A, then A is a dependent of B), one may be easier to compute than the other in some contexts and so this class combines the results.

Description of the algorithm:

1. Construct the dependency graph with getRequirements(Object) and getDependencies(Object). The out edges represent requirements, and in edges represent dependencies. This graph may be disconnected if there are nodes with no dependencies amongst each other.
2. Sort the list of identifiers by their out-degree, and then by in-degree. Ids with out-degree 0 are roots; if there is no id with out-degree 0 then we have a cycle. We sort nodes with the same out-degree by their in-degree to privilege nodes within the cycle from those that are dependencies (e.g., consider: A → B, B → C, C → A, D → A; all have out-degree 1, but A has in-degree 2, and A must be output before D).
3. While there are ids left to consider, take the id with lowest out-degree and add its objects to the list. Remove the id from all of its dependents' required lists. This removal changes the out-degree and may require that the id list be resorted since some of the dependents may now be roots. Note that should we encounter a cycle (i.e., no nodes of degree 0), we process all the bundles within the cycle, since any dependencies to any single ndoe within the cycle effectively extends to all.

Constructor Summary

Constructors

Constructor and Description
TopologicalSort()

Method Summary

Modifier and Type	Method and Description
protected abstract java.util.Collection<ID>	getDependencies(ID id) Return the list of IDs depended upon by id.
protected abstract ID	getId(T object) Return the identifier for the given object.
protected abstract java.util.Collection<ID>	getRequirements(ID id) Return the list of IDs required by id.
T[]	sort(T[] objects) Sort the provided extensions by the dependencies of their contributors.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TopologicalSort

public TopologicalSort()

Method Detail

getId

protected abstract ID getId(T object)

Return the identifier for the given object. The implementation properly tracks where multiple objects have the same identifier.

Parameters:

object - the object

Returns:

the identifier

getRequirements

protected abstract java.util.Collection<ID> getRequirements(ID id)

Return the list of IDs required by id. Implementors may choose to return null or an empty collection if this information is more easily computed by getDependencies(Object).

Parameters:

id - the id

Returns:

the IDs required by id; may be null

getDependencies

protected abstract java.util.Collection<ID> getDependencies(ID id)

Return the list of IDs depended upon by id. Implementors may choose to return null or an empty collection if this information is more easily computed by getRequirements(Object).

Parameters:

id - the id

Returns:

the IDs depended upon by id; may be null

sort

public T[] sort(T[] objects)

Sort the provided extensions by the dependencies of their contributors. Note that sorting is done in-place.

Parameters:

objects - the objects to be sorted

Returns:

the objects in a topologically-sorted order