[boost] [interval container (itl)] A pretty large bitset

Subject: [boost] [interval container (itl)] A pretty large bitset
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-11-02 12:25:06

Dear list!

In thread

http://lists.boost.org/Archives/boost/2009/06/152786.php

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

http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html

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

https://svn.boost.org/svn/boost/sandbox/itl/boost/itl_xt/interval_bitset.hpp

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.

Best regards
Joachim