Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
114 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

C++ Trees Part 1


3. Using the core::tree<>

C++'s STL implementation is genius. The advantages and subtleties of its implementation are so numerous, it is impossible to cover them in a single article, or even in a single book. It was with STL in mind, that the core::tree<> was designed. The core::tree<> container follows as many of the STL design practices as possible, while still ensuring its own tree behavior remains correct.

The core::tree<> implements both const_iterators and iterators for tree iteration. By default, it uses operator<() and operator==() for inserts and finds/removes, but allows predicates to be used to overload that functionality. The core::tree<> implements begin() and end() on its containers as well as post-increment and pre-increment on its iterators. For moving in and out within the tree, methods in() and out() can be called – this makes tree depth iteration very simple. Many other powerful pieces of functionality are implemented as well, such as size(), level() and, of course, full tree copying (just like all STL containers) by use of operator=().

Perhaps the biggest downfall of the std::map<> tree implementation is its lack of simple "complete" tree copying. Calling operator=() on the std::map<> would result in pointer copying, not object copying and implementing a full tree copy would require even more dynamical memory allocation introducing more possibilities for erroneous programmer made memory management mistakes (more memory leaks).

Again, the above problems dissolve when using the core::tree<>. Copying a tree into another tree is as simple as:

   core::tree<Leaf> tree1;
   // ... do work on tree1 here
   // now copy the entire contents of tree1 into tree2
   core::tree<Leaf> tree2 = tree1;

Thus, the core::tree<> container's learning curve is very low for anyone who is already familiar with C++'s STL containers.

The below sample code demonstrates the ease of use of the core::tree<> container. The code in figure 3.1 performs simple tree construction and tree output.

#include <iostream>
#include "tree.h"

void fun()
{
   // the tree containers all sit inside the core namespace
   using namespace core;
   using namespace nTreeData;

   tree<Leaf> leafTree;

   ////////////////////////////////////////////////////
   // create a simple leaf tree
   ////////////////////////////////////////////////////
   for (int i = 0; i < kMaxLeaves; ++i)
   {
      // insert a starter leaf
      tree<Leaf>::iterator iter = leafTree.insert(Leaf(i));

      // continue inserting children each time
      for (int depth = 0; depth < kMaxDepth; ++depth)
      {
         // insert and step into the newly created branch 
         iter = iter.insert(Leaf(depth));
      }
   }

   ////////////////////////////////////////////////////
   // output the leaf tree
   ////////////////////////////////////////////////////
   for (tree<Leaf>::const_iterator iter = leafTree.begin();
        iter != leafTree.end();
        ++iter)
   {
      std::cout << iter.data().value() << std::endl;

      tree<Leaf>::const_iterator inner = iter;
      // tree's iterators are containers themselves - use the
      // same iterator to traverse inwards through the tree
      for (inner = inner.in(); inner != inner.end();
           inner = inner.in())
      {
         for (int tabs = 1; tabs < inner.level(); ++tabs)
            std::cout << "\t";

         std::cout << (*inner).value() << std::endl;
      }
   }
}
Figure 3.1

For clarity, a step-by-step analysis of the core::tree<> code in figure 3.1 is given below.

  1. Construct the tree container:

    tree<Leaf> leafTree;
    
  2. Populate the tree with data. The outer for loop inserts branches into the root tree. The inner for loop inserts branches into each additional branch inserted. Thus, the outer for loop is a breadth population and the inner for loop is a depth population. Notice that the inner for loop assigns the inserted iterator to itself: iter = iter.insert(). This forces iter to continue stepping inward, becoming the iterator of the branch inserted by the iter.insert() operation.

    for (int i = 0; i < kMaxLeaves; ++i)
    {
       // insert a starter leaf
       tree<Leaf>::iterator iter = leafTree.insert(Leaf(i));
    
       // continue inserting children each time
       for (int depth = 0; depth < kMaxDepth; ++depth)
       {
          // insert and step into the newly created branch 
          iter = iter.insert(Leaf(depth));
       }
    }
    
  3. Iterate through the tree. The outer for loop iterates through the branches of the root tree. The inner for loop iterates inward. Again, notice how inner = inner.in() is performed within the nested for loop. This forces the inner iterator to continue to step into itself until there are no further branches inward.

    for (tree<Leaf>::const_iterator iter = leafTree.begin();
         iter != leafTree.end();
         ++iter)
    {
       std::cout << iter.data().value() << std::endl;
    
       tree<Leaf>::const_iterator inner = iter;
       // tree's iterators are containers themselves - use
       // the same iterator to traverse inwards through the tree
       for (inner = inner.in(); inner != inner.end();
            inner = inner.in())
       {
          for (int tabs = 1; tabs < inner.level(); ++tabs)
             std::cout << "\t";
    
          std::cout << (*inner).value() << std::endl;
       }
    }
    
  4. The output of the leafTree that's built above is as follows:

    0
           0
                   1
                           2
                                   3
                                           4
    1
           0
                   1
                           2
                                   3
                                           4
    2
           0
                   1
                           2
                                   3
                                           4
    3
           0
                   1
                           2
                                   3
                                           4
    4
           0
                   1
                           2
                                   3
                                           4
    5
           0
                   1
                           2
                                   3
                                           4
    6
           0
                   1
                           2
                                   3
                                           4
    7
           0
                   1
                           2
                                   3
                                           4
    8
           0
                   1
                           2
                                   3
                                           4
    9
           0
                   1
                           2
                                   3
                                           4
    

As you can see from the above output the root of the tree has ten branches. Each of those ten branches contain five inner branches, all nested within each other. Analyzing the output in step 4 can aid in understanding the code in step 3.

Due to the core::tree<> design following some of the STL container paradigms, certain STL algorithms can be followed. For example, the std::for_each algorithm can be used to iterate across any breadth of tree (keep in mind, tree depth iteration requires a bit more work). Figure 3.2 demonstrates a simple core::tree<> implementation using std::for_each.

#include <algorithm>
#include <iostream>
#include "tree.h"

////////////////////////////////////////////////////
void outputLeaf(const Leaf &l)
{
   std::cout << l.value() << std::endl;
}

////////////////////////////////////////////////////
void fun()
{
   core::tree<Leaf> leafTree;

   for (int i = 0; i < nTreeData::kMaxLeaves; ++i)
      leafTree.insert(Leaf(i));
   std::for_each(leafTree.begin(), leafTree.end(), outputLeaf);
}
Figure 3.2

To perform complete tree output iteration (both breadth and depth) in a single function, a minor amount of recursion is generally suggested (although it can be performed iteratively). However, the code is still very straightforward and easy to write:

#include <iostream>
#include "tree.h"

////////////////////////////////////////////////////
void outputLeaf(core::tree<Leaf>::const_iterator &tree)
{
   // a tree iterator can check itself for its end
   for (core::tree<Leaf>::const_iterator i = tree.begin();
        i != tree.end(); ++i)
   {
      for (int tabs = 1; tabs < i.level(); ++tabs)
         std::cout << "\t";
      std::cout << (*i).value() << std::endl;

      outputLeaf(i);
   }
}
   
////////////////////////////////////////////////////
void fun()
{
   // the tree containers all sit inside the core namespace
   using namespace core;
   using namespace nTreeData;

   core::tree<Leaf> leafTree;

   //for (int i = 0; i < nTreeData::kMaxLeaves; ++i)
   //   leafTree.insert(Leaf(i));
   ////////////////////////////////////////////////////
   // create a simple leaf tree
   ////////////////////////////////////////////////////
   for (int i = 0; i < kMaxLeaves; ++i)
   {
      // insert a starter leaf
      tree<Leaf>::iterator iter = leafTree.insert(Leaf(i));

      // continue inserting children each time
      for (int depth = 0; depth < kMaxDepth; ++depth)
      {
         // insert a 100 placeholder leaf, then insert a leaf
         // and step into it
         iter.insert(Leaf(100));
         iter = iter.insert(Leaf(depth));
      }
   }

   outputLeaf(static_cast<core::tree<Leaf>::const_iterator >(leafTree));
}
Figure 3.3

Figure 3.3 will properly output a tree with any number of branches within any given branch. Additionally, figure 3.3 demonstrates a fundamental difference between core::tree<> containers and STL containers:

core::trees<> are core::tree<>::iterators.

The last line of code in figure 3.3 shows the static_cast<> operation converting a core::tree<> into a core::tree<>const_iterator. This is a fundamental deviation and necessity for the core::tree<> implementation. This concept alone, is what makes the core::tree<> container possible. More detailed explanation is given about this concept in the next portion of the core::tree<> series.





Conclusion


Contents
  Introduction
  std::map<> versus core::tree<>
  Using the core::tree<>
  Conclusion

  Printable version
  Discuss this article

The Series
  Part 1
  Part 2