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 pre-order, post-order, and traversals with multiple visits of non-terminal 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

Constructor Index

 o DAGIterator(DAG)
Constructs a DAGIterator.

Method Index

 o allorder()
Iterates to the next DAG node by going through all edges first forward and then backward.
 o current()
Returns the latest visited node of the traversed DAG.
 o isPost()
Returns true current() is not a leaf node and it is the post visit of current().
 o isPre()
Returns true if the currently visited node is not a leaf node and it is the first visit of this node.
 o pop()
Forces to walk to the parent of the currently visited node.
 o postorder()
Iterates to the next DAG node in post-order.
 o preorder()
Iterates to the next DAG node in pre-order.
 o push(int)
Forces to walk to the child with the specified index from the currently visited node.
 o 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).
 o singlePostorder()
Iterates to the next DAG node in post-order (edges leading to already visited nodes are skipped).
 o singlePreorder()
Iterates to the next DAG node in pre-order (edges leading to already visited nodes are skipped).
 o skip()
Forces to skip visiting of yet unvisited children of the currently visited node.
 o visit()
Returns the ordinal number of the current visit for the same parent.

Constructors

 o DAGIterator
 public DAGIterator(DAG p)
Constructs a DAGIterator. Its parameter is the DAG to traverse.

Parameters:
p - DAG to traverse

Methods

 o 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 non-terminal nodes. This method always returns 1 for pre-order. It returns lastIndex()+1 when walking non-terminal nodes in post-order. This method is useful when doing allorder traversals in which non-terminal DAG nodes are visited several times.

 o 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.

 o isPost
 public boolean isPost()
Returns true current() is not a leaf node and it is the post visit of current(). Returns false otherwise.

 o 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.

 o preorder
 public synchronized DAG preorder()
Iterates to the next DAG node in pre-order.

 o singlePreorder
 public synchronized DAG singlePreorder()
Iterates to the next DAG node in pre-order (edges leading to already visited nodes are skipped).

 o postorder
 public synchronized DAG postorder()
Iterates to the next DAG node in post-order.

 o singlePostorder
 public synchronized DAG singlePostorder()
Iterates to the next DAG node in post-order (edges leading to already visited nodes are skipped).

 o 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.

 o 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.

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

 o pop
 public synchronized void pop()
Forces to walk to the parent of the currently visited node.

 o 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