Section 3 - Traversals and Functors

4A.3.1 Tree Traversals

The FHtree::display() method is a special case of something called a tree traversal, or just traversal. In a traversal, we process (or visit) every node of the tree exactly once. This, like almost all tree processes, is a recursive venture. Before showing the entire function, let's look at the kernel of the function:

template <class Object>
void FHtree<Object>::display(
   FHtreeNode<Object> *treeNode) const
{
   FHtreeNode<Object> *child;

   // pre-order processing done here ("visit")
   cout << treeNode->data  << endl;
   
   // recursive step done here
   for (child = treeNode->firstChild; 
        child != NULL; 
        child = child->sib)
      display(child);
}

Here you have the two main parts of every traversal.

• The visit step does the actual processing on the current node.
• The recursive step calls the function recursively, processing some smaller subtree (or subtrees).

You don't see an if statement, suggesting there is something wrong with the traversal algorithm (recursion needs an escape valve), but it's there in the guise of a for-loop. Eventually, treeNode will be a leaf because we keep going lower in the tree, and when that happens there are no children. So the loop is a null loop, and the recursion stops.

The above function will not really work as is because it has some key protection left out ( intentionally, to help us inspect the salient features of the traversal). So I will supply the full display() method below. It adds the indentation by using a static local (Java programmers take note: you can't do static locals in Java). static locals are very useful in recursion because they allow a neat and efficient communication between recursive calls and do not contribute to inflating function stack size. Keep in mind that we come into this method with a default value of treeNode = NULL, meaning that we want to display everything.

template <class Object>
void FHtree<Object>::display(FHtreeNode<Object> *treeNode, int level) const
{
   FHtreeNode<Object> *child;

   // this will be static and so will be shared by all calls
   static string blankString = "                                    ";
   string indent;

   // stop runaway indentation/recursion
   if  (level > (int)blankString.length() - 1)
   {
      cout << blankString << " ... " << endl;
      return;
   }

   indent = blankString.substr(0, level);

   if (mRoot == NULL)
      return;
   if (treeNode == NULL)
   {
      display(mRoot);
      return;
   }

   cout << indent << treeNode->data  << endl;
   for (child = treeNode->firstChild; child != NULL; child = child->sib)
      display(child, level+1);
}

The above is called a pre-order traversal because we process the node (visit step) before the recursive calls. If we had first made the recursive calls and done the visit step afterwards, it would be a post-order traversal. If we did some recursive calls, visited the node, then did the remainder of the recursive calls, it would be an in-order traversal.

Warning: while these traversal terms are standard vocabulary, the "visit step" is my own invention, so don't expect anyone to understand this phrase without an explanation.

4A.3.2 Functors

The above function, display() not only traverses the tree, but also performs a specific task when each node is visited, namely performing a cout on treeNode->data. If you think about it, we might want to do any number of different tasks in a traversal, some having nothing to do with screen output. It would be nice if we could call a general function (called traversal()) that looked like display() but which traversed the tree, visiting each node, but not committing to a particular task. How, then, would a client call traversal() and specify the task to be performed?

The general idea is that we provide a traversal() member function that works like display() but takes, as a parameter, the task function. Then traversal() could, in the visit step, i.e., in place of cout << treeNode->data;, call the task function that the client passed down.

All this dreaming is predicated on the hope that we can pass a function as a parameter to another function. We can. The way this is handled in C++ is with function objects aka functors.

Defining the Functor

Functors are very short classes that contain only one method and no data. What method? An overloading of the () operator (the parens). Here is an example of a functor (defined at global scope above a client):

class PrintMom
{
public:
   void operator()( )
   {
      cout << "hi mom" ;
   }
};

The double parens, () ( ), might confuse you, but don't let them. The first () is always empty and tells the compiler that we are overloading the () operator (as opposed to, say the ++ or * operator). The second ( ) is where any formal parameters might go for the operator. I put a space in there to help distinguish the two sets of parens, but the space is only for humans. In the example above, there were no parameters, so it happened that both sets of parens were empty. If we wanted operator to take a parameter, it might look like this:

class PrintString
{
public:
   void operator()(string s)
   {
      cout << s << endl;
   }
};

Instantiating and Invoking a Functor

Next, we have to instantiate an object of the Functor. We do this as with any class:

int main()
{
   PrintString g;

   g("Does this really work?");
   g("Apparently");
   ...

As you can see, overloading the () operator allows us to use it in the expected way. The object, g, tells C++ that when it is followed by "(some string)", the () operator, an instance method, must be invoked. It looks just like a global function call. This is not, however, how we would normally use a functor.

Defining a Function that Takes a Functor Argument

The reason we define a functor object, g, is so we might pass g as a parameter to a function. Here is a non-template version of a function that takes a PrintString object as a parameter:

void ShowArrayUsingThisFunc( PrintString g )
{
   string myArray[] = {"hi", "mom!", "3", "45", "this is wild"};
   int k;

   for (k = 0; k < sizeof(myArray)/sizeof(myArray[0]); k++)
      g(myArray[k]);
}

This global scope function will apply the functor object g to each element of the array. It is really not much more sophisticated than what we did in the last section. Now, we are simply passing g to a function and using it in the function, rather than using it in the client. Here is full example plus run:

class PrintString
{
public:
   void operator()(string s)
   {
      cout << s << " ";
   }
};

void ShowArrayUsingThisFunc( PrintString g )
{
   string myArray[] = {"hi", "mom!", "3", "45", "this is wild"};
   int k;

   for (k = 0; k < sizeof(myArray)/sizeof(myArray[0]); k++)
      g(myArray[k]);
}
int main()
{
   PrintString g;

   g("Does this really work?");
   g("Apparently");
   cout << endl;

   ShowArrayUsingThisFunc(g);
   cout << endl;

}

/* ------------------ RUN -------------

Does this really work? Apparently
hi mom! 3 45 this is wild

-------------------------------------- */

Using Functors With Templates

We take our next step now, which applies the above ideas to templates. There are two different template opportunities, and we demonstrate them both at once.

• We templatize our functor class so we can use it to cout any object type (that supports the cout << functionality).

template <typename Object>
class PrintObject
{
public:
   void operator()(Object obj)
   {
      cout << obj << " ";
   }
};

• We templatize our function that takes the functor, so that it can accept a functor of any kind. While we're at it, we may as well allow it to take any kind of array, so we simultaneously templatize the array parameter.

template <class ArrayType, class FunctorType>
void ShowArrayUsingFunc( ArrayType myArray[], int size, FunctorType g )
{
   int k;

   for (k = 0; k < size; k++)
      g(myArray[k]);
   cout << endl;
}

The completely generalizes our functor and the function that processes the array. Here is the client, defined below

#include <iostream>
#include <string>
using namespace std;

// templates omitted (see above boxes)

int main()
{
    // create two different functors
   PrintObject<int> intPrinter;
   PrintObject<string> stringPrinter;

   // create two different kinds of arrays
   int someInts[] = {3, 5, 7, 9, 11};
   string someStrings[] = {"twitter", "lhc", "c++", "korfu", "health care"};

   ShowArrayUsingFunc(someInts, 5, intPrinter);
   ShowArrayUsingFunc(someStrings, 5, stringPrinter);
   cout << endl;
   return 0;
}

/* ------------------ RUN -----------------
3 5 7 9 11
twitter lhc c++ korfu health care

Press any key to continue . . .
---------------------------------------- */

4A.3.3 A Tree Traversal Method that Takes a Functor

We now apply all of this to our original problem. We wish to

1. define a traverse() method that works much like display(), visiting each node in the tree, and
2. pass a functor to traverse() so that the client can decide what to do when visiting each node.

The rules for doing this can be found above. Just apply them directly. To simplify the syntax, I will define traverse() completely within the FHtree prototype. In the FHtree.h file, I prototype traverse() inside the FHtree class prototype, and define traverse() externally.

First, we show the definition of traverse().

// ---------------------- FHtree Prototype --------------------------
template <class Object>
class FHtree
{
private:
   int mSize;
   FHtreeNode<Object> *mRoot;

public:
   // ... prototypes omitted

   template <class Processor>
   void traverse(Processor func, FHtreeNode<Object> *treeNode = NULL) const
   {
      FHtreeNode<Object> *child;

      if (mRoot == NULL)
         return;
      if (treeNode == NULL)
      {
         traverse(func, mRoot);
         return;
      }

      func(treeNode->data);

      for (child = treeNode->firstChild; child != NULL; child = child->sib)
         traverse(func, child);
   }
};

Here we have pulled only the bare essentials from display() and abstracted them in this traverse() method. The indentation code has been removed because we are not necessarily printing anything. This traversal may be a purely computational one. Only the author of the functor Processor func, passed down as an argument, knows what func() is going to do.

Here is how the client uses this new traverse() method, rather than the specialized display(), to show the contents of the tree:

// FHtree main
// CS 2B/C, Foothill College, Michael Loceff, creator

#include <iostream>
#include <string>
using namespace std;
#include "FHtree.h"

template <typename Object>
class PrintObject
{
public:
   void operator()(Object obj)
   {
      cout << obj << " ";
   }
};

int main()
{
   FHtree<string> sceneTree;
   FHtreeNode<string> *tn;

   // code that builds the tree identical to previous program - omitted

   PrintObject<string> formatlessStringPrinter;
   sceneTree.traverse( formatlessStringPrinter );
   cout << endl;

   return 0;
}

/* ------------------ RUN -------------
room table south west leg south east leg north west leg north east leg Miguel th
e human torso right arm right hand pinky ring finger middle finger index finger
thumb left arm left hand pinky ring finger middle finger index finger thumb Lily
 the canine torso wagging tail spare mutant paw right left paw right rear paw le
ft front paw right front paw
Press any key to continue . . .
-------------------------------------------- */

Of course, there is no indenting. In order to support that, we would have to add an int level parameter in our traverse() method, much as we did with display(), and make use of it in the client-supplied functor. However, that is left as an exercise for the reader.