00001
00002
00003
00004
00005
00006
00007
00008 #ifndef __CS_BITARRAY_H__
00009 #define __CS_BITARRAY_H__
00010
00011 #include <memory.h>
00012 #include <assert.h>
00013
00015 class csBitArray
00016 {
00017 private:
00018
00019 typedef unsigned long store_type;
00020 enum
00021 {
00022 bits_per_byte = 8,
00023 cell_size = sizeof(store_type) * bits_per_byte
00024 };
00025
00026 store_type *mpStore;
00027 store_type mSingleWord;
00028 unsigned mLength;
00029 unsigned mNumBits;
00030
00032 static unsigned GetIndex(unsigned bit_num)
00033 {
00034 return bit_num / cell_size;
00035 }
00036
00037 static unsigned GetOffset(unsigned bit_num)
00038 {
00039 return bit_num % cell_size;
00040 }
00041
00042 void Init(unsigned size)
00043 {
00044 mNumBits = size;
00045
00046 if (size == 0)
00047 mLength = 0;
00048 else
00049 mLength = 1 + GetIndex(size - 1);
00050
00051
00052 if (mLength <= 1)
00053 mpStore = &mSingleWord;
00054 else
00055 mpStore = new store_type[mLength];
00056 }
00057
00059 inline void Trim()
00060 {
00061 unsigned extra_bits = mNumBits % cell_size;
00062 if (mLength > 0 && extra_bits != 0)
00063 mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
00064 }
00065
00066 public:
00067
00071 class BitProxy
00072 {
00073 private:
00074 csBitArray &mArray;
00075 unsigned mPos;
00076 public:
00077 BitProxy(csBitArray &array, unsigned pos):
00078 mArray(array), mPos(pos)
00079 {}
00080
00081 BitProxy &operator=(bool value)
00082 {
00083 mArray.Set(mPos, value);
00084 return *this;
00085 }
00086
00087 BitProxy &operator=(const BitProxy &that)
00088 {
00089 mArray.Set(mPos, that.mArray.IsBitSet(that.mPos));
00090 return *this;
00091 }
00092
00093 operator bool() const
00094 {
00095 return mArray.IsBitSet(mPos);
00096 }
00097
00098 bool Flip()
00099 {
00100 mArray.FlipBit(mPos);
00101 return mArray.IsBitSet(mPos);
00102 }
00103 };
00104
00105
00106 friend class BitProxy;
00107
00108
00109
00110
00111
00113 explicit csBitArray(unsigned size)
00114 {
00115 Init(size);
00116
00117 Trim();
00118 }
00119
00121 csBitArray(const csBitArray &that)
00122 {
00123 mpStore = 0;
00124 *this = that;
00125 }
00126
00128 virtual ~csBitArray()
00129 {
00130 if (mLength > 1)
00131 delete mpStore;
00132 }
00133
00134
00135
00136
00137
00139 csBitArray &operator=(const csBitArray &that)
00140 {
00141 if (this != &that)
00142 {
00143 if (mLength > 1)
00144 delete mpStore;
00145
00146 Init(that.mNumBits);
00147
00148 memcpy(mpStore, that.mpStore, mLength * sizeof(store_type));
00149 }
00150 return *this;
00151 }
00152
00154 BitProxy operator[](unsigned pos)
00155 {
00156 assert(pos < mNumBits);
00157 return BitProxy(*this, pos);
00158 }
00159
00161 const BitProxy operator[](unsigned pos) const
00162 {
00163 assert(pos < mNumBits);
00164 return BitProxy(CONST_CAST(csBitArray&,*this), pos);
00165 }
00166
00168 bool operator==(const csBitArray &that) const
00169 {
00170 if (mNumBits != that.mNumBits)
00171 return false;
00172
00173 for (unsigned i = 0; i < mLength; i++)
00174 if (mpStore[i] != that.mpStore[i])
00175 return false;
00176 return true;
00177 }
00178
00180 bool operator!=(const csBitArray &that) const
00181 {
00182 return !(*this == that);
00183 }
00184
00186 csBitArray &operator&=(const csBitArray &that)
00187 {
00188 assert(mNumBits == that.mNumBits);
00189 for (unsigned i = 0; i < mLength; i++)
00190 mpStore[i] &= that.mpStore[i];
00191 return *this;
00192 }
00193
00195 csBitArray operator|=(const csBitArray &that)
00196 {
00197 assert(mNumBits == that.mNumBits);
00198 for (unsigned i = 0; i < mLength; i++)
00199 mpStore[i] |= that.mpStore[i];
00200 return *this;
00201 }
00202
00204 csBitArray operator^=(const csBitArray &that)
00205 {
00206 assert(mNumBits == that.mNumBits);
00207 for (unsigned i = 0; i < mLength; i++)
00208 mpStore[i] ^= that.mpStore[i];
00209 return *this;
00210 }
00211
00213 csBitArray operator~() const
00214 {
00215 return csBitArray(*this).FlipAllBits();
00216 }
00217
00219 friend csBitArray operator&(const csBitArray &a1, const csBitArray &a2)
00220 {
00221 return csBitArray(a1) &= a2;
00222 }
00223
00225 friend csBitArray operator|(const csBitArray &a1, const csBitArray &a2)
00226 {
00227 return csBitArray(a1) |= a2;
00228 }
00229
00231 friend csBitArray operator^(const csBitArray &a1, const csBitArray &a2)
00232 {
00233 return csBitArray(a1) ^= a2;
00234 }
00235
00236
00237
00238
00239
00241 void Clear()
00242 {
00243 memset(mpStore, 0, mLength * sizeof(store_type));
00244 }
00245
00247 void SetBit(unsigned pos)
00248 {
00249 assert(pos < mNumBits);
00250 mpStore[GetIndex(pos)] |= 1 << GetOffset(pos);
00251 }
00252
00254 void ClearBit(unsigned pos)
00255 {
00256 assert(pos < mNumBits);
00257 mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos));
00258 }
00259
00261 void FlipBit(unsigned pos)
00262 {
00263 assert(pos < mNumBits);
00264 mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos);
00265 }
00266
00268 void Set(unsigned pos, bool val)
00269 {
00270 val ? SetBit(pos) : ClearBit(pos);
00271 }
00272
00274 bool IsBitSet(unsigned pos) const
00275 {
00276 assert(pos < mNumBits);
00277 return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
00278 }
00279
00281 bool AllBitsFalse() const
00282 {
00283 for (unsigned i=0; i < mLength; i++)
00284 if (mpStore[i] != 0)
00285 return false;
00286 return true;
00287 }
00288
00290 csBitArray &FlipAllBits()
00291 {
00292 for (unsigned i=0; i < mLength; i++)
00293 mpStore[i] = ~mpStore[i];
00294
00295 Trim();
00296 return *this;
00297 }
00298
00300 store_type* GetArrayBits()
00301 {
00302 return mpStore;
00303 }
00304
00306 unsigned GetSingleWord()
00307 {
00308 return mSingleWord;
00309 }
00310
00312 void SetSingleWord(unsigned w)
00313 {
00314 mSingleWord=w;
00315 }
00316 };
00317
00318 #endif // __CS_BITARRAY_H__