T - the type of objects being sortedID - the type of the object identifiers; multiple objects of T may correspond to the same
IDpublic abstract class TopologicalSort<T,ID>
extends java.lang.Object
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:
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.| Constructor and Description |
|---|
TopologicalSort() |
| 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.
|
protected abstract ID getId(T object)
object - the objectprotected abstract java.util.Collection<ID> getRequirements(ID id)
id. Implementors may choose to return null
or an empty collection if this information is more easily computed by
getDependencies(Object).id - the idid; may be nullprotected abstract java.util.Collection<ID> getDependencies(ID id)
id. Implementors may choose to return
null or an empty collection if this information is more easily computed by
getRequirements(Object).id - the idid; may be null