----- Original Message ----- From: "Joao Abecasis" <jpabecasis@zmail.pt> To: <boost@lists.boost.org> Sent: Thursday, February 24, 2005 3:02 PM Subject: [boost] Re: Boost library inclusion: generic tree containers?
christopher diggins wrote:
Why not have just one kind of iterator:
template<typename T, typename Iter_T> struct tree { typedef typename Iter_T iterator; iterator preorder_begin(); iterator postorder_end(); iterator inorder_end(); iterator end(); iterator begin(); // calls inorder_begin() }
?
Hm... That looks too much like a Sequence to me ;)
I think this is not feasible in the general case. Consider a minimal node containing only a pointer to the next sibling and to the first child. Or a binary tree that keeps pointers to its left and right children.
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?
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.
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?
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? 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. best, Christopher