Re: [boost] Re: new component, extent_set<>

From: joel de guzman (djowel_at_[hidden])
Date: 2001-12-27 16:16:44

----- Original Message -----
From: "Beman Dawes" :
>
> I guess the question this raises is whether or not a half-open range is
the
> best way to specify ranges for arbitrary types?  It's really natural for
> iterators, but seems unnatural at least for the HouseNumber application.
>
> Are there killer arguments in favor of half-open ranges for extent_set?

Hi,

I posted something similar a few months ago:
http://groups.yahoo.com/group/boost/message/13490

It is a full-fledged sparse bit set implementation using closed ranges.
It is now being used by the Spirit parser to allow 16/32 bit character
set support. For instance, in XML, there are lots of rules that work on
character ranges. The implementation has matured significantly since
then. It supports all the set operators inverse, union, intersection, 
difference and xor. It has specializations for 8 bit ranges. Unlike the 
extent_set being discussed, overlapping ranges can be added and 
removed. The implementation coalesces and splits ranges as necessary.
Speed is 0(log N) where N is the number of ranges and O(1) for
8 bit ranges. Internally the implementation uses vectors.

Half-open ranges are unnatural for Spirit's use since grammars 
such as XML are often defined using Reg-ex style character ranges.
Example: 

chset_t Char(L"\x9\xA\xD\x20-\xD7FF\xE000-\xFFFD\x10000-\x10FFFF");

which is also equivalent to:

chset_t Char = 
    ch_p(0x9) | 0xA | 0xD 
    | range_p(0x20,0xD7FF) 
    | range_p(0xE000,0xFFFD)
    | range_p(0x10000,0x10FFFF)
    ;

--Joel