From: Greg Colvin (gcolvin_at_[hidden])
Date: 2001-06-20 23:56:43
From: joel de guzman <isis-tech_at_[hidden]>
> 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)? ]
There are other ways to do sparse bit vectors. My favorite
is a very compact binary tree representation that uses on
average two bits for every "on" bit and no bits for the
"off" bits. It's not patented so far as I know. If it is
I know of plenty of prior art.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk