On Mon, Nov 2, 2009 at 10:25 AM, Joachim Faulhaber <afojgo@googlemail.com> wrote:
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/pro...
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.
Hmm, this looks quite fascinating, I have very random bitset and normal sparse methods do not work, might see if this does.