Re: [boost] [dynamic_bitset] Append byte to the less significant end

Subject: Re: [boost] [dynamic_bitset] Append byte to the less significant end
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-12-24 10:00:50

Merry Christmas, Romain :)

2010/12/24 Romain CHANU <romainchanu_at_[hidden]>:
> Here is my problem: i am using boost::dynamic_bitset and I would like to
> append a byte to the bitset.
>
> The idea is the following:
>
> 1) read a byte (represented as an unsigned char)
> 2) append the byte to the bitset
> 3) repeat these steps until there is no more data to read
>
> The current "append" in the API appends a byte to the most significant end.
> I would like to actually append the byte to the less significant end.

I think you are trying to use the data structure, dynamic_bitset in a
way that it was not designed for. Class templates bitset and
dynamic_bitset are ususally interpreted in two ways.

(1) As sets of elements, represented by bits.
(2) As a binary number with binary digits starting from the least to
the most significant bit.

Of the two concepts, set and binary number, the set concept is the
more important one. It gives the class template its name: bit*set*.
The operation that you are intending to apply is not a simple append
of elements, because it always changes the whole set. All elements
that are in the set already have to be added a value of 8. Then you
are setting some of the first 8 values from your new byte.
Dynamic_bitset::append does not alter the elements in the the bitset
and cheaply adds a new block, containing some new elements, at the
end.

I'd say you could collect your single bytes (bitsets) in a vector,
appending them at the end with push_back and then populate a
dynamic_bitset in reverse order using BlockIterators.

As an alternative to dynamic_bitsets you could also use
icl::interval_bitsets form the extended Interval Container Library
ICL+. Class template icl::interval_bitset can represent very lare
bitsets in a compact form because it uses a combination of interval
compression and bit compression. You can find examples and an
introductory implementation here:

http://www.joachim-faulhaber.de/boost_icl/doc/libs/icl/doc/html/boost_icl/projects.html#boost_icl.projects.large_bitset

Note, that icl::interval_bitset is not yet a part of the Interval
Container Library [Boost.Icl] that will be available with the next
Boost release 1.46. But you can download ICL+ from sourceforge:

http://sourceforge.net/projects/itl/

or get a copy via SVN from the sandbox

https://svn.boost.org/svn/boost/sandbox/icl/

I am planning to add icl::interval_bitsets to the core library
[Boost.Icl] next and will also add functions for the addition/deletion
of blocks (elementary bitsets).

HTH
Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de