Re: [boost] Sparse Bit Vectors

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.