2009/11/3 Scott McMurray <me22.ca+boost@gmail.com>:
2009/11/2 Joachim Faulhaber <afojgo@googlemail.com>:
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 bitsets.
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) [2,4)->"111...1" ... [k,k+2)->"111...1" 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 "100100100...100" 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 http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/pro... on top of itl::interval_map, which demonstrates the potential of interval containers. Cheers Joachim