From LiteratePrograms

Introduction

An exemplary generic, visitable tree, implemented in Java 5. The tree uses Java Generics and can therefore contain arbitrary objects. Methods for accessing the tree are implemented using the Visitor Pattern, so the methods can be defined without changing the actual tree class, improving encapsulation and reusability. This implementation is based on the binary tree described in Naftalin and Wadler (2006).

Implementation

A visitor visits the actual elements of type E as well as recursive branches, and returns elements of type R. The Tree class defines an abstract method, which takes a visitor as an argument and returns an object of the desired return value:

<<visitor>>=
public abstract <R> R visit(Visitor<? super E, R> v);
public interface Visitor<E, R> {
	public R leaf(E elt);
	public R branch(List<? extends R> children);
}

The tree supplies a static factory method for creating a leaf, a tree implementation that overrides the abstract visit method:

<<leaf>>=
public static <T> Tree<T> leaf(final T e) {
	// return anonymous subclass for a leaf:
	return new Tree<T>() {
		@Override
		public <R> R visit(Visitor<? super T, R> v) {
			return v.leaf(e);
		}
	};
}

The tree also has a static factory method for creating a branch, also a tree implementation that overrides the abstract visit method:

<<branch>>=
public static <T> Tree<T> branch(final List<? extends Tree<T>> children) {
	// return anonymous subclass for a branch:
	return new Tree<T>() {
		@Override
		public <R> R visit(Visitor<? super T, R> v) {
			List<R> result = new ArrayList<R>();
			for (Tree<T> tree : children) {
				result.add(tree.visit(v));
			}
			return v.branch(result);
		}
	};
}

Now we can add operations on the tree outside of it, in a client, by implementing a visitor that will perform the operation, e.g. for output :

<<op_1>>=
public static String toString(Tree<?> t) {
	// return an anonymous implementation of a visitor:
	return t.visit(new Tree.Visitor<Object, String>() {
		public String leaf(Object e) {
			return e.toString();
		}
		public String branch(List<? extends String> children) {
			String result = "(";
			for (String c : children) {
				result += c + " ";
			}
			return result.trim() + ")";
		}
	});
}

We can also add another visitor that will compute the sum of all nodes for a tree of numbers:

<<op_2>>=
public static double sum(Tree<? extends Number> t) {
	// return an anonymous implementation of a visitor:
	return t.visit(new Tree.Visitor<Number, Double>() {
		public Double leaf(Number e) {
			return e.doubleValue();
		}
		public Double branch(List<? extends Double> children) {
			Double res = 0.0;
			for (Double d : children) {
				res += d;
			}
			return res;
		}
	});
}

In a main method, we can then construct a particular tree (here for integers) and perform the defined operations on it:

<<main>>=
public static void main(String[] args) {
	Tree<Integer> t = Tree.branch(Arrays.asList(Tree.branch(Arrays
			.asList(Tree.leaf(1), Tree.leaf(2))), Tree.leaf(3)));
	System.out.println(toString(t)); // --> ((1,2),3)
	System.out.println(sum(t)); // --> 6.0
}

We import the required Java classes:

<<imports>>=
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

And finally we have the complete program:

<<Tree.java>>=
imports
abstract class Tree<E> {
	visitor
	branch
	leaf
	static class TreeClient {
		op_1
		op_2
		main
	}
}

References

• Maurice Naftalin and Philip Wadler (2006), Java Generics and Collections, O'Reilly.

Download code