T
- The type to be sorted. It must be able to be added to a HashSet
public class TopologicalSort<T>
extends java.lang.Object
A Topological sort is used when you have a partial ordering expressed as
dependencies between elements (also often represented as edges in a directed
acyclic graph). A Topological sort should not be used when you have a total
ordering expressed as a Comparator
over the items. The algorithm has
the additional characteristic that dependency sets are sorted by the original
list order so that order is preserved when possible.
The sort algorithm works by recursively visiting every item, once and only once. On each visit, the items dependencies are first visited and then the item is added to the sorted list. Thus the algorithm ensures that dependency items are always added before dependent items.
Modifier and Type | Class and Description |
---|---|
private static class |
TopologicalSort.CyclicException |
private static class |
TopologicalSort.InitialOrderComparator<T>
A comparator that is used to sort dependencies in the order they
were in the original list.
|
Modifier and Type | Field and Description |
---|---|
private java.util.Map<T,java.util.Set<T>> |
_dependencies |
Constructor and Description |
---|
TopologicalSort() |
Modifier and Type | Method and Description |
---|---|
void |
addDependency(T dependent,
T dependency)
Add a dependency to be considered in the sort.
|
void |
sort(java.util.Collection<T> list)
Sort the passed list according to dependencies previously set with
addDependency(Object, Object) . |
void |
sort(T[] array)
Sort the passed array according to dependencies previously set with
addDependency(Object, Object) . |
java.lang.String |
toString() |
private void |
visit(T item,
java.util.Set<T> visited,
java.util.List<T> sorted,
java.util.Comparator<T> comparator)
Visit an item to be sorted.
|
public void addDependency(T dependent, T dependency)
dependent
- The dependent item will be sorted after all its dependenciesdependency
- The dependency item, will be sorted before its dependent itempublic void sort(T[] array)
addDependency(Object, Object)
. Where possible, ordering will be
preserved if no dependencyarray
- The array to be sorted.public void sort(java.util.Collection<T> list)
addDependency(Object, Object)
. Where possible, ordering will be
preserved if no dependencylist
- The list to be sorted.private void visit(T item, java.util.Set<T> visited, java.util.List<T> sorted, java.util.Comparator<T> comparator)
item
- The item to be visitedvisited
- The Set of items already visitedsorted
- The list to sort items intocomparator
- A comparator used to sort dependencies.public java.lang.String toString()
toString
in class java.lang.Object