xml-dev - Walking the DOM (was: XML APIs)

[John Cowan <cowan@locke.ccil.org>]

Stephen R. Savitzky wrote:

> [T]he classic algorithm for traversing a tree is:
> 
> traverse(node) {
>   visit(node);
>   if (node.firstChild != null) traverse(node.firstChild);
>   if (node.nextSibling != null) traverse(node.nextSibling);
> }

The trouble with that algorithm is that it is recursive.  It will
blow up if the tree is sufficiently deep.  Indeed, in
languages that cannot be relied on to do tail recursion, like
Java, it will blow up if the tree is merely sufficiently wide.

Furthermore, if there is any end-of-node processing to do, such as
emitting an end tag indication, then the algorithm is no longer
even partly tail recursive and will blow up on both depth and
width even in safe-tail-recursion languages.

The algorithm I use in DOMParser, therefore, is non-recursive:

   traverse(Node node) {
    Node currentNode = node;

    while (currentNode != null) {
      visit(currentNode);

      // Move down to first child
      Node nextNode = currentNode.getFirstChild();
      if (nextNode != null) {
        currentNode = nextNode;
        continue;
        }

      // No child nodes, so walk tree
      while (currentNode != null) {
        revisit(currentNode)	// do end-of-node processing, if any

        // Move to sibling if possible.
        nextNode = currentNode.getNextSibling();
        if (nextNode != null) {
          currentNode = nextNode;
          break;
          }

       // Move up
       if (currentNode = node)
	 currentNode = null;
       else
	 currentNode = currentNode.getParentNode();
       }
    }
  }

Because of the reliability of this algorithm vis-a-vis the recursive
one, I believe it should be the standard way of walking DOM trees,
and therefore it is essential that DOM implementations make the
structural access methods fast.

-- 
John Cowan	http://www.ccil.org/~cowan		cowan@ccil.org
	You tollerday donsk?  N.  You tolkatiff scowegian?  Nn.
	You spigotty anglease?  Nnn.  You phonio saxo?  Nnnn.
		Clear all so!  'Tis a Jute.... (Finnegans Wake 16.5)

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@ic.ac.uk)