Java Generics and Collections

Chapter 9. Design Patterns

This chapter reviews five well-known design patterns—Visitor, Interpreter, Function, Strategy, and Subject-Observer—and shows how they can take advantage of generics. The Function pattern generalizes the idea behind the Comparator interface. The other four patterns are described in the seminal book Design Patterns, by Gamma, Helm, Johnson, and Vlissides (Addison-Wesley).

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 numbers—for simplicity, ...