Hi João,
In my design nodes were made an implementation detail but I also attempted to define some node concepts to allow advanced users to plug their own node types into pre-defined trees.
I'm curious what one would do with that ability ... what kind of use cases were you picturing? I've been attempting not to expose nodes in the interface, but maybe there's a reason why I should?
I'd be interested in looking at the details, however draft they are (Feel free to mail them privately).
Actually, I shouldn't be such a tease. I'll try to get the document semi-workable and post it here when I get back from work this evening.
I have a couple "selector" structs, basically identical to Boost Graph Library's vecS, listS, etc, and the tree<> class template takes one of these selectors as a template parameter.
I'm not sure if you're referring to the standard containers here. I initially considered using those, after considering allocator issues and the (potentially) large per-node overhead I almost completely dropped the idea.
Well, vecS and listS do refer specifically to the standard containers, but my idea was that you could plug any container conforming to the standard Sequence concept into the tree. But yes, the overhead is one of the aspects of this approach that's been plaguing me.
Right now, I'm pondering on a node concept based on boost::range, plus some free functions (insert, update, erase...) that would allow greater flexibility and extensibility, with no overhead.
I haven't looked at boost::range at all. I'll check that out!
Personally, I prefer a tree-iterator concept that allows traversal of the tree without needing to carry the tree around. Having children as a member function of the tree prevents this.
Oh, I think I was unclear, sorry. I wanted to provide children() as a convenience, rather than as a necessary method for traversal and mutation of the tree. In lieu of having a document prepared, let me give you a little more detail on my basic idea for the concepts behind the tree. The basic building blocks are what I've been calling a "Multiply Traversable Container" and a "Traversal", which go hand in hand. The notion is that if there is no single, canonical traversal of a container from beginning to end (unlike the present standard containers which are all "flat"), I still want to be able to ask for a begin() and an end() and use standard algorithms on an iterator range. So iterators and member functions such as begin() and end() are parametrized on a traversal policy. In the case of the Tree concept, I've provided the obvious ones: X::pre_order_traversal X::post_order_traversal X::depth_first_traversal X::breadth_first_traversal X::sibling_traversal X::first_descendant_traversal X::last_descendant_traversal The first four traverse the whole tree, whereas the second three may traverse only a subset of the tree. One outcome of having multiple potential traversals is that, although it still makes sense for a Multiply Traversable Container to be EqualityComparable, it no longer makes sense to be LessThanComparable. So I also thought, in the event that you actually want to compare two trees (or other multiply-traversable containers) via operator <, I could provide a little wrapper utility (I've called this "single_traversal") modelling the standard Container concept, which hangs onto a traversal policy and gives you only a single iterator type. Anyway, I'm omitting a lot of detail here (Multiply Traversable Container is split up into Forward, Reversable and Random Access variants, and I also have a separate Binary Tree concept, which provides in-order iterators, etc.), but hopefully this gives you a better basic idea of what I'm going for.
That's one of the reasons I decided to define a TreeIterator concept that overlaps with the standard Iterator concept when it comes to sibling traversal. [snip] On the thread Justin Gottschlich started on this issue (http://tinyurl.com/44e3u), I suggested pre-order and other linearizations of a tree could be provided externally. I think putting these on the tree unnecessarily complicates the design of the tree and the iterators.
So, hopefully my comments above illustrate my opinions on this. I think the minimum set of iterators necessary to build all other tree iterators on (with reasonable efficiency) is first_descendant_iterator, last_descendant_iterator, and sibling_iterator. If I understand you correctly, I think that jives with what you're saying, and seems to be in rough agreement with the general consensus in Justin's thread. But I think it's a good thing to have the full set of traversals in the tree as well, even if for no other reason than for consistency with those three "fundamental" traversals.
I solved parent/root issue by having the tree class promise only the most basic TreeIterator: for traversal from parent to child. [snip] From the initial root iterator one could get SiblingIterators for iteration over its children.
So, from your description, I'm picturing two things: - A TreeIterator is an extension of the standard iterator concept that provides an additional method, something like children(), which returns a SiblingIterator, to provide access to a node's children. - The only way to get a SiblingIterator is via a TreeIterator's children() method. I'm not sure if this is what you were implying or not. But in my own design, I was thinking two things: first, my iterators do not extend the standard Iterator concept, and second, all iterator types should be convertible to each other. For example, if I'm doing a pre-order traversal of a tree -- maybe as a means of searching -- and I find an interesting element, I might want to convert my iterator to a sibling iterator to deal with the siblings of the element I've found. That implies that even for the root of the tree, I should be able to get a sibling iterator to point to it (though it would have no previous or next siblings).
Depending on the underlying node, both iterators could actually be the same. This could be inspected through separate traits classes.
Hmm, this gets back to the question about providing a node concept and interface. I'm having trouble picturing what you're describing here.
My idea was to write the basic single and double-linked lists operations from scratch. We don't be need the whole std::list interface for the nodes anyway.
I think I tend to agree now. I'd like to be able to plug in arbitrary sequences (including std::list) to represent a node's children, but that seems to come encumbered with too many penalties. On the other hand, I'm still soliciting clever approaches to this problem, and I'm still curious whether (despite having given up on it) you think it's a good idea conceptually. I think at this point (lacking a decent solution for the pluggable child sequence problem) if I were to provide a tree::children() method to expose a child sequence, the sequence returned still should conform to the standard Sequence concept, but needn't literally be a std::vector, std::list, or whatever. Thanks again for your insight, dr