From: joel de guzman (isis-tech_at_[hidden])
Date: 2001-06-20 20:21:34
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
-> 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;
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
Joel de Guzman
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk