"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