Top Description Inners Fields Constructors Methods
org.eclipse.jetty.util

public Class TopologicalSort<T>

extends Object
Class Inheritance
Type Parameters
<T>
The type to be sorted. It must be able to be added to a HashSet
Imports
java.util.ArrayList, .Collection, .Comparator, .HashMap, .HashSet, .List, .Map, .Set, .SortedSet, .TreeSet
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 and Inner Type Summary

Modifier and TypeClass 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.

Field Summary

Modifier and TypeField and Description
private final Map<T, Set<T>>
_dependencies

Constructor Summary

AccessConstructor and Description
public
TopologicalSort()

Method Summary

Modifier and TypeMethod and Description
public void
addBeforeAfter(T
The item will be sorted before the after
before, T
The item will be sorted after the before
after)

An alternative to addDependency(Object, Object[]), which is equivalent to addDependency(after,before) as the after item is dependent of the before item.

public void
addDependency(T
The dependent item will be sorted after all its dependencies
dependent, T...
The dependency item, will be sorted before its dependent item
dependency)

Add a dependency to be considered in the sort.

public void
sort(T[]
The array to be sorted.
array)

Sort the passed array according to dependencies previously set with addDependency(Object, Object[]).

public void
sort(Collection<T>
The list to be sorted.
list)

Sort the passed list according to dependencies previously set with addDependency(Object, Object[]).

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

private void
visit(T
The item to be visited
item, Set<T>
The Set of items already visited
visited, List<T>
The list to sort items into
sorted, Comparator<T>
A comparator used to sort dependencies.
comparator)

Visit an item to be sorted.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

_dependenciesback to summary
private final Map<T, Set<T>> _dependencies

Constructor Detail

TopologicalSortback to summary
public TopologicalSort()

Method Detail

addBeforeAfterback to summary
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:T

The item will be sorted before the after

after:T

The item will be sorted after the before

addDependencyback to summary
public void addDependency(T dependent, T... dependency)

Add a dependency to be considered in the sort.

Parameters
dependent:T

The dependent item will be sorted after all its dependencies

dependency:T[]

The dependency item, will be sorted before its dependent item

sortback to summary
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:T[]

The array to be sorted.

sortback to summary
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:Collection<T>

The list to be sorted.

toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

Returns:String

a string representation of the object

Annotations
@Override
visitback to summary
private void visit(T item, Set<T> visited, List<T> sorted, Comparator<T> comparator)

Visit an item to be sorted.

Parameters
item:T

The item to be visited

visited:Set<T>

The Set of items already visited

sorted:List<T>

The list to sort items into

comparator:Comparator<T>

A comparator used to sort dependencies.

org.eclipse.jetty.util back to summary

private Class TopologicalSort.CyclicException

extends IllegalStateException
Class Inheritance

Constructor Summary

AccessConstructor and Description
pack-priv
CyclicException(Object item)

pack-priv
CyclicException(Object item, TopologicalSort.CyclicException e)

Constructor Detail

CyclicExceptionback to summary
pack-priv CyclicException(Object item)
CyclicExceptionback to summary
pack-priv CyclicException(Object item, TopologicalSort.CyclicException e)
org.eclipse.jetty.util back to summary

private Class TopologicalSort.InitialOrderComparator<T>

extends Object
implements Comparator<T>
Class Inheritance
  • java.lang.Object
  • org.eclipse.jetty.util.TopologicalSort.InitialOrderComparator
All Implemented Interfaces
java.util.Comparator
A comparator that is used to sort dependencies in the order they were in the original list. This ensures that dependencies are visited in the original order and no needless reordering takes place.

Field Summary

Modifier and TypeField and Description
private final Map<T, Integer>
_indexes

Constructor Summary

AccessConstructor and Description
pack-priv
InitialOrderComparator(T[] initial)

pack-priv
InitialOrderComparator(Collection<T> initial)

Method Summary

Modifier and TypeMethod and Description
public int
compare(T
the first object to be compared.
o1, T
the second object to be compared.
o2)

Implements java.util.Comparator.compare.

Compares its two arguments for order.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

_indexesback to summary
private final Map<T, Integer> _indexes

Constructor Detail

InitialOrderComparatorback to summary
pack-priv InitialOrderComparator(T[] initial)
InitialOrderComparatorback to summary
pack-priv InitialOrderComparator(Collection<T> initial)

Method Detail

compareback to summary
public int compare(T o1, T o2)

Implements java.util.Comparator.compare.

Doc from java.util.Comparator.compare.

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that signum(compare(x, z))==signum(compare(y, z)) for all z.

Parameters
o1:T

the first object to be compared.

o2:T

the second object to be compared.

Returns:int

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Annotations
@Override