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

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-22 20:00:45

"Thorsten Ottosen" <nesotto_at_[hidden]> wrote in message 
news:cvff74$fi3$1_at_sea.gmane.org...

> The ad hoc implementation of a tree is not exactly "industrial strength" 
> :-)

Ahh yes, it definitely needs some beefing up to be of boost quality. =) If 
we start getting into serious design discussions and decide on a proper way 
to do things, I'd be more than happy to spend the required time to really 
raise the bar on the interfaces, internal implementation, template params 
(allocators), etc..

> One major issue with the design: I don't like that iterators are trees. It
> must be possible to break the two concepts apart like in

Thorsten, you're absolutely right - that's really the big "question", the 
one I've struggled with for months really. I could definitely design the 
tree so iterators are not trees, but I'm not sure that's correct. The big 
problem by separating them out is that tree functionality is really required 
within an iterator - not because it can't be done outside of the iterator 
(as you've pointed out, it surely must be possible), but because nodes 
within trees are naturally trees themselves. This is not to say I can't be 
swayed on this, I am definitely up for a dialogue here =).

In my second article I spend a good five pages discussing just this point, 
here are two highlights:

1) Iterator should be trees because Knuth says so =) (I'm only half serious 
here, but I think Knuth has a very valid point):

The term "tree" and "subtree" will follow Knuth's definition from The Art of 
Computer Programming [2]:

A finite set T of one or more nodes such that:

a)    there is one specially designated node called the root of the tree, 
root(T); and
b)    the remaining nodes (excluding the root) are partitioned into m >= 0 
disjoint sets T1, ..., Tm, and each of these sets in turn is a tree. The 
trees T1, ..., Tm are called the subtrees of the root.

In short, the above definition says "trees are defined by trees". 
Truthfully, there is no distinction between a node in a tree and the tree 
itself (as all nodes in a tree are trees themselves). Knuth notes that his 
definition of trees is a recursive one, as he defines trees in terms of 
trees. He further explains that trees can be defined in nonrecursive ways, 
yet it is most appropriate to define trees recursively as recursion is an 
innate characteristic of tree structures [3].

2) This example shows the how inserts are done into subtrees from iterators:

    core::tree<char> t;
    *t = 'a';
    t.insert('b');
    t.insert('c');

    core::tree<char>::iterator iter;

    // find the 'b' node
    iter = t.find('b');

    // insert nodes d and e inside the b tree
    iter.insert('d');
    iter.insert('e');

    // find the 'c' node
    iter = t.find('c');

    // insert nodes f and g inside the c tree
    iter.insert('f');
    iter.insert('g');

I think this is an important point simply because it shows that the iterator 
iter is required to act as a container in order to satisfy "natural" 
characteristics of a tree. Otherwise, the base tree t would be required for 
all inserts and natural iteration through a tree (determined by the 
programmer) would become extremely difficult to "conceptually" understand. 
Not to say that would be wrong, Kasper Peeter's does this with his tree 
implementation. However, I personally, see the concept of the iterator 
functionally changing when dealing with trees.

My second article (http://nodeka.com/TreePart2.pdf) explains these points 
much better with pictures. =)

>
> tree<T>::level_iterator i = the_tree.level_begin();
> tree<T>::recursive_iterator ii = the_tree.recursive_begin();
>
> I do think it would be good to have several
> iteration strategies over the trees:
>
> 1. depth first
> 2. breadth first
> 3. on one level (ei, no recursion)
>

I completely agree with you on multiple types of iterators - and they 
wouldn't be hard to create. Additionally, I already have "finds" on all 
three points you pointed out above:

    1) find_tree_depth() (with or without iterator starting point, with or 
without predicate)
    2) find_tree_breadth() (with or without iterator starting point, with or 
without predicate)
    3) find() (level only, with or without iterator starting point, with or 
without predicate)

> For all iterators I would like to be able to say
>
> if( i.is_leaf() ).

That's a great suggestion too - I don't have that as a direct function call, 
but can achieve it by this:

    if (0 == i.size()) // it's a leaf if its size is 0, since it's checking 
the number of the elements it contains

Thanks for the great feedback,
Justin