Re: new component, extent_set<>

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