Original source at http://www.ddj.com/ftp/2000/2000_11/aa0011.txt
Algorithm Alley
by Alexander Ananiev
Example 1:
if ( levelIter.hasChildren() ) {
levelIter=levelIter.nextLevel();
}
Object nextElt=null;
// if there are more siblings at the current level
if ( levelIter.hasMoreElements() )
nextElt=levelIter.nextElement();
// the entire level has been processed--go to the parent level
else if (levelIter.hasParent() ) {
levelIter=levelIter.toParent();
nextElt=levelIter.nextElement();
}
return nextElt;
Example 2:
/** Returns enumeration of the children of the node. */
public Enumeration getChildren( Object node );
/** Returns true if node has children. */
public boolean hasChildren( Object node );
Example 3:
(a)
if (nodeAdapter.hasChildren( node) && depth<=maxDepth) // go to children's level ...
(b)
public static final int idLevel = 2;
//...
Document xdoc = parser.readStream(new FileReader( "personnel.xml"));
TIterator tIterator = new TIterator ( xdoc , new DOMAdapter(), idLevel );
for( Node node = xdoc; node!=null; node=(Node)tIterator.next() ){
// perform processing...
}
Figure 1:
MARUYAMA Hiroshi maruyama@jp.ibm.com
URAMOTO Naohiko uramoto@jp.ibm.com
TAMURA Kent
Listing One
package aan.treexamples;
import org.w3c.dom.*;
public class RecursiveTraversal implements ITraversal {
/* Performs full tree traversal using recursion. */
public void traverse( Node parentNode ) {
// traverse all nodes that belong to the parent
for(Node node=parentNode.getFirstChild(); node!=null;
node=node.getNextSibling()) {
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
// traverse children
traverse(node);
}
}
}
Listing Two
package aan.treexamples;
import org.w3c.dom.*;
import java.util.*;
public class StackTraversal implements ITraversal {
/* Performs full tree traversal using stack. */
public void traverse( Node rootNode ) {
Stack stack = new Stack();
// ignore root -- root acts as a container
Node node=rootNode.getFirstChild();
while (node!=null) {
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
if ( node.hasChildNodes()) {
// store next sibling in stack. Return to it after all children
// are processed.
if (node.getNextSibling()!=null)
stack.push( node.getNextSibling() );
node = node.getFirstChild();
}
else {
node = node.getNextSibling();
if (node==null && !stack.isEmpty())
// return to the parent's level. // some levels can be skipped if parent's node was the last one.
node=(Node) stack.pop();
}
}
}
}
Listing Three
package aan.treexamples;
import org.w3c.dom.*;
public class LinkTraversal implements ITraversal {
/* Performs full tree traversal usingchild-parent link. */
public void traverse( Node rootNode ) {
// ignore root -- root acts as a container
Node node=rootNode.getFirstChild();
while (node!=null) {
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
if ( node.hasChildNodes()) {
node = node.getFirstChild();
}
else { // leaf
// find the parent level
while (node.getNextSibling()==null && node != rootNode)
// use child-parent link to get to the parent level
node=node.getParentNode();
node = node.getNextSibling();
}
}
}
}
Listing Four
package aan.treexamples;
import aan.tree.*;
import org.w3c.dom.*;
public class IterFullTraversal implements ITraversal {
/* Performs full tree traversal using tree iterator. */
public void traverse ( Node rootNode ) {
// create iterator
TIterator tIterator = new TIterator ( rootNode , new DOMAdapter() );
Node node = null;
while( (node=(Node)tIterator.next()) != null ) {
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
}
}
}
Listing Five
package aan.tree;
import java.util.Enumeration;
import javax.swing.tree.TreeNode;
/* This adapter maps javax.swing.tree.TreeNode interface to
* generic methods required by TIterator. */
public class SwingAdapter implements TNodeAdapter {
public Enumeration getChildren( Object node ) {
return ((TreeNode)node).children();
}
public boolean hasChildren( Object node ) {
return ! ((TreeNode)node).isLeaf();
}
}
Listing Six
package aan.tree;
import java.util.Enumeration;
import org.w3c.dom.*;
/** This adapter maps org.w3c.dom.Node interface to generic
* methods required by TIterator. Enumeration provided by the
* nested class in order to conforom to w3c spec. */
public class DOMAdapter implements TNodeAdapter {
public Enumeration getChildren( Object node ) {
return new Enumerator( ((Node)node).getFirstChild() );
}
public boolean hasChildren( Object node ) {
return ((Node)node).hasChildNodes();
}
/* Maps org.w3c.dom.Node methods to Enumeration.
* Inner class HeadNode provides dummy impelmemtation for
* Node, it is used as the head of the list. This is needed
* to advance to the first element after the next() */
static public class Enumerator implements Enumeration {
private Node node;
Enumerator( Node node) {
// empty node is the head of the list
this.node = new HeadNode( node );
}
public Object nextElement() {
node = node.getNextSibling();
return node;
}
public boolean hasMoreElements() {
return (node.getNextSibling() != null);
}
/* Dummy implementation of the Node.
* It returns its node after the nextSibling call */
private class HeadNode implements Node {
private Node nextNode;
/* Creates the node and initiates with the current node */
private HeadNode( Node node){
nextNode = node;
}
/* Returns current node as the next. This is the only method that's * used out of Node interface. @return current node */
public Node getNextSibling() {
return nextNode;
}
// all these methods are not used
public String getNodeName(){ return null;}
public String getNodeValue() throws DOMException { return null;}
public void setNodeValue(String nodeValue) throws DOMException {}
public short getNodeType() {return 0;}
public Node getParentNode() {return null;}
public NodeList getChildNodes() {return null;}
public Node getFirstChild() {return null;}
public Node getLastChild() {return null;}
public Node getPreviousSibling() {return null;}
public NamedNodeMap getAttributes(){return null;}
public Document getOwnerDocument(){return null;}
public Node insertBefore(Node newChild, Node refChild)
throws DOMException {return null;}
public Node replaceChild(Node newChild, Node oldChild)
throws DOMException {return null;}
public Node removeChild(Node oldChild)
throws DOMException {return null;}
public Node appendChild(Node newChild)
throws DOMException {return null;}
public boolean hasChildNodes() {return false;}
public Node cloneNode(boolean deep) {return null;}
} // end of HeadNode
} // end of Enumerator
}
Listing Seven
package aan.tree;
import java.util.Enumeration;
import org.w3c.dom.Node;
import com.ibm.xml.parser.Parent;
/* Maps org.w3c.dom.Node and
* com.ibm.xml.parser.Parent to generic methods required
* by TIterator. */
public class XML4JAdapter implements TNodeAdapter {
public Enumeration getChildren( Object node ) {
return ((Parent)node).elements();
}
public boolean hasChildren( Object node ) {
return ((Node)node).hasChildNodes();
}
}
Listing Eight
package aan.treexamples;
import aan.tree.*;
import org.w3c.dom.*;
public class IterMaxDepthTraversal implements ITraversal {
/* Traverses tree with traversal depth set to depth of the "person" level */
public void traverse ( Node rootNode ) {
// create iterator
TIterator tIterator = new TIterator ( rootNode, new DOMAdapter() );
// find the depth of the required level
int targetDepth = -1;
Node node = null;
while( (node=(Node)tIterator.next()) != null )
if (node.getNodeName().equals("person")) {
targetDepth = tIterator.getDepth();
break;
}
// we can reuse the same iterator
tIterator.setRoot(rootNode);
// limit the depth of traversal
tIterator.setMaxDepth( targetDepth );
while( (node=(Node)tIterator.next()) != null ) {
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
}
}
}
Listing Nine
package aan.treexamples;
import aan.tree.*;
import org.w3c.dom.*;
public class SelectiveNestedTraversal implements ITraversal {
/* Selectively traverses the tree ising nested loops. */
public void traverse ( Node rootNode ) {
// create 1st iterator. depth should be limited to ID's level
DOMAdapter domAdapter = new DOMAdapter();
TIterator tIterator = new TIterator ( rootNode, domAdapter, 2 );
Node node = null;
while( ( node=(Node)tIterator.next() )!=null ){
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
if (node instanceof Element && ((Element)node).getAttribute( "id" ).
equalsIgnoreCase( "K.TAMURA" )) {
// create 2nd iterator, perform nested loop to process the branch.
TIterator branchIterator = new TIterator ( node, domAdapter);
Node branchNode = null;
while( (branchNode=(Node)branchIterator.next()) != null )
// print node information
System.out.println( branchNode.getNodeName()+"="+branchNode.getNodeValue());
}
}
}
}
Listing Ten
package aan.treexamples;
import aan.tree.*;
import org.w3c.dom.*;
public class SelectiveSkipTraversal implements ITraversal {
/* Selectively traverses the tree ising skip flag. */
public void traverse ( Node rootNode ) {
// create an iterator.
int idLevel = 2;
TIterator tIterator = new TIterator ( rootNode, new DOMAdapter());
Node node = null;
while( ( node=(Node)tIterator.next() )!=null ){
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
if ( tIterator.getDepth() == idLevel && ! (node instanceof Element &&
((Element)node).getAttribute( "id").equalsIgnoreCase("K.TAMURA" ))) {
// allow parsing all children of the node -- applies only to the current node
tIterator.skipChildren();
}
}
}
}
Listing Eleven
package aan.treexamples;
import aan.tree.*;
import org.w3c.dom.*;
public class SelectiveSetDepthTraversal implements ITraversal {
/* Selectively traverses the tree using setLevelDepth */
public void traverse (Node rootNode) {
// create iterator, initially it is limited to the ID level
int idLevel =2;
TIterator tIterator = new TIterator (rootNode,new DOMAdapter(),idLevel);
Node node = null;
while( ( node=(Node)tIterator.next() )!=null ){
// print node information
System.out.println( node.getNodeName()+"="+node.getNodeValue());
if ( tIterator.getDepth() == idLevel && (node instanceof Element &&
((Element)node).getAttribute( "id").equalsIgnoreCase("K.TAMURA" ))) {
// this allows iterator to traverse children of the current node
tIterator.setLevelDepth( TIterator.DEPTH_UNLIMITED);
}
}
}
}