Package org.eclipse.jetty.util
Class TopologicalSort<T>
- java.lang.Object
-
- org.eclipse.jetty.util.TopologicalSort<T>
-
- Type Parameters:
T
- The type to be sorted. It must be able to be added to aHashSet
public class TopologicalSort<T> extends java.lang.Object
Topological sort a list or array.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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.
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<T,java.util.Set<T>>
_dependencies
-
Constructor Summary
Constructors Constructor Description TopologicalSort()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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 withaddDependency(Object, Object)
.void
sort(T[] array)
Sort the passed array according to dependencies previously set withaddDependency(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.
-
-
-
Method Detail
-
addDependency
public void addDependency(T dependent, T dependency)
Add a dependency to be considered in the sort.- Parameters:
dependent
- The dependent item will be sorted after all its dependenciesdependency
- The dependency item, will be sorted before its dependent item
-
sort
public void sort(T[] array)
Sort the passed array according to dependencies previously set withaddDependency(Object, Object)
. Where possible, ordering will be preserved if no dependency- Parameters:
array
- The array to be sorted.
-
sort
public void sort(java.util.Collection<T> list)
Sort the passed list according to dependencies previously set withaddDependency(Object, Object)
. Where possible, ordering will be preserved if no dependency- Parameters:
list
- The list to be sorted.
-
visit
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.- Parameters:
item
- The item to be visitedvisited
- The Set of items already visitedsorted
- The list to sort items intocomparator
- A comparator used to sort dependencies.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-