Hmmm ... =) you might be right. Still, have you read my explanation behind this argument (http://nodeka.com/TreePart2.pdf)?
Howdy, Justin.
I assume you mean the argument that the name should be "iterator" instead of "cursor". Could you give the page of the pdf file where you make this argument?
Hi Larry - yeppers that's exactly what I mean, sorry for not being more clear. =)
From the article (http://nodeka.com/TreePart2.pdf), the sections I'm referring to about an iterator being a tree and vice versa are here:
Section 2 - Terminology (pp 1-3) Section 3.2 - Understanding the core::tree<> recursive characteristic (p 3) Section 3.3 - 3.4 - trees as iterators, iterators as trees (pp 4 - 9) I'd be very curious to hear your thoughts on the arguments made there.
By "wrapped inside" do you mean something like the Bridge pattern in GOF where a virtual operator++ would actually be implemented by vector<T>::iterator++ or list<T>::iterator++ since the actual container type wouldn't be known for a "generic" (i.e. abstract) tree? If so, then I've got a bridge_iterator I created for this purpose; however, it does have the virtual function call overhead :(
To be honest, Larry, I'm not really sure what means would be best to "wrap" the base iterator functionality - I like your suggestion though. =) Using the bridge pattern would be a very nice way to achieve this, both for definition of an abstract iterator or an abstruct tree. Inline with that thinking (after such great feedback and thought provoking discussion), I think it's apparent that there are two distinct types of trees we need: 1) algorithmic trees 2) container trees Each tree serves a completely different purposes than the other and based on the number of points brought up here, it seems we need to build solutions towards both ends. I am currently thinking of a very basic tree design, like this: class base_tree {}; class container_tree : public base_tree {}; class algorithmic_tree : public base_tree {};
From there, you can go nuts:
class multitree : public container_tree {}; class tree_pair : public container_tree {}; class binary_tree : public algorithmic_tree {}; class balanced_binary_tree : public binary_tree {}; Or maybe, instead of direct derivation, you use policies for more flexible "undecided" routes: template <typename T> class DefaultTreeIterator {}; template <typename T> class DefaultTreePolicy { public: typedef DefaultTreeIterator<T> iterator; typedef const DefaultTreeIterator<T> const_iterator; // policy specific implementation here? }; template <typename T, template <class> class TreePolicy = DefaultTreePolicy> class base_tree : public TreePolicy<T> { // basic tree implementation here? }; base_tree<int, binary_tree_policy> binaryTree; base_tree<std::string, xml_tree_policy> xmlTree; Of course the ending tree hierarchy and template parameters would be different, but I think basic tree functionality must be achieved at some base level (at least that's what I'm thinking right now). From there, the differing goals of the trees (algorithmic and containment) can be tended towards for the two different paths. This is just an extremely basic layout of what I'm thinking at the moment ... =) What's perhaps most interesting to me is that many people would be required to implement what is seeming to be an entire "collection" of trees - but from the number of stellar-coder people who have shown interest, it seems we might just be able to pull it off. =) What we really need at this point is an agreed upon design decision - in order to do that I think we need to figure out if the above goals (of a container_tree and algorithmic_tree) are really what we want the tree libraries to be build on, or if something's being missed. As Rene was pointing out, what are we really trying to achieve? Hmmm ... Thanks for the great insight Larry, =) Justin p.s.
One example of a tree iterator which works on any sequence of "nested" (see below) stl container types, is at:
I'll definitely take a closer look at this once we can work out the details for the overall tree design - it seems the flatten_value_type_iterators would be a good match for the algorithmic_tree. While the idea of the bridge_iterator is excellent for this tree design, I wonder if those people interested in the algorithmic_trees would be willing to take the overhead of a virtual table lookup (albeit minor, the use of a algorithmic_tree would be concretely founded in efficiency).