Volume Number: 13 (1997)
Issue Number: 4
Column Tag: Programming Techniques

The Tao of Design

By John Schettino

Using Design Patterns to help reuse the structure of your code

I know what you're thinking not another "Eastern Mysticism as applied to Object Oriented Programming" article. Don't worry, although I'm going to begin with an eastern mysticism example, I'll spend most of the article presenting real examples of design patterns in C++. You're now probably wondering what is a design pattern? To answer that question we need to consider Tai Chi, Fibonocci, and the Tao.

I used to study Tai Chi, a martial art and a philosophy towards life. As I was learning the "form" (a series of body positions) my teacher would often tell us stories that illustrated the principals of Tai Chi. One day he began talking about Fibonocci. This mathematician and philosopher studied Nature and numbers. What he discovered, and Mandelbrot later refined, was that nature was really into reuse. There are patterns to both numbers and organisms. My teacher related Fibonocci sequences to Tai Chi by pointing out the many patterns within the form: how large movements are built from similar small movements in a Fibonocci sequence, how positions repeated in slight variations, and so on. It was all rather enlightening. What of the Tao? The Tao-te Ching roughly translates into "the way." It is the essential unifying element of all that is. It is a way of perception and living, as are using design patterns. Once you grasp the concept of design patterns you will see how and where to apply them. In essence, you'll be living the Tao of Design.

Design patterns are an attempt to express the sameness of design solutions in object oriented programs. It is really a way of thinking about a problem and the design of that problem's solution. Think about your own programming style. A large portion of it is most likely the way you structure your solutions, rather than the minute details of your code. If you could reuse the structure from one project to the next, you would gain all of the benefits of reuse (savings of time, higher quality, etc.) on a larger scale than simply reusing classes or functions. This is the central premise behind the book "Design Patterns" by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.

The book is an attempt to present the concept behind design patterns and describe several patterns that you can use. It is not intended as an introductory text on object oriented programming! The authors state up front that you should be proficient in at least one object oriented language (the examples are in Smalltalk and C++), and that you have object oriented design experience. To understand the book you must be familiar with such concepts as types, polymorphism, and interface versus implementation inheritance. This is not a light book. If you don't know object oriented design this is not the place to start. If, on the other hand, you have been involved with object oriented design and/or programming and feel that you could get more reuse or elegance out of your efforts, this is precisely the place to start.

The book begins with a description of the concept of design patterns and the motivation for using them. The idea is sound. We all reuse our own personal set of design solutions that we've built up through years of experience. We should study those solutions to discover the patterns within them, and then formalize those patterns into reusable classes.

What the authors propose is that we develop a common way of referring to and specifying designs. Not only do they propose it, they then give a detailed example of how to apply design patterns in an application. The example is somewhat academic, as is the entire book, but don't let that stop you from learning from it. Following the example are the 23 patterns themselves. They are organized into three categories: creational, structural, and behavioral. Each category contains several patterns.

Creational patterns abstract the instantiation process. When you are designing complex object oriented systems you often rely on composite objects along with class-based inheritance. Creational patterns are used to delegate instantiation, abstract behavior, and hide instantiation and composition details.

Structural patterns focus on the composition of classes and objects into larger structures. They deal with run-time compositions that are more dynamic than traditional multiple inheritance, object sharing and interface adaptation, and dynamic addition of responsibilities to objects.

Behavioral patterns deal with encapsulating algorithms and managing or delegating responsibility among objects. They focus more on communication and interaction, dynamic interfaces, object composition, and object dependency.

Many design problems fall into one or more of these categories. Typically, one must create several objects to represent the data in a design and decide how those objects interact and behave. When design patterns are applied to these problems you create more general, extensible, and reusable solutions than you might otherwise have done. You're not doing this extra work simply to feel good about yourself. You're helping yourself in the future when you must maintain this code or solve a similar problem.

Each pattern is described from several perspectives:

• Intent: a description of the purpose the pattern serves.

• Also Known As: common names used for the pattern, such as Wrapper instead of Adapter.

• Motivation: why you would use the pattern.

• Applicability: when to use the pattern.

• Structure: one or more diagrams describing the classes in the pattern and how they relate.

• Participants: a description of each of the classes used in the Structure section.

• Collaborations: a description of the run-time interaction between instances of the classes used in the Structure section.

• Consequences: a description of the trade-offs and issues with using the pattern.

• Implementation: a description of the implementation issues. The authors tell you what to avoid and what to consider when implementing a pattern.

• Sample Code: implementations of classes illustrating the pattern in Smalltalk and C++.

• Know Uses: a description of some well-known commercial and academic applications, toolkits, and languages that use the pattern.

• Related Patterns: a list of the patterns that may be implemented by, use, or interact with this pattern.

The authors close each section with a discussion of the type of problems the category of patterns is attempting to solve. This section is most useful to those with limited design experience. Old hands will find that they can think of many situations where they could (or perhaps already do) apply the patterns.

You'll gain three new skills from reading the book. First, you'll know more about design patterns themselves. You'll even know how to identify and classify them. Second, you'll know the patterns and classes presented. This can act as a standard nomenclature when you're discussing designs with other programmers. Third, you'll have 23 patterns to use in your own programs. Some of these you will have already discovered yourself while others will probably be complete revelations to you.

Let's put the principals of design patterns into action. Illustrating all 23 patterns presented in the book is beyond the scope of this article, but I'll present an example that applies a pattern from each category to help motivate you to explore the topic further. Since these are design patterns, we need a problem to solve. I'm going to take the easy road and select a completely made-up problem - tree manipulation. We will build two tree structures containing file names found in a Macintosh file directory and perform some operations on it.

The program traverses a Macintosh file directory and the subdirectories in it to create a single tree structure containing all the names of the files and folders visited. The names are then retrieved by traversing the tree.

This is not exactly rocket science. There are plenty of ways of doing this without resorting to objects at all, let alone the design patterns described in the book. The example is simple so that you can focus on applying the patterns.

We are talking about design patterns, so let's begin with a design before we start coding. We want some form of tree that consists of nodes representing the file names. Using a tree is an easy way to get a sorted list. To abstract the building process we'll apply a creational pattern called Builder. This allows us to hide the internal structure of the tree being built, and to build different types of trees using the same program.

Once the trees are built we must access them to retrieve the file names. A behavioral pattern called Iterator allows us to encapsulate the access algorithm such that the main program does not know the tree structure or the algorithm used to traverse the tree. This is in contrast to the more common recursive tree walking algorithms you'd consider first. Using an Iterator to traverse trees means you have to use stacks and queues to maintain your current location. Rather than implement our own stack and queue objects, we can take advantage of a structural pattern called Adapter to extend a list object to include the additional behaviors of a stack and a queue. We'll take advantage of several templated classes from the C++ Standard Template Library (STL) for this.

We'll use three classes for the project. The first class hierarchy represents nodes in the tree. The TreeNode base class defines the common interface for our tree nodes and a subclass implements a simple binary tree node. This isn't a design pattern - just good object oriented design. The second class hierarchy is for a TreeIterator class that retrieves the nodes of a tree. Two subclasses of the TreeIterator class implement depth-first and breadth-first traversals of the tree.

Finally, the TreeBuilder class hierarchy builds trees consisting of TreeNodes. One subclass of this class builds binary trees, the other builds height-balanced binary trees. The main program uses instances of both TreeBuilder subclasses to create two different trees containing instances of the TreeNode class. It then retrieves and prints the file names from each tree using instances of both of the TreeIterator classes. It performs all these operations without explicit knowledge of the internal representations of the trees or the algorithms used to traverse them.

Three patterns are used in the design: Iterator, Adapter, and Builder. Let me summarize each of these patterns and how they are applied to the problem.

An Iterator is an example of a behavioral pattern. It is a class that is instantiated with a compound data structure. Each time you call a member function of the instance it returns the next element of the structure. A null value is returned once all elements have been accessed. In our project a tree consisting of several nodes is the compound data structure. The elements returned are the nodes in the tree. We use the Iterator to encapsulate the tree traversal algorithm in a class and remove that code from our main program. That means the main program does not know how the tree is organized. It isn't changed if the tree implementation changes or if we discover a more efficient algorithm for traversing the tree.

An Adapter is an example of a structural pattern. It adds new interfaces to an existing object or class to create a new object or class with additional behaviors. We use STL stacks and queues in our TreeIterator subclasses. Stacks and queues must store elements in a list, so a list class can be adapted by adding new member functions such as push() and pop().

A Builder is an example of a creational pattern. It encapsulates the actual building of a composite data structure and hides the details of how that structure is composed by defining one or more member functions to add elements to the composite structure. You can create general purpose data collection routines that accept instances of a Builder class and then build different forms of the composite data structure. In our project the TreeBuilder class builds trees. Because we use a Builder we can structure the trees in many different ways without affecting the main program.

The TreeNode class represents a node in a tree. The base class defines the minimal interface for a TreeNode.

typedef class TreeNode * TreeNodePtr;
typedef class BinaryTreeNode * BinaryTreeNodePtr;

class TreeNode {
 friend ostream& operator<< (ostream& os, 
 TreeNode& t);
 friend ostream& operator<< (ostream& os, 
 const TreeNodePtr& t);
public:
 virtual const char * output(void) {};
 virtual int compare (const TreeNode& otherNode)
 {};
};

All TreeNode subclasses must implement the output() and compare() member functions. Use output() to get a string form of the node suitable for printing. Use compare() to determine if this TreeNode is less than, equal to, or greater than another TreeNode. We use a class hierarchy so we can create new subclasses that hold more complex data in a node.

The BinaryTreeNode subclass of TreeNode represents a node in a binary tree.

class BinaryTreeNode: public TreeNode {
public:
 BinaryTreeNode(const char *name)
 { _fname = new char[strlen(name)+1];
  strcpy(_fname, name);
  _leftChild = _rightChild = 0; }
 virtual const char* output(void) 
 { return _fname; }
 virtual int compare (const BinaryTreeNode&
 otherNode)
 { return strcmp(_fname, otherNode._fname); }
 void setLeftChild(const BinaryTreeNodePtr l) 
 { _leftChild = l; }
 void setRightChild(const BinaryTreeNodePtr r) 
 { _rightChild = r; }
 BinaryTreeNodePtr leftChild() 
 { return _leftChild; }
 BinaryTreeNodePtr rightChild() 
 { return _rightChild; }
private:
 char *_fname;
 BinaryTreeNodePtr _leftChild;
 BinaryTreeNodePtr _rightChild;
};

It uses a string stored in _fname as the node value. The output() member function simply returns _fname. The compare() member function used strcmp() to compare the values of the two nodes. We also define member functions to get and set the left and right child pointers stored in the node. This allows other classes to build and traverse trees consisting of these nodes.

The TreeNodeIterator class hierarchy implements the Iterator design pattern. It is a class that is instantiated with a compound data structure. Each time you call a member function of an instance of this class it returns the next node of the tree. The base class defines the interface.

class TreeNodeIterator {
public:
 virtual TreeNodePtr operator++ (int) {};// next 
 virtual TreeNodePtr current() {}; // get current
 virtual TreeNodePtr next() {};    // get next
 virtual void reset() {}; // reset
};

This class implements both the ++ increment operator and the current() and next() member functions to retrieve nodes in the tree. It also includes a reset() member function so the same Iterator can be used to extract elements multiple times. We use a class hierarchy so we can provide two ways of iterating through the tree. The DFTreeNodeIterator subclass implements a depth-first access of the tree. This retrieves nodes in sorted order if it is accessing a binary tree.

The DFTreeNodeIterator returns nodes in sorted order.

// Depth-First BinaryTree Node Iterator
class DFTreeNodeIterator : public TreeNodeIterator {
public:
 DFTreeNodeIterator(BinaryTreeNode &tree);
 virtual TreeNodePtr operator++ (int);
 virtual TreeNodePtr current();
 virtual TreeNodePtr next();
 virtual void reset();
private:
 BinaryTreeNode *_origTree, *_tree;
 // use an STL Stack
 stack<list<BinaryTreeNodePtr> > _pendingNodes;
 void _pushLeft();
};

The private members of the class add a couple of pointers to nodes in the tree. The *_origTree pointer holds the root node of the tree used to instantiate the iterator. This is used to reset the iterator. The *_tree pointer points to the current node in the tree. A STL stack (_pendingNodes) is used to hold the pending nodes as the tree is traversed. This is similar to using the program stack in a recursive traversal of the tree. Finally, a member function that pushes nodes onto the stack is declared. Let's look at the implementation of the member functions next.

// - DFTreeNodeIterator member functions -
DFTreeNodeIterator::
DFTreeNodeIterator(BinaryTreeNode &tree)
{
 _origTree = _tree = &tree;
 _pushLeft();
}

The constructor takes a BinaryTreeNode as its only parameter. The two pointers stored in the are initialized to this value. Then the _pushLeft() member function is used to set the _tree pointer to the first node to return. The iterator is now ready to return successive nodes of the tree.

void
DFTreeNodeIterator::_pushLeft()
{
 while (_tree->leftChild())
 {
 _pendingNodes.push(_tree);
 _tree = _tree->leftChild();
 }
}

The _pushLeft() member function traverses the tree to the leaf node on the left hand side, pushing each visited node onto the _pendingNodes stack. Once the end of the tree is reached that node is consider the current node. Let's look at the three member functions that return nodes.

TreeNodePtr
DFTreeNodeIterator::operator++ (int)
{
 TreeNode* theNode = current();
 next();
 return theNode;
}

The ++ operator retrieves the current node, moves the to the next node, and then returns the current node. This acts just like the postfix ++ operator in C++.

TreeNodePtr
DFTreeNodeIterator::current ()
{
 return _tree;
}

Because _tree always points to the current node in the tree, the current() member function just returns it.

TreeNodePtr
DFTreeNodeIterator::next()
{
 if (_tree)
 {
    // follow right child ptr
 if (_tree->rightChild())
 {
 _tree = _tree->rightChild();
 _pushLeft();
 }
 else if (_pendingNodes.size() > 0)
 { 
 // end of branch, pop and return node itself
 _tree = _pendingNodes.top();
 _pendingNodes.pop();
 }
 else
 _tree = 0; // all done
 }
 return _tree;
}

The next() member function traverses the tree to the next node. The current node's right child is accessed. If it exists then the tree is traversed thru the left child from that node, again stacking up all visited nodes. If there is no right child then the stack is popped, and the popped node becomes the current node. If there are no nodes in the stack then the tree has been traversed completely.

void
DFTreeNodeIterator::reset()
{
 _tree = _origTree;
 _pushLeft();
}

The reset() member function restores _tree to the originally supplied value and then calls _pushLeft(). This restores the iterator to its initial state.

The BFTreeNodeIterator subclass implements a breadth-first access of the tree. This retrieves nodes in height order (in other words, all nodes at height N of the tree are returned before moving to nodes at height N+1.)

// Breadth-First BinaryTree Node
class BFTreeNodeIterator : public TreeNodeIterator {
public:
 BFTreeNodeIterator(BinaryTreeNode &tree);
 virtual TreeNodePtr operator++ (int);
 virtual TreeNodePtr current();
 virtual TreeNodePtr next();
 virtual void reset();
private:
 BinaryTreeNode *_origTree, *_tree;
    // use an STL queue
 queue<list<BinaryTreeNodePtr> > _pendingNodes;
 enum {IO_node, IO_left, IO_right} _current;
};

The private members of the class add a couple of pointers to nodes in the tree as was done in the other. A STL queue (_pendingNodes) is used to hold the pending nodes as the tree is traversed. Since we traverse the tree by level we use a queue to revisit nodes. Finally, an enumeration is used to keep track of the state of the current node in the retrieval process. The implementations of the member functions of this class differ somewhat from the other, because it returns nodes in a different order.

// - BFTreeNodeIterator member fns -
BFTreeNodeIterator::
BFTreeNodeIterator(BinaryTreeNode &tree)
{
 _origTree = _tree = &tree;
 _current = IO_node;
}

TreeNodePtr
BFTreeNodeIterator::operator++ (int)
{
 TreeNode* theNode = current();
 next();
 return theNode;
}

TreeNodePtr
BFTreeNodeIterator::current ()
{
 if (!_tree) return 0;
 
 switch (_current) {
 case IO_node:
 return _tree;
 case IO_left:
 return _tree->leftChild();
 case IO_right:
 return _tree->rightChild();
 }
 
}

TreeNodePtr
BFTreeNodeIterator::next()
{
 BinaryTreeNodePtr c;
 switch (_current) {
 case IO_node:
 if (_tree->leftChild()) _current = IO_left;
 else if (_tree->rightChild()) 
 _current = IO_right;
 else if (_pendingNodes.size() > 0)
 {
 _tree = _pendingNodes.front();
 _pendingNodes.pop();
 _current = _tree->leftChild() ? 
 IO_left : IO_right;
 }
 else _tree = 0;
 return current();
 case IO_left:
 c = (BinaryTreeNodePtr) current();
 if (c->leftChild() || c->rightChild())
 _pendingNodes.push(c);
 if (_tree->rightChild()) _current = IO_right;
 else if (_pendingNodes.size() > 0)
 {
 _tree = _pendingNodes.front();
 _pendingNodes.pop();
 _current = _tree->leftChild() ? 
 IO_left : IO_right;
 } 
 else _tree = 0;
 return current();
 case IO_right:
 c = (BinaryTreeNodePtr) current();
 if (c->leftChild() || c->rightChild()) 
 _pendingNodes.push(c);
 if (_pendingNodes.size() > 0)
 {
 _tree = _pendingNodes.front();
 _pendingNodes.pop();
 _current = _tree->leftChild() ?
 IO_left : IO_right;
 } 
 else _tree = 0; 
 return current();
 }
}

void
BFTreeNodeIterator::reset()
{
 _tree = _origTree;
 _current = IO_node;
}

I'm not going to give a detailed explanation of these member functions. The basic behavior is that the root node is returned via current() and then its left and right children are returned when next() is called. As each child is returned it is added to a queue. Once all children of a node have been returned the node at the head of the queue is retrieved and then that node's children are returned and queued. The result is that each "level" of the tree is visited and all nodes below that level are enqueued to be revisited.

The TreeBuilder class hierarchy implements the Builder design pattern. It encapsulates the building of a composite data structure and hides the details of how that structure is composed by defining an AddNode() member function to add nodes to the tree. The base class defines this interface.

// Builder for making trees - base class
class TreeBuilder {
public:
 virtual void AddNode(TreeNodePtr theNode) {}
 virtual TreeNodePtr GetTree() { return 0; }
protected:
 TreeBuilder() {};
};

New nodes are added to the current tree being built by allocating them and passing them to the TreeBuilder AddNode() member function. The completed tree is returned by the GetTree() member function. The BinaryTreeBuilder subclass implements a simple binary tree. No effort is made to balance the tree.

// Builder for making binary trees
class BinaryTreeBuilder : public TreeBuilder {
public:
 BinaryTreeBuilder();
 virtual void AddNode(TreeNodePtr theNode);
 virtual TreeNodePtr GetTree();
private:
 TreeNodePtr _currentBTree;
};

// - BinaryTreeBuilder member fns -
BinaryTreeBuilder::BinaryTreeBuilder() 
{
 _currentBTree = 0;
}

TreeNodePtr
BinaryTreeBuilder::GetTree() 
{
 return _currentBTree;
}

void
BinaryTreeBuilder::AddNode(TreeNode* theNode) 
{
 BinaryTreeNodePtr testNode = 
 (BinaryTreeNodePtr) _currentBTree;
 if (!testNode) _currentBTree = theNode;
 else
 {
 for (;;)
 {
 if (((BinaryTreeNodePtr)theNode)
 ->compare(*testNode) <0)
 {
 if (testNode->leftChild()) 
 testNode = testNode->leftChild();
 else 
 {
 testNode->setLeftChild(
 (BinaryTreeNodePtr)theNode);
 return;
 }
 }
 else 
 {
 if (testNode->rightChild()) 
 testNode = testNode->rightChild();
 else 
 {
 testNode->setRightChild(
 (BinaryTreeNodePtr)theNode);
 return;
 }
 }
 }
 }
}

The AddNode() member function traverses the current tree, comparing the new node to the current node by using the TreeNode compare() member function. Once the correct location is located (i.e., a leaf node is reached) the new node is added as a left or right child of the leaf node.

The HBTreeBuilder subclass builds height-balanced binary trees. To implement a height-balanced binary tree we restructure the tree as we add new nodes.

// Builder for making height-balanced binary trees
class HBTreeBuilder : public TreeBuilder {
public:
 HBTreeBuilder();
 virtual void AddNode(TreeNodePtr theNode);
 virtual TreeNodePtr GetTree();
private:
 TreeNodePtr _currentBTree;
};

// - HBTreeBuilder member fns -
HBTreeBuilder::HBTreeBuilder() 
{
 _currentBTree = 0;
}

TreeNodePtr
HBTreeBuilder::GetTree() 
{
 return _currentBTree;
}

void
HBTreeBuilder::AddNode(TreeNode* theNode) 
{
 BinaryTreeNodePtr testNode = 
 (BinaryTreeNodePtr) _currentBTree;
 if (!testNode) _currentBTree = theNode;
 else
 {
 BinaryTreeNodePtr grandparent = 0, parent = 0;
 for (;;)
 {
 if (((BinaryTreeNodePtr)theNode)
 ->compare(*testNode) <0)
 {
 if (testNode->leftChild())
 {
 grandparent = parent;
 parent = testNode;
 testNode = testNode->leftChild();
 }
 else 
 {
    // balance a tree with a long left chain
 if (parent && grandparent &&
 !(parent->rightChild()) && 
 !(testNode->rightChild()))
 {
 if (parent->compare(*grandparent) <0)
 grandparent->setLeftChild(testNode);
 else 
 grandparent->setRightChild(testNode);
 parent->setLeftChild(0);
 testNode->setRightChild(parent);
 }
 testNode->setLeftChild(
 (BinaryTreeNodePtr)theNode);
 return;
 }
 }
 else 
 {
 if (testNode->rightChild())
 {
 grandparent = parent;
 parent = testNode;
 testNode = testNode->rightChild();
 }
 else 
 {
    // balance a tree with a long right chain
 if (parent && grandparent &&
 !(parent->leftChild()) && 
 !(testNode->leftChild()))
 {
 if (parent->compare(*grandparent) <0)
 grandparent->setLeftChild(testNode);
 else 
 grandparent->setRightChild(testNode);
 parent->setRightChild(0);
 testNode->setLeftChild(parent);
 }
 testNode->setRightChild(
 (BinaryTreeNodePtr)theNode);
 return;
 }
 }
 }
 }
}

As in the last class, the AddNode() member function traverses the current tree, comparing the new node to the current node by using the TreeNode compare() member function. This version keeps track of the previous two nodes visited as the tree is traversed. Once the correct location is found (that is, a leaf node is reached) the current and previous nodes are checked to see if both lack a child on the opposite side. If they do, then the subtree from the grandparent node (that is, two nodes above the leaf) is re-arranged such that it forms a balanced tree when a new node is added.

We implement a few functions, including main(), to put these classes to use. I'm using a function from the MoreFiles 1.4.3 library to traverse a Macintosh directory. The IterateDirectory() function accepts a directory, a function pointer that is a callback function you write, and a void * that can be whatever you'd like to supply to the callback. This is perfect for a Builder! All I do is pass a TreeBuilder to IterateDirectory(). It will be passed along to my callback, where I can use it to add the file or folder name to the current tree. Besides the main() and my callback function, I've written two functions that use tree node iterators to print the nodes in a tree.

#include "Patterns.h"
#include <iostream.h>
#include "IterateDirectory.h" 

// - ostream operators to print tree nodes -
ostream&
operator<< (ostream& os, const TreeNodePtr& t)
{
 os << *t; return os;
}
ostream&
operator<< (ostream& os, TreeNode& t)
{
 os << "[" << t.output() << "]\n";
 return os;
}

This pair of ostream operators use the output() member function of the TreeNode base class to print out a node in the tree. They can print out any subclass of TreeNode.

// - callback for IterateDirectory() -
pascal
void
getName(const CInfoPBRec * const cpbPtr,
 Boolean *quitFlag,
 void *tbuilder)
{
 char *cstr = p2cstr(cpbPtr->hFileInfo.ioNamePtr);
 ((TreeBuilder *)tbuilder)->
 AddNode(new BinaryTreeNode(cstr));
}

The getName() callback function is called for each name found by IterateDirectory(). The Pascal string version of the file name is converted into a C string. That string is used to allocate a BinaryTreeNode, which is passed to the TreeBuilder. Recall that the TreeBuilder instance was passed into this function by IterateDirectory() - we'll see where in a moment.

// - walk a tree using the TreeNodeIterator
void walkTree1(TreeNodeIterator &treeNodes)
{
 cout << 
 "* Fetching nodes via current/next operators\n";
 
 for ( ;treeNodes.current(); treeNodes.next())
 cout << treeNodes.current();
}
// - walk a tree using the TreeNodeIterator
void walkTree2(TreeNodeIterator &treeNodes)
{
 cout << "* Fetching nodes via ++ operator\n";

 while (TreeNodePtr p = treeNodes++)
 cout << p;

}

The walkTree1() and walkTree2() functions take a TreeNodeIterator and use it to access the nodes of a tree. They both produce the same output. They just use the two alternative APIs of TreeNodeIterator. I personally prefer the ++ operator version used in walkTree2() because it looks more like C++.

// - main program 
void main(void)
{
 cout << "Building binary tree\n";

 BinaryTreeBuilder b;

    // iterate over a directory named Example Dir
    // within the program's current working directory
 StringPtr dir = c2pstr(":Example Dir");

 IterateDirectory(0,0,dir,2,getName, &b);
 TreeNodePtr myTree = 
 (BinaryTreeNodePtr) b.GetTree();
 
 cout << 
 "The nodes, using a depth-first iterator:\n";

 DFTreeNodeIterator depthFirst(
 *(BinaryTreeNodePtr)myTree);
 walkTree1(depthFirst);
 
 cout << 
 "\nThe nodes, same iterator, alternate API:\n";

 depthFirst.reset();
 walkTree2(depthFirst);
 
 cout << 
 "\nThe nodes, using a breadth-first "
 << "iterator:\n";

 BFTreeNodeIterator bredthFirst(
 *(BinaryTreeNodePtr)myTree);
 walkTree2(bredthFirst);

 cout << 
 "\nBuilding height balanced binary tree\n";

 HBTreeBuilder hb;

 IterateDirectory(0,0,dir,2, getName, &hb);
 myTree = (BinaryTreeNodePtr) hb.GetTree();

 cout << 
 "The HB nodes, using a depth-first iterator:\n";
 
 DFTreeNodeIterator depthFirstHB(
 *(BinaryTreeNodePtr)myTree);
 walkTree2(depthFirstHB);

 cout << 
 "\nThe HB nodes, using a BF iterator:\n";

 BFTreeNodeIterator bredthFirstHB(
 *(BinaryTreeNodePtr)myTree);
 walkTree2(bredthFirstHB);
 
 cout << "\nDone\n";
}

The main() function first builds a binary tree version of the example directory by allocating a BinaryTreeBuilder object and passing that object to IterateDirectory(), along with a pointer to the callback function getName(). IterateDirectory() calls getName() with each matching file or directory, and supplies the BinaryTreeBuilder object. Once all the entries are processed the completed tree is extracted by calling the GetTree() member function of the BinaryTreeBuilder object. The tree is used in the constructor for a DFTreeNodeIterator and the resulting object is passed to each of the walkTree functions. Notice that we reset the iterator before passing it to the second walkTree function.

The whole process is repeated a second time. The only difference is that we create a HBTreeBuilder object to build a height-balanced binary tree. The example directory and program output are shown in Figure 1.

Figure 1. Program Output.

Building binary tree
The nodes, using a depth-first:
* Fetching nodes via current/next operators
[Folder 1]
[Folder 2]
[Folder 3]
[FolderHelp]
[Fri]
[Jaki]
[Jan]
[Mar]

The nodes, same iterator, alternate API:
* Fetching nodes via ++ operator
[Folder 1]
[Folder 2]
[Folder 3]
[FolderHelp]
[Fri]
[Jaki]
[Jan]
[Mar]

The nodes, using a breadth-first iterator:
* Fetching nodes via ++ operator
[Folder 1]
[Fri]
[Folder 2]
[Jaki]
[Folder 3]
[Jan]
[FolderHelp]
[Mar]

Building height balanced binary tree
The HB nodes, using a depth-first iterator:
* Fetching nodes via ++ operator
[Folder 1]
[Folder 2]
[Folder 3]
[FolderHelp]
[Fri]
[Jaki]
[Jan]
[Mar]

The HB nodes, using a BF iterator:
* Fetching nodes via ++ operator
[Folder 1]
[Fri]
[Folder 3]
[Jan]
[Folder 2]
[FolderHelp]
[Jaki]
[Mar]

Done

Note that although both the binary and height-balanced trees produce the same output when accessed via the depth-first, they produce different output with a breadth-first. That's because the two trees are organized differently.

I use the Standard Template Library stack, queue, and list objects in the class implementations. The STL (with documentation) is provided with recent versions of CodeWarrior. I mention this because the STL implements several important design patterns as templated classes, and is itself very dependent on design patterns. The stack and queue class templates are examples of the Adapter design pattern. They add new interfaces (such as the stack push() and pop() and the queue top() methods) to an existing object (the list) to create new objects. You can learn quite a bit about design patterns simply by reading about the STL.

Applying design patterns to a design makes major impacts to both the design and the implementation. Let me point out exactly what those impacts are in the example program.

We used a TreeBuilder class (an example of the Builder creational pattern) to construct our tree of file names. That moved the code (and algorithm, since we used subclasses) out of our main program and into a class. Our main program is simpler, and can build many different kinds of trees. We also gain a reusable TreeBuilder class just in case we ever want to build these or similar types of trees again.

We used the TreeNodeIterator class (an example of the behavioral pattern) to retrieve the nodes from the tree. This allows us to move the implementation (and algorithm) for accessing tree nodes from the application into the class. We could use a TreeNodeIterator to access each node of the tree and do whatever we want to the node. For example we might search the tree for a particular file name using the iterator.

We used STL stacks and queues (examples of the Adapter structural pattern) within our TreeNodeIterator subclasses. This allowed us to quickly and easily extend an existing class (the STL list) to provide new behavior specific to a stack and queue. Adapters are an excellent way to reuse trusted and debugged code. They simply add new behavior in the form of new member functions to an existing class.

Is this just good object oriented programming? Sort of. Good object oriented designers would almost certainly create a TreeNode class hierarchy. Since we applied design patterns we ended up with a main program that is structured a little differently than the obvious non-pattern approach to design. We also encapsulated the building and accessing algorithms in class hierarchies. This makes the classes smarter, and frees the main program from the details of the tree organization. We get more general (and therefore more reusable) classes and a simpler main program.

I hope I've been able to interest you in the who area of design patterns. This is not just an academic area of study. You can make real improvements to your designs and gain real productivity advances in maintaining and reusing code. All you have to do is look at the problem with patterns in mind.

E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns. Addison-Wesley, ISBN 0-201-63361-2, 1995

Luther, Jim. "MoreFiles 1.4.3". Available via FTP at

ftp://ftpdev.info.apple.com/Developer_Services/Sample_Code/MoreFiles_1.4.3/.

Rensselaer Polytechnic Institute, "The Standard Template Library". A web site with a general description of STL and links to web sites containing documentation.

http://www.cs.rpi.edu/~musser/stl.html.