From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-24 00:52:31
> > 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:
>
> http://boost-sandbox.sourceforge.net/vault
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).