Boost logo

Boost :

Subject: Re: [boost] [interval container (itl)] A pretty large bitset
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-11-03 05:08:06

2009/11/3 Scott McMurray <[hidden]>:
> 2009/11/2 Joachim Faulhaber <afojgo_at_[hidden]>:
>> 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??
> Quite.

The compact storage of repeated bit patterns is only the lead story
to baffle the reader a bit ;)

In the end I do not think that this is the most important property of
large_bitset. In fact it is just a byproduct of the basic idea to
combine interval and bitset compression via an itl::interval_map of

> How does it handle a repeat of 128 1s then 128 0s then 128 1s etc?
> (Or any repeating signal with a period longer than one storage unit?)

So a large_bitset<uint64_t, mini::bits<uint64_t> > would handle
them this way:

[0,2)->"111...1" (all 64 bits set)

which is obviously much less compact than the initial example
but still a good compression.

But, to be honest, the "periodic bit compression magic" has
more limitations than that. For instance it does not manage
to represent a bit pattern
with a single node like this can be done for patterns with
an even period length <= 64 (or word_length).

As I said, it's just a nice byproduct of the design. More
important IMO is the combination of interval and bit
compression as such and also the fact that large_bitset
can be implemented with *very little* code

on top of itl::interval_map, which demonstrates the potential
of interval containers.


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