# Boost :

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