"Rene Rivera" <grafik.list@redshift-software.com> wrote in message news:421C0E3A.3080003@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..
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