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

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-23 00:46:14

"Rene Rivera" <grafik.list_at_[hidden]> wrote in message 
news:421C0E3A.3080003_at_redshift-software.com...
>
> Obviously there's interest ;-) But..
>
> Like Thorsten I would think it a requirement that some basic 
> interfaces/concepts come ahead of an implementation. What I don't see from 
> your proposal, nor Kaspers tree, is some consideration for what makes a 
> container a tree. I think we desperately need some definitions of what 
> operations should be part of a tree, n_ary_tree, binary_tree, rank_tree, 
> b_tree, etc.

Hi Rene - you make an excellent point here. The more I think about this, the 
more I realize, perhaps a step back to look at what we're really trying to 
achieve is the way to solve this.

>
> Additionally, I'm also of the opinion that the "iterator" concept should 
> be kept as it's currently used in STL. An object that does more than an 
> iterator, because it happens to be an iterator in a tree should be called 
> something else, "cursor" comes to mind. If it's really masquerading as a 
> sub-tree, or a tree, then call it a tree.

Hmmm ... =) you might be right. Still, have you read my explanation behind 
this argument (http://nodeka.com/TreePart2.pdf)? I'm not saying I disagree 
with you, but rather I want to make sure we're on the same page on the 
reasoning behind this node/sub-tree/tree/iterator/branch definition. =) Damn 
that Knuth for shaping my thoughts on trees!

> But to not talk in a complete vacuum here's my implementation of a 
> rank_tree..
>
> http://redshift-software.com/~grafik/RankTree.h

Wonderful code. =)

> I think the most important aspect we need to keep in mind is that having a 
> tree container, or a set of tree containers, is not to have basic n-ary 
> tree to build from. But to have generic algorithms, programs, iterators, 
> mutators, etc. that can operate on different kinds of tree implementations 
> so that programmers can make storage and algorithmic trade offs in 
> programs. Having a n-ary tree in STL doesn't help me much because I would 
> never use it. But having various tree implementations in STL such that I 
> can write an algorithm that works regardless of which type of tree i use 
> it on is the real win.

Yes, I completely agree with you here. The reason behind my initial 
implementation of the core::tree was to do just that - create a framework 
that will allow multiple types of trees to be constructed from it. However, 
it's the details that we differ on - I see using the n-ary tree path as the 
perfect means to achieving our mutual goal, because it can be wrapped inside 
its end-resultant tree and then expose only the interfaces (and iterators) 
necessary for that tree. Additionally, I see usefulness in n-ary trees for 
generalized tree container purposes, rather than algorithmic constructs.

Your rank tree is really making me think about this in more detail, perhaps 
this is the biggest roadblock of the generic tree path - there are such a 
wide ranging purposes for trees, coming to a common goal that achieves all 
generalized purposes may be challenging. =)

At any rate, this is great intellectual stimulation ... I personally am 
going to take a step back and think about this whole tree thing for a bit 
(my brain is beginning to hurt). Maybe walking the dog will give some 
revelations. =)
Justin