Re: [boost] Re: Challenge: bit_vector/bit_string

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-05-13 19:51:51

At 08:43 AM 5/12/2001, Daryle Walker wrote:

 >I'm not sure this counts as an example, but I'm curious about what
 >bit_string is like.  I have an (inactive) project for an
 >arbitrary-precision
 >integer type for Boost.  It strings together many bits for the 
value.  I've
 >had two choices for the bit container:
 >
 >1.  vector<bool> since it stores the bits compactly
 >2.  deque<bool> to allow inserts from either end (for shifts)
 >
 >If bit_string could provide compact representation with efficient pushing
 >(and popping) from either end, it would be great!

See below for the interface.

Please don't criticize this interface in light of modern STL practice - it 
was designed before there was an STL.

--Beman

-----------

The header <bitstring> defines a class and several function signatures
   for representing and manipulating varying-length sequences of bits.
   class bit_string {
   public:
       bit_string();
       bit_string(unsigned long val, size_t n);
       bit_string(const bit_string& str, size_t pos = 0, size_t n = NPOS);
       bit_string(const string& str, size_t pos = 0, size_t n = NPOS);

       bit_string& operator+=(const bit_string& rhs);
       bit_string& operator&=(const bit_string& rhs);
       bit_string& operator|=(const bit_string& rhs);
       bit_string& operator^=(const bit_string& rhs);
       bit_string& operator<<=(size_t pos);
       bit_string& operator>>=(size_t pos);
       bit_string& append(const bit_string& str, pos = 0, n = NPOS);
       bit_string& assign(const bit_string& str, pos = 0, n = NPOS);
       bit_string& insert(size_t pos1, const bit_string& str,
                          size_t pos2 = 0, size_t n = NPOS);
       bit_string& remove(size_t pos = 0, size_t n = NPOS);
       bit_string& replace(size_t pos1, size_t n1, const bit_string& str,
                           size_t pos2 = 0, size_t n2 = NPOS);
       bit_string& set();
       bit_string& set(size_t pos, bool val = 1);
       bit_string& reset();
       bit_string& reset(size_t pos);
       bit_string& toggle();
       bit_string& toggle(size_t pos);
       string to_string() const;
       size_t count() const;
       size_t length() const;
       size_t resize(size_t n, bool val = 0);
       size_t trim();
       size_t find(bool val, size_t pos = 0, size_t n = NPOS) const;
       size_t rfind(bool val, size_t pos = 0, size_t n = NPOS) const;
       bit_string substr(size_t pos, size_t n = NPOS) const;
       bool operator==(const bit_string& rhs) const;
       bool operator!=(const bit_string& rhs) const;
       bool test(size_t pos) const;
       bool any() const;
       bool none() const;
       bit_string operator<<(size_t pos) const;
       bit_string operator>>(size_t pos) const;
       bit_string operator~() const;
   private:
   //  char* ptr;  exposition only
   //  size_t len; exposition only
   };

2 The class bit_string describes an object that  can  store  a  sequence
   consisting  of  a  varying  number  of  bits.  Such a sequence is also
   called a bit string (or simply a string if the type of the elements is
   clear from context).  Storage for the string is allocated and freed as
   necessary by the member functions of class bit_string.

3 Each bit represents either the value zero (reset) or  one  (set).   To
   toggle  a  bit is to change the value zero to one, or the value one to
   zero.  Each bit has a  non-negative  position  pos.   When  converting
   between  an  object  of  class bit_string of length len and a value of
   some integral type, bit position pos corresponds to the bit value 1 <<
   (len  -  pos  -  1).2) The integral value corresponding to two or more
   _________________________
   2)  Note that bit position zero is the most-significant bit for an ob­

   bits is the sum of their bit values.

4 For the sake of exposition, the maintained data is presented here as:

   --char*  ptr,  points  to  the  sequence  of  bits, stored one bit per
     element;3)

   --size_t len, the length of the bit sequence.

5 The  functions  described  in this subclause can report three kinds of
   errors, each associated with a distinct exception:

   --an invalid-argument error is  associated  with  exceptions  of  type
     invalid_argument;

   --a length error is associated with exceptions of type length_error;

   --an   out-of-range  error  is  associated  with  exceptions  of  type
     out_of_range.

------  end  ------