TopSort (Jikes RVM API)

Overview

Package

Class

Use

Tree

Serialized

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

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>
extends Stack<SortedGraphNode>

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

Field Summary
`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
`private`	`TopSort()` Prevent instantiation

Method Summary
`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`

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)

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