Section 9.1. Visitor

9.1. Visitor

Often, a data structure is defined by case analysis and recursion. For example, a binary tree of type tree<E> is one of the following:

• A leaf, containing a single value of type E

• A branch, containing a left subtree and a right subtree, both of type TRee<E>

It is easy to think of many other examples: a shape may be either a triangle, a rectangle, a combination of two shapes, or the transposition of a shape; an XML node is either a text node, an attribute node, or an element node (which may contain other nodes); and so on.

To represent such a structure in an object-oriented language, the data structure is represented by an abstract class, and each case is represented by a subclass. The abstract class declares an abstract method for each possible operation on the data structure, and each subclass implements the method as appropriate for the corresponding case.

Example 9.1 illustrates this technique applied to trees. There is an abstract class, tree<E>, with two abstract methods, toString and sum. (The former applies to any tree, while the latter applies only to a tree of numbersfor simplicity, this restriction is enforced by a cast at run time rather than a type at compile time, as discussed later.) There are two static factory methods, one to construct a leaf and one to construct a branch. Each of these contains a nested class that extends TRee<E> and implements each of the methods toString and sum.

A simple tree and client

 abstract class Tree<E> {   abstract public String toString();   abstract public Double sum();   public static <E> Tree<E> leaf(final E e) {     return new Tree<E>() {       public String toString() {         return e.toString();       }       public Double sum() {         return ((Number)e).doubleValue();       }     };   }   public static <E> Tree<E> branch(final Tree<E> l, final Tree<E> r) {     return new Tree<E>() {       public String toString() {         return "("+l.toString()+"^"+r.toString()+")";       }       public Double sum() {         return l.sum() + r.sum();       }     };   } } class TreeClient {   public static void main(String[] args) {     Tree<Integer> t =       Tree.branch(Tree.branch(Tree.leaf(1),                               Tree.leaf(2)),                   Tree.leaf(3));     assert t.toString().equals("((1^2)^3)");     assert t.sum() == 6;   } } 

This approach is adequate if you know in advance all of the operations required on the data structure, or can modify the classes that define the structure when the requirements change. However, sometimes this is not the case, particularly when different developers are responsible for the classes that define the structure and the classes that are clients of the structure.

The Visitor pattern makes it possible to provide new operations without modifying the classes that define the data structure. In this pattern, the abstract class that represents the structure declares an abstract visit method, which takes a visitor as an argument. The visitor implements an interface that specifies one method for each case in the specification of the structure. Each subclass implements the visit method by calling the method of the visitor for the corresponding case.

Example 9.2 illustrates this pattern applied to trees. Now the abstract class TRee<E> has only one abstract method, visit, which accepts an argument of type Visitor<E, R>. The interface Visitor<E, R> specifies two methods, a leaf method that accepts a value of type E and returns a value of type R, and a branch method that accepts two values of type R and returns a value of type R. The subclass corresponding to a leaf implements visit by invoking the leaf method of the visitor on the element in the leaf, and the subclass corresponding to a branch implements visit by invoking the branch method of the visitor on the result of recursive calls of the visitor on the left and right subtrees.

A tree with visitors

 abstract class Tree<E> {   public interface Visitor<E, R> {     public R leaf(E elt);     public R branch(R left, R right);   }   public abstract <R> R visit(Visitor<E, R> v);   public static <T> Tree<T> leaf(final T e) {     return new Tree<T>() {       public <R> R visit(Visitor<T, R> v) {         return v.leaf(e);       }     };   }   public static <T> Tree<T> branch(final Tree<T> l, final Tree<T> r) {     return new Tree<T>() {       public <R> R visit(Visitor<T, R> v) {         return v.branch(l.visit(v), r.visit(v));       }     };   } } 

Example 9.3 illustrates how to implement the toString and sum methods on trees within the client, rather than within the class that defines the data structure. Whereas before these were methods with the tree as the receiver, now they are static methods that take the tree as an argument.

A client with visitors

 class TreeClient {   public static <T> String toString(Tree<T> t) {     return t.visit(new Tree.Visitor<T, String>() {       public String leaf(T e) {         return e.toString();       }       public String branch(String l, String r) {         return "("+l+"^"+r+")";       }     });   }   public static <N extends Number> double sum(Tree<N> t) {     return t.visit(new Tree.Visitor<N, Double>() {       public Double leaf(N e) {         return e.doubleValue();       }       public Double branch(Double l, Double r) {         return l+r;       }     });   }   public static void main(String[] args) {     Tree<Integer> t =       Tree.branch(Tree.branch(Tree.leaf(1),                               Tree.leaf(2)),                   Tree.leaf(3));     assert toString(t).equals("((1^2)^3)");     assert sum(t) == 6;   } } 

There is a pleasing duality between the two approaches. For simple trees, each factory method (leaf and branch) groups together definitions for each operator method (toString and sum). For trees with visitors, each operator method (toString and sum) groups together definitions for each visitor method (leaf and branch).

With generics, each visitor has two type parameters, one for the element type of the tree and one for the return type of the visitor. Without generics, each visitor would have to return a result of type Object, and many additional casts would be required. Because of this, when generics are not present, often visitors are designed not to return a value; instead, the result is accumulated in a variable local to the visitor, complicating the flow of data through the program.

It is interesting to note that the generic type of the sum method can be more precise with visitors. With simple trees, the sum method must have a type signature that indicates that it works on any element type; a cast is required to convert each leaf to type Number; and a class cast error is raised at run time if sum is invoked on a tree not containing numbers. With visitors, the sum method may have a type signature that indicates that it works only on elements that are numbers; no cast is required; and a type error is reported at compile time if sum is invoked on a tree not containing numbers.

In practice, you will often use a combination of the simple approach and the Visitor pattern. For instance, you might choose to define standard methods, such as toString, using the simple approach, while using Visitor for other methods, such as sum.