[boost] Re: Boost library inclusion: generic tree containers?

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-22 21:53:36

"Fredrik Blomqvist" <fredrik_blomqvist_at_[hidden]> wrote in message 
news:cvfhbf$n4i$1_at_sea.gmane.org...
>I haven't studied your proposal in detail yet, but - I think it would be
> valuable
> for further discussion if you could compare your tree implementation to
> Kasper Peeter's version: http://www.damtp.cam.ac.uk/user/kp229/tree/

Hi Fredrik - thanks for your feedback. =)

After quickly looking through Kasper's design, I see the fundamental 
difference between my tree and Kasper's is that Kasper attempts to cover all 
possible tree iterations by definition of all possible types of iterators. 
My tree implements an iterator that functions as a tree and therefore 
naturally covers all possible types of iterations - given any node within 
the tree, you can iterate however you like (in, out, ++, --) from that node.

As I was saying in response to Thorsten's post, I have defined my iterator 
as a tree itself (yes, this may end up being a topic of great 
discussion/contention =), so the natural semantics of trees are seen in the 
way it works. Kasper's design is very nice (and his code is more refined 
than mine, that's for sure), but is a bit "difficult" to manage relatively 
simplistic behavior. Again, this isn't because his design is flawed, rather 
it is because he is trying to follow the semantics of STL iterators, one 
which I intentionally deviated from due to my decision that tree nodes are 
trees and iterators take on different meanings when constructing trees (due 
to their recursive nature).

>From his webpage example, we can compare how the two of us build and output 
the same tree:

Kasper's tree and output:

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i)
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

Performing the same behavior, my tree and output:

int main()
{
   core::tree<string> tr;
   core::tree<string>::iterator iter, inner, two, banana;

   tr.data("one");
   two = tr.push_back("two");
   two.push_back("apple");
   banana = two.push_back("banana");
   banana.push_back("cherry");
   two.push_back("peach");
   tr.push_back("three");

   for (iter = two.begin(); iter != two.end(); ++iter) cout << *iter << 
endl;
   cout << endl;

   for (iter = two.begin(); iter != two.end(); ++iter) {
      cout << *iter << endl;
      for (inner = iter.begin(); inner != iter.end(); ++inner) {
         cout << "  " << *inner << endl;
      }
   }
}

The fundamental difference is that Kasper's tree uses iterators that 
strictly follow STL's understanding of iterators (flat-containers), whereas 
my tree uses iterators as trees, thus the natural semantics of trees are 
maintained so the code (at least to me) is more simplistic.

Additionally as you suggested above, I can add a number of iterators to my 
tree to perform any type of iteration - and doing such will allow standard 
algorithms to be used as they would on flat containers (if that's the goal 
of the iterator being created). However, that can also be achieved by the 
programmer which is really what I was shooting for. The fundamental driving 
force of my tree design was to create a framework where any type of tree 
could be constructed from its base functionality. I was driving for a 
front-end that is inherently simplistic to use and conceptualize by the 
programmer allowing him or her to construct their own trees and that 
behavior as needed.

Lastly, in my second article, I explain the reasoning behind my design much 
better than I do here. I'd be very curious to know yours and others thoughts 
on that (http://nodeka.com/TreePart2.pdf). I'm sorry the file is so big - 
ack!

Thanks again for the delightful interchange and insight, =)
Justin