Re: [boost] Recursive iterator/range adaptors

From: David Abrahams (dave_at_[hidden])
Date: 2008-07-11 11:11:08

on Thu Jul 10 2008, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:

> David Abrahams wrote:
>> This sounds a bit like http://lafstern.org/matt/segmented.pdf
>> Did you have something like that in mind?
>
> Not really.
> I was more thinking of an iterator that does the job.

No iterator can do the job that the paper addresses, because it implies
great inefficiency.

> Basically, an iterator like this (succint pseudo code):
>
> template<typename T>
> struct tree_adaptor
> {
>
> void increment()
> {	
>     if(has_children(current))
>     {
>         current = first_child(current);
>     }
>     else
>     {
>         while(current != root && !has_sibling(current))
>         {
>             current = father(current);
>         }
>         if(current != root)
>         {
>             current = next_sibling(current);
>         }
>     }
> }

That looks like a generalization of deque iterators, with all the same
efficiency issues (lots of tests for every increment).

> Only father is really needed within those primitives.
>
> That way you can simply write
>
> foreach(value_type v, make_tree_range(range))
> {
>    // code
> }
>
> and it automatically does an efficient depth-first search.

Well, I wouldn't say it's efficient; at least, not at the leaves.  But
if you look at the paper, all these segmented iterators *are* iterators,
so they do present the flat view of the data structure that you're
trying to achieve.  It takes smarter algorithms to realize that the
iterators are segmented and actually look at the data's true structure.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com