Eric Niebler wrote:
David Abrahams wrote:
Hmm, this is interesting. There's some inherent complexity in
segmented iterators that this seems to be either masking, or
eliminating. It has to do with subranges. To tell which it is, you
have to think about doing something like two finds in a hierarchical
sequence, using the resulting iterators to delimit a subrange, and
doing something like fill on the result.
+---+---+
| A | B |
+-|-+-|-+
+----------+ +-----------+
| |
V V
+---+---+---+ +---+---+---+
| 1 | 2 | 3 | | 4 | 5 | 6 |
+-|-+-|-+-|-+ +-|-+-|-+-|-+
+-------+ | +---+ +---+ | +-------+
| +-+ | | +-+ |
| | | | | |
V V V V V V
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
| a | b | | c | d | | e | f | | g | h | | i | j | | k | l |
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
So what happens when we find, in separate steps, d and j, then use the
resulting subrange [d,j) to do a fill with x?
I think you have to see some kind of segmented iterator at some point:
the new hierarchical range is [ <A,2,d>, <B,5,j> ).
Now, you can build a sequence out of those two endpoints, but it's not
as simple as it looks, because above the leaves you don't have
half-open ranges anymore. That is, the range doesn't include j, but
it does include 5.
Well there's more to think about here but I'll leave you guys with
that head start. I'm pretty sure that doing this in terms of
sequences can't make all the complexity disappear.
I agree. That thought occurred to me as well. Fusion has dealt with this
problem by providing a range<> type that turns two iterators into a
sequence, so you can pass them to a Fusion algorithm. We may need to
extend this concept, so that you can build a segmented_range<>. So
fusion::find() on a segmented sequence should return a segmented
iterator, and two segmented iterators make a segmented range. We can
isolate the complexity there. I /think/ it should be possible to build a
generic segmented iterator that works with any segmented sequence, by
remembering the parent segments. And a segmented_range<> should know how
to assemble two segmented iterators back into a segmented sequence.
Since a generic segmented iterator would need to remember parents, it
won't be as light-weight as it could be. But I don't think this is a
very common usage pattern in Fusion. (Is it, Joel?) I've never needed
fusion::range<>. Better to optimize for the common case, IMO.
I admit, it's all pretty hand-wavey at this point. It would be wise to
begin our investigation of this approach there.
I toyed with this a bit over the weekend, and implemented the scheme I
had in mind. Attached is:
1) segmented_iterator<>: A generic segmented iterator, capable of
iterating over any segmented Fusion data sequence.
2) A specialization of iterator_range<> that takes two segmented
iterators and reconstitutes a segmented view of the underlying
segmented data structure.
3) find_if_s<>: A segmented implementation of find_if which works
with segmented data structures and returns segmented iterators.
Also, there is a simple fusion::tree<> implementation for testing purposes.
As we suspected, segmented_iterator<> and the segmented iterator_range<>
are pretty gnarly, but the ugliness can be isolated there; they are
general and only need to be implemented once. find_if_s<> is moderately
ugly, but not too bad. The rest is all pretty straightforward.
With this behind us, I feel pretty confident that the simplified
segmentation interface for Fusion is sound and reasonable.
Joel, I've got a nice little pile of segmented Fusion code now. Perhaps
we should have a branch for it. What do you think?
--
Eric Niebler
Boost Consulting
www.boost-consulting.com
segmented-fusion2.tar.gz
Description: GNU Zip compressed data
