1.4.2 The Composite Pattern

Let's return to our department directory example and show how to use the union pattern to represent department directory data.

A DeptDirectory is either:

• an Empty directory, or
• a composite directory Cons(e,d) where e is the first Entry of the directory and d is the rest of the directory.

Note: the use of the name Cons for composite objects is taken from functional languages like Scheme; it abbreviates the word ``construct''.

In Java, each new type of data is represented by a class. Since the DeptDirectory type has two variants, we must use the union pattern to represent this type. The following collection of class definitions relies on the union pattern to define the DeptDirectory type. Since the DeptDirectory type is implemented by an abstract class, we will prepend the name DeptDirectory with the letter A to indicate that the class is abstract.

/**  an DeptDirectory is either:
 *   (i)  the empty directory new Empty(), or
 *   (ii) the non-empty directory new Cons(Entry,DeptDirectory)
 */
abstract class DeptDirectory {}

class Empty extends DeptDirectory {}

class Cons extends DeptDirectory {
  Entry first;
  DeptDirectory rest;

  /* constructor */
  Cons(Entry f, DeptDirectory r) {
    this.first = f;
    this.rest = r;
  }

  /* accessors */
  Entry getFirst() { return this.first; }
  DeptDirectory getRest() { return this.rest; }	
}

Note that our data definition comment is redundant; all of the information in the data definition is given by the group class definitions. But the commment is useful because it is so much more compact than the code.

The class Empty contains no fields, because empty directories have no embedded data. The class Cons contains two fields first and rest as specified in the data defintion for DeptDirectory. Similarly, the Entry class contains three fields name, address, and phone. The abstract class DeptDirectory is extended by only two classes: Empty and Cons. Hence, DeptDirectory is the union of Empty and Cons.

The Java code in the DeptDirectory example relies on one new feature that we have not seen before, namely the notion of a default constructor. The class Empty is concrete but does not include a constructor to initialize its fields because there are no fields to initialize! Java automatically generates a default zero-ary constructor for any class definition that does not include a constructor. As a result, the expression

new Empty()

generates a new instance of the class Empty.

When Unions are Composite The use of the union pattern in the DeptDirectory example has an extra feature not present in the preceding CityEntry example. One of the variants of the union class DeptDirectory includes a field of type DeptDirectory which makes the structure of the union definition self-referential. Self-referential structures are ubiquitous in computation, because any the concrete definition of an infinite set ultimately involves self-reference. In the OOP (``object-oriented programming'') community, this specialized usage of the union pattern is called the composite pattern. To repeat, a union pattern with root class C is composite when one or more of the variants of the pattern contains fields of type C.

The following expression creates a DeptDirectory containing the address and phone information for Corky and Matthias:

new Cons(new Entry("Corky","DH3104","x 6042"), 
  new Cons(new Entry("Matthias","DH3106","x 5732"), new Empty()))

This syntax is wordy but straightforward. Don't forget to include the keyword new at the front on each constructor invocation!

Finger Exercise Enter the text for the DeptDirectory example in the DrJava Definitions pane. Define a variable d of type DeptDirectory initialized to the value of the expression given in the preceding example. Try evaluating the following expressions:

d.getFirst()
d.getFirst().getName()
d.getFirst().getNumber()
d.getRest().getRest()
d.getRest().getRest()
d.getRest().getFirst()
d.getRest().getFirst().getName()

Save your program in a file called DeptDirectory.java.