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:

<personnel>
  <person id="H.MARUYAMA" >
    <name><family>MARUYAMA</family> <given>Hiroshi</given></name>
    <email>maruyama@jp.ibm.com</email>
    <link subordinates="  N.URAMOTO    K.TAMURA "/>
  </person>
  <person id="N.URAMOTO">
    <name><family>URAMOTO</family> <given>Naohiko</given></name>
    <email>uramoto@jp.ibm.com</email>
    <link manager="		H.MARUYAMA"/>
  </person>
  <person id="K.TAMURA">
    <name>
      <family>TAMURA</family> <given>Kent</given>
    </name>
    <!-- This URL is mail address.-->
    <url href="mailto:kent@trl.ibm.co.jp"/>
    <url href="mailto:tkent@jp.ibm.com"/>
    <link manager="H.MARUYAMA"/>
  </person>
</personnel>


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 <code>javax.swing.tree.TreeNode</code> interface to
 * generic methods required by <code>TIterator</code>. */
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 <code>org.w3c.dom.Node</code> interface to generic 
 * methods required by <code>TIterator</code>. 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 <code>org.w3c.dom.Node</code> methods to <code>Enumeration<code>.
   * Inner class <code>HeadNode</code> provides dummy impelmemtation for
   * <code>Node</code>, it is used as the head of the list. This is needed 
   * to advance to the first element after the <code>next()</code> */
  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 <code>Node</code>.
     * It returns its node after the <code>nextSibling</code> 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 <code>Node</code> 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 <code>org.w3c.dom.Node</code> and 
 * <code>com.ibm.xml.parser.Parent</code> to generic methods required 
 * by <code>TIterator</code>. */
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 <code>setLevelDepth</code> */
  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);
      }
    }
  }
}


1