org.jikesrvm.compilers.opt.util

Class TopSort

java.lang.Object

org.jikesrvm.compilers.opt.util.Stack<SortedGraphNode>

org.jikesrvm.compilers.opt.util.TopSort

All Implemented Interfaces:

Iterable<SortedGraphNode>

public final class TopSort
extends Stack<SortedGraphNode>

Depth First Spanning Tree, builds topological sort of a graph consisting of SortedGraphNode.

Field Summary

Fields

Modifier and Type	Field and Description
private boolean	forward are we processing the graph in forward order?
private SortedGraphNode	lastNumberedNode the last node to get a number
private int	sortMarker the "visited" marker to use
private int	sortNumber the next "number" to give out

Constructor Summary

Constructors

Modifier	Constructor and Description
private	TopSort() Prevent instantiation

Method Summary

Modifier and Type	Method and Description
static SortedGraphNode	buildTopological(TopSortInterface graph, boolean forward)
private void	DFS(SortedGraphNode node, int numNodes) Depth-first numbering in a non-recursive manner

Methods inherited from class org.jikesrvm.compilers.opt.util.Stack

compare, copy, empty, getTOS, isEmpty, iterator, peek, pop, push, shallowCopy, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

sortMarker

private int sortMarker

the "visited" marker to use

sortNumber

private int sortNumber

the next "number" to give out

lastNumberedNode

private SortedGraphNode lastNumberedNode

the last node to get a number

forward

private boolean forward

are we processing the graph in forward order?

Constructor Detail

TopSort

private TopSort()

Prevent instantiation

Method Detail

buildTopological

public static SortedGraphNode buildTopological(TopSortInterface graph,
                                               boolean forward)

Parameters:

graph - the graph

forward - should we treat edges as forward? This is the second version of the implementation (see CVS file for older one)

Returns:

the last sorted node

DFS

private void DFS(SortedGraphNode node,
                 int numNodes)

Depth-first numbering in a non-recursive manner

Parameters:

node - the root node

numNodes - the number of nodes in this graph