"Richard Peters" <r.a.peters@student.tue.nl> wrote in message news:076301c51983$c5319ba0$0a01a8c0@campus.tue.nl...
I think these formalizations of different parts of the tree is a very good start, but I'd like to see the iterator eliminated for a while, or at least totally decoupled from the tree: The reason for this is Separation of Concerns. A tree class is a container quite similar like the standard containers in that it stores values, but the big difference is that the structure of the tree matters, instead of the sequence. Therefore, I think the tree class should provide functions to navigate through the tree, and functions to alter the structure of a tree, like insertion, deletion, and rotation. These functions should probably work on things like the above-defined cursor.
Hi Richard - your above points are extremely well made, and I've been swayed by yours (and the others arguments) about the iterator / cursor points. You and Rene are right, we should eliminate the concept of an iterator for awhile, it's just getting in the way of us defining a generic tree.
Once this tree class is built, then it is time to start thinking how the structure of the tree should be translated to flat sequences. There are of course a lot of options: depth first, breadth first, only a single level, or from top to a single node. Navigating in this way is done via 'normal' iterators. These iterators work on cursors, and should not be a part of the tree class itself (the iterator type should not be a member of the tree class). These iterators are like 'cursor-to-iterator adaptors'.
So I guess my point is this: The tree doesn't need a normal or default or any iterator type, because it doesn't have a proper meaning: a tree is about structure, not about sequence. Translating that structure into a sequence can be done outside the tree.
These are all interesting points and I think you've hit the concepts we need to focus on square on the head. As Larry and I were discussing just above this, I currently think we have two main design concerns to tackle: 1) container trees 2) algorithmic trees As you pointed out, the structure of the tree is the important aspect, not the delivery system of that structure (that can be determined afterwards). However, the reason I'm narrowing my focus to the above two types of trees is because I'm seeing differing opinions on the goals of a "tree" and I think both are valid. I currently think that we should try to identify the overlapping characteristics of the two fundamental types of trees and then begin working on identifying how that commonality can be implemented in our base tree definition, to achieve both ends in an elegant and robust manner. I fear even this distinction may be getting too low into detail, but I worry that without putting both types of trees in the picture before a base tree is defined, either group will feel slighted and believe our interests are not going to achieve their goals. Thanks for your insight Richard, =) Justin