[boost] [fusion] segmented sequences and hierarchical algorithms (was: [review] Fusion review begins)

From: Eric Niebler (eric_at_[hidden])
Date: 2006-05-10 15:43:30

Larry Evans wrote:
> On 05/10/2006 12:34 PM, Eric Niebler wrote:
> 
>>Joel de Guzman wrote:
>>
>>>I think the segmentation idea is very good. I love the direction that
>>>this is leading to. Thank you very much for spear-heading the effort.
>>
>>My pleasure. FYI - I now have a general implementation of 
>>fusion::segmented_iterator<>, so we can proceed with our simplified 
>>segmentation interface.
> 
> Hi Eric,
> 
> Could you give us some idea of what a segmented_iterator is or post
> your general implementation.  I'm sure others are curious too.

Joel and I have been having an extensive discussion on spirit-devel 
about support in Fusion for segmented sequence. See Matt Austern's 
"Segmented Iterators and Hierarchial Algorithms": 
http://lafstern.org/matt/segmented.pdf.

Feel free to read the last few weeks of 
http://news.gmane.org/gmane.comp.parsers.spirit.devel to bring yourself 
up to speed. The short story is that many Fusion sequences are 
segmented, like fusion::joint_view. Some day we'll have fusion trees, 
which will be segmented out the wazoo. Making them look non-segmented so 
that the algorithms can work with them is inefficient, not to mention 
rather tricky.

My proposal is to make Fusion algorithms hierarchical, so they can work 
efficiently with segmented data structures. Rather that using Matt 
Austern's formulation, I've come up with a much simpler interface based 
not on segmented iterators, but rather on segmented sequences. This 
works great until you need to return an iterator into a segmented 
sequence, as fusion::find must do. Then you need a segmented iterator. 
But it's possible to implement fusion::segmented_iterator<> just once so 
that it works with any segmented sequence, and a 
segmented_iterator_range<> that reconstitutes a segmented sequence from 
two segmented iterators.

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