christopher diggins wrote:
You do bring up very good points, and I am not sure what my position is yet so I will play the Devil's advocate for now. A useful tree iterator, in my view should provide access to the parent node from a given position in the tree. Without that algorithms, etc. are harder to write, and the tree is much harder to manage. Being able to move to a parent node makes the various traversals trivial (and without overhead as far as I can tell). I also do not believe that implementation should dictate interface. Implementations that try to save a pointer by not providing a pointer to the parent, are really just making life complicated for the sake of a few bytes. Arguably if space is that much of a concern perhaps the tree is not the right data structure for the job?
I agree with some of the points you make but perhaps I didn't make myself completely clear in the first place. I was not trying to make space or efficiency constraints limit the interface. My point was that the Concepts themselves should allow different implementations, the same way a you can have single- and double-linked lists implementations of a Sequence. Sure, for many applications you'll want every kind of traversal possible. But not in all important applications. For example, searching a binary search tree only requires parent-to-child traversal. My point is that you can have different trees, all exposing the same basic interface that can provide different traversal possibilities and different complexity tradeoffs. In my design a tree_iterator is categorized according to a VerticalTraversalCategory which can be Forward (only parent-to-child) or Bidirectional. So if a tree_iterator supports it you could: it.ascend(); it.descend(); ++it /* next sibling */; --it /* previous sibling */; A separate traits class tells us the particular traversal category of a tree_iterator. Based on this any algorithm can choose an implementation for the particular traversal categories or require tree_iterators of a specific category.
Inorder, preorder and postorder traversals are possible using a stack of ancestors. In the general case, though you shouldn't have to pay for this extra overhead at all times.
I am not convinced that there is *significant* overhead.
Well, IMO, *if and when* a tree_iterator does not provide access to the parent, keeping a stack of pointers to allow for traversals I may not need is significant overhead for a tree_iterator. If we also allow traversals to be reversible we would end up with an iterator that holds a pointer to every node in the tree. But my point is not that the overhead is significant in all cases. Only that it may be in some, so we cannot assume that every tree implementation will provide a single iterator for inorder/preorder/postorder and general tree traversal.
IMO a tree container should be just that. Preorder, postorder and inorder are ways to turn a tree into a sequence, I see them as views of the tree.
Yes. However traversing a tree is a rather common and important task for a tree data structure.
This is the main reason I'd prefer to have them as separate entities.
That or the overhead? If there is no *significant* overhead then why not allow a tree to provide a direct treatment as a sequence. Clearly the question becomes, what overhead is significant?
IMO, if this can be provided in a general way outside the tree it would keep the interface of a tree simpler. I see no reason why linear traversals cannot be provided in a general way outside trees without loss of efficiency or added overhead. Still, Thorsten makes the point that this will make for more cryptic error messages and less "pleasant" code. I'm not sure I agree with him on that, but only an implementation will tell ;)
Btw, here's my short view of a tree:
template <typename T> struct Tree { typedef /**/ tree_iterator; typedef /**/ const_tree_iterator; typedef /**/ sibling_iterator; typedef /**/ const_sibling_iterator;
tree_iterator root(); tree_const_iterator root() const; };
This appears to be good code (upon cursory examination) however I am really at only concerned with binary trees at this point. They are in my view very separate things from k-ary trees and mandate separate implementations. Do you agree?
I think we can single out binary trees and give them a specific interface (I did!) where it makes sense to do so, but without putting aside the general tree interface. I also think a Boost Tree library should not lose the opportunity to define general concepts that can work with different trees and not only k-ary trees.
As I said before, you make excellent points but I am not *yet* convinced that a tree should not be inherently treatable as a sequence.
If you can have a tree that is only a tree and outside means of linearizing the tree (as in a LinearView or something) can be provided only once in a general way, what keeps us from doing that? I view this as the member/non-member functions debate. Best, João