CrystalSpace

Public API Reference

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

csutil/bitarray.h

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 
00030 class csBitArray
00031 {
00032 private:
00033   typedef unsigned long store_type;
00034   enum
00035   {
00036     bits_per_byte = 8,
00037     cell_size     = sizeof(store_type) * bits_per_byte
00038   };
00039 
00040   store_type *mpStore;
00041   store_type mSingleWord; // Use this buffer when mLength is 1
00042   unsigned mLength;       // Length of mpStore in units of store_type
00043   unsigned mNumBits;
00044 
00046   static unsigned GetIndex(unsigned bit_num)
00047   {
00048     return bit_num / cell_size;
00049   }
00050 
00051   static unsigned GetOffset(unsigned bit_num)
00052   {
00053     return bit_num % cell_size;
00054   }
00055 
00056   void Init(unsigned size)
00057   {
00058     mNumBits = size;
00059 
00060     if (size == 0)
00061       mLength = 0;
00062     else
00063       mLength = 1 + GetIndex(size - 1);
00064 
00065     // Avoid allocation if length is 1 (common case)
00066     if (mLength <= 1)
00067       mpStore = &mSingleWord;
00068     else
00069       mpStore = new store_type[mLength];
00070   }
00071 
00073   inline void Trim()
00074   {
00075     unsigned extra_bits = mNumBits % cell_size;
00076     if (mLength > 0 && extra_bits != 0)
00077       mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
00078   }
00079 
00080 public:
00084   class BitProxy
00085   {
00086   private:
00087     csBitArray &mArray;
00088     unsigned  mPos;
00089   public:
00090     BitProxy(csBitArray &array, unsigned pos): mArray(array), mPos(pos)
00091     {}
00092 
00093     BitProxy &operator= (bool value)
00094     {
00095       mArray.Set(mPos, value);
00096       return *this;
00097     }
00098 
00099     BitProxy &operator= (const BitProxy &that)
00100     {
00101       mArray.Set(mPos, that.mArray.IsBitSet(that.mPos));
00102       return *this;
00103     }
00104 
00105     operator bool() const
00106     {
00107       return mArray.IsBitSet(mPos);
00108     }
00109 
00110     bool Flip()
00111     {
00112       mArray.FlipBit(mPos);
00113       return mArray.IsBitSet(mPos);
00114     }
00115   };
00116 
00117 
00118   friend class BitProxy;
00119 
00120   //
00121   // Constructors and destructor
00122   //
00123 
00125   explicit csBitArray(unsigned size)
00126   {
00127     Init(size);
00128     // Clear last bits
00129     Trim();
00130   }
00131 
00133   csBitArray(const csBitArray &that)
00134   {
00135     mpStore = 0;
00136     *this = that;
00137   }
00138 
00140   virtual ~csBitArray()
00141   {
00142     if (mLength > 1)
00143       delete mpStore;
00144   }
00145 
00146   //
00147   // Operators
00148   //
00149 
00151   csBitArray &operator=(const csBitArray &that)
00152   {
00153     if (this != &that)
00154     {
00155       if (mLength > 1)
00156         delete mpStore;
00157 
00158       Init(that.mNumBits);
00159 
00160       memcpy (mpStore, that.mpStore, mLength * sizeof(store_type));
00161     }
00162     return *this;
00163   }
00164 
00166   BitProxy operator[](unsigned pos)
00167   {
00168     CS_ASSERT (pos < mNumBits);
00169     return BitProxy(*this, pos);
00170   }
00171 
00173   const BitProxy operator[](unsigned pos) const
00174   {
00175     CS_ASSERT (pos < mNumBits);
00176     return BitProxy(CS_CONST_CAST(csBitArray&,*this), pos);
00177   }
00178 
00180   bool operator==(const csBitArray &that) const
00181   {
00182     if (mNumBits != that.mNumBits)
00183       return false;
00184 
00185     for (unsigned i = 0; i < mLength; i++)
00186       if (mpStore[i] != that.mpStore[i])
00187         return false;
00188     return true;
00189   }
00190 
00192   bool operator!=(const csBitArray &that) const
00193   {
00194     return !(*this == that);
00195   }
00196 
00198   csBitArray &operator&=(const csBitArray &that)
00199   {
00200     CS_ASSERT (mNumBits == that.mNumBits);
00201     for (unsigned i = 0; i < mLength; i++)
00202       mpStore[i] &= that.mpStore[i];
00203     return *this;
00204   }
00205 
00207   csBitArray operator|=(const csBitArray &that)
00208   {
00209     CS_ASSERT (mNumBits == that.mNumBits);
00210     for (unsigned i = 0; i < mLength; i++)
00211       mpStore[i] |= that.mpStore[i];
00212     return *this;
00213   }
00214 
00216   csBitArray operator^=(const csBitArray &that)
00217   {
00218     CS_ASSERT (mNumBits == that.mNumBits);
00219     for (unsigned i = 0; i < mLength; i++)
00220       mpStore[i] ^= that.mpStore[i];
00221     return *this;
00222   }
00223 
00225   csBitArray operator~() const
00226   {
00227     return csBitArray(*this).FlipAllBits();
00228   }
00229 
00231   friend csBitArray operator&(const csBitArray &a1, const csBitArray &a2)
00232   {
00233     return csBitArray(a1) &= a2;
00234   }
00235 
00237   friend csBitArray operator|(const csBitArray &a1, const csBitArray &a2)
00238   {
00239     return csBitArray(a1) |= a2;
00240   }
00241 
00243   friend csBitArray operator^(const csBitArray &a1, const csBitArray &a2)
00244   {
00245     return csBitArray(a1) ^= a2;
00246   }
00247 
00248   //
00249   // Plain English interface
00250   //
00251 
00253   void Clear()
00254   {
00255     memset (mpStore, 0, mLength * sizeof(store_type));
00256   }
00257 
00259   void SetBit(unsigned pos)
00260   {
00261     CS_ASSERT (pos < mNumBits);
00262     mpStore[GetIndex(pos)] |= 1 << GetOffset(pos);
00263   }
00264 
00266   void ClearBit(unsigned pos)
00267   {
00268     CS_ASSERT (pos < mNumBits);
00269     mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos));
00270   }
00271 
00273   void FlipBit(unsigned pos)
00274   {
00275     CS_ASSERT (pos < mNumBits);
00276     mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos);
00277   }
00278 
00280   void Set(unsigned pos, bool val)
00281   {
00282     val ? SetBit(pos) : ClearBit(pos);
00283   }
00284 
00286   bool IsBitSet(unsigned pos) const
00287   {
00288     CS_ASSERT (pos < mNumBits);
00289     return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
00290   }
00291 
00293   bool AllBitsFalse() const
00294   {
00295     for (unsigned i=0; i < mLength; i++)
00296       if (mpStore[i] != 0)
00297         return false;
00298     return true;
00299   }
00300 
00302   csBitArray &FlipAllBits()
00303   {
00304     for (unsigned i=0; i < mLength; i++)
00305       mpStore[i] = ~mpStore[i];
00306 
00307     Trim();
00308     return *this;
00309   }
00310 
00312   store_type* GetArrayBits()
00313   {
00314     return mpStore;
00315   }
00316 
00321   unsigned GetSingleWord()
00322   {
00323     return mSingleWord;
00324   }
00325 
00330   void SetSingleWord(unsigned w)
00331   {
00332     mSingleWord=w;
00333   }
00334 };
00335 
00336 #endif // __CS_BITARRAY_H__

Generated for Crystal Space by doxygen 1.2.18