Boost logo

Boost :

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

"Rene Rivera" <grafik.list_at_[hidden]> wrote in message
> 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 ( 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..

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. =)

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