Sparse Bit Vectors

From: joel de guzman (isis-tech_at_[hidden])
Date: 2001-06-20 20:21:34

Hello,

For quite some time now, I've had this urge to implement
sparse bit vectors. I've done some research and cannot
(pardon me if I'm just ignorant) find an implementation
anywhere in the web. OK, so I wrote one.

It is implemented using a collection of disjoint ranges. The
standard set operators apply [ set union, set intersection,
set difference, set xor, set inverse ]. The set can be constructed
from single values and ranges and of course, sets.

What is it good for?

-> I need it to do Unicode 16 and 32 bit character sets. 
     Representing say: a set of all Unicode Kanji Japanese 
     characters will overwhelm the std::set. Also, the std bit 
     vector is also only  practical up to around 256 bits 
     [ASCII characters].

-> Macintosh style graphical regions. A vector of sparse bit
    vectors can represent something like Regions in the Mac.
    in fact the Mac-Region inspired this implementation. [  I 
    am aware that this is patented. I don't know if my 
     implementation infringes on this patent. But I am also
     aware that this patent will expire soon (now)? ]

-> Compresses bitmaps. Ok, same as above :-)

-> This is interesting... A set of floating point numbers
    and ranges. Say we want a set of floating point numbers
    from -1 to 1 except 0. You'd write: 

       fs = range<float>(-1.0,+1.0) - 0.0;

--> More?

I just want to share this to anyone interested. I'm a bit
unsure if there's interest in such a thing. I'm quite well
aware of its usefullness though. At the very least, I
intend to use it with the Spirit inline parser. 

So, I'm all ears if anyone wants the thing :-)
Here's a very rough, single file, bare-bones 
demo program.

http://www.mydestiny.net/~isis-tech/sparse.cpp

Cheers,
Joel de Guzman