The Art of the Visitor Pattern (1)

The visitor design pattern is one of those relatively simple patterns that you can use in many situations. Some situations are more complex than others, though, and may require some modifications. I will first present the basic pattern, and then some variations:

  1. process before and after a node
  2. skip parts of the data structure
  3. eliminate recursion
  4. support re-entrancy
  5. manipulate the data structure during visiting

This first post in a series will set the stage by discussing the basic pattern and the first two variations.

The basic pattern

Consider the following example. We have a data structure that represents a file system, with folders, files, links, devices, etc. This structure is basically a tree:

public interface FileSystemNode {

  FileSystemNode getParent();
  void setParent(FileSystemNode node);
	
  Iterator getChildren();
  void add(FileSystemNode child);
	
  void accept(FileSystemVisitor visitor);

  String getName();

}

Note: I’m using generics here but am not showing it, since it messes up the formatting.

Each of the implementors of this interface is listed in the FileSystemVisitor, so that it can handle them differently:

public interface FileSystemVisitor {

  void visit(Folder folder);
  void visit(File file);
  void visit(Link link);
  void visit(Device device);
  // ...

}

The gist of the visitor pattern is a double dispatch where the visitor calls the accept() method of the FileSystemNode:

public class BaseFileSystemVisitor 
    implements FileSystemVisitor {

  public void visit(final FileSystemNode node) {
    node.accept(this);
	  
    Iterator children = node.getChildren();
    while (children.hasNext()) {
      visit(children.next());
    }
  }

  public void visit(Folder folder) {
    // For descendants to implement
  }

  public void visit(File file) {
    // For descendants to implement
  }

  public void visit(Link link) {
    // For descendants to implement
  }

  public void visit(Device device) {
    // For descendants to implement
  }

  // ...
	
}

…and the FileSystemNode calls the visit() method of the visitor:

public class FolderImpl extends AbstractFileSystemNode 
    implements Folder {

  public void accept(final FileSystemVisitor visitor) {
    visitor.visit(this);
  }

  // Folder implementation...

}

An implementation for listing files (like the Unix ls command) could be implemented as follows:

public class ListVisitor extends BaseFileSystemVisitor {

  private final PrintStream out;

  public ListVisitor() {
    this(System.out);  
  }
  
  public ListVisitor(final PrintStream out) {
    super();
    this.out = out;
  }

  @Override
  public void visit(final Device device) {
    out.println(device.getType() + ": " 
        + device.getName());
  }

  @Override
  public void visit(final File file) {
    out.println(file.getName());
  }

  @Override
  public void visit(final Folder folder) {
    out.println(folder.getName() + "/");
  }

  @Override
  public void visit(final Link link) {
    out.println(link.getName() + " ->" 
        + link.getTarget());
  }
  
  // ...
  
}

Variation 1: Process before and after a node

Now suppose we don’t want a simple list like the one provided by ListVisitor, but we want to export to XML. For that to work, we need to open and close the containing folder tag, e.g.:

<folder name='remon'>
  <file name='quotes.txt'/>
  <device name='wlan' type='usb'/>
  <link name='java'
      target='/usr/lib/jvm/java-6-sun/bin/java'/>
</folder>

To implement this, we replace the visit() methods with start() and stop() methods:

public interface FileSystemVisitor {
  void start(Folder folder);
  void stop(Folder folder);

  void start(File file);
  void stop(File file);


  void start(Link link);
  void stop(Link link);

  void start(Device device);
  void stop(Device device);

  // ...
}

public class BaseFileSystemVisitor 
    implements FileSystemVisitor {

  public void visit(final FileSystemNode node) {
    node.start(this);
	  
    Iterator children = node.getChildren();
    while (children.hasNext()) {
      visit(children.next());
    }
	  
    node.stop(this);      
  }

  // ...
}

This allows us to implement the XmlVisitor:

public class XmlVisitor extends BaseFileSystemVisitor {

  private final PrintStream out;

  public XmlVisitor() {
    this(System.out);  
  }
  
  public XmlVisitor(final PrintStream out) {
    this.out = out;
  }

  @Override
  public void start(Device device) {
    out.println("<device type='" + device.getType() 
        + "' name='" + device.getName() + "'/>");
  }

  @Override
  public void start(File file) {
    out.println("<file name='" + file.getName() 
        + "'/>");
  }

  @Override
  public void start(Folder folder) {
    out.println("<folder name='" + folder.getName() 
        + "'>");
  }

  @Override
  public void stop(Folder folder) {
    out.println("</folder>");
  }
  
  @Override
  public void start(Link link) {
    out.println("<link name='" + link.getName() 
        + "' target='" + link.getTarget() + "'/>");
  }

}

Variation 2: Skip parts of the data structure

Now suppose we want to skip processing a sub-tree. For instance, we may want to skip folders and files whose names start with a dot. We can achieve this by having the start() method return a boolean that indicates whether the sub-tree starting at the node is to be processed:

public interface FileSystemVisitor {
  boolean start(Folder folder);
  void stop(Folder folder);

  boolean start(File file);
  void stop(File file);

  boolean start(Link link);
  void stop(Link link);

  boolean start(Device device);
  void stop(Device device);
  
  // ...
}

public class BaseFileSystemVisitor
    implements FileSystemVisitor {

  public void visit(final FileSystemNode node) {
    if (node.start(this)) {
      Iterator children = node.getChildren();
      while (children.hasNext()) {
        visit(children.next());
      }
  	  
      node.stop(this);
    }
  }

  public boolean start(Folder folder) {
    // For descendants to implement
    return true;
  }

  // ...
}

public class FolderImpl extends AbstractFileSystemNode 
    implements Folder {

  public FolderImpl(final String name) {
    super(name);
  }

  public boolean start(final FileSystemVisitor visitor) {
    return visitor.start(this);
  }

  public void stop(final FileSystemVisitor visitor) {
    visitor.stop(this);
  }

}

public class XmlVisitor extends BaseFileSystemVisitor {
  // ...

  @Override
  public boolean start(Folder folder) {
    boolean result = !folder.getName().startsWith(".");
    if (result) {
      out.println("<folder name='" + folder.getName() 
          + "'>");
    }
    return result;
  }

  // ...
}

Next time we’ll get serious with the visitor pattern by eliminating the recursion, so stay tuned!

Advertisements

2 thoughts on “The Art of the Visitor Pattern (1)

Please Join the Discussion

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s