Boost logo

Boost :

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


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


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at