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

From: Larry Evans (cppljevans_at_[hidden])
Date: 2005-02-23 14:44:53

On 02/22/2005 10:46 PM, Justin Gottschlich wrote:
 > "Rene Rivera" <grafik.list_at_[hidden]> wrote in message
 > news:421C0E3A.3080003_at_redshift-software.com...
[snip]

 > 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?

[snip]

 >>But to have generic algorithms, programs, iterators,
 >>mutators, etc. that can operate on different kinds of tree
 >>implementations so that programmers can make storage and
 >>algorithmic trade offs in programs.

Would flatten_value_type_iterator (see below) work for you?

[snip]
 > However, it's the details that we differ on - I see using
 > the n-ary tree path as the perfect means to achieving our
 > mutual goal, because it can be wrapped inside its
 > end-resultant tree and then expose only the interfaces
 > (and iterators) necessary for that tree.

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 :(

[snip]

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

in file:

    flatten_value_type_iterator.zip

It determines the depth of the tree by specializing
mpl::{next,deref} to make the outermost container appear as
a mpl sequence and where mpl::next returns the type of the
next innermost (or nested) container.  IOW, in case of:

   vector<list<int> >

the outermost container would be vector<list<int> > and the
next (and, in this case leaf container) would be list<int>.

The iterators are actually composed of two iterators:

   flatten_iterator_value_type_iterator<Parent,Children>::my_current
   flatten_iterator_value_type_iterator<Parent,Children>::child_iter_type

The first, or "parent iterator" corresponds to the higher
level in the tree, and the other, or "child iterator",
corresponds to all lower levels in the tree down to the leaf
nodes.

Because of mpl::fold, this code doesn't have the virtual
function call overhead of the bridge_iterator mentioned
above.

Test code is in flatten_value_type_iterator_test.cpp where,
in function, test_print, the "tree" is of type:

   typedef std::vector<std::list<std::deque<int> > > tree_type;