ix.util
Class TopologicalSorter

java.lang.Object
  ix.util.TopologicalSorter

Direct Known Subclasses:

PlanCheckingSimulator.ExecOrderSorter, SimpleRSim.ExecOrderSorter

public abstract class TopologicalSorter
extends java.lang.Object

DAG topological sort, returning ancestors before descendents.

You should make a new sorter each time.

Field Summary

(package private) static java.lang.Object	FINISH
(package private) java.util.Map	marks
(package private) LListCollector	result
(package private) static java.lang.Object	START

Constructor Summary

TopologicalSorter()

Method Summary

protected abstract java.util.Collection	getChildren(java.lang.Object node)
java.util.List	sort(java.util.Collection roots)
protected void	walk(java.util.Collection items)

Methods inherited from class java.lang.Object

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

Field Detail

START

static final java.lang.Object START

FINISH

static final java.lang.Object FINISH

marks

final java.util.Map marks

result

final LListCollector result

Constructor Detail

TopologicalSorter

public TopologicalSorter()

Method Detail

sort

public java.util.List sort(java.util.Collection roots)

walk

protected void walk(java.util.Collection items)

getChildren

protected abstract java.util.Collection getChildren(java.lang.Object node)