Re: segmented fusion - a-ha!

David Abrahams wrote:
> Joel de Guzman <joel@xxxxxxxxxxxxxxxxxxxx> writes:
>
> > Eric Niebler wrote:
> > > I just had an a-ha! moment. Segmentation in Fusion is *so* much
> > > simpler than I was making it. Fusion doesn't need segmented
> > > iterators, it needs segmented sequences! Fusion's algorithms don't
> > > take iterators like the std algorithms do -- they take sequences. I
> > > was trying to shoe-horn Matt Austern's formulation into Fusion, but
> > > that's the wrong approach.
> > > Consider the joint_view. It should advertise itself as a segmented
> > > view. Then, the only thing it needs to provide is a way to step
> > > through the internal segments -- which are Fusion sequences that may
> > > or may not be segmented. What you get, essentially, is:
> > Yeah! This is "make it as simple as possible" thing that I was
> > looking for. Essentially, segmented sequences are sequences with
> > child sequences (segments). I see:
> >
> >     traits::is_segmented<Seq>::type // --> mpl::true_/false_
> >
> > Then for segmented sequences:
> >
> >     segments(seq) // --> a sequence of sequences
> >     result_of::segments<Seq>::type // --> a sequence of sequences type
> >
> > Now, a joint_view can hold and return a vector2<Sequence1, Sequence2>&
> > when its intrinsic "segments" is called (via tag-dispatch).
>
> 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.

--
Eric Niebler
Boost Consulting
www.boost-consulting.com


-------------------------------------------------------
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