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