Boost logo

Boost :

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

"Thorsten Ottosen" <nesotto_at_[hidden]> wrote in message

> 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';

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

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

    // insert nodes d and e inside the b tree

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

    // insert nodes f and g inside the c tree

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 ( 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,

Boost list run by bdawes at, gregod at, cpdaniel at, john at