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

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-24 01:32:36

"Richard Peters" <r.a.peters_at_[hidden]> wrote in message 
news:076301c51983$c5319ba0$0a01a8c0_at_campus.tue.nl...

> I think these formalizations of different parts of the tree is a very good
> start, but I'd like to see the iterator eliminated for a while, or at 
> least
> totally decoupled from the tree: The reason for this is Separation of
> Concerns. A tree class is a container quite similar like the standard
> containers in that it stores values, but the big difference is that the
> structure of the tree matters, instead of the sequence. Therefore, I think
> the tree class should provide functions to navigate through the tree, and
> functions to alter the structure of a tree, like insertion, deletion, and
> rotation. These functions should probably work on things like the
> above-defined cursor.

Hi Richard - your above points are extremely well made, and I've been swayed 
by yours (and the others arguments) about the iterator / cursor points. You 
and Rene are right, we should eliminate the concept of an iterator for 
awhile, it's just getting in the way of us defining a generic tree.

> Once this tree class is built, then it is time to start thinking how the
> structure of the tree should be translated to flat sequences. There are of
> course a lot of options: depth first, breadth first, only a single level, 
> or
> from top to a single node. Navigating in this way is done via 'normal'
> iterators. These iterators work on cursors, and should not be a part of 
> the
> tree class itself (the iterator type should not be a member of the tree
> class). These iterators are like 'cursor-to-iterator adaptors'.
>
> So I guess my point is this: The tree doesn't need a normal or default or
> any iterator type, because it doesn't have a proper meaning: a tree is 
> about
> structure, not about sequence. Translating that structure into a sequence
> can be done outside the tree.

These are all interesting points and I think you've hit the concepts we need 
to focus on square on the head.

As Larry and I were discussing just above this, I currently think we have 
two main design concerns to tackle:

    1) container trees
    2) algorithmic trees

As you pointed out, the structure of the tree is the important aspect, not 
the delivery system of that structure (that can be determined afterwards).

However, the reason I'm narrowing my focus to the above two types of trees 
is because I'm seeing differing opinions on the goals of a "tree" and I 
think both are valid. I currently think that we should try to identify the 
overlapping characteristics of the two fundamental types of trees and then 
begin working on identifying how that commonality can be implemented in our 
base tree definition, to achieve both ends in an elegant and robust manner.

I fear even this distinction may be getting too low into detail, but I worry 
that without putting both types of trees in the picture before a base tree 
is defined, either group will feel slighted and believe our interests are 
not going to achieve their goals.

Thanks for your insight Richard, =)
Justin