Section 4 - Traversals and Functors

9A.4.1 Tree Traversals

tree pic 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. We review the public version, which takes no parameters, and then calls its private (recursive) work-horse. Here is the public version again:

void display() const { display(mRoot, 0); }

And here, again, is the kernel of often private (but which we made public) recursive partner:

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

  cout << treeNode->data  << endl;
  display( treeNode->firstChild, level + 1 );
  if (level > 0)
  display( treeNode->sib, level );
}

Here you have the two main parts of every traversal.

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

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.

9A.4.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 traverse()) 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 traverse() and specify the task to be performed?

The general idea is that we provide a traverse() member function that works like display() but takes, as a parameter, the task function. Then traverse() 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 the 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 . . .
---------------------------------------- */

9A.4.3 A Tree Traversal Method that Takes a Functor

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

define a public, client callable traverse() which implies we want to recurse the entire tree, which would call (passing the master root)...
... a recursive version of traverse() that visits each node in the subtree defined by the tree node passed in, and
pass a functor to either traverse() so that the client can decide what to do when visiting each node.

To simplify the syntax, I will define both traverse()s completely within the FHtree prototype. In the FHtree.h file, I prototype the recursive traverse() inside the FHtree class prototype, and define that version externally.

First, we show the definition of the traverse() methods.

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

public:
  // ... prototypes omitted

  // usual client interface (entire tree implied)
  template <class Processor>
  void traverse(Processor func) const { traverse(func, mRoot, 0); }

  // often helper of typical public version, but also client-callable on a subtree
  template <class Processor>

  void FHtree<Object>::traverse(Processor func, FHtreeNode<Object> *treeNode, int level)
  const
  {
   if (treeNode == NULL)
     return;

   func(treeNode->data);

   traverse(func, treeNode->firstChild, level+1);
   if (level > 0)
     traverse(func, treeNode->sib, level);
  }
};

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 left rear paw right rear paw lef
t front paw right front paw
Press any key to continue . . .
-------------------------------------------- */

Of course, there is no indentation. However, that is left as an exercise for the reader.