----- Original Message ----- From: "Rene Rivera" <grafik.list@redshift-software.com>
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. If it's a pointer to a node in the tree, then perhaps a "node_pointer". Mixing the terms will just cause more confusion than it's worth. Reading some of your later posts I can see the confusion already creeping in. My suggestion would be for you to formalize the different parts of a tree:
* node; Holder for the value, structure pointers, and tree coloring information
* cursor; pointer to a node with tree specific operations to move the cursor within the tree and to interrogate the tree
* iterator; linear traversal of the nodes in the tree
* tree; the container of nodes and producer of cursors and iterators, and the needed allocators
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. 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. best regards, Richard Peters