Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk