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 00029 #include "csextern.h" 00030 00034 class CS_CSUTIL_EXPORT csBitArray 00035 { 00036 public: 00037 typedef unsigned long store_type; 00038 private: 00039 enum 00040 { 00041 bits_per_byte = 8, 00042 cell_size = sizeof(store_type) * bits_per_byte 00043 }; 00044 00045 store_type *mpStore; 00046 store_type mSingleWord; // Use this buffer when mLength is 1 00047 size_t mLength; // Length of mpStore in units of store_type 00048 size_t mNumBits; 00049 00051 static inline size_t GetIndex (size_t bit_num) 00052 { 00053 return bit_num / cell_size; 00054 } 00055 00056 static inline size_t GetOffset (size_t bit_num) 00057 { 00058 return bit_num % cell_size; 00059 } 00060 00061 void SetSize (size_t newSize) 00062 { 00063 size_t newLength; 00064 if (newSize == 0) 00065 newLength = 0; 00066 else 00067 newLength = 1 + GetIndex (newSize - 1); 00068 00069 // Avoid allocation if length is 1 (common case) 00070 store_type* newStore; 00071 if (newLength <= 1) 00072 newStore = &mSingleWord; 00073 else 00074 newStore = new store_type[newLength]; 00075 00076 if (newLength > 0) 00077 { 00078 if (mLength > 0) 00079 memcpy (newStore, mpStore, 00080 (MIN (mLength, newLength)) * sizeof (store_type)); 00081 else 00082 memset (newStore, 0, newLength * sizeof (store_type)); 00083 } 00084 00085 if (mLength > 1) 00086 delete mpStore; 00087 00088 mpStore = newStore; 00089 mNumBits = newSize; 00090 mLength = newLength; 00091 } 00092 00094 inline void Trim() 00095 { 00096 size_t extra_bits = mNumBits % cell_size; 00097 if (mLength > 0 && extra_bits != 0) 00098 mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits); 00099 } 00100 00101 public: 00105 class CS_CSUTIL_EXPORT BitProxy 00106 { 00107 private: 00108 csBitArray &mArray; 00109 size_t mPos; 00110 public: 00112 BitProxy(csBitArray &array, unsigned pos): mArray(array), mPos(pos) 00113 {} 00114 00116 BitProxy &operator= (bool value) 00117 { 00118 mArray.Set (mPos, value); 00119 return *this; 00120 } 00121 00123 BitProxy &operator= (const BitProxy &that) 00124 { 00125 mArray.Set (mPos, that.mArray.IsBitSet (that.mPos)); 00126 return *this; 00127 } 00128 00130 operator bool() const 00131 { 00132 return mArray.IsBitSet (mPos); 00133 } 00134 00136 bool Flip() 00137 { 00138 mArray.FlipBit (mPos); 00139 return mArray.IsBitSet (mPos); 00140 } 00141 }; 00142 friend class BitProxy; 00143 00147 csBitArray () : mpStore(0), mSingleWord(0), mLength(0), mNumBits(0) 00148 { 00149 SetSize (0); 00150 // Clear last bits 00151 Trim(); 00152 } 00153 00157 explicit csBitArray(size_t size) : 00158 mpStore(0), mSingleWord(0), mLength(0), mNumBits(0) 00159 { 00160 SetSize (size); 00161 // Clear last bits 00162 Trim(); 00163 } 00164 00168 csBitArray (const csBitArray &that) : 00169 mpStore(0), mSingleWord(0), mLength(0), mNumBits(0) 00170 { 00171 *this = that; 00172 } 00173 00175 virtual ~csBitArray() 00176 { 00177 if (mLength > 1) 00178 delete mpStore; 00179 } 00180 00182 size_t Length() const 00183 { 00184 return mNumBits; 00185 } 00186 00192 void SetLength (size_t newSize) 00193 { 00194 SetSize (newSize); 00195 // Clear last bits 00196 Trim (); 00197 } 00198 00199 // 00200 // Operators 00201 // 00202 00204 csBitArray &operator=(const csBitArray &that) 00205 { 00206 if (this != &that) 00207 { 00208 SetSize (that.mNumBits); 00209 memcpy (mpStore, that.mpStore, mLength * sizeof(store_type)); 00210 } 00211 return *this; 00212 } 00213 00215 BitProxy operator[] (size_t pos) 00216 { 00217 CS_ASSERT (pos < mNumBits); 00218 return BitProxy(*this, pos); 00219 } 00220 00222 const BitProxy operator[] (size_t pos) const 00223 { 00224 CS_ASSERT (pos < mNumBits); 00225 return BitProxy(CS_CONST_CAST(csBitArray&,*this), pos); 00226 } 00227 00229 bool operator==(const csBitArray &that) const 00230 { 00231 if (mNumBits != that.mNumBits) 00232 return false; 00233 00234 for (unsigned i = 0; i < mLength; i++) 00235 if (mpStore[i] != that.mpStore[i]) 00236 return false; 00237 return true; 00238 } 00239 00241 bool operator != (const csBitArray &that) const 00242 { 00243 return !(*this == that); 00244 } 00245 00247 csBitArray& operator &= (const csBitArray &that) 00248 { 00249 CS_ASSERT (mNumBits == that.mNumBits); 00250 for (size_t i = 0; i < mLength; i++) 00251 mpStore[i] &= that.mpStore[i]; 00252 return *this; 00253 } 00254 00256 csBitArray operator |= (const csBitArray &that) 00257 { 00258 CS_ASSERT (mNumBits == that.mNumBits); 00259 for (size_t i = 0; i < mLength; i++) 00260 mpStore[i] |= that.mpStore[i]; 00261 return *this; 00262 } 00263 00265 csBitArray operator ^= (const csBitArray &that) 00266 { 00267 CS_ASSERT (mNumBits == that.mNumBits); 00268 for (size_t i = 0; i < mLength; i++) 00269 mpStore[i] ^= that.mpStore[i]; 00270 return *this; 00271 } 00272 00274 csBitArray operator~() const 00275 { 00276 return csBitArray(*this).FlipAllBits(); 00277 } 00278 00280 friend csBitArray operator& (const csBitArray &a1, const csBitArray &a2) 00281 { 00282 return csBitArray(a1) &= a2; 00283 } 00284 00286 friend csBitArray operator | (const csBitArray &a1, const csBitArray &a2) 00287 { 00288 return csBitArray(a1) |= a2; 00289 } 00290 00292 friend csBitArray operator ^ (const csBitArray &a1, const csBitArray &a2) 00293 { 00294 return csBitArray(a1) ^= a2; 00295 } 00296 00297 // 00298 // Plain English interface 00299 // 00300 00302 void Clear() 00303 { 00304 memset (mpStore, 0, mLength * sizeof(store_type)); 00305 } 00306 00308 void SetBit (size_t pos) 00309 { 00310 CS_ASSERT (pos < mNumBits); 00311 mpStore[GetIndex(pos)] |= 1 << GetOffset(pos); 00312 } 00313 00315 void ClearBit (size_t pos) 00316 { 00317 CS_ASSERT (pos < mNumBits); 00318 mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos)); 00319 } 00320 00322 void FlipBit (size_t pos) 00323 { 00324 CS_ASSERT (pos < mNumBits); 00325 mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos); 00326 } 00327 00329 void Set (size_t pos, bool val) 00330 { 00331 val ? SetBit(pos) : ClearBit(pos); 00332 } 00333 00335 bool IsBitSet (size_t pos) const 00336 { 00337 CS_ASSERT (pos < mNumBits); 00338 return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0; 00339 } 00340 00345 bool AreSomeBitsSet (size_t pos, size_t count) const 00346 { 00347 CS_ASSERT (pos < mNumBits); 00348 CS_ASSERT ((pos + count) < mNumBits); 00349 00350 while (count > 0) 00351 { 00352 size_t index = GetIndex (pos); 00353 size_t offset = GetOffset (pos); 00354 size_t checkCount = MIN(count, cell_size - offset); 00355 00356 store_type mask = ((1 << checkCount) - 1) << offset; 00357 if (mpStore[index] & mask) return true; 00358 pos += checkCount; 00359 count -= checkCount; 00360 } 00361 return false; 00362 } 00363 00365 bool AllBitsFalse() const 00366 { 00367 for (unsigned i=0; i < mLength; i++) 00368 if (mpStore[i] != 0) 00369 return false; 00370 return true; 00371 } 00372 00374 csBitArray &FlipAllBits() 00375 { 00376 for (unsigned i=0; i < mLength; i++) 00377 mpStore[i] = ~mpStore[i]; 00378 00379 Trim(); 00380 return *this; 00381 } 00382 00384 store_type* GetArrayBits() 00385 { 00386 return mpStore; 00387 } 00388 00393 store_type GetSingleWord() 00394 { 00395 return mSingleWord; 00396 } 00397 00402 void SetSingleWord (store_type sw) 00403 { 00404 mSingleWord = sw; 00405 } 00406 }; 00407 00408 #endif // __CS_BITARRAY_H__
Generated for Crystal Space by doxygen 1.2.18