Re: [boost] Recursive iterator/range adaptors

From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2008-07-10 23:14:47

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.

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);
        }
    }
}

value_type dereference() const
{
    return *current;
}

T root;
T current;

};

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.