MindView Inc.
[ Viewing Hints ] [ 2nd Edition ] [ Free Newsletter ]
[ Seminars ] [ Seminars on CD ROM ] [ Consulting ]

Thinking in Java, 1st edition

©1998 by Bruce Eckel

[ Previous Chapter ] [ Short TOC ] [ Table of Contents ] [ Index ] [ Next Chapter ]

16: Design patterns

This chapter introduces the important and yet non-traditional “patterns” approach to program design.

Probably the most important step forward in object-oriented design is the “design patterns” movement, chronicled in Design Patterns, by Gamma, Helm, Johnson & Vlissides (Addison-Wesley 1995).[66] That book shows 23 different solutions to particular classes of problems. In this chapter, the basic concepts of design patterns will be introduced along with several examples. This should whet your appetite to read Design Patterns (a source of what has now become an essential, almost mandatory, vocabulary for OOP programmers).

The latter part of this chapter contains an example of the design evolution process, starting with an initial solution and moving through the logic and process of evolving the solution to more appropriate designs. The program shown (a trash sorting simulation) has evolved over time, and you can look at that evolution as a prototype for the way your own design can start as an adequate solution to a particular problem and evolve into a flexible approach to a class of problems.

The pattern concept

Initially, you can think of a pattern as an especially clever and insightful way of solving a particular class of problems. That is, it looks like a lot of people have worked out all the angles of a problem and have come up with the most general, flexible solution for it. The problem could be one you have seen and solved before, but your solution probably didn’t have the kind of completeness you’ll see embodied in a pattern.

Although they’re called “design patterns,” they really aren’t tied to the realm of design. A pattern seems to stand apart from the traditional way of thinking about analysis, design, and implementation. Instead, a pattern embodies a complete idea within a program, and thus it can sometimes appear at the analysis phase or high-level design phase. This is interesting because a pattern has a direct implementation in code and so you might not expect it to show up before low-level design or implementation (and in fact you might not realize that you need a particular pattern until you get to those phases).

The basic concept of a pattern can also be seen as the basic concept of program design: adding a layer of abstraction. Whenever you abstract something you’re isolating particular details, and one of the most compelling motivations behind this is to separate things that change from things that stay the same. Another way to put this is that once you find some part of your program that’s likely to change for one reason or another, you’ll want to keep those changes from propagating other changes throughout your code. Not only does this make the code much cheaper to maintain, but it also turns out that it is usually simpler to understand (which results in lowered costs).

Often, the most difficult part of developing an elegant and cheap-to-maintain design is in discovering what I call “the vector of change.” (Here, “vector” refers to the maximum gradient and not a collection class.) This means finding the most important thing that changes in your system, or put another way, discovering where your greatest cost is. Once you discover the vector of change, you have the focal point around which to structure your design.

So the goal of design patterns is to isolate changes in your code. If you look at it this way, you’ve been seeing some design patterns already in this book. For example, inheritance can be thought of as a design pattern (albeit one implemented by the compiler). It allows you to express differences in behavior (that’s the thing that changes) in objects that all have the same interface (that’s what stays the same). Composition can also be considered a pattern, since it allows you to change – dynamically or statically – the objects that implement your class, and thus the way that class works.

You’ve also already seen another pattern that appears in Design Patterns: the iterator (Java 1.0 and 1.1 capriciously calls it the Enumeration; Java 1.2 collections use “iterator”). This hides the particular implementation of the collection as you’re stepping through and selecting the elements one by one. The iterator allows you to write generic code that performs an operation on all of the elements in a sequence without regard to the way that sequence is built. Thus your generic code can be used with any collection that can produce an iterator.

The singleton

Possibly the simplest design pattern is the singleton, which is a way to provide one and only one instance of an object. This is used in the Java libraries, but here’s a more direct example:

//: SingletonPattern.java
// The Singleton design pattern: you can
// never instantiate more than one.
package c16;

// Since this isn't inherited from a Cloneable
// base class and cloneability isn't added,
// making it final prevents cloneability from
// being added in any derived classes:
final class Singleton {
  private static Singleton s = new Singleton(47);
  private int i;
  private Singleton(int x) { i = x; }
  public static Singleton getHandle() { 
    return s; 
  }
  public int getValue() { return i; }
  public void setValue(int x) { i = x; }
}

public class SingletonPattern {
  public static void main(String[] args) {
    Singleton s = Singleton.getHandle();
    System.out.println(s.getValue());
    Singleton s2 = Singleton.getHandle();
    s2.setValue(9);
    System.out.println(s.getValue());
    try {
      // Can't do this: compile-time error.
      // Singleton s3 = (Singleton)s2.clone();
    } catch(Exception e) {}
  }
} ///:~

The key to creating a singleton is to prevent the client programmer from having any way to create an object except the ways you provide. You must make all constructors private, and you must create at least one constructor to prevent the compiler from synthesizing a default constructor for you (which it will create as “friendly”).

At this point, you decide how you’re going to create your object. Here, it’s created statically, but you can also wait until the client programmer asks for one and create it on demand. In any case, the object should be stored privately. You provide access through public methods. Here, getHandle( ) produces the handle to the Singleton object. The rest of the interface (getValue( ) and setValue( )) is the regular class interface.

Java also allows the creation of objects through cloning. In this example, making the class final prevents cloning. Since Singleton is inherited directly from Object, the clone( ) method remains protected so it cannot be used (doing so produces a compile-time error). However, if you’re inheriting from a class hierarchy that has already overridden clone( ) as public and implemented Cloneable, the way to prevent cloning is to override clone( ) and throw a CloneNotSupportedException as described in Chapter 12. (You could also override clone( ) and simply return this, but that would be deceiving since the client programmer would think they were cloning the object, but would instead still be dealing with the original.)

Note that you aren’t restricted to creating only one object. This is also a technique to create a limited pool of objects. In that situation, however, you can be confronted with the problem of sharing objects in the pool. If this is an issue, you can create a solution involving a check-out and check-in of the shared objects.

Classifying patterns

The Design Patterns book discusses 23 different patterns, classified under three purposes (all of which revolve around the particular aspect that can vary). The three purposes are:

  1. Creational: how an object can be created. This often involves isolating the details of object creation so your code isn’t dependent on what types of objects there are and thus doesn’t have to be changed when you add a new type of object. The aforementioned Singleton is classified as a creational pattern, and later in this chapter you’ll see examples of Factory Method and Prototype.
  2. Structural: designing objects to satisfy particular project constraints. These work with the way objects are connected with other objects to ensure that changes in the system don’t require changes to those connections.
  3. Behavioral: objects that handle particular types of actions within a program. These encapsulate processes that you want to perform, such as interpreting a language, fulfilling a request, moving through a sequence (as in an iterator), or implementing an algorithm. This chapter contains examples of the Observer and the Visitor patterns.

The Design Patterns book has a section on each of its 23 patterns along with one or more examples for each, typically in C++ but sometimes in Smalltalk. (You’ll find that this doesn’t matter too much since you can easily translate the concepts from either language into Java.) This book will not repeat all the patterns shown in Design Patterns since that book stands on its own and should be studied separately. Instead, this chapter will give some examples that should provide you with a decent feel for what patterns are about and why they are so important.

The observer pattern

The observer pattern solves a fairly common problem: What if a group of objects needs to update themselves when some object changes state? This can be seen in the “model-view” aspect of Smalltalk’s MVC (model-view-controller), or the almost-equivalent “Document-View Architecture.” Suppose that you have some data (the “document”) and more than one view, say a plot and a textual view. When you change the data, the two views must know to update themselves, and that’s what the observer facilitates. It’s a common enough problem that its solution has been made a part of the standard java.util library.

There are two types of objects used to implement the observer pattern in Java. The Observable class keeps track of everybody who wants to be informed when a change happens, whether the “state” has changed or not. When someone says “OK, everybody should check and potentially update themselves,” the Observable class performs this task by calling the notifyObservers( ) method for each one on the list. The notifyObservers( ) method is part of the base class Observable.

There are actually two “things that change” in the observer pattern: the quantity of observing objects and the way an update occurs. That is, the observer pattern allows you to modify both of these without affecting the surrounding code.

The following example is similar to the ColorBoxes example from Chapter 14. Boxes are placed in a grid on the screen and each one is initialized to a random color. In addition, each box implements the Observer interface and is registered with an Observable object. When you click on a box, all of the other boxes are notified that a change has been made because the Observable object automatically calls each Observer object’s update( ) method. Inside this method, the box checks to see if it’s adjacent to the one that was clicked, and if so it changes its color to match the clicked box.

//: BoxObserver.java
// Demonstration of Observer pattern using
// Java's built-in observer classes.
import java.awt.*;
import java.awt.event.*;
import java.util.*;

// You must inherit a new type of Observable:
class BoxObservable extends Observable {
  public void notifyObservers(Object b) {
    // Otherwise it won't propagate changes:
    setChanged();
    super.notifyObservers(b);
  }
}

public class BoxObserver extends Frame {
  Observable notifier = new BoxObservable();
  public BoxObserver(int grid) {
    setTitle("Demonstrates Observer pattern");
    setLayout(new GridLayout(grid, grid));
    for(int x = 0; x < grid; x++)
      for(int y = 0; y < grid; y++)
        add(new OCBox(x, y, notifier));
  }   
  public static void main(String[] args) {
    int grid = 8;
    if(args.length > 0)
      grid = Integer.parseInt(args[0]);
    Frame f = new BoxObserver(grid);
    f.setSize(500, 400);
    f.setVisible(true);
    f.addWindowListener(
      new WindowAdapter() {
        public void windowClosing(WindowEvent e) {
          System.exit(0);
        }
      });
  }
}

class OCBox extends Canvas implements Observer {
  Observable notifier;
  int x, y; // Locations in grid
  Color cColor = newColor();
  static final Color[] colors = { 
    Color.black, Color.blue, Color.cyan, 
    Color.darkGray, Color.gray, Color.green,
    Color.lightGray, Color.magenta, 
    Color.orange, Color.pink, Color.red, 
    Color.white, Color.yellow 
  };
  static final Color newColor() {
    return colors[
      (int)(Math.random() * colors.length)
    ];
  }
  OCBox(int x, int y, Observable notifier) {
    this.x = x;
    this.y = y;
    notifier.addObserver(this);
    this.notifier = notifier;
    addMouseListener(new ML());
  }
  public void paint(Graphics  g) {
    g.setColor(cColor);
    Dimension s = getSize();
    g.fillRect(0, 0, s.width, s.height);
  }
  class ML extends MouseAdapter {
    public void mousePressed(MouseEvent e) {
      notifier.notifyObservers(OCBox.this);
    }
  }
  public void update(Observable o, Object arg) {
    OCBox clicked = (OCBox)arg;
    if(nextTo(clicked)) {
      cColor = clicked.cColor;
      repaint();
    }
  }
  private final boolean nextTo(OCBox b) {
    return Math.abs(x - b.x) <= 1 && 
           Math.abs(y - b.y) <= 1;
  }
} ///:~

When you first look at the online documentation for Observable, it’s a bit confusing because it appears that you can use an ordinary Observable object to manage the updates. But this doesn’t work; try it – inside BoxObserver, create an Observable object instead of a BoxObservable object and see what happens: nothing. To get an effect, you must inherit from Observable and somewhere in your derived-class code call setChanged( ). This is the method that sets the “changed” flag, which means that when you call notifyObservers( ) all of the observers will, in fact, get notified. In the example above setChanged( ) is simply called within notifyObservers( ), but you could use any criterion you want to decide when to call setChanged( ).

BoxObserver contains a single Observable object called notifier, and every time an OCBox object is created, it is tied to notifier. In OCBox, whenever you click the mouse the notifyObservers( ) method is called, passing the clicked object in as an argument so that all the boxes receiving the message (in their update( ) method) know who was clicked and can decide whether to change themselves or not. Using a combination of code in notifyObservers( ) and update( ) you can work out some fairly complex schemes.

It might appear that the way the observers are notified must be frozen at compile time in the notifyObservers( ) method. However, if you look more closely at the code above you’ll see that the only place in BoxObserver or OCBox where you're aware that you’re working with a BoxObservable is at the point of creation of the Observable object – from then on everything uses the basic Observable interface. This means that you could inherit other Observable classes and swap them at run-time if you want to change notification behavior then.

Simulating the trash recycler

The nature of this problem is that the trash is thrown unclassified into a single bin, so the specific type information is lost. But later, the specific type information must be recovered to properly sort the trash. In the initial solution, RTTI (described in Chapter 11) is used.

This is not a trivial design because it has an added constraint. That’s what makes it interesting – it’s more like the messy problems you’re likely to encounter in your work. The extra constraint is that the trash arrives at the trash recycling plant all mixed together. The program must model the sorting of that trash. This is where RTTI comes in: you have a bunch of anonymous pieces of trash, and the program figures out exactly what type they are.

//: RecycleA.java 
// Recycling with RTTI
package c16.recyclea;
import java.util.*;
import java.io.*;

abstract class Trash {
  private double weight;
  Trash(double wt) { weight = wt; }
  abstract double value();
  double weight() { return weight; }
  // Sums the value of Trash in a bin:
  static void sumValue(Vector bin) {
    Enumeration e = bin.elements();
    double val = 0.0f;
    while(e.hasMoreElements()) {
      // One kind of RTTI:
      // A dynamically-checked cast
      Trash t = (Trash)e.nextElement();
      // Polymorphism in action:
      val += t.weight() * t.value();
      System.out.println(
        "weight of " +
        // Using RTTI to get type
        // information about the class:
        t.getClass().getName() +
        " = " + t.weight());
    }
    System.out.println("Total value = " + val);
  }
}

class Aluminum extends Trash {
  static double val  = 1.67f;
  Aluminum(double wt) { super(wt); }
  double value() { return val; }
  static void value(double newval) {
    val = newval;
  }
}

class Paper extends Trash {
  static double val = 0.10f;
  Paper(double wt) { super(wt); }
  double value() { return val; }
  static void value(double newval) {
    val = newval;
  }
}

class Glass extends Trash {
  static double val = 0.23f;
  Glass(double wt) { super(wt); }
  double value() { return val; }
  static void value(double newval) {
    val = newval;
  }
}

public class RecycleA {
  public static void main(String[] args) {
    Vector bin = new Vector();
    // Fill up the Trash bin:
    for(int i = 0; i < 30; i++)
      switch((int)(Math.random() * 3)) {
        case 0 :
          bin.addElement(new
            Aluminum(Math.random() * 100));
          break;
        case 1 :
          bin.addElement(new
            Paper(Math.random() * 100));
          break;
        case 2 :
          bin.addElement(new
            Glass(Math.random() * 100));
      }
    Vector 
      glassBin = new Vector(),
      paperBin = new Vector(),
      alBin = new Vector();
    Enumeration sorter = bin.elements();
    // Sort the Trash:
    while(sorter.hasMoreElements()) {
      Object t = sorter.nextElement();
      // RTTI to show class membership:
      if(t instanceof Aluminum)
        alBin.addElement(t);
      if(t instanceof Paper)
        paperBin.addElement(t);
      if(t instanceof Glass)
        glassBin.addElement(t);
    }
    Trash.sumValue(alBin);
    Trash.sumValue(paperBin);
    Trash.sumValue(glassBin);
    Trash.sumValue(bin);
  }
} ///:~


The first thing you’ll notice is the package statement:

package c16.recyclea;

This means that in the source code listings available for the book, this file will be placed in the subdirectory recyclea that branches off from the subdirectory c16 (for Chapter 16). The unpacking tool in Chapter 17 takes care of placing it into the correct subdirectory. The reason for doing this is that this chapter rewrites this particular example a number of times and by putting each version in its own package the class names will not clash.

Several Vector objects are created to hold Trash handles. Of course, Vectors actually hold Objects so they’ll hold anything at all. The reason they hold Trash (or something derived from Trash) is only because you’ve been careful to not put in anything except Trash. If you do put something “wrong” into the Vector, you won’t get any compile-time warnings or errors – you’ll find out only via an exception at run-time.

When the Trash handles are added, they lose their specific identities and become simply Object handles (they are upcast). However, because of polymorphism the proper behavior still occurs when the dynamically-bound methods are called through the Enumeration sorter, once the resulting Object has been cast back to Trash. sumValue( ) also uses an Enumeration to perform operations on every object in the Vector.

It looks silly to upcast the types of Trash into a collection holding base type handles, and then turn around and downcast. Why not just put the trash into the appropriate receptacle in the first place? (Indeed, this is the whole enigma of recycling). In this program it would be easy to repair, but sometimes a system’s structure and flexibility can benefit greatly from downcasting.

The program satisfies the design requirements: it works. This might be fine as long as it’s a one-shot solution. However, a useful program tends to evolve over time, so you must ask, “What if the situation changes?” For example, cardboard is now a valuable recyclable commodity, so how will that be integrated into the system (especially if the program is large and complicated). Since the above type-check coding in the switch statement could be scattered throughout the program, you must go find all that code every time a new type is added, and if you miss one the compiler won’t give you any help by pointing out an error.

The key to the misuse of RTTI here is that every type is tested. If you’re looking for only a subset of types because that subset needs special treatment, that’s probably fine. But if you’re hunting for every type inside a switch statement, then you’re probably missing an important point, and definitely making your code less maintainable. In the next section we’ll look at how this program evolved over several stages to become much more flexible. This should prove a valuable example in program design.

Improving the design

The solutions in Design Patterns are organized around the question “What will change as this program evolves?” This is usually the most important question that you can ask about any design. If you can build your system around the answer, the results will be two-pronged: not only will your system allow easy (and inexpensive) maintenance, but you might also produce components that are reusable, so that other systems can be built more cheaply. This is the promise of object-oriented programming, but it doesn’t happen automatically; it requires thought and insight on your part. In this section we’ll see how this process can happen during the refinement of a system.

The answer to the question “What will change?” for the recycling system is a common one: more types will be added to the system. The goal of the design, then, is to make this addition of types as painless as possible. In the recycling program, we’d like to encapsulate all places where specific type information is mentioned, so (if for no other reason) any changes can be localized to those encapsulations. It turns out that this process also cleans up the rest of the code considerably.

“Make more objects”

This brings up a general object-oriented design principle that I first heard spoken by Grady Booch: “If the design is too complicated, make more objects.” This is simultaneously counterintuitive and ludicrously simple, and yet it’s the most useful guideline I’ve found. (You might observe that “making more objects” is often equivalent to “add another level of indirection.”) In general, if you find a place with messy code, consider what sort of class would clean that up. Often the side effect of cleaning up the code will be a system that has better structure and is more flexible.

Consider first the place where Trash objects are created, which is a switch statement inside main( ):

    for(int i = 0; i < 30; i++)
      switch((int)(Math.random() * 3)) {
        case 0 :
          bin.addElement(new
            Aluminum(Math.random() * 100));
          break;
        case 1 :
          bin.addElement(new
            Paper(Math.random() * 100));
          break;
        case 2 :
          bin.addElement(new
            Glass(Math.random() * 100));
      }

This is definitely messy, and also a place where you must change code whenever a new type is added. If new types are commonly added, a better solution is a single method that takes all of the necessary information and produces a handle to an object of the correct type, already upcast to a trash object. In Design Patterns this is broadly referred to as a creational pattern (of which there are several). The specific pattern that will be applied here is a variant of the Factory Method. Here, the factory method is a static member of Trash, but more commonly it is a method that is overridden in the derived class.

The idea of the factory method is that you pass it the essential information it needs to know to create your object, then stand back and wait for the handle (already upcast to the base type) to pop out as the return value. From then on, you treat the object polymorphically. Thus, you never even need to know the exact type of object that’s created. In fact, the factory method hides it from you to prevent accidental misuse. If you want to use the object without polymorphism, you must explicitly use RTTI and casting.

But there’s a little problem, especially when you use the more complicated approach (not shown here) of making the factory method in the base class and overriding it in the derived classes. What if the information required in the derived class requires more or different arguments? “Creating more objects” solves this problem. To implement the factory method, the Trash class gets a new method called factory. To hide the creational data, there’s a new class called Info that contains all of the necessary information for the factory method to create the appropriate Trash object. Here’s a simple implementation of Info:

class Info {
  int type;
  // Must change this to add another type:
  static final int MAX_NUM = 4;
  double data;
  Info(int typeNum, double dat) {
    type = typeNum % MAX_NUM;
    data = dat;
  }
}

An Info object’s only job is to hold information for the factory( ) method. Now, if there’s a situation in which factory( ) needs more or different information to create a new type of Trash object, the factory( ) interface doesn’t need to be changed. The Info class can be changed by adding new data and new constructors, or in the more typical object-oriented fashion of subclassing.

The factory( ) method for this simple example looks like this:

  static Trash factory(Info i) {
    switch(i.type) {
      default: // To quiet the compiler
      case 0:
        return new Aluminum(i.data);
      case 1:
        return new Paper(i.data);
      case 2:
        return new Glass(i.data);
      // Two lines here:
      case 3: 
        return new Cardboard(i.data);
    }
  }

Here, the determination of the exact type of object is simple, but you can imagine a more complicated system in which factory( ) uses an elaborate algorithm. The point is that it’s now hidden away in one place, and you know to come to this place when you add new types.

The creation of new objects is now much simpler in main( ):

    for(int i = 0; i < 30; i++)
      bin.addElement(
        Trash.factory(
          new Info(
            (int)(Math.random() * Info.MAX_NUM),
            Math.random() * 100)));

An Info object is created to pass the data into factory( ), which in turn produces some kind of Trash object on the heap and returns the handle that’s added to the Vector bin. Of course, if you change the quantity and type of argument, this statement will still need to be modified, but that can be eliminated if the creation of the Info object is automated. For example, a Vector of arguments can be passed into the constructor of an Info object (or directly into a factory( ) call, for that matter). This requires that the arguments be parsed and checked at runtime, but it does provide the greatest flexibility.

You can see from this code what “vector of change” problem the factory is responsible for solving: if you add new types to the system (the change), the only code that must be modified is within the factory, so the factory isolates the effect of that change.

A pattern for prototyping creation

A problem with the design above is that it still requires a central location where all the types of the objects must be known: inside the factory( ) method. If new types are regularly being added to the system, the factory( ) method must be changed for each new type. When you discover something like this, it is useful to try to go one step further and move all of the information about the type – including its creation – into the class representing that type. This way, the only thing you need to do to add a new type to the system is to inherit a single class.

To move the information concerning type creation into each specific type of Trash, the “prototype” pattern (from the Design Patterns book) will be used. The general idea is that you have a master sequence of objects, one of each type you’re interested in making. The objects in this sequence are used only for making new objects, using an operation that’s not unlike the clone( ) scheme built into Java’s root class Object. In this case, we’ll name the cloning method tClone( ). When you’re ready to make a new object, presumably you have some sort of information that establishes the type of object you want to create, then you move through the master sequence comparing your information with whatever appropriate information is in the prototype objects in the master sequence. When you find one that matches your needs, you clone it.

In this scheme there is no hard-coded information for creation. Each object knows how to expose appropriate information and how to clone itself. Thus, the factory( ) method doesn’t need to be changed when a new type is added to the system.

One approach to the problem of prototyping is to add a number of methods to support the creation of new objects. However, in Java 1.1 there’s already support for creating new objects if you have a handle to the Class object. With Java 1.1 reflection (introduced in Chapter 11) you can call a constructor even if you have only a handle to the Class object. This is the perfect solution for the prototyping problem.

The list of prototypes will be represented indirectly by a list of handles to all the Class objects you want to create. In addition, if the prototyping fails, the factory( ) method will assume that it’s because a particular Class object wasn’t in the list, and it will attempt to load it. By loading the prototypes dynamically like this, the Trash class doesn’t need to know what types it is working with, so it doesn’t need any modifications when you add new types. This allows it to be easily reused throughout the rest of the chapter.

//: Trash.java
// Base class for Trash recycling examples
package c16.trash;
import java.util.*;
import java.lang.reflect.*;

public abstract class Trash {
  private double weight;
  Trash(double wt) { weight = wt; }
  Trash() {}
  public abstract double value();
  public double weight() { return weight; }
  // Sums the value of Trash in a bin:
  public static void sumValue(Vector bin) {
    Enumeration e = bin.elements();
    double val = 0.0f;
    while(e.hasMoreElements()) {
      // One kind of RTTI:
      // A dynamically-checked cast
      Trash t = (Trash)e.nextElement();
      val += t.weight() * t.value();
      System.out.println(
        "weight of " +
        // Using RTTI to get type
        // information about the class:
        t.getClass().getName() +
        " = " + t.weight());
    }
    System.out.println("Total value = " + val);
  }
  // Remainder of class provides support for
  // prototyping:
  public static class PrototypeNotFoundException
      extends Exception {}
  public static class CannotCreateTrashException
      extends Exception {}
  private static Vector trashTypes = 
    new Vector();
  public static Trash factory(Info info) 
      throws PrototypeNotFoundException, 
      CannotCreateTrashException {
    for(int i = 0; i < trashTypes.size(); i++) {
      // Somehow determine the new type
      // to create, and create one:
      Class tc = 
        (Class)trashTypes.elementAt(i);
      if (tc.getName().indexOf(info.id) != -1) {
        try {
          // Get the dynamic constructor method
          // that takes a double argument:
          Constructor ctor =
            tc.getConstructor(
              new Class[] {double.class});
          // Call the constructor to create a 
          // new object:
          return (Trash)ctor.newInstance(
            new Object[]{new Double(info.data)});
        } catch(Exception ex) {
          ex.printStackTrace();
          throw new CannotCreateTrashException();
        }
      }
    }
    // Class was not in the list. Try to load it,
    // but it must be in your class path!
    try {
      System.out.println("Loading " + info.id);
      trashTypes.addElement(
        Class.forName(info.id));
    } catch(Exception e) {
      e.printStackTrace();
      throw new PrototypeNotFoundException();
    }
    // Loaded successfully. Recursive call 
    // should work this time:
    return factory(info);
  }
  public static class Info {
    public String id;
    public double data;
    public Info(String name, double data) {
      id = name;
      this.data = data;
    }
  }
} ///:~

The basic Trash class and sumValue( ) remain as before. The rest of the class supports the prototyping pattern. You first see two inner classes (which are made static, so they are inner classes only for code organization purposes) describing exceptions that can occur. This is followed by a Vector trashTypes, which is used to hold the Class handles.

In Trash.factory( ), the String inside the Info object id (a different version of the Info class than that of the prior discussion) contains the type name of the Trash to be created; this String is compared to the Class names in the list. If there’s a match, then that’s the object to create. Of course, there are many ways to determine what object you want to make. This one is used so that information read in from a file can be turned into objects.

Once you’ve discovered which kind of Trash to create, then the reflection methods come into play. The getConstructor( ) method takes an argument that’s an array of Class handles. This array represents the arguments, in their proper order, for the constructor that you’re looking for. Here, the array is dynamically created using the Java 1.1 array-creation syntax:

new Class[] {double.class}

This code assumes that every Trash type has a constructor that takes a double (and notice that double.class is distinct from Double.class). It’s also possible, for a more flexible solution, to call getConstructors( ), which returns an array of the possible constructors.

What comes back from getConstructor( ) is a handle to a Constructor object (part of java.lang.reflect). You call the constructor dynamically with the method newInstance( ), which takes an array of Object containing the actual arguments. This array is again created using the Java 1.1 syntax:

new Object[]{new Double(info.data)}

In this case, however, the double must be placed inside a wrapper class so that it can be part of this array of objects. The process of calling newInstance( ) extracts the double, but you can see it is a bit confusing – an argument might be a double or a Double, but when you make the call you must always pass in a Double. Fortunately, this issue exists only for the primitive types.

Once you understand how to do it, the process of creating a new object given only a Class handle is remarkably simple. Reflection also allows you to call methods in this same dynamic fashion.

Of course, the appropriate Class handle might not be in the trashTypes list. In this case, the return in the inner loop is never executed and you’ll drop out at the end. Here, the program tries to rectify the situation by loading the Class object dynamically and adding it to the trashTypes list. If it still can’t be found something is really wrong, but if the load is successful then the factory method is called recursively to try again.

As you’ll see, the beauty of this design is that this code doesn’t need to be changed, regardless of the different situations it will be used in (assuming that all Trash subclasses contain a constructor that takes a single double argument).

Trash subclasses

To fit into the prototyping scheme, the only thing that’s required of each new subclass of Trash is that it contain a constructor that takes a double argument. Java 1.1 reflection handles everything else.

Here are the different types of Trash, each in their own file but part of the Trash package (again, to facilitate reuse within the chapter):

//: Aluminum.java 
// The Aluminum class with prototyping
package c16.trash;

public class Aluminum extends Trash {
  private static double val = 1.67f;
  public Aluminum(double wt) { super(wt); }
  public double value() { return val; }
  public static void value(double newVal) {
    val = newVal;
  }
} ///:~
//: Paper.java 
// The Paper class with prototyping
package c16.trash;

public class Paper extends Trash {
  private static double val = 0.10f;
  public Paper(double wt) { super(wt); }
  public double value() { return val; }
  public static void value(double newVal) {
    val = newVal;
  }
} ///:~
//: Glass.java 
// The Glass class with prototyping
package c16.trash;

public class Glass extends Trash {
  private static double val = 0.23f;
  public Glass(double wt) { super(wt); }
  public double value() { return val; }
  public static void value(double newVal) {
    val = newVal;
  }
} ///:~

And here’s a new type of Trash:

//: Cardboard.java 
// The Cardboard class with prototyping
package c16.trash;

public class Cardboard extends Trash {
  private static double val = 0.23f;
  public Cardboard(double wt) { super(wt); }
  public double value() { return val; }
  public static void value(double newVal) {
    val = newVal;
  }
} ///:~

You can see that, other than the constructor, there’s nothing special about any of these classes.

Parsing Trash from an external file

The information about Trash objects will be read from an outside file. The file has all of the necessary information about each piece of trash on a single line in the form Trash:weight, such as:

c16.Trash.Glass:54
c16.Trash.Paper:22
c16.Trash.Paper:11
c16.Trash.Glass:17
c16.Trash.Aluminum:89
c16.Trash.Paper:88
c16.Trash.Aluminum:76
c16.Trash.Cardboard:96
c16.Trash.Aluminum:25
c16.Trash.Aluminum:34
c16.Trash.Glass:11
c16.Trash.Glass:68
c16.Trash.Glass:43
c16.Trash.Aluminum:27
c16.Trash.Cardboard:44
c16.Trash.Aluminum:18
c16.Trash.Paper:91
c16.Trash.Glass:63
c16.Trash.Glass:50
c16.Trash.Glass:80
c16.Trash.Aluminum:81
c16.Trash.Cardboard:12
c16.Trash.Glass:12
c16.Trash.Glass:54
c16.Trash.Aluminum:36
c16.Trash.Aluminum:93
c16.Trash.Glass:93
c16.Trash.Paper:80
c16.Trash.Glass:36
c16.Trash.Glass:12
c16.Trash.Glass:60
c16.Trash.Paper:66
c16.Trash.Aluminum:36
c16.Trash.Cardboard:22

Note that the class path must be included when giving the class names, otherwise the class will not be found.

To parse this, the line is read and the String method indexOf( ) produces the index of the ‘:’. This is first used with the String method substring( ) to extract the name of the trash type, and next to get the weight that is turned into a double with the static Double.valueOf( ) method. The trim( ) method removes white space at both ends of a string.

The Trash parser is placed in a separate file since it will be reused throughout this chapter:

//: ParseTrash.java 
// Open a file and parse its contents into
// Trash objects, placing each into a Vector
package c16.trash;
import java.util.*;
import java.io.*;

public class ParseTrash {
  public static void 
  fillBin(String filename, Fillable bin) {
    try {
      BufferedReader data =
        new BufferedReader(
          new FileReader(filename));
      String buf;
      while((buf = data.readLine())!= null) {
        String type = buf.substring(0, 
          buf.indexOf(':')).trim();
        double weight = Double.valueOf(
          buf.substring(buf.indexOf(':') + 1)
          .trim()).doubleValue();
        bin.addTrash(
          Trash.factory(
            new Trash.Info(type, weight)));
      }
      data.close();
    } catch(IOException e) {
      e.printStackTrace();
    } catch(Exception e) {
      e.printStackTrace();
    }
  }
  // Special case to handle Vector:
  public static void 
  fillBin(String filename, Vector bin) {
    fillBin(filename, new FillableVector(bin));
  }
} ///:~

In RecycleA.java, a Vector was used to hold the Trash objects. However, other types of collections can be used as well. To allow for this, the first version of fillBin( ) takes a handle to a Fillable, which is simply an interface that supports a method called addTrash( ):

//: Fillable.java 
// Any object that can be filled with Trash
package c16.trash;

public interface Fillable {
  void addTrash(Trash t);
} ///:~

Anything that supports this interface can be used with fillBin. Of course, Vector doesn’t implement Fillable, so it won’t work. Since Vector is used in most of the examples, it makes sense to add a second overloaded fillBin( ) method that takes a Vector. The Vector can be used as a Fillable object using an adapter class:

//: FillableVector.java 
// Adapter that makes a Vector Fillable
package c16.trash;
import java.util.*;

public class FillableVector implements Fillable {
  private Vector v;
  public FillableVector(Vector vv) { v = vv; }
  public void addTrash(Trash t) {
    v.addElement(t);
  }
} ///:~

You can see that the only job of this class is to connect Fillable’s addTrash( ) method to Vector’s addElement( ). With this class in hand, the overloaded fillBin( ) method can be used with a Vector in ParseTrash.java:

  public static void 
  fillBin(String filename, Vector bin) {
    fillBin(filename, new FillableVector(bin));
  }

This approach works for any collection class that’s used frequently. Alternatively, the collection class can provide its own adapter that implements Fillable. (You’ll see this later, in DynaTrash.java.)

Recycling with prototyping

Now you can see the revised version of RecycleA.java using the prototyping technique:

//: RecycleAP.java 
// Recycling with RTTI and Prototypes
package c16.recycleap;
import c16.trash.*;
import java.util.*;

public class RecycleAP {
  public static void main(String[] args) {
    Vector bin = new Vector();
    // Fill up the Trash bin:
    ParseTrash.fillBin("Trash.dat", bin);
    Vector 
      glassBin = new Vector(),
      paperBin = new Vector(),
      alBin = new Vector();
    Enumeration sorter = bin.elements();
    // Sort the Trash:
    while(sorter.hasMoreElements()) {
      Object t = sorter.nextElement();
      // RTTI to show class membership:
      if(t instanceof Aluminum)
        alBin.addElement(t);
      if(t instanceof Paper)
        paperBin.addElement(t);
      if(t instanceof Glass)
        glassBin.addElement(t);
    }
    Trash.sumValue(alBin);
    Trash.sumValue(paperBin);
    Trash.sumValue(glassBin);
    Trash.sumValue(bin);
  }
} ///:~

All of the Trash objects, as well as the ParseTrash and support classes, are now part of the package c16.trash so they are simply imported.

The process of opening the data file containing Trash descriptions and the parsing of that file have been wrapped into the static method ParseTrash.fillBin( ), so now it’s no longer a part of our design focus. You will see that throughout the rest of the chapter, no matter what new classes are added, ParseTrash.fillBin( ) will continue to work without change, which indicates a good design.

In terms of object creation, this design does indeed severely localize the changes you need to make to add a new type to the system. However, there’s a significant problem in the use of RTTI that shows up clearly here. The program seems to run fine, and yet it never detects any cardboard, even though there is cardboard in the list! This happens because of the use of RTTI, which looks for only the types that you tell it to look for. The clue that RTTI is being misused is that every type in the system is being tested, rather than a single type or subset of types. As you will see later, there are ways to use polymorphism instead when you’re testing for every type. But if you use RTTI a lot in this fashion, and you add a new type to your system, you can easily forget to make the necessary changes in your program and produce a difficult-to-find bug. So it’s worth trying to eliminate RTTI in this case, not just for aesthetic reasons – it produces more maintainable code.

Abstracting usage

With creation out of the way, it’s time to tackle the remainder of the design: where the classes are used. Since it’s the act of sorting into bins that’s particularly ugly and exposed, why not take that process and hide it inside a class? This is the principle of “If you must do something ugly, at least localize the ugliness inside a class.” It looks like this:


(This diagram is using the more modern ArrayList, but it also describes the Vector implementation.) The TrashSorter object initialization must now be changed whenever a new type of Trash is added to the model. You could imagine that the TrashSorter class might look something like this:

class TrashSorter extends Vector {
  void sort(Trash t) { /* ... */ }
}

That is, TrashSorter is a Vector of handles to Vectors of Trash handles, and with addElement( ) you can install another one, like so:

TrashSorter ts = new TrashSorter();
ts.addElement(new Vector());

Now, however, sort( ) becomes a problem. How does the statically-coded method deal with the fact that a new type has been added? To solve this, the type information must be removed from sort( ) so that all it needs to do is call a generic method that takes care of the details of type. This, of course, is another way to describe a dynamically-bound method. So sort( ) will simply move through the sequence and call a dynamically-bound method for each Vector. Since the job of this method is to grab the pieces of trash it is interested in, it’s called grab(Trash). The structure now looks like:


(This diagram is using the more modern ArrayList, but it also describes the Vector implementation.) TrashSorter needs to call each grab( ) method and get a different result depending on what type of Trash the current Vector is holding. That is, each Vector must be aware of the type it holds. The classic approach to this problem is to create a base “Trash bin” class and inherit a new derived class for each different type you want to hold. If Java had a parameterized type mechanism that would probably be the most straightforward approach. But rather than hand-coding all the classes that such a mechanism should be building for us, further observation can produce a better approach.

A basic OOP design principle is “Use data members for variation in state, use polymorphism for variation in behavior.” Your first thought might be that the grab( ) method certainly behaves differently for a Vector that holds Paper than for one that holds Glass. But what it does is strictly dependent on the type, and nothing else. This could be interpreted as a different state, and since Java has a class to represent type (Class) this can be used to determine the type of Trash a particular Tbin will hold.

The constructor for this Tbin requires that you hand it the Class of your choice. This tells the Vector what type it is supposed to hold. Then the grab( ) method uses Class BinType and RTTI to see if the Trash object you’ve handed it matches the type it’s supposed to grab.

Here is the whole program. The commented numbers (e.g. (*1*) ) mark sections that will be described following the code.

//: RecycleB.java
// Adding more objects to the recycling problem
package c16.recycleb;
import c16.trash.*;
import java.util.*;

// A vector that admits only the right type:
class Tbin extends Vector {
  Class binType;
  Tbin(Class binType) { 
    this.binType = binType; 
  }
  boolean grab(Trash t) {
    // Comparing class types:
    if(t.getClass().equals(binType)) {
      addElement(t);
      return true; // Object grabbed
    }
    return false; // Object not grabbed
  }
}

class TbinList extends Vector { //(*1*)
  boolean sort(Trash t) {
    Enumeration e = elements();
    while(e.hasMoreElements()) {
      Tbin bin = (Tbin)e.nextElement();
      if(bin.grab(t)) return true;
    }
    return false; // bin not found for t
  }
  void sortBin(Tbin bin) { // (*2*)
    Enumeration e = bin.elements();
    while(e.hasMoreElements())
      if(!sort((Trash)e.nextElement()))
        System.out.println("Bin not found");
  }
}

public class RecycleB {
  static Tbin bin = new Tbin(Trash.class);
  public static void main(String[] args) {
    // Fill up the Trash bin:
    ParseTrash.fillBin("Trash.dat", bin);

    TbinList trashBins = new TbinList();
    trashBins.addElement(
      new Tbin(Aluminum.class));
    trashBins.addElement(
      new Tbin(Paper.class));
    trashBins.addElement(
      new Tbin(Glass.class));
    // add one line here: (*3*)
    trashBins.addElement(
      new Tbin(Cardboard.class));

    trashBins.sortBin(bin); // (*4*)

    Enumeration e = trashBins.elements();
    while(e.hasMoreElements()) {
      Tbin b = (Tbin)e.nextElement();
      Trash.sumValue(b);
    }
    Trash.sumValue(bin);
  }
} ///:~
  1. TbinList holds a set of Tbin handles, so that sort( ) can iterate through the Tbins when it’s looking for a match for the Trash object you’ve handed it.
  2. sortBin( ) allows you to pass an entire Tbin in, and it moves through the Tbin, picks out each piece of Trash, and sorts it into the appropriate specific Tbin. Notice the genericity of this code: it doesn’t change at all if new types are added. If the bulk of your code doesn’t need changing when a new type is added (or some other change occurs) then you have an easily-extensible system.
  3. Now you can see how easy it is to add a new type. Few lines must be changed to support the addition. If it’s really important, you can squeeze out even more by further manipulating the design.
  4. One method call causes the contents of bin to be sorted into the respective specifically-typed bins.

Multiple dispatching

The above design is certainly satisfactory. Adding new types to the system consists of adding or modifying distinct classes without causing code changes to be propagated throughout the system. In addition, RTTI is not “misused” as it was in RecycleA.java. However, it’s possible to go one step further and take a purist viewpoint about RTTI and say that it should be eliminated altogether from the operation of sorting the trash into bins.

To accomplish this, you must first take the perspective that all type-dependent activities – such as detecting the type of a piece of trash and putting it into the appropriate bin – should be controlled through polymorphism and dynamic binding.

The previous examples first sorted by type, then acted on sequences of elements that were all of a particular type. But whenever you find yourself picking out particular types, stop and think. The whole idea of polymorphism (dynamically-bound method calls) is to handle type-specific information for you. So why are you hunting for types?

The answer is something you probably don’t think about: Java performs only single dispatching. That is, if you are performing an operation on more than one object whose type is unknown, Java will invoke the dynamic binding mechanism on only one of those types. This doesn’t solve the problem, so you end up detecting some types manually and effectively producing your own dynamic binding behavior.

The solution is called multiple dispatching, which means setting up a configuration such that a single method call produces more than one dynamic method call and thus determines more than one type in the process. To get this effect, you need to work with more than one type hierarchy: you’ll need a type hierarchy for each dispatch. The following example works with two hierarchies: the existing Trash family and a hierarchy of the types of trash bins that the trash will be placed into. This second hierarchy isn’t always obvious and in this case it needed to be created in order to produce multiple dispatching (in this case there will be only two dispatches, which is referred to as double dispatching).

Implementing the double dispatch

Remember that polymorphism can occur only via method calls, so if you want double dispatching to occur, there must be two method calls: one used to determine the type within each hierarchy. In the Trash hierarchy there will be a new method called addToBin( ), which takes an argument of an array of TypedBin. It uses this array to step through and try to add itself to the appropriate bin, and this is where you’ll see the double dispatch.


The new hierarchy is TypedBin, and it contains its own method called add( ) that is also used polymorphically. But here’s an additional twist: add( ) is overloaded to take arguments of the different types of trash. So an essential part of the double dispatching scheme also involves overloading.

Redesigning the program produces a dilemma: it’s now necessary for the base class Trash to contain an addToBin( ) method. One approach is to copy all of the code and change the base class. Another approach, which you can take when you don’t have control of the source code, is to put the addToBin( ) method into an interface, leave Trash alone, and inherit new specific types of Aluminum, Paper, Glass, and Cardboard. This is the approach that will be taken here.

Most of the classes in this design must be public, so they are placed in their own files. Here’s the interface:

//: TypedBinMember.java
// An interface for adding the double dispatching
// method to the trash hierarchy without 
// modifying the original hierarchy.
package c16.doubledispatch;

interface TypedBinMember {
  // The new method:
  boolean addToBin(TypedBin[] tb);
} ///:~

In each particular subtype of Aluminum, Paper, Glass, and Cardboard, the addToBin( ) method in the interface TypedBinMember is implemented,, but it looks like the code is exactly the same in each case:

//: DDAluminum.java
// Aluminum for double dispatching
package c16.doubledispatch;
import c16.trash.*;

public class DDAluminum extends Aluminum 
    implements TypedBinMember {
  public DDAluminum(double wt) { super(wt); }
  public boolean addToBin(TypedBin[] tb) {
    for(int i = 0; i < tb.length; i++)
      if(tb[i].add(this))
        return true;
    return false;
  }
} ///:~
//: DDPaper.java
// Paper for double dispatching
package c16.doubledispatch;
import c16.trash.*;

public class DDPaper extends Paper 
    implements TypedBinMember {
  public DDPaper(double wt) { super(wt); }
  public boolean addToBin(TypedBin[] tb) {
    for(int i = 0; i < tb.length; i++)
      if(tb[i].add(this))
        return true;
    return false;
  }
} ///:~
//: DDGlass.java
// Glass for double dispatching
package c16.doubledispatch;
import c16.trash.*;

public class DDGlass extends Glass 
    implements TypedBinMember {
  public DDGlass(double wt) { super(wt); }
  public boolean addToBin(TypedBin[] tb) {
    for(int i = 0; i < tb.length; i++)
      if(tb[i].add(this))
        return true;
    return false;
  }
} ///:~
//: DDCardboard.java
// Cardboard for double dispatching
package c16.doubledispatch;
import c16.trash.*;

public class DDCardboard extends Cardboard 
    implements TypedBinMember {
  public DDCardboard(double wt) { super(wt); }
  public boolean addToBin(TypedBin[] tb) {
    for(int i = 0; i < tb.length; i++)
      if(tb[i].add(this))
        return true;
    return false;
  }
} ///:~

The code in each addToBin( ) calls add( ) for each TypedBin object in the array. But notice the argument: this. The type of this is different for each subclass of Trash, so the code is different. (Although this code will benefit if a parameterized type mechanism is ever added to Java.) So this is the first part of the double dispatch, because once you’re inside this method you know you’re Aluminum, or Paper, etc. During the call to add( ), this information is passed via the type of this. The compiler resolves the call to the proper overloaded version of add( ). But since tb[i] produces a handle to the base type TypedBin, this call will end up calling a different method depending on the type of TypedBin that’s currently selected. That is the second dispatch.

Here’s the base class for TypedBin:

//: TypedBin.java
// Vector that knows how to grab the right type
package c16.doubledispatch;
import c16.trash.*;
import java.util.*;

public abstract class TypedBin {
  Vector v = new Vector();
  protected boolean addIt(Trash t) {
    v.addElement(t);
    return true;
  }
  public Enumeration elements() {
    return v.elements();
  }
  public boolean add(DDAluminum a) {
    return false;
  }
  public boolean add(DDPaper a) {
    return false;
  }
  public boolean add(DDGlass a) {
    return false;
  }
  public boolean add(DDCardboard a) {
    return false;
  }
} ///:~

You can see that the overloaded add( ) methods all return false. If the method is not overloaded in a derived class, it will continue to return false, and the caller (addToBin( ), in this case) will assume that the current Trash object has not been added successfully to a collection, and continue searching for the right collection.

In each of the subclasses of TypedBin, only one overloaded method is overridden, according to the type of bin that’s being created. For example, CardboardBin overrides add(DDCardboard). The overridden method adds the trash object to its collection and returns true, while all the rest of the add( ) methods in CardboardBin continue to return false, since they haven’t been overridden. This is another case in which a parameterized type mechanism in Java would allow automatic generation of code. (With C++ templates, you wouldn’t have to explicitly write the subclasses or place the addToBin( ) method in Trash.)

Since for this example the trash types have been customized and placed in a different directory, you’ll need a different trash data file to make it work. Here’s a possible DDTrash.dat:

c16.DoubleDispatch.DDGlass:54
c16.DoubleDispatch.DDPaper:22
c16.DoubleDispatch.DDPaper:11
c16.DoubleDispatch.DDGlass:17
c16.DoubleDispatch.DDAluminum:89
c16.DoubleDispatch.DDPaper:88
c16.DoubleDispatch.DDAluminum:76
c16.DoubleDispatch.DDCardboard:96
c16.DoubleDispatch.DDAluminum:25
c16.DoubleDispatch.DDAluminum:34
c16.DoubleDispatch.DDGlass:11
c16.DoubleDispatch.DDGlass:68
c16.DoubleDispatch.DDGlass:43
c16.DoubleDispatch.DDAluminum:27
c16.DoubleDispatch.DDCardboard:44
c16.DoubleDispatch.DDAluminum:18
c16.DoubleDispatch.DDPaper:91
c16.DoubleDispatch.DDGlass:63
c16.DoubleDispatch.DDGlass:50
c16.DoubleDispatch.DDGlass:80
c16.DoubleDispatch.DDAluminum:81
c16.DoubleDispatch.DDCardboard:12
c16.DoubleDispatch.DDGlass:12
c16.DoubleDispatch.DDGlass:54
c16.DoubleDispatch.DDAluminum:36
c16.DoubleDispatch.DDAluminum:93
c16.DoubleDispatch.DDGlass:93
c16.DoubleDispatch.DDPaper:80
c16.DoubleDispatch.DDGlass:36
c16.DoubleDispatch.DDGlass:12
c16.DoubleDispatch.DDGlass:60
c16.DoubleDispatch.DDPaper:66
c16.DoubleDispatch.DDAluminum:36
c16.DoubleDispatch.DDCardboard:22

Here’s the rest of the program:

//: DoubleDispatch.java
// Using multiple dispatching to handle more
// than one unknown type during a method call.
package c16.doubledispatch;
import c16.trash.*;
import java.util.*;

class AluminumBin extends TypedBin {
  public boolean add(DDAluminum a) {
    return addIt(a);
  }
}

class PaperBin extends TypedBin {
  public boolean add(DDPaper a) {
    return addIt(a);
  }
}

class GlassBin extends TypedBin {
  public boolean add(DDGlass a) {
    return addIt(a);
  }
}

class CardboardBin extends TypedBin {
  public boolean add(DDCardboard a) {
    return addIt(a);
  }
}

class TrashBinSet {
  private TypedBin[] binSet = {
    new AluminumBin(),
    new PaperBin(),
    new GlassBin(),
    new CardboardBin()
  };
  public void sortIntoBins(Vector bin) {
    Enumeration e = bin.elements();
    while(e.hasMoreElements()) {
      TypedBinMember t = 
        (TypedBinMember)e.nextElement();
      if(!t.addToBin(binSet))
        System.err.println("Couldn't add " + t);
    }
  }
  public TypedBin[] binSet() { return binSet; }
}

public class DoubleDispatch {
  public static void main(String[] args) {
    Vector bin = new Vector();
    TrashBinSet bins = new TrashBinSet();
    // ParseTrash still works, without changes:
    ParseTrash.fillBin("DDTrash.dat", bin);
    // Sort from the master bin into the 
    // individually-typed bins:
    bins.sortIntoBins(bin);
    TypedBin[] tb = bins.binSet();
    // Perform sumValue for each bin...
    for(int i = 0; i < tb.length; i++)
      Trash.sumValue(tb[i].v);
    // ... and for the master bin
    Trash.sumValue(bin);
  }
} ///:~

TrashBinSet encapsulates all of the different types of TypedBins, along with the sortIntoBins( ) method, which is where all the double dispatching takes place. You can see that once the structure is set up, sorting into the various TypedBins is remarkably easy. In addition, the efficiency of two dynamic method calls is probably better than any other way you could sort.

Notice the ease of use of this system in main( ), as well as the complete independence of any specific type information within main( ). All other methods that talk only to the Trash base-class interface will be equally invulnerable to changes in Trash types.

The changes necessary to add a new type are relatively isolated: you inherit the new type of Trash with its addToBin( ) method, then you inherit a new TypedBin (this is really just a copy and simple edit), and finally you add a new type into the aggregate initialization for TrashBinSet.

The “visitor” pattern

Now consider applying a design pattern with an entirely different goal to the trash-sorting problem.

For this pattern, we are no longer concerned with optimizing the addition of new types of Trash to the system. Indeed, this pattern makes adding a new type of Trash more complicated. The assumption is that you have a primary class hierarchy that is fixed; perhaps it’s from another vendor and you can’t make changes to that hierarchy. However, you’d like to add new polymorphic methods to that hierarchy, which means that normally you’d have to add something to the base class interface. So the dilemma is that you need to add methods to the base class, but you can’t touch the base class. How do you get around this?

The design pattern that solves this kind of problem is called a “visitor” (the final one in the Design Patterns book), and it builds on the double dispatching scheme shown in the last section.

The visitor pattern allows you to extend the interface of the primary type by creating a separate class hierarchy of type Visitor to virtualize the operations performed upon the primary type. The objects of the primary type simply “accept” the visitor, then call the visitor’s dynamically-bound method. It looks like this:


Now, if v is a Visitable handle to an Aluminum object, the code:

PriceVisitor pv = new PriceVisitor();
v.accept(pv);

causes two polymorphic method calls: the first one to select Aluminum’s version of accept( ), and the second one within accept( ) when the specific version of visit( ) is called dynamically using the base-class Visitor handle v.

This configuration means that new functionality can be added to the system in the form of new subclasses of Visitor. The Trash hierarchy doesn’t need to be touched. This is the prime benefit of the visitor pattern: you can add new polymorphic functionality to a class hierarchy without touching that hierarchy (once the accept( ) methods have been installed). Note that the benefit is helpful here but not exactly what we started out to accomplish, so at first blush you might decide that this isn’t the desired solution.

But look at one thing that’s been accomplished: the visitor solution avoids sorting from the master Trash sequence into individual typed sequences. Thus, you can leave everything in the single master sequence and simply pass through that sequence using the appropriate visitor to accomplish the goal. Although this behavior seems to be a side effect of visitor, it does give us what we want (avoiding RTTI).

The double dispatching in the visitor pattern takes care of determining both the type of Trash and the type of Visitor. In the following example, there are two implementations of Visitor: PriceVisitor to both determine and sum the price, and WeightVisitor to keep track of the weights.

You can see all of this implemented in the new, improved version of the recycling program. As with DoubleDispatch.java, the Trash class is left alone and a new interface is created to add the accept( ) method:

//: Visitable.java
// An interface to add visitor functionality to 
// the Trash hierarchy without modifying the 
// base class.
package c16.trashvisitor;
import c16.trash.*;

interface Visitable {
  // The new method:
  void accept(Visitor v);
} ///:~

The subtypes of Aluminum, Paper, Glass, and Cardboard implement the accept( ) method:

//: VAluminum.java
// Aluminum for the visitor pattern
package c16.trashvisitor;
import c16.trash.*;

public class VAluminum extends Aluminum 
    implements Visitable {
  public VAluminum(double wt) { super(wt); }
  public void accept(Visitor v) {
    v.visit(this);
  }
} ///:~
//: VPaper.java
// Paper for the visitor pattern
package c16.trashvisitor;
import c16.trash.*;

public class VPaper extends Paper 
    implements Visitable {
  public VPaper(double wt) { super(wt); }
  public void accept(Visitor v) {
    v.visit(this);
  }
} ///:~
//: VGlass.java
// Glass for the visitor pattern
package c16.trashvisitor;
import c16.trash.*;

public class VGlass extends Glass 
    implements Visitable {
  public VGlass(double wt) { super(wt); }
  public void accept(Visitor v) {
    v.visit(this);
  }
} ///:~
//: VCardboard.java
// Cardboard for the visitor pattern
package c16.trashvisitor;
import c16.trash.*;

public class VCardboard extends Cardboard 
    implements Visitable {
  public VCardboard(double wt) { super(wt); }
  public void accept(Visitor v) {
    v.visit(this);
  }
} ///:~

Since there’s nothing concrete in the Visitor base class, it can be created as an interface:

//: Visitor.java
// The base interface for visitors
package c16.trashvisitor;
import c16.trash.*;

interface Visitor {
  void visit(VAluminum a);
  void visit(VPaper p);
  void visit(VGlass g);
  void visit(VCardboard c);
} ///:~

Once again custom Trash types have been created in a different subdirectory. The new Trash data file is VTrash.dat and looks like this:

c16.TrashVisitor.VGlass:54
c16.TrashVisitor.VPaper:22
c16.TrashVisitor.VPaper:11
c16.TrashVisitor.VGlass:17
c16.TrashVisitor.VAluminum:89
c16.TrashVisitor.VPaper:88
c16.TrashVisitor.VAluminum:76
c16.TrashVisitor.VCardboard:96
c16.TrashVisitor.VAluminum:25
c16.TrashVisitor.VAluminum:34
c16.TrashVisitor.VGlass:11
c16.TrashVisitor.VGlass:68
c16.TrashVisitor.VGlass:43
c16.TrashVisitor.VAluminum:27
c16.TrashVisitor.VCardboard:44
c16.TrashVisitor.VAluminum:18
c16.TrashVisitor.VPaper:91
c16.TrashVisitor.VGlass:63
c16.TrashVisitor.VGlass:50
c16.TrashVisitor.VGlass:80
c16.TrashVisitor.VAluminum:81
c16.TrashVisitor.VCardboard:12
c16.TrashVisitor.VGlass:12
c16.TrashVisitor.VGlass:54
c16.TrashVisitor.VAluminum:36
c16.TrashVisitor.VAluminum:93
c16.TrashVisitor.VGlass:93
c16.TrashVisitor.VPaper:80
c16.TrashVisitor.VGlass:36
c16.TrashVisitor.VGlass:12
c16.TrashVisitor.VGlass:60
c16.TrashVisitor.VPaper:66
c16.TrashVisitor.VAluminum:36
c16.TrashVisitor.VCardboard:22

The rest of the program creates specific Visitor types and sends them through a single list of Trash objects:

//: TrashVisitor.java 
// The "visitor" pattern
package c16.trashvisitor;
import c16.trash.*;
import java.util.*;

// Specific group of algorithms packaged
// in each implementation of Visitor:
class PriceVisitor implements Visitor {
  private double alSum; // Aluminum
  private double pSum; // Paper
  private double gSum; // Glass
  private double cSum; // Cardboard
  public void visit(VAluminum al) {
    double v = al.weight() * al.value();
    System.out.println(
      "value of Aluminum= " + v);
    alSum += v;
  }
  public void visit(VPaper p) {
    double v = p.weight() * p.value();
    System.out.println(
      "value of Paper= " + v);
    pSum += v;
  }
  public void visit(VGlass g) {
    double v = g.weight() * g.value();
    System.out.println(
      "value of Glass= " + v);
    gSum += v;
  }
  public void visit(VCardboard c) {
    double v = c.weight() * c.value();
    System.out.println(
      "value of Cardboard = " + v);
    cSum += v;
  }
  void total() {
    System.out.println(
      "Total Aluminum: $" + alSum + "\n" +
      "Total Paper: $" + pSum + "\n" +
      "Total Glass: $" + gSum + "\n" +
      "Total Cardboard: $" + cSum);
  }
}

class WeightVisitor implements Visitor {
  private double alSum; // Aluminum
  private double pSum; // Paper
  private double gSum; // Glass
  private double cSum; // Cardboard
  public void visit(VAluminum al) {
    alSum += al.weight();
    System.out.println("weight of Aluminum = "
        + al.weight());
  }
  public void visit(VPaper p) {
    pSum += p.weight();
    System.out.println("weight of Paper = "
        + p.weight());
  }
  public void visit(VGlass g) {
    gSum += g.weight();
    System.out.println("weight of Glass = "
        + g.weight());
  }
  public void visit(VCardboard c) {
    cSum += c.weight();
    System.out.println("weight of Cardboard = "
        + c.weight());
  }
  void total() {
    System.out.println("Total weight Aluminum:"
        + alSum);
    System.out.println("Total weight Paper:"
        + pSum);
    System.out.println("Total weight Glass:"
        + gSum);
    System.out.println("Total weight Cardboard:"
        + cSum);
  }
}

public class TrashVisitor {
  public static void main(String[] args) {
    Vector bin = new Vector();
    // ParseTrash still works, without changes:
    ParseTrash.fillBin("VTrash.dat", bin);
    // You could even iterate through
    // a list of visitors!
    PriceVisitor pv = new PriceVisitor();
    WeightVisitor wv = new WeightVisitor();
    Enumeration it = bin.elements();
    while(it.hasMoreElements()) {
      Visitable v = (Visitable)it.nextElement();
      v.accept(pv);
      v.accept(wv);
    }
    pv.total();
    wv.total();
  }
} ///:~

Note that the shape of main( ) has changed again. Now there’s only a single Trash bin. The two Visitor objects are accepted into every element in the sequence, and they perform their operations. The visitors keep their own internal data to tally the total weights and prices.

Finally, there’s no run-time type identification other than the inevitable cast to Trash when pulling things out of the sequence. This, too, could be eliminated with the implementation of parameterized types in Java.

One way you can distinguish this solution from the double dispatching solution described previously is to note that, in the double dispatching solution, only one of the overloaded methods, add( ), was overridden when each subclass was created, while here each one of the overloaded visit( ) methods is overridden in every subclass of Visitor.

More coupling?

There’s a lot more code here, and there’s definite coupling between the Trash hierarchy and the Visitor hierarchy. However, there’s also high cohesion within the respective sets of classes: they each do only one thing (Trash describes Trash, while Visitor describes actions performed on Trash), which is an indicator of a good design. Of course, in this case it works well only if you’re adding new Visitors, but it gets in the way when you add new types of Trash.

Low coupling between classes and high cohesion within a class is definitely an important design goal. Applied mindlessly, though, it can prevent you from achieving a more elegant design. It seems that some classes inevitably have a certain intimacy with each other. These often occur in pairs that could perhaps be called couplets, for example, collections and iterators (Enumerations). The Trash-Visitor pair above appears to be another such couplet.

RTTI considered harmful?

Various designs in this chapter attempt to remove RTTI, which might give you the impression that it’s “considered harmful” (the condemnation used for poor, ill-fated goto, which was thus never put into Java). This isn’t true; it is the misuse of RTTI that is the problem. The reason our designs removed RTTI is because the misapplication of that feature prevented extensibility, while the stated goal was to be able to add a new type to the system with as little impact on surrounding code as possible. Since RTTI is often misused by having it look for every single type in your system, it causes code to be non-extensible: when you add a new type, you have to go hunting for all the code in which RTTI is used, and if you miss any you won’t get help from the compiler.

However, RTTI doesn’t automatically create non-extensible code. Let’s revisit the trash recycler once more. This time, a new tool will be introduced, which I call a TypeMap. It contains a Hashtable that holds Vectors, but the interface is simple: you can add( ) a new object, and you can get( ) a Vector containing all the objects of a particular type. The keys for the contained Hashtable are the types in the associated Vector. The beauty of this design (suggested by Larry O’Brien) is that the TypeMap dynamically adds a new pair whenever it encounters a new type, so whenever you add a new type to the system (even if you add the new type at run-time), it adapts.

Our example will again build on the structure of the Trash types in package c16.Trash (and the Trash.dat file used there can be used here without change):

//: DynaTrash.java 
// Using a Hashtable of Vectors and RTTI
// to automatically sort trash into
// vectors. This solution, despite the
// use of RTTI, is extensible.
package c16.dynatrash;
import c16.trash.*;
import java.util.*;

// Generic TypeMap works in any situation:
class TypeMap {
  private Hashtable t = new Hashtable();
  public void add(Object o) {
    Class type = o.getClass();
    if(t.containsKey(type))
      ((Vector)t.get(type)).addElement(o);
    else {
      Vector v = new Vector();
      v.addElement(o);
      t.put(type,v);
    }
  }
  public Vector get(Class type) {
    return (Vector)t.get(type);
  }
  public Enumeration keys() { return t.keys(); }
  // Returns handle to adapter class to allow
  // callbacks from ParseTrash.fillBin():
  public Fillable filler() { 
    // Anonymous inner class:
    return new Fillable() {
      public void addTrash(Trash t) { add(t); }
    };
  }
}

public class DynaTrash {
  public static void main(String[] args) {
    TypeMap bin = new TypeMap();
    ParseTrash.fillBin("Trash.dat",bin.filler());
    Enumeration keys = bin.keys();
    while(keys.hasMoreElements())
      Trash.sumValue(
        bin.get((Class)keys.nextElement()));
  }
} ///:~

Although powerful, the definition for TypeMap is simple. It contains a Hashtable, and the add( ) method does most of the work. When you add( ) a new object, the handle for the Class object for that type is extracted. This is used as a key to determine whether a Vector holding objects of that type is already present in the Hashtable. If so, that Vector is extracted and the object is added to the Vector. If not, the Class object and a new Vector are added as a key-value pair.

You can get an Enumeration of all the Class objects from keys( ), and use each Class object to fetch the corresponding Vector with get( ). And that’s all there is to it.

The filler( ) method is interesting because it takes advantage of the design of ParseTrash.fillBin( ), which doesn’t just try to fill a Vector but instead anything that implements the Fillable interface with its addTrash( ) method. All filler( ) needs to do is to return a handle to an interface that implements Fillable, and then this handle can be used as an argument to fillBin( ) like this:

ParseTrash.fillBin("Trash.dat", bin.filler());

To produce this handle, an anonymous inner class (described in Chapter 7) is used. You never need a named class to implement Fillable, you just need a handle to an object of that class, thus this is an appropriate use of anonymous inner classes.

An interesting thing about this design is that even though it wasn’t created to handle the sorting, fillBin( ) is performing a sort every time it inserts a Trash object into bin.

Much of class DynaTrash should be familiar from the previous examples. This time, instead of placing the new Trash objects into a bin of type Vector, the bin is of type TypeMap, so when the trash is thrown into bin it’s immediately sorted by TypeMap’s internal sorting mechanism. Stepping through the TypeMap and operating on each individual Vector becomes a simple matter:

    Enumeration keys = bin.keys();
    while(keys.hasMoreElements())
      Trash.sumValue(
        bin.get((Class)keys.nextElement()));

As you can see, adding a new type to the system won’t affect this code at all, nor the code in TypeMap. This is certainly the smallest solution to the problem, and arguably the most elegant as well. It does rely heavily on RTTI, but notice that each key-value pair in the Hashtable is looking for only one type. In addition, there’s no way you can “forget” to add the proper code to this system when you add a new type, since there isn’t any code you need to add.

Summary

Coming up with a design such as TrashVisitor.java that contains a larger amount of code than the earlier designs can seem at first to be counterproductive. It pays to notice what you’re trying to accomplish with various designs. Design patterns in general strive to separate the things that change from the things that stay the same. The “things that change” can refer to many different kinds of changes. Perhaps the change occurs because the program is placed into a new environment or because something in the current environment changes (this could be: “The user wants to add a new shape to the diagram currently on the screen”). Or, as in this case, the change could be the evolution of the code body. While previous versions of the trash-sorting example emphasized the addition of new types of Trash to the system, TrashVisitor.java allows you to easily add new functionality without disturbing the Trash hierarchy. There’s more code in TrashVisitor.java, but adding new functionality to Visitor is cheap. If this is something that happens a lot, then it’s worth the extra effort and code to make it happen more easily.

The discovery of the vector of change is no trivial matter; it’s not something that an analyst can usually detect before the program sees its initial design. The necessary information will probably not appear until later phases in the project: sometimes only at the design or implementation phases do you discover a deeper or more subtle need in your system. In the case of adding new types (which was the focus of most of the “recycle” examples) you might realize that you need a particular inheritance hierarchy only when you are in the maintenance phase and you begin extending the system!

One of the most important things that you’ll learn by studying design patterns seems to be an about-face from what has been promoted so far in this book. That is: “OOP is all about polymorphism.” This statement can produce the “two-year-old with a hammer” syndrome (everything looks like a nail). Put another way, it’s hard enough to “get” polymorphism, and once you do, you try to cast all your designs into that one particular mold.

What design patterns say is that OOP isn’t just about polymorphism. It’s about “separating the things that change from the things that stay the same.” Polymorphism is an especially important way to do this, and it turns out to be helpful if the programming language directly supports polymorphism (so you don’t have to wire it in yourself, which would tend to make it prohibitively expensive). But design patterns in general show other ways to accomplish the basic goal, and once your eyes have been opened to this you will begin to search for more creative designs.

Since the Design Patterns book came out and made such an impact, people have been searching for other patterns. You can expect to see more of these appear as time goes on. Here are some sites recommended by Jim Coplien, of C++ fame (http://www.bell-labs.com/~cope), who is one of the main proponents of the patterns movement:

http://st-www.cs.uiuc.edu/users/patterns
http://c2.com/cgi/wiki
http://c2.com/ppr
http://www.bell-labs.com/people/cope/Patterns/Process/index.html
http://www.bell-labs.com/cgi-user/OrgPatterns/OrgPatterns
http://st-www.cs.uiuc.edu/cgi-bin/wikic/wikic
http://www.cs.wustl.edu/~schmidt/patterns.html
http://www.espinc.com/patterns/overview.html

Also note there has been a yearly conference on design patterns, called PLOP, that produces a published proceedings, the third of which came out in late 1997 (all published by Addison-Wesley).

Exercises
  1. Using SingletonPattern.java as a starting point, create a class that manages a fixed number of its own objects.
  2. Add a class Plastic to TrashVisitor.java.
  3. Add a class Plastic to DynaTrash.java.

[66] But be warned: the examples are in C++.

[ Previous Chapter ] [ Short TOC ] [ Table of Contents ] [ Index ] [ Next Chapter ]
Last Update:02/04/2000