1.5.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.

In Scheme, we could implement this definition using the following collection of structures:

;; a DeptDirectory is either:
;;   the empty directory (make-Empty), or
;;   the non-empty directory (make-Cons Entry DeptDirectory)
(define-struct Empty ())
(define-struct Cons (first rest))

;; an Entry is (make-Entry String String String)
(define-struct Entry (name address phone))

Note that the preceding Scheme code leaves most of the corresponding data definition unstated! It never mentions the new type DeptDirectory. It does not express the fact that instances of Empty and Cons are elements of the type DeptDirectory, nor does it state that the first and rest fields of a Cons must be of type Entry and DeptDirectory, respectively. Similarly, it fails to state that the fields name, address and phone are all strings. In Scheme, we must compose comments to communicate this information. Unfortunately, since these comments are not code they are not checked for consistency.

In Java, each new type of data is represented by a class. Since the DeptDirectory type has two variants, we should use the union pattern to represent this type. The following collection of class definitions relies on the union pattern to define the DeptDirectory type.

/**  DeptDirectory := Empty() + Cons(Entry, DeptDirectory)
 */
abstract class DeptDirectory {}

class Empty extends DeptDirectory {}

class Cons extends DeptDirectory {
  Entry first;
  DeptDirectory rest;

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

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

The Java code is wordier, but it captures all of the information in the data definition. Our data definition comment is redundant. The class Empty contains no fields, just like the corresponding Scheme struct. The class Cons contains two fields first and rest akin to the two fields in the corresponding Scheme struct. Similarly, the Entry class contains three fields name, address, and phone just like the Scheme struct Entry given above. 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 public 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 class self-referential. Since self-referential structures are ubiquitous in Scheme (and other functional languages), this feature is not at all surprising to programmers familiar with functional programming. In the OOP (``object-oriented programming'') community, which has strong historical ties to imperative programming, this feature is viewed as distinctive because it implies that methods that process the union class are naturally recursive. For this reason, the OOP community assigns a distinct pattern name, namely composite pattern, to the the special case of the union pattern where self-reference is present in the data definition. We will use this terminology in the remainder of the monograph.

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!