base/BitArray

Go to the documentation of this file.

// A one-dimensional array of bits, similar to STL bitset.
//
// Copyright 2000 Andrew Kirmse.  All rights reserved.
//
// Permission is granted to use this code for any purpose, as long as this
// copyright message remains intact.

#ifndef _BASE_BITARRAY_
#define _BASE_BITARRAY_

#include <memory>

namespace base {

class BitArray
{
public:

   //
   // Constructors and destructor
   //
   
   explicit BitArray(unsigned size)
   {
      Init(size);

      // Clear last bits
      Trim();
   }
   
   BitArray(const BitArray &that)
   {
      mpStore = 0;
      *this = that;
   }
   
   virtual ~BitArray()
   {
      if (mLength > 1)
         delete[] mpStore;
   }

   //
   // Operators
   //

   class BitProxy;
   
   BitArray &operator=(const BitArray &that)
   {
      if (this != &that)
      {
         if (mLength > 1)
            delete[] mpStore;

         Init(that.mNumBits);
         
         memcpy(mpStore, that.mpStore, mLength * sizeof(store_type));
      }
      return *this;
   }

   BitProxy operator[](unsigned pos)
   {
      Assert(pos < mNumBits);
      return BitProxy(*this, pos);
   }

   const BitProxy operator[](unsigned pos) const
   {
      Assert(pos < mNumBits);
      return BitProxy(const_cast<BitArray &>(*this), pos);
   }
   
   bool operator==(const BitArray &that) const
   {
      if (mNumBits != that.mNumBits)
         return false;
      
      for (unsigned i = 0; i < mLength; i++)
         if (mpStore[i] != that.mpStore[i])
            return false;
      return true;
   }

   bool operator!=(const BitArray &that) const
   {
      return !(*this == that);
   }

   BitArray &operator&=(const BitArray &that)
   {
      Assert(mNumBits == that.mNumBits);
      for (unsigned i = 0; i < mLength; i++)
         mpStore[i] &= that.mpStore[i];
      return *this;
   }

   BitArray operator|=(const BitArray &that)
   {
      Assert(mNumBits == that.mNumBits);
      for (unsigned i = 0; i < mLength; i++)
         mpStore[i] |= that.mpStore[i];
      return *this;
   }

   BitArray operator^=(const BitArray &that)
   {
      Assert(mNumBits == that.mNumBits);
      for (unsigned i = 0; i < mLength; i++)
         mpStore[i] ^= that.mpStore[i];
      return *this;
   }

   BitArray operator~() const
   {
      return BitArray(*this).FlipAllBits();
   }

   friend BitArray operator&(const BitArray &a1, const BitArray &a2)
   {
      return BitArray(a1) &= a2;
   }

   friend BitArray operator|(const BitArray &a1, const BitArray &a2)
   {
      return BitArray(a1) |= a2;
   }

   friend BitArray operator^(const BitArray &a1, const BitArray &a2)
   {
      return BitArray(a1) ^= a2;
   }

   //
   // Plain English interface
   //
   
   // Set all bits to false.
   void Clear()
   {
      memset(mpStore, 0, mLength * sizeof(store_type));
   }
   
   // Set the bit at position pos to true.
   void SetBit(unsigned pos)
   {
      Assert(pos < mNumBits);
      mpStore[GetIndex(pos)] |= 1 << GetOffset(pos); 
   }

   // Set the bit at position pos to false.
   void ClearBit(unsigned pos)
   { 
      Assert(pos < mNumBits);
      mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos)); 
   }

   // Toggle the bit at position pos.
   void FlipBit(unsigned pos) 
   { 
      Assert(pos < mNumBits);
      mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos); 
   }

   // Set the bit at position pos to the given value.
   void Set(unsigned pos, bool val)
   { 
      val ? SetBit(pos) : ClearBit(pos);
   }

   // Returns true iff the bit at position pos is true.
   bool IsBitSet(unsigned pos) const
   {
      Assert(pos < mNumBits);
      return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
   }

   // Returns true iff all bits are false.
   bool AllBitsFalse() const
   {
      for (unsigned i=0; i < mLength; i++)
         if (mpStore[i] != 0)
            return false;
      return true;
   }

   // Change value of all bits
   BitArray &FlipAllBits()
   {
      for (unsigned i=0; i < mLength; i++)
         mpStore[i] = ~mpStore[i];

      Trim();
      return *this;
   }

   //
   // Bit proxy (for operator[])
   //
   
   friend class BitProxy;
   
   class BitProxy
   {
   public:
      BitProxy(BitArray &array, unsigned pos):
            mArray(array), mPos(pos)
      {}

      BitProxy &operator=(bool value)
      {
         mArray.Set(mPos, value);
         return *this;
      }

      BitProxy &operator=(const BitProxy &that)
      {
         mArray.Set(mPos, that.mArray.IsBitSet(that.mPos));
         return *this;
      }

      operator bool() const
      {
         return mArray.IsBitSet(mPos);
      }

      bool Flip()
      {
         mArray.FlipBit(mPos);
         return mArray.IsBitSet(mPos);
      }

   private:
      BitArray &mArray;
      unsigned  mPos;
   };
   
private:
   
   typedef unsigned long store_type;
   enum
   {
      bits_per_byte = 8,
      cell_size     = sizeof(store_type) * bits_per_byte
   };

   store_type        *mpStore;  
   store_type         mSingleWord; // Use this buffer when mLength is 1
   unsigned           mLength;     // Length of mpStore in units of store_type
   unsigned           mNumBits;

   // Get the index and bit offset for a given bit number.
   static unsigned GetIndex(unsigned bit_num)
   {
      return bit_num / cell_size;
   }

   static unsigned GetOffset(unsigned bit_num)
   {
      return bit_num % cell_size;
   }

   void Init(unsigned size)
   {
      mNumBits = size;
      
      if (size == 0)
         mLength = 0;
      else
         mLength = 1 + GetIndex(size - 1);

      // Avoid allocation if length is 1 (common case)
      if (mLength <= 1)
         mpStore = &mSingleWord;      
      else
         mpStore = new store_type[mLength];
   }
   
   // Force overhang bits at the end to 0
   inline void Trim()
   {
      unsigned extra_bits = mNumBits % cell_size;
      if (mLength > 0 && extra_bits != 0)
         mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
   }
};

} // base

#endif

---