"Thorsten Ottosen" <nesotto@cs.auc.dk> wrote in message news:cvff74$fi3$1@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