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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Viber 11.9.1 - Send messages and make fr...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
Vallum 3.3.2 - $15.00
Vallum is a little tool that helps you monitor and block apps connections and throttle apps bandwidth. It is able to intercept connections at the application layer, and hold them while you decide... Read more
Microsoft OneNote 16.31 - Free digital n...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more
Apple Pages 8.2.1 - Apple's word pr...
Apple Pages is a powerful word processor that gives you everything you need to create documents that look beautiful. And read beautifully. It lets you work seamlessly between Mac and iOS devices, and... Read more
Numbers 6.2.1 - Apple's spreadsheet...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
f.lux 39.9873 - Adjusts the color of you...
f.lux makes the color of your computer's display adapt to the time of day, warm at night and like sunlight during the day. Ever notice how people texting at night have that eerie blue glow? Or wake... Read more
Deeper 2.5.0 - Enable hidden features in...
Deeper is a personalization utility for macOS which allows you to enable and disable the hidden functions of the Finder, Dock, QuickTime, Safari, iTunes, login window, Spotlight, and many of Apple's... Read more
NTFS 15.5.71 - Provides full read and wr...
NTFS breaks down the barriers between Windows and macOS. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS. Write, edit, copy, move, delete files on NTFS... Read more
MTR 5.3.0.0 - The Mac's oldest and...
MTR (was MacTheRipper)--the Mac's oldest and smartest DVD-backup app. MTR - the complete toolbox, not a one-trick, point-and-click extractor. MTR is intended for making fair-use, backup copies of... Read more
Keynote 9.2.1 - Apple's presentatio...
Easily create gorgeous presentations with the all-new Keynote, featuring powerful yet easy-to-use tools and dazzling effects that will make you a very hard act to follow. The Theme Chooser lets you... Read more

Latest Forum Discussions

See All

Black Desert Mobile gets an official rel...
Pearl Abyss has just announced that its highly-anticipated MMO, Black Desert Mobile, will launch globally for iOS and Android on December 11th. [Read more] | Read more »
Another Eden receives new a episode, cha...
Another Eden, WFS' popular RPG, has received another update that brings new story content to the game alongside a few new heroes to discover. [Read more] | Read more »
Overdox guide - Tips and tricks for begi...
Overdox is a clever battle royale that changes things up by adding MOBA mechanics and melee combat to the mix. This new hybrid game can be quite a bit to take in at first, so we’ve put together a list of tips to help you get a leg up on the... | Read more »
Roterra Extreme - Great Escape is a pers...
Roterra Extreme – Great Escape has been described by developers Dig-It Games as a mini-sequel to their acclaimed title Roterra: Flip the Fairytale. It continues that game's tradition of messing with which way is up, tasking you with solving... | Read more »
Hearthstone: Battlegrounds open beta lau...
Remember earlier this year when auto battlers were the latest hotness? We had Auto Chess, DOTA Underlords, Chess Rush, and more all gunning for our attention. They all had their own reasons to play, but, at least from where I'm standing, most... | Read more »
The House of Da Vinci 2 gets a new gamep...
The House of Da Vinci launched all the way back in 2017. Now, developer Blue Brain Games is gearing up to deliver a second dose of The Room-inspired puzzling. Some fresh details have now emerged, alongside the game's first official trailer. [Read... | Read more »
Shoot 'em up action awaits in Battl...
BattleBrew Productions has just introduced another entry into its award winning, barrelpunk inspired, BattleSky Brigade series. Whilst its previous title BattleSky Brigade TapTap provided fans with idle town building gameplay, this time the... | Read more »
Arcade classic R-Type Dimensions EX blas...
If you're a long time fan of shmups and have been looking for something to play lately, Tozai Games may have just released an ideal game for you on iOS. R-Type Dimensions EX brings the first R-Type and its sequel to iOS devices. [Read more] | Read more »
Intense VR first-person shooter Colonicl...
Our latest VR obsession is Colonicle, an intense VR FPS, recently released on Oculus and Google Play, courtesy of From Fake Eyes and Goboogie Games. It's a pulse-pounding multiplayer shooter which should appeal to genre fanatics and newcomers alike... | Read more »
PUBG Mobile's incoming update bring...
PUGB Mobile's newest Royale Pass season they're calling Fury of the Wasteland arrives tomorrow and with it comes a fair chunk of new content to the game. We'll be seeing a new map, weapon and even a companion system. [Read more] | Read more »

Price Scanner via MacPrices.net

Weekend Sale: Apple AirPods Pro for $234.98 a...
Abt Electronics has Apple’s new AirPods Pro in stock and on sale today for $234.98 including free shipping and free returns. Their price is $15 off Apple’s MSRP for these AirPods and tie Amazon... Read more
New 2019 16″ MacBook Pros on sale for $100 of...
Apple Authorized Reseller Adorama has new 2019 16″ MacBook Pros on sale today for $100 off Apple’s MSRP, each including free shipping. In addition, Adorama charges sales tax for NY & NJ residents... Read more
Apple Watch Series 3 GPS models on sale for l...
Amazon has Apple Watch Series 3 GPS models on sale starting at only $179. There prices are the lowest we’ve ever seen for these models from any Apple reseller. Choose Amazon as the seller rather than... Read more
iOS Bug In Facebook News Feed Lets Device Ca...
NEWS: 11.15.19- Users of the Facebook social media platform’s mobile app running on iOS devices won’t, like, this piece of news one bit in where a bug in the News Feed gave access to the camera... Read more
16″ MacBook Pros on sale! Preorder at Amazon...
Apple’s new 16″ MacBook Pros were only introduced yesterday, but Amazon is already offering a $100 discount on preorders. Prices for the base 6-Core 16″ MacBook Pros start at $2299: – 2019 16″ 2.6GHz... Read more
Use our exclusive MacBook Price Trackers to f...
Our Apple award-winning MacBook price trackers are the best place to look for the best sales & lowest prices on new and clearance MacBook Airs and MacBook Pros–including Apple’s new 16″ MacBook... Read more
New November Verizon iPhone deal: Get an iPho...
Verizon has the 64GB iPhone Xr on sale for 50% off for a limited time, plus they will include a free $200 prepaid MasterCard and a free Amazon Echo Dot. That reduces their price for the 64GB iPhone... Read more
Apple cuts prices on clearance, refurbished 2...
Apple has clearance 2018 15″ 6-Core Touch Bar MacBook Pros, Certified Refurbished, now available starting at only $1829. Each model features a new outer case, shipping is free, and an Apple 1-year... Read more
Up to $450 price drop on clearance 15″ MacBoo...
B&H Photo has dropped prices Apple’s 2019 15″ 6-Core and 8-Core MacBook Pros by $400-$450 off original MSRP, starting at $1999, with free overnight shipping available to many addresses in the US... Read more
Here’s how to save $200 on Apple’s new 16″ Ma...
Apple has released details of their Education discount associated with the new 2019 16″ 6-Core and 8-Core MacBook Pros. Take $200 off the price of the new 8-Core model (now $2599) and $200 off the 16... Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**746887BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 001512-Ankeny-Store **Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**746836BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Store NUmber or Department:** 000341-Scranton-Store **Job Description:** **What Read more
QA Manager, *Apple* - CBS Corporation (Unit...
# QA Manager, Apple **REF#:** 35331 **CBS BUSINESS UNIT:** CBS Interactive **JOB TYPE:** Full-Time Staff **JOB SCHEDULE:** **JOB LOCATION:** Burbank, CA **ABOUT Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**744315BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000662-Auburn AL-Store **Job Description:** At Best Read more
Nurse Practitioner - Field Based (San Bernard...
Nurse Practitioner - Field Based (San Bernardino, CA, Apple Valley, Hesperia) **Location:** **United States** **New** **Requisition #:** PS30312 **Post Date:** 4 Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.