All Packages Class Hierarchy This Package Previous Next Index
Class graph.DAGIterator
java.lang.Object

+graph.DAGIterator
 public class DAGIterator
 extends Object
This class is an iterator for class DAG.
Iteration over objects of class DAG is essentially DAG traversal.
Traversal of DAGs is implemented with using a stack of nodes.
Traversals in preorder, postorder, and traversals with
multiple visits of nonterminal nodes are supported.
Ther are two variants of each of the above traversals  with and
without visiting nodes that were already reached from another parent.
 See Also:
 DAG

DAGIterator(DAG)
 Constructs a DAGIterator.

allorder()
 Iterates to the next DAG node by going through all edges first forward and then backward.

current()
 Returns the latest visited node of the traversed DAG.

isPost()
 Returns true current() is not a leaf node and it is the post visit of current().

isPre()
 Returns true if the currently visited node is not a leaf node and it is
the first visit of this node.

pop()
 Forces to walk to the parent of the currently visited node.

postorder()
 Iterates to the next DAG node in postorder.

preorder()
 Iterates to the next DAG node in preorder.

push(int)
 Forces to walk to the child with the specified index from the currently visited node.

singleAllorder()
 Iterates to the next DAG node by going through all edges first forward and then backward
(edges leading to already visited nodes are skipped).

singlePostorder()
 Iterates to the next DAG node in postorder
(edges leading to already visited nodes are skipped).

singlePreorder()
 Iterates to the next DAG node in preorder
(edges leading to already visited nodes are skipped).

skip()
 Forces to skip visiting of yet unvisited children of the currently visited node.

visit()
 Returns the ordinal number of the current visit for the same parent.
DAGIterator
public DAGIterator(DAG p)
 Constructs a DAGIterator. Its parameter is the DAG to traverse.
 Parameters:
 p  DAG to traverse
visit
public int visit()
 Returns the ordinal number of the current visit for the same parent.
If this is the last visit, lastIndex()+1 is returned for nonterminal nodes.
This method always returns 1 for preorder.
It returns lastIndex()+1 when walking nonterminal nodes in postorder.
This method is useful when doing allorder traversals in which
nonterminal DAG nodes are visited several times.
isPre
public boolean isPre()
 Returns true if the currently visited node is not a leaf node and it is
the first visit of this node.
Returns false otherwise.
isPost
public boolean isPost()
 Returns true current() is not a leaf node and it is the post visit of current().
Returns false otherwise.
skip
public synchronized void skip()
 Forces to skip visiting of yet unvisited children of the currently visited node.
This method sets the ordinal number of the current visit to Integer.MAX_VALUE.
Due to that, the currently visited node can be modified before
the following iterator invocation.
preorder
public synchronized DAG preorder()
 Iterates to the next DAG node in preorder.
singlePreorder
public synchronized DAG singlePreorder()
 Iterates to the next DAG node in preorder
(edges leading to already visited nodes are skipped).
postorder
public synchronized DAG postorder()
 Iterates to the next DAG node in postorder.
singlePostorder
public synchronized DAG singlePostorder()
 Iterates to the next DAG node in postorder
(edges leading to already visited nodes are skipped).
allorder
public synchronized DAG allorder()
 Iterates to the next DAG node by going through all edges first forward and then backward.
Therefore, each node is visited before visiting the first child
and then after visiting each child. Terminal nodes are visited once.
singleAllorder
public synchronized DAG singleAllorder()
 Iterates to the next DAG node by going through all edges first forward and then backward
(edges leading to already visited nodes are skipped).
Therefore, each node is visited before visiting the first child
and then after visiting each child. Terminal nodes are visited once.
current
public DAG current()
 Returns the latest visited node of the traversed DAG.
pop
public synchronized void pop()
 Forces to walk to the parent of the currently visited node.
push
public synchronized void push(int n)
 Forces to walk to the child with the specified index from the currently visited node.
 Parameters:
 n  index of the child to push onto the traversal stack
All Packages Class Hierarchy This Package Previous Next Index