The traversal library that has been discussed allows tree-like traversal of structures using a functional approach. I suggest an alternative approach: a range-based one. It certainly has limitations: ranges are monomorphic. So you can only do it if is_same< typename range_value<Range>::type, typename range_value< typename range_value<Range> >::type >. However, it would be very practical to use, since you could simply use a foreach loop to perform depth-first search and stop iteration whenever you like. Also, it is lazy and you can combine it easily with other range adaptors (filtering, transforming...) or algorithms. For performance, one would need to provide a way to get the father range of a given range. Maybe that's the occasion to create a new concept. Otherwise iterators will need to have their own stack. Did anyone ever work on that? Does it look like a good idea?
on Thu Jul 10 2008, Mathias Gaunard <mathias.gaunard-AT-ens-lyon.org> wrote:
The traversal library that has been discussed allows tree-like traversal of structures using a functional approach.
I suggest an alternative approach: a range-based one. It certainly has limitations: ranges are monomorphic. So you can only do it if is_same< typename range_value<Range>::type, typename range_value< typename range_value<Range> >::type >.
However, it would be very practical to use, since you could simply use a foreach loop to perform depth-first search and stop iteration whenever you like. Also, it is lazy and you can combine it easily with other range adaptors (filtering, transforming...) or algorithms.
For performance, one would need to provide a way to get the father range of a given range. Maybe that's the occasion to create a new concept. Otherwise iterators will need to have their own stack.
Did anyone ever work on that? Does it look like a good idea?
This sounds a bit like http://lafstern.org/matt/segmented.pdf Did you have something like that in mind? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
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.
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
participants (2)
-
David Abrahams -
Mathias Gaunard