Boost logo

Boost :

From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-30 00:59:09


"David A. Greene" wrote:
> Nathan Myers 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. In use it looks like:
>
> Cool! Why "extent_set" though? What about range_set or interval_set?

"Extent" is the standard term of art when speaking of ranges of disk
blocks, particularly as part of a file system. Also, since it's not
really a set of ranges, range_set seemed inappropriate.

> Any way this could be adapted to allow non-scalar ranges? What are
> the requirements on the range element type? I would think anything
> less-than-comparable should be useable but I didn't implement the
> class. :)

The current version uses closed ranges, BTW. The requirements are
minimal: as listed in the header file, the Bound argument must be
copyable, assignable, equality-comparable, comparable using the Compare
argument, and incrementable and decrementable using the Succ and Pred
arguments. It imposes no other requirements, so a non-scalar could
work.

Unfortunately I don't know how to define a useful decrement operator
for a string, or a Compare operator for a complex number. Did you
have some particular non-scalar in mind?

The original version didn't need the increment and decrement operations,
internally, but the client was still obliged to apply the equivalent of
an increment operation. That made it slippery to use on strings. You
could define increment to mean "append a space", so that a dictionary
page might occupy the range "lost" to "love " (note the space). That
assumes a lot about the character encoding, which the client (but not
extent_set<>) is allowed to do. Unfortunately there is no simple
equivalent for decrementing, so the trick doesn't work with closed
ranges.

It is conceivable that I might be able to continue storing half-open
ranges internally, and thus avoid needing a decrement operation. It
seems a bit fragile though.

> Is there a way to control when ranges are combined (maybe sometimes
> I want [10, 20) and [20, 30) to stay separate)? A policy for this
> would be nice.

It doesn't provide that in the current version. In fact, the presence
of such a pair of extents would violate an invariant, breaking the
insert and erase members as written. (They could probably be changed
to accommodate it, at some cost in complexity.) How would you use
such a feature?

Nathan Myers
ncm at cantrip dot org


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk