Guide to Notation

Foundation Classes

This appendix documents the foundation classes we use in the C++ sample code of several design patterns. We've intentionally kept the classes simple and minimal. We describe the following classes:

  • List, an ordered list of objects.
  • Iterator, the interface for accessing an aggregate's objects in a sequence.
  • ListIterator, an iterator for traversing a List.
  • Point, a two-dimensional point.
  • Rect, an axis-aligned rectangle.

Some newer C++ standard types may not be available on all compilers. In particular, if your compiler doesn't define bool, then define it manually as

typedef int bool;
const int true = 1;
const int false = 0;


The List class template provides a basic container for storing an ordered list of objects. List stores elements by value, which means it works for built-in types as well as class instances. For example, List declares a list of ints. But most of the patterns use List to store pointers to objects, as in List. That way List can be used for heterogeneous lists.

For convenience, List also provides synonyms for stack operations, which make code that uses List for stacks more explicit without defining another class.

template <class Item>
class List {
    List(long size = DEFAULT_LIST_CAPACITY);
    List& operator=(const List&);

    long Count() const;
    Item& Get(long index) const;
    Item& First() const;
    Item& Last() const;
    bool Includes(const Item&) const;

    void Append(const Item&);
    void Prepend(const Item&);

    void Remove(const Item&);
    void RemoveLast();
    void RemoveFirst();
    void RemoveAll();

    Item& Top() const;
    void Push(const Item&);
    Item& Pop();

The following sections describe these operations in greater detail.

Construction, Destruction, Initialization, and Assignment

List(long size)
initializes the list. The size parameter is a hint for the initial number of elements.
overrides the default copy constructor so that member data are initialized properly.
frees the list's internal data structures but not the elements in the list. The class is not designed for subclassing; therefore the destructor isn't virtual.
List& operator=(const List&)
implements the assignment operation to assign member data properly.


These operations provide basic access to the list's elements.

long Count() const
returns the number of objects in the list.
Item& Get(long index) const
returns the object at the given index.
Item& First() const
returns the first object in the list.
Item& Last() const
returns the last object in the list.


void Append(const Item&)
adds the argument to the list, making it the last element.
void Prepend(const Item&)
adds the argument to the list, making it the first element.


void Remove(const Item&)
removes the given element from the list. This operation requires that the type of elements in the list supports the == operator for comparison.
void RemoveFirst()
removes the first element from the list.
void RemoveLast()
removes the last element from the list.
void RemoveAll()
removes all elements from the list.

Stack Interface

Item& Top() const
returns the top element (when the List is viewed as a stack).
void Push(const Item&)
pushes the element onto the stack.
Item& Pop()
pops the top element from the stack.


Iterator is an abstract class that defines a traversal interface for aggregates.

template <class Item>
class Iterator {
    virtual void First() = 0;
    virtual void Next() = 0;
    virtual bool IsDone() const = 0;
    virtual Item CurrentItem() const = 0;

The operations do the following:

virtual void First()
positions the iterator to the first object in the aggregate.
virtual void Next()
positions the iterator to the next object in the sequence.
virtual bool IsDone() const
returns true when there are no more objects in the sequence.
virtual Item CurrentItem() const
returns the object at the current position in the sequence.


ListIterator implements the Iterator interface to traverse List objects. Its constructor takes a list to traverse as an argument.

template <class Item>
class ListIterator : public Iterator<Item> {
    ListIterator(const List<Item>* aList);

    virtual void First();
    virtual void Next();
    virtual bool IsDone() const;
    virtual Item CurrentItem() const;


Point represents a point in a two-dimensional Cartesian coordinate space. Point supports some minimal vector arithmetic. The coordinates of a Point are defined as

typedef float Coord;

Point's operations are self-explanatory.

class Point {
    static const Point Zero;	

    Point(Coord x = 0.0, Coord y = 0.0);

    Coord X() const;  void X(Coord x);
    Coord Y() const;  void Y(Coord y);

    friend Point operator+(const Point&, const Point&);
    friend Point operator-(const Point&, const Point&);
    friend Point operator*(const Point&, const Point&);
    friend Point operator/(const Point&, const Point&);

    Point& operator+=(const Point&);
    Point& operator-=(const Point&);
    Point& operator*=(const Point&);
    Point& operator/=(const Point&);

    Point operator-();

    friend bool operator==(const Point&, const Point&);
    friend bool operator!=(const Point&, const Point&);

    friend ostream& operator<<(ostream&, const Point&);
    friend istream& operator>>(istream&, Point&);

The static member Zero represents Point(0, 0).


Rect represents an axis-aligned rectangle. A Rect is defined by an origin point and an extent (that is, width and height). The Rect operations are self-explanatory.

class Rect {
    static const Rect Zero;	

    Rect(Coord x, Coord y, Coord w, Coord h);
    Rect(const Point& origin, const Point& extent);

    Coord Width() const;   void Width(Coord);
    Coord Height() const;  void Height(Coord);
    Coord Left() const;    void Left(Coord);
    Coord Bottom() const;  void Bottom(Coord);

    Point& Origin() const; void Origin(const Point&);
    Point& Extent() const; void Extent(const Point&);

    void MoveTo(const Point&);
    void MoveBy(const Point&);

    bool IsEmpty() const;
    bool Contains(const Point&) const;

The static member Zero is equivalent to the rectangle

Rect(Point(0, 0), Point(0, 0));