|
bitarray.h00001 // A one-dimensional array of bits, similar to STL bitset. 00002 // 00003 // Copyright 2000 Andrew Kirmse. All rights reserved. 00004 // 00005 // Permission is granted to use this code for any purpose, as long as this 00006 // copyright message remains intact. 00007 00008 #ifndef _csBitArray_H 00009 #define _csBitArray_H 00010 00011 #include <memory.h> 00012 #include <assert.h> 00013 00014 class csBitArray 00015 { 00016 private: 00017 00018 typedef unsigned long store_type; 00019 enum 00020 { 00021 bits_per_byte = 8, 00022 cell_size = sizeof(store_type) * bits_per_byte 00023 }; 00024 00025 store_type *mpStore; 00026 store_type mSingleWord; // Use this buffer when mLength is 1 00027 unsigned mLength; // Length of mpStore in units of store_type 00028 unsigned mNumBits; 00029 00030 // Get the index and bit offset for a given bit number. 00031 static unsigned GetIndex(unsigned bit_num) 00032 { 00033 return bit_num / cell_size; 00034 } 00035 00036 static unsigned GetOffset(unsigned bit_num) 00037 { 00038 return bit_num % cell_size; 00039 } 00040 00041 void Init(unsigned size) 00042 { 00043 mNumBits = size; 00044 00045 if (size == 0) 00046 mLength = 0; 00047 else 00048 mLength = 1 + GetIndex(size - 1); 00049 00050 // Avoid allocation if length is 1 (common case) 00051 if (mLength <= 1) 00052 mpStore = &mSingleWord; 00053 else 00054 mpStore = new store_type[mLength]; 00055 } 00056 00057 // Force overhang bits at the end to 0 00058 inline void Trim() 00059 { 00060 unsigned extra_bits = mNumBits % cell_size; 00061 if (mLength > 0 && extra_bits != 0) 00062 mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits); 00063 } 00064 00065 public: 00066 00067 // 00068 // Bit proxy (for operator[]) 00069 // 00070 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 // Constructors and destructor 00110 // 00111 00112 explicit csBitArray(unsigned size) 00113 { 00114 Init(size); 00115 00116 // Clear last bits 00117 Trim(); 00118 } 00119 00120 csBitArray(const csBitArray &that) 00121 { 00122 mpStore = 0; 00123 *this = that; 00124 } 00125 00126 virtual ~csBitArray() 00127 { 00128 if (mLength > 1) 00129 delete mpStore; 00130 } 00131 00132 // 00133 // Operators 00134 // 00135 00136 00137 00138 csBitArray &operator=(const csBitArray &that) 00139 { 00140 if (this != &that) 00141 { 00142 if (mLength > 1) 00143 delete mpStore; 00144 00145 Init(that.mNumBits); 00146 00147 memcpy(mpStore, that.mpStore, mLength * sizeof(store_type)); 00148 } 00149 return *this; 00150 } 00151 00152 BitProxy operator[](unsigned pos) 00153 { 00154 assert(pos < mNumBits); 00155 return BitProxy(*this, pos); 00156 } 00157 00158 const BitProxy operator[](unsigned pos) const 00159 { 00160 assert(pos < mNumBits); 00161 return BitProxy(CONST_CAST(csBitArray&,*this), pos); 00162 } 00163 00164 bool operator==(const csBitArray &that) const 00165 { 00166 if (mNumBits != that.mNumBits) 00167 return false; 00168 00169 for (unsigned i = 0; i < mLength; i++) 00170 if (mpStore[i] != that.mpStore[i]) 00171 return false; 00172 return true; 00173 } 00174 00175 bool operator!=(const csBitArray &that) const 00176 { 00177 return !(*this == that); 00178 } 00179 00180 csBitArray &operator&=(const csBitArray &that) 00181 { 00182 assert(mNumBits == that.mNumBits); 00183 for (unsigned i = 0; i < mLength; i++) 00184 mpStore[i] &= that.mpStore[i]; 00185 return *this; 00186 } 00187 00188 csBitArray operator|=(const csBitArray &that) 00189 { 00190 assert(mNumBits == that.mNumBits); 00191 for (unsigned i = 0; i < mLength; i++) 00192 mpStore[i] |= that.mpStore[i]; 00193 return *this; 00194 } 00195 00196 csBitArray operator^=(const csBitArray &that) 00197 { 00198 assert(mNumBits == that.mNumBits); 00199 for (unsigned i = 0; i < mLength; i++) 00200 mpStore[i] ^= that.mpStore[i]; 00201 return *this; 00202 } 00203 00204 csBitArray operator~() const 00205 { 00206 return csBitArray(*this).FlipAllBits(); 00207 } 00208 00209 friend csBitArray operator&(const csBitArray &a1, const csBitArray &a2) 00210 { 00211 return csBitArray(a1) &= a2; 00212 } 00213 00214 friend csBitArray operator|(const csBitArray &a1, const csBitArray &a2) 00215 { 00216 return csBitArray(a1) |= a2; 00217 } 00218 00219 friend csBitArray operator^(const csBitArray &a1, const csBitArray &a2) 00220 { 00221 return csBitArray(a1) ^= a2; 00222 } 00223 00224 // 00225 // Plain English interface 00226 // 00227 00229 void Clear() 00230 { 00231 memset(mpStore, 0, mLength * sizeof(store_type)); 00232 } 00233 00235 void SetBit(unsigned pos) 00236 { 00237 assert(pos < mNumBits); 00238 mpStore[GetIndex(pos)] |= 1 << GetOffset(pos); 00239 } 00240 00242 void ClearBit(unsigned pos) 00243 { 00244 assert(pos < mNumBits); 00245 mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos)); 00246 } 00247 00249 void FlipBit(unsigned pos) 00250 { 00251 assert(pos < mNumBits); 00252 mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos); 00253 } 00254 00256 void Set(unsigned pos, bool val) 00257 { 00258 val ? SetBit(pos) : ClearBit(pos); 00259 } 00260 00262 bool IsBitSet(unsigned pos) const 00263 { 00264 assert(pos < mNumBits); 00265 return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0; 00266 } 00267 00269 bool AllBitsFalse() const 00270 { 00271 for (unsigned i=0; i < mLength; i++) 00272 if (mpStore[i] != 0) 00273 return false; 00274 return true; 00275 } 00276 00278 csBitArray &FlipAllBits() 00279 { 00280 for (unsigned i=0; i < mLength; i++) 00281 mpStore[i] = ~mpStore[i]; 00282 00283 Trim(); 00284 return *this; 00285 } 00286 00288 unsigned GetSingleWord() 00289 { 00290 return mSingleWord; 00291 } 00292 00294 void SetSingleWord(unsigned w) 00295 { 00296 mSingleWord=w; 00297 } 00298 }; 00299 00300 #endif Generated for Crystal Space by doxygen 1.2.5 written by Dimitri van Heesch, ©1997-2000 |