In my previous post, we took a look at the basic Visitor design pattern, and a couple of simple variations. I now continue with a more ambitious variation.

This is where the fun begins.

Variation 3: Eliminate recursion

Suppose we have a huge file system tree and that processing it takes a lot of time. We’d then want to update some progress indicator, or give other threads some time to run. To do that, we’d need to interrupt the processing. The current implementation doesn’t support that, because of the recursion.

Most developers probably know that every recursive implementation can be replaced by an iterative one. In a recursive function, there is an iteration of the same method call on the program’s stack. We can replace that using an explicit stack.

But in order to be able to use iteration, we need to be able to move from one node in the file system tree to the next:

public interface FileSystemNode {

  FileSystemNode getFirstChild();
  FileSystemNode getLastChild();
  
  FileSystemNode getNextSibling();
  FileSystemNode getPrevSibling();
  
  FileSystemNode getNext();
  FileSystemNode getPrev();
  
  FileSystemNode getNextNoChild();

  boolean isAncestorOf(FileSystemNode next);

  // other methods as before ...
}

We can implement that as follows:

public abstract class AbstractFileSystemNode
    implements FileSystemNode {

  public FileSystemNode getFirstChild() {
    return children.isEmpty() ? null : children.get(0);
  }

  public FileSystemNode getLastChild() {
    return children.isEmpty() ? null
        : children.get(children.size() - 1);
  }

  public FileSystemNode getNextSibling() {
    FileSystemNode result = null;
    if (parent != null) {
      final int index = 
          parent.children.indexOf(this) + 1;
      if (index < parent.children.size()) {
        result = parent.children.get(index);
      }
    }
    return result;
  }
  
  public FileSystemNode getPrevSibling() {
    FileSystemNode result = null;
    if (parent != null) {
      final int index = 
          parent.children.indexOf(this) - 1;
      if (index >= 0) {
        result = parent.children.get(index);
      }
    }
    return result;
  }
  
  public FileSystemNode getNext() {
    FileSystemNode result = getFirstChild();
    if (result == null) {
      result = getNextNoChild();
    }
    return result;
  }

  public FileSystemNode getNextNoChild() {
    FileSystemNode result = getNextSibling();
    if (result == null) {
      FileSystemNode next = this;
      while (next.getParent() != null) {
        next = next.getParent();
        if (next.getNextSibling() != null) {
          result = next.getNextSibling();
          break;
        }
      }
    }
    return result;
  }

  public FileSystemNode getPrev() {
    FileSystemNode result = null;
    FileSystemNode prev = getPrevSibling();
    if (prev == null) {
      result = getParent();
    } else {
      while (prev.getLastChild() != null) {
        prev = prev.getLastChild();
      }
      result = prev;
    }
    return result;
  }

  public boolean isAncestorOf(
      final FileSystemNode descendant) {
    boolean result = false;
    FileSystemNode current = descendant;
    while (!result && current != null) {
      result = equals(current);
      current = current.getParent();
    }
    return result;
  }

  // other methods as before...
}

With these navigational methods in place, we can eliminate the recursion:

public class BaseFileSystemVisitor
    implements FileSystemVisitor {

  public void visit(final FileSystemNode node) {
    Stack stack = new Stack();
    FileSystemNode current = node;

    while (current != null) {
      stack.push(current);
      if (current.start(this)) {
        current = current.getNext();
      } else {
        current = current.getNextNoChild();
      }
      while (!stack.isEmpty() 



          && !stack.peek().isAncestorOf(current)) {
        stack.pop().stop(this);
      }
    }
  }

  // other methods as before...

}

Note: I use generics here (e.g. Stack<FileSystemNode>), but am not showing it, since that messes up the formatting in the code viewer thingie.

The current solution has some advantages over the recursive one, like not suffering from stack overflows with deeply nested trees, but my goal was to be able to traverse the tree in multiple calls. To make that possible, we need to be able to specify how many nodes can be visited in a single call:

public interface FileSystemVisitor {
  FileSystemNode visit(FileSystemNode node);
  void setMaxNodes(int maxNodes);
  
  // ...
}

The visit() method returns where it stopped, so you can supply that information with your next call. In our implementation, we need to make the stack a field instead of a local variable, so that its contents is preserved between calls:

public class BaseFileSystemVisitor
    implements FileSystemVisitor {

  private int maxNodes = Integer.MAX_VALUE;
  private final Stack stack = new Stack();
  
  public void setMaxNodes(int maxNodes) {
    this.maxNodes = maxNodes;
  }

  public FileSystemNode visit(final FileSystemNode node) {
    int numNodesVisited = 0;
    FileSystemNode current = node;

    while (current != null
        && numNodesVisited < maxNodes) {
      numNodesVisited++;
      stack.push(current);
      if (current.start(this)) {
        current = current.getNext();
      } else {
        current = current.getNextNoChild();
      }
      while (!stack.isEmpty()
          && !stack.peek().isAncestorOf(current)) {
        stack.pop().stop(this);
      }
    }
    return current;
  }

  // other methods as before...
}

And voila, we’re done. Next time we will look at making this code re-entrant, so that we can start visiting a node while we’re visiting another node.