Boost logo

Boost :

Subject: Re: [boost] [interval container (itl)] A pretty large bitset
From: OvermindDL1 (overminddl1_at_[hidden])
Date: 2009-11-02 20:22:56

On Mon, Nov 2, 2009 at 10:25 AM, Joachim Faulhaber
<afojgo_at_[hidden]> wrote:
> Dear list!
> In thread
> Zachary Turner posted an article about a compressed bitset,
> that uses run-length defined intervals to achieve a compact
> representation of large bitsets that are useful for
> managing huge file allocation tables.
> As I mentioned in a reply to this article, Zach's compressed
> bitsets, in their basic ideas, are quite similar to
> itl::interval_sets: They allow for compression of large
> quantities of elements as long as they occur in (large)
> uninterrupted chunks.
> As Zach pointed out, this nice behavior is completely
> spoiled, if we would want to handle a set like
> {1,3,5,7,9,...,2(k-1)}   or as bitset
> '0101010101...01'
> Here, the capability of usual bitsets to compress elements
> that are distributed over only small ranges can neither
> be applied to Zach's compressed bitset nor to an
> itl::interval_set of the Interval Template Library.
> As a new use case of interval containers I have developed
> a *large_bitset* class template on top of itl::interval_map
> that is able to combine interval compression *and* bitset
> compression. It is, for instance, capable of representing
> the bitset mentioned above
> '01010101...010'
>  a            b
>  a: bit 0
>  b: bit 2^64-1
> containing 2^63 bits (or elements) with just *one* internal
> interval associated to only *one* value of 64bit length ;)
> Curious??
> Find the documented example code in my updated library
> docs at
> While the documented class template 'large_bitset', for
> reasons of a short presentation, is only a minimal one,
> you can find a more elaborated version as 'interval_bitset'
> in the sandbox at
> I'd like to ask Zachary Turner to comment on the
> use case. Can this be useful in your field?
> Moreover I'd like to encourage everyone to give feedback
> on my interval container library, report problems, bugs
> and share suggestions. If you find this stuff useful
> please volunteer as review manager for the submitted
> library Boost Interval Containers.
> Note, that the new example on 'large_bitsets'
> is not yet included in the library submitted for review
> in the vault but it is contained in the sandbox.
> I am currently preparing an update of the review version of
> the itl, that is adjusted and corrected for the feedback,
> suggestions and patches that I have received during the
> last weeks. I will integrate further feedback and account
> for bug reports if you have any.

Hmm, this looks quite fascinating, I have very random bitset and
normal sparse methods do not work, might see if this does.

Boost list run by bdawes at, gregod at, cpdaniel at, john at