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
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.
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionvoid
addBeforeAfter
(T before, T after) An alternative toaddDependency(Object, Object[])
, which is equivalent to addDependency(after,before) as the after item is dependent of the before item.void
addDependency
(T dependent, T... dependency) Add a dependency to be considered in the sort.void
sort
(Collection<T> list) Sort the passed list according to dependencies previously set withaddDependency(Object, Object[])
.void
Sort the passed array according to dependencies previously set withaddDependency(Object, Object[])
.toString()
-
Constructor Details
-
TopologicalSort
public TopologicalSort()
-
-
Method Details
-
addDependency
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
-
addBeforeAfter
An alternative toaddDependency(Object, Object[])
, which is equivalent to addDependency(after,before) as the after item is dependent of the before item.- Parameters:
before
- The item will be sorted before the afterafter
- The item will be sorted after the before
-
sort
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
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.
-
toString
-