CrystalSpace

Public API Reference

Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

bitarray.h

Go to the documentation of this file.
00001 /*
00002     Copyright (C) 2000 by Andrew Kirmse
00003 
00004     This library is free software; you can redistribute it and/or
00005     modify it under the terms of the GNU Library General Public
00006     License as published by the Free Software Foundation; either
00007     version 2 of the License, or (at your option) any later version.
00008 
00009     This library is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012     Library General Public License for more details.
00013 
00014     You should have received a copy of the GNU Library General Public
00015     License along with this library; if not, write to the Free
00016     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00017 */
00018 
00019 // A one-dimensional array of bits, similar to STL bitset.
00020 //
00021 // Copyright 2000 Andrew Kirmse.  All rights reserved.
00022 //
00023 // Permission is granted to use this code for any purpose, as long as this
00024 // copyright message remains intact.
00025 
00026 #ifndef __CS_BITARRAY_H__
00027 #define __CS_BITARRAY_H__
00028 
00033 #include "csextern.h"
00034 
00038 class CS_CSUTIL_EXPORT csBitArray
00039 {
00040 public:
00041   typedef unsigned long store_type;
00042 private:
00043   enum
00044   {
00045     bits_per_byte = 8,
00046     cell_size     = sizeof(store_type) * bits_per_byte
00047   };
00048 
00049   store_type *mpStore;
00050   store_type mSingleWord; // Use this buffer when mLength is 1
00051   size_t mLength;       // Length of mpStore in units of store_type
00052   size_t mNumBits;
00053 
00055   static inline size_t GetIndex (size_t bit_num)
00056   {
00057     return bit_num / cell_size;
00058   }
00059 
00060   static inline size_t GetOffset (size_t bit_num)
00061   {
00062     return bit_num % cell_size;
00063   }
00064 
00065   void SetSize (size_t newSize)
00066   {
00067     size_t newLength;
00068     if (newSize == 0)
00069       newLength = 0;
00070     else
00071       newLength = 1 + GetIndex (newSize - 1);
00072 
00073     // Avoid allocation if length is 1 (common case)
00074     store_type* newStore;
00075     if (newLength <= 1)
00076       newStore = &mSingleWord;
00077     else
00078       newStore = new store_type[newLength];
00079     
00080     if (newLength > 0)
00081     {
00082       if (mLength > 0)
00083       {
00084         if (newStore != mpStore)
00085           memcpy (newStore, mpStore, 
00086             (MIN (mLength, newLength)) * sizeof (store_type));
00087       }
00088       else
00089         memset (newStore, 0, newLength * sizeof (store_type));
00090     }
00091 
00092     if (mLength > 1)
00093       delete mpStore;
00094 
00095     mpStore = newStore;
00096     mNumBits = newSize;
00097     mLength = newLength;
00098   }
00099 
00101   inline void Trim()
00102   {
00103     size_t extra_bits = mNumBits % cell_size;
00104     if (mLength > 0 && extra_bits != 0)
00105       mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
00106   }
00107 
00108 public:
00112   class CS_CSUTIL_EXPORT BitProxy
00113   {
00114   private:
00115     csBitArray &mArray;
00116     size_t mPos;
00117   public:
00119     BitProxy(csBitArray &array, size_t pos): mArray(array), mPos(pos)
00120     {}
00121 
00123     BitProxy &operator= (bool value)
00124     {
00125       mArray.Set (mPos, value);
00126       return *this;
00127     }
00128 
00130     BitProxy &operator= (const BitProxy &that)
00131     {
00132       mArray.Set (mPos, that.mArray.IsBitSet (that.mPos));
00133       return *this;
00134     }
00135 
00137     operator bool() const
00138     {
00139       return mArray.IsBitSet (mPos);
00140     }
00141 
00143     bool Flip()
00144     {
00145       mArray.FlipBit (mPos);
00146       return mArray.IsBitSet (mPos);
00147     }
00148   };
00149   friend class BitProxy;
00150 
00154   csBitArray () : mpStore(0), mSingleWord(0), mLength(0), mNumBits(0)
00155   {
00156     SetSize (0);
00157     // Clear last bits
00158     Trim();
00159   }
00160 
00164   explicit csBitArray(size_t size) :
00165     mpStore(0), mSingleWord(0), mLength(0), mNumBits(0)
00166   {
00167     SetSize (size);
00168     // Clear last bits
00169     Trim();
00170   }
00171 
00175   csBitArray (const csBitArray &that) :
00176     mpStore(0), mSingleWord(0), mLength(0), mNumBits(0)
00177   {
00178     *this = that;
00179   }
00180 
00182   virtual ~csBitArray()
00183   {
00184     if (mLength > 1)
00185       delete mpStore;
00186   }
00187 
00189   size_t Length() const
00190   {
00191     return mNumBits;
00192   }
00193 
00199   void SetLength (size_t newSize)
00200   {
00201     SetSize (newSize);
00202     // Clear last bits
00203     Trim ();
00204   }
00205 
00206   //
00207   // Operators
00208   //
00209 
00211   csBitArray &operator=(const csBitArray &that)
00212   {
00213     if (this != &that)
00214     {
00215       SetSize (that.mNumBits);
00216       memcpy (mpStore, that.mpStore, mLength * sizeof(store_type));
00217     }
00218     return *this;
00219   }
00220 
00222   BitProxy operator[] (size_t pos)
00223   {
00224     CS_ASSERT (pos < mNumBits);
00225     return BitProxy(*this, pos);
00226   }
00227 
00229   const BitProxy operator[] (size_t pos) const
00230   {
00231     CS_ASSERT (pos < mNumBits);
00232     return BitProxy(CS_CONST_CAST(csBitArray&,*this), pos);
00233   }
00234 
00236   bool operator==(const csBitArray &that) const
00237   {
00238     if (mNumBits != that.mNumBits)
00239       return false;
00240 
00241     for (unsigned i = 0; i < mLength; i++)
00242       if (mpStore[i] != that.mpStore[i])
00243         return false;
00244     return true;
00245   }
00246 
00248   bool operator != (const csBitArray &that) const
00249   {
00250     return !(*this == that);
00251   }
00252 
00254   csBitArray& operator &= (const csBitArray &that)
00255   {
00256     CS_ASSERT (mNumBits == that.mNumBits);
00257     for (size_t i = 0; i < mLength; i++)
00258       mpStore[i] &= that.mpStore[i];
00259     return *this;
00260   }
00261 
00263   csBitArray operator |= (const csBitArray &that)
00264   {
00265     CS_ASSERT (mNumBits == that.mNumBits);
00266     for (size_t i = 0; i < mLength; i++)
00267       mpStore[i] |= that.mpStore[i];
00268     return *this;
00269   }
00270 
00272   csBitArray operator ^= (const csBitArray &that)
00273   {
00274     CS_ASSERT (mNumBits == that.mNumBits);
00275     for (size_t i = 0; i < mLength; i++)
00276       mpStore[i] ^= that.mpStore[i];
00277     return *this;
00278   }
00279 
00281   csBitArray operator~() const
00282   {
00283     return csBitArray(*this).FlipAllBits();
00284   }
00285 
00287   friend csBitArray operator& (const csBitArray &a1, const csBitArray &a2)
00288   {
00289     return csBitArray(a1) &= a2;
00290   }
00291 
00293   friend csBitArray operator | (const csBitArray &a1, const csBitArray &a2)
00294   {
00295     return csBitArray(a1) |= a2;
00296   }
00297 
00299   friend csBitArray operator ^ (const csBitArray &a1, const csBitArray &a2)
00300   {
00301     return csBitArray(a1) ^= a2;
00302   }
00303 
00304   //
00305   // Plain English interface
00306   //
00307 
00309   void Clear()
00310   {
00311     memset (mpStore, 0, mLength * sizeof(store_type));
00312   }
00313 
00315   void SetBit (size_t pos)
00316   {
00317     CS_ASSERT (pos < mNumBits);
00318     mpStore[GetIndex(pos)] |= 1 << GetOffset(pos);
00319   }
00320 
00322   void ClearBit (size_t pos)
00323   {
00324     CS_ASSERT (pos < mNumBits);
00325     mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos));
00326   }
00327 
00329   void FlipBit (size_t pos)
00330   {
00331     CS_ASSERT (pos < mNumBits);
00332     mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos);
00333   }
00334 
00336   void Set (size_t pos, bool val)
00337   {
00338     val ? SetBit(pos) : ClearBit(pos);
00339   }
00340 
00342   bool IsBitSet (size_t pos) const
00343   {
00344     CS_ASSERT (pos < mNumBits);
00345     return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
00346   }
00347 
00352   bool AreSomeBitsSet (size_t pos, size_t count) const
00353   {
00354     CS_ASSERT (pos < mNumBits);
00355     CS_ASSERT ((pos + count) < mNumBits);
00356     
00357     while (count > 0)
00358     {
00359       size_t index = GetIndex (pos);
00360       size_t offset = GetOffset (pos);
00361       size_t checkCount = MIN(count, cell_size - offset);
00362             
00363       store_type mask = ((1 << checkCount) - 1) << offset;
00364       if (mpStore[index] & mask) return true;
00365       pos += checkCount;
00366       count -= checkCount;
00367     }
00368     return false;
00369   }
00370   
00372   bool AllBitsFalse() const
00373   {
00374     for (unsigned i=0; i < mLength; i++)
00375       if (mpStore[i] != 0)
00376         return false;
00377     return true;
00378   }
00379 
00381   csBitArray &FlipAllBits()
00382   {
00383     for (unsigned i=0; i < mLength; i++)
00384       mpStore[i] = ~mpStore[i];
00385 
00386     Trim();
00387     return *this;
00388   }
00389 
00391   store_type* GetArrayBits()
00392   {
00393     return mpStore;
00394   }
00395 
00400   store_type GetSingleWord()
00401   {
00402     return mSingleWord;
00403   }
00404 
00409   void SetSingleWord (store_type sw)
00410   {
00411     mSingleWord = sw;
00412   }
00413 };
00414 
00415 #endif // __CS_BITARRAY_H__

Generated for Crystal Space by doxygen 1.3.9.1