Re: [boost] [fusion] segmented sequences and hierarchical algorithms

From: Eric Niebler (eric_at_[hidden])
Date: 2006-05-10 19:45:48

Giovanni P. Deretta wrote:
> Hi Eric,
> 
> Eric Niebler wrote:
>  > [...]
> 
>>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. 
> 
> 
> What's wrong with Austern's interface? I've both implemented and used it 
> and found it both simple and powerful. Then again I didn't deal with 
> anything the complexity of fusion.

It's more complicated than it needs to be for the purposes of Fusion. A 
strightforward translation of Austern's segmented_iterator_traits<> 
interface into Fusion would require the following new Fusion primitives 
(which all operate on Fusion iterator):

is_segmented
segment
local
segment_begin
segment_end

These are necessary because the STL algorithm interface deals with 
iterators. Fusion's algorithms deal with sequences, however. The 
proposed segmentation interface for Fusion requires only the following 
primitives (which operate on Fusion sequences):

is_segmented
segments

where segments(seq) returns seq's segments as a sequence of sequences. 
This makes it vastly simpler to satisfy the requirements for a segmented 
Fusion sequence. For example, I implemented segmented Fusion sequence 
support for a Fusion tree data structure both in Austern's interface and 
the new one. With Austern's interface, it look ~200 lines of code. With 
the proposed interface, it took ~50. The implementation of the segmented 
Fusion algorithms gets dramatically simpler, too.

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