Re: [boost] new component, extent_set<>

From: Darin Adler (darin_at_[hidden])
Date: 2001-12-29 15:30:31

On 12/26/01 12:26 AM, Nathan Meyers <ncm-yahoospam_at_[hidden]> wrote:

> boost::extent_set<> implements a set of half-open ranges on a scalar
> type, with automatic splitting and merging, appropriate for managing
> ranges of disk blocks or video frames.

On a previous project in 1995, my colleague Waldemar Horwat implemented
three different data structures like the one you propose. One we called
RangeSet was like the extent_set you propose. We also had RangeMap that
mapped half-open ranges to values. And we had IncrementalRangeMap that
mapped half-open numeric ranges to numeric value ranges of the same size.
The IncrementalRangeMap was an efficient data structure to express what goes
where when you are rearranging something.

I seem that recall that our classes worked only on integers, but that was
more a sign of the times -- we weren't doing much generic C++ programming
yet. (I remember that Waldemar went to a talk about the STL sometime close
to this time.)

On the project I just completed, the iPod Updater, I could have used your
proposed extent_set. I had to compute a set of disk blocks; I implemented my
own half-assed non-generic subset of extent_set. I mention this because it's
additional evidence that this is a generally-useful class.

The one thing I'm slightly uncomfortable with is the interface that uses
separate integers rather than something like half_open_range. I'm not sure I
can clearly articulate the reason I'd prefer using half_open_range in the
interface, and I'm also not certain how it would affect the details, but I
suspect that I'd prefer the higher-level interface even if it has a cost.

    -- Darin