TweetFollow Us on Twitter

Design Patterns Tutorial

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

The Tao

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.

Design Patterns

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.

Patterns in Action

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.

Problem Statement

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.

Design

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.

Patterns

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.

Implementing The TreeNode Class

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.

Implementing The TreeNodeIterator Class

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.

Implementing The TreeBuilder Class

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.

Implementing The Program

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.

Design Patterns, Made Easy

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.

Tao, Revisited

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.

Bibliography and References

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.

 
AAPL
$116.47
Apple Inc.
+0.16
MSFT
$47.98
Microsoft Corpora
-0.72
GOOG
$537.50
Google Inc.
+2.67

MacTech Search:
Community Search:

Software Updates via MacUpdate

Cobook 3.0.7 - Intelligent address book....
Cobook Contacts is an intuitive, engaging address book. Solve the problem of contact management with Cobook Contacts and its simple interface and powerful syncing and integration possibilities.... Read more
StatsBar 1.9 - Monitor system processes...
StatsBar gives you a comprehensive and detailed analysis of the following areas of your Mac: CPU usage Memory usage Disk usage Network and bandwidth usage Battery power and health (MacBooks only)... Read more
Cyberduck 4.6 - FTP and SFTP browser. (F...
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Evernote 6.0.1 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
calibre 2.11 - Complete e-library manage...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
Herald 5.0.1 - Notification plugin for M...
Note: Versions 2.1.3 (for OS X 10.7), 3.0.6 (for OS X 10.8), and 4.0.8 (for OS X 10.9) are no longer supported by the developer. Herald is a notification plugin for Mail.app, Apple's Mac OS X email... Read more
Firetask 3.7 - Innovative task managemen...
Firetask uniquely combines the advantages of classical priority-and-due-date-based task management with GTD. Stay focused and on top of your commitments - Firetask's "Today" view shows all relevant... Read more
TechTool Pro 7.0.6 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
PhotoDesk 3.0.1 - Instagram client for p...
PhotoDesk lets you view, like, comment, and download Instagram pictures/videos! (NO Uploads! / Image Posting! Instagram forbids that! AND you *need* an *existing* Instagram account). But you can do... Read more

Latest Forum Discussions

See All

Ubisoft Gives Everyone Two New Ways to E...
Ubisoft Gives Everyone Two New Ways to Earn In-Game Stuff for Far Cry 4 Posted by Jessica Fisher on November 21st, 2014 [ permalink ] | Read more »
Golfinity – Tips, Tricks, Strategies, an...
Dig this: Would you like to know what we thought of being an infinite golfer? Check out our Golfinity review! Golfinity offers unlimited ways to test your skills at golf. Here are a few ways to make sure your score doesn’t get too high and your... | Read more »
Dark Hearts, The Sequel to Haunting Meli...
Dark Hearts, The Sequel to Haunting Melissa, is Available Now Posted by Jessica Fisher on November 21st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Meowza! Toyze Brings Talking Tom to Life...
Meowza! | Read more »
Square Enix Announces New Tactical RPG f...
Square Enix Announces New Tactical RPG for Mobile, Heavenstrike Rivals. Posted by Jessica Fisher on November 21st, 2014 [ permalink ] With their epic stories and gorgeous graphics, | Read more »
Quest for Revenge (Games)
Quest for Revenge 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: The great Kingdom of the west has fallen. The gods ignore the prayers of the desperate. A dark warlord has extinguished... | Read more »
Threadz is a New Writing Adventure for Y...
Threadz is a New Writing Adventure for You and Your Friends Posted by Jessica Fisher on November 21st, 2014 [ permalink ] In the tradition of round-robin storytelling, | Read more »
SteelSeries Stratus XL Hardware Review
Made by: SteelSeries Price: $59.99 Hardware/iOS Integration Rating: 4 out of 5 stars Usability Rating: 4.5 out of 5 stars Reuse Value Rating: 4.25 out of 5 stars Build Quality Rating: 4.5 out of 5 stars Overall Rating: 4.31 out of 5 stars | Read more »
ACDSee (Photography)
ACDSee 1.0.0 Device: iOS iPhone Category: Photography Price: $1.99, Version: 1.0.0 (iTunes) Description: Capture, perfect, and share your photos with ACDSee. The ACDSee iPhone app combines an innovative camera, a powerful photo... | Read more »
ProTube for YouTube (Entertainment)
ProTube for YouTube 2.0.2 Device: iOS Universal Category: Entertainment Price: $1.99, Version: 2.0.2 (iTunes) Description: ProTube is the ultimate, fully featured YouTube app. With it's highly polished design, ProTube offers ad-free... | Read more »

Price Scanner via MacPrices.net

Save up to $400 with Apple refurbished 2014 1...
The Apple Store has restocked Apple Certified Refurbished 2014 15″ Retina MacBook Pros for up to $400 off the cost of new models. An Apple one-year warranty is included with each model, and shipping... Read more
New 13-inch 1.4GHz MacBook Air on sale for $8...
 Adorama has the 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. B&H Photo has the 13″ 1.4GHz/128GB MacBook... Read more
Apple Expected to Reverse Nine-Month Tablet S...
Apple and Samsung combined accounted for 62 percent of the nearly 36 million branded tablets shipped in 3Q 2014, according to early vendor shipment share estimates from market intelligence firm ABI... Read more
Stratos: 30 Percent of US Smartphone Owners t...
Stratos, Inc., creator of the Bluetooth Connected Card Platform, has announced results from its 2014 Holiday Mobile Payments Survey. The consumer survey found that nearly one out of three (30 percent... Read more
2014 1.4GHz Mac mini on sale for $449, save $...
 B&H Photo has lowered their price on the new 1.4GHz Mac mini to $449.99 including free shipping plus NY tax only. Their price is $50 off MSRP, and it’s the lowest price available for this new... Read more
Check Apple prices on any device with the iTr...
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
64GB iPod touch on sale for $249, save $50
Best Buy has the 64GB iPod touch on sale for $249 on their online store for a limited time. Their price is $50 off MSRP. Choose free shipping or free local store pickup (if available). Sale price for... Read more
15″ 2.2GHz Retina MacBook Pro on sale for $17...
 B&H Photo has the 2014 15″ 2.2GHz Retina MacBook Pro on sale for $1799.99 for a limited time. Shipping is free, and B&H charges NY sales tax only. B&H will also include free copies of... Read more
New Logitech AnyAngle Case/Stand Brings Flexi...
Logitec has announced the newest addition to its suite of tablet products — the Logitech AnyAngle. A protective case with an any-angle stand for iPad Air 2 and all iPad mini models, AnyAngle is the... Read more
Notebook PC Shipments Rise Year-Over-Year as...
According to preliminary results from the upcoming DisplaySearch Quarterly Mobile PC Shipment and Forecast Report, the global notebook PC market grew 10 percent year-over-year in Q3’14 to 49.4... Read more

Jobs Board

*Apple* Solutions Consultant (ASC)- Retail S...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager, *Apple* Financial Services...
**Job Summary** Apple Financial Services (AFS) offers consumers, businesses and educational institutions ways to finance Apple purchases. We work with national and Read more
*Apple* Store Leader Program - College Gradu...
Job Description: Job Summary As an Apple Store Leader Program agent, you can continue your education as you major in the art of leadership at the Apple Store. You'll Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.