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 a HashSet

public class TopologicalSort<T>
extends 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.

Constructor Summary

Constructors

Constructor	Description
TopologicalSort()

Method Summary

Modifier and Type	Method	Description
void	addBeforeAfter(T before, T after)	An alternative to addDependency(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 with addDependency(Object, Object[]).
void	sort(T[] array)	Sort the passed array according to dependencies previously set with addDependency(Object, Object[]).
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Details

TopologicalSort

public TopologicalSort()

Method Details

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 dependencies

dependency - The dependency item, will be sorted before its dependent item

addBeforeAfter

public void addBeforeAfter(T before,
 T after)

An alternative to addDependency(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 after

after - The item will be sorted after the before

sort

public void sort(T[] array)

Sort the passed array according to dependencies previously set with addDependency(Object, Object[]). Where possible, ordering will be preserved if no dependency

Parameters:

array - The array to be sorted.

sort

public void sort(Collection<T> list)

Sort the passed list according to dependencies previously set with addDependency(Object, Object[]). Where possible, ordering will be preserved if no dependency

Parameters:

list - The list to be sorted.

toString

public String toString()

Overrides:

toString in class Object