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
>
> http://listarchives.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.
Hmm, this looks quite fascinating, I have very random bitset and
normal sparse methods do not work, might see if this does.