[boost] Re: Boost library inclusion: generic tree containers?

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).