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