Re: segmented fusion - a-ha!

Eric Niebler wrote:
> 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?

Wouldn't it be better if we simply tag the branch and just add on
top of the current FUSION_V2 branch? We'll need to do some
post review tweaks there so, I anticipate lots of changes to
the code that will likely cause lots of conflicts with your
branch. Thoughts?

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642