Panda3D
|
00001 // Filename: bitArray.I 00002 // Created by: drose (20Jan06) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 00016 //////////////////////////////////////////////////////////////////// 00017 // Function: BitArray::Constructor 00018 // Access: Published 00019 // Description: 00020 //////////////////////////////////////////////////////////////////// 00021 INLINE BitArray:: 00022 BitArray() { 00023 _highest_bits = 0; 00024 } 00025 00026 //////////////////////////////////////////////////////////////////// 00027 // Function: BitArray::Constructor 00028 // Access: Published 00029 // Description: 00030 //////////////////////////////////////////////////////////////////// 00031 INLINE BitArray:: 00032 BitArray(WordType init_value) { 00033 if (init_value != 0) { 00034 _array.push_back(MaskType(init_value)); 00035 } 00036 _highest_bits = 0; 00037 } 00038 00039 //////////////////////////////////////////////////////////////////// 00040 // Function: BitArray::Copy Constructor 00041 // Access: Published 00042 // Description: 00043 //////////////////////////////////////////////////////////////////// 00044 INLINE BitArray:: 00045 BitArray(const BitArray ©) : 00046 _array(copy._array), 00047 _highest_bits(copy._highest_bits) 00048 { 00049 } 00050 00051 //////////////////////////////////////////////////////////////////// 00052 // Function: BitArray::Copy Assignment Operator 00053 // Access: Published 00054 // Description: 00055 //////////////////////////////////////////////////////////////////// 00056 INLINE BitArray &BitArray:: 00057 operator = (const BitArray ©) { 00058 _array = copy._array; 00059 _highest_bits = copy._highest_bits; 00060 return *this; 00061 } 00062 00063 //////////////////////////////////////////////////////////////////// 00064 // Function: BitArray::Named all_on constructor 00065 // Access: Published, Static 00066 // Description: Returns a BitArray with an infinite array of bits, 00067 // all on. 00068 //////////////////////////////////////////////////////////////////// 00069 INLINE BitArray BitArray:: 00070 all_on() { 00071 BitArray result; 00072 result._highest_bits = 1; 00073 return result; 00074 } 00075 00076 //////////////////////////////////////////////////////////////////// 00077 // Function: BitArray::Named all_on constructor 00078 // Access: Published, Static 00079 // Description: Returns a BitArray whose bits are all off. 00080 //////////////////////////////////////////////////////////////////// 00081 INLINE BitArray BitArray:: 00082 all_off() { 00083 return BitArray(); 00084 } 00085 00086 //////////////////////////////////////////////////////////////////// 00087 // Function: BitArray::Named lower_on constructor 00088 // Access: Published, Static 00089 // Description: Returns a BitArray whose lower on_bits bits are on. 00090 //////////////////////////////////////////////////////////////////// 00091 INLINE BitArray BitArray:: 00092 lower_on(int on_bits) { 00093 BitArray result; 00094 result.set_range(0, on_bits); 00095 return result; 00096 } 00097 00098 //////////////////////////////////////////////////////////////////// 00099 // Function: BitArray::Named bit constructor 00100 // Access: Published, Static 00101 // Description: Returns a BitArray with only the indicated bit on. 00102 //////////////////////////////////////////////////////////////////// 00103 INLINE BitArray BitArray:: 00104 bit(int index) { 00105 BitArray result; 00106 result.set_bit(index); 00107 return result; 00108 } 00109 00110 //////////////////////////////////////////////////////////////////// 00111 // Function: BitArray::Named range constructor 00112 // Access: Published, Static 00113 // Description: Returns a BitArray whose size bits, beginning at 00114 // low_bit, are on. 00115 //////////////////////////////////////////////////////////////////// 00116 INLINE BitArray BitArray:: 00117 range(int low_bit, int size) { 00118 BitArray result; 00119 result.set_range(low_bit, size); 00120 return result; 00121 } 00122 00123 //////////////////////////////////////////////////////////////////// 00124 // Function: BitArray::Destructor 00125 // Access: Published 00126 // Description: 00127 //////////////////////////////////////////////////////////////////// 00128 INLINE BitArray:: 00129 ~BitArray() { 00130 } 00131 00132 //////////////////////////////////////////////////////////////////// 00133 // Function: BitArray::has_max_num_bits 00134 // Access: Published, Static 00135 // Description: Returns true if there is a maximum number of bits 00136 // that may be stored in this structure, false 00137 // otherwise. If this returns true, the number may be 00138 // queried in get_max_num_bits(). 00139 // 00140 // This method always returns false. The BitArray has 00141 // no maximum number of bits. This method is defined so 00142 // generic programming algorithms can use BitMask or 00143 // BitArray interchangeably. 00144 //////////////////////////////////////////////////////////////////// 00145 INLINE bool BitArray:: 00146 has_max_num_bits() { 00147 return false; 00148 } 00149 00150 //////////////////////////////////////////////////////////////////// 00151 // Function: BitArray::get_max_num_bits 00152 // Access: Published, Static 00153 // Description: If get_max_num_bits() returned true, this method may 00154 // be called to return the maximum number of bits that 00155 // may be stored in this structure. It is an error to 00156 // call this if get_max_num_bits() return false. 00157 // 00158 // It is always an error to call this method. The 00159 // BitArray has no maximum number of bits. This method 00160 // is defined so generic programming algorithms can use 00161 // BitMask or BitArray interchangeably. 00162 //////////////////////////////////////////////////////////////////// 00163 INLINE int BitArray:: 00164 get_max_num_bits() { 00165 nassertr(false, 0); 00166 return 0; 00167 } 00168 00169 //////////////////////////////////////////////////////////////////// 00170 // Function: BitArray::get_num_bits_per_word 00171 // Access: Published, Static 00172 // Description: Returns the number of bits stored per word 00173 // internally. This is of interest only in that it 00174 // limits the maximum number of bits that may be queried 00175 // or set at once by extract() and store(). 00176 //////////////////////////////////////////////////////////////////// 00177 INLINE int BitArray:: 00178 get_num_bits_per_word() { 00179 return num_bits_per_word; 00180 } 00181 00182 //////////////////////////////////////////////////////////////////// 00183 // Function: BitArray::get_num_bits 00184 // Access: Published 00185 // Description: Returns the current number of possibly different bits 00186 // in this array. There are actually an infinite number 00187 // of bits, but every bit higher than this bit will have 00188 // the same value, either 0 or 1 (see 00189 // get_highest_bits()). 00190 // 00191 // This number may grow and/or shrink automatically as 00192 // needed. 00193 //////////////////////////////////////////////////////////////////// 00194 INLINE int BitArray:: 00195 get_num_bits() const { 00196 return get_num_words() * num_bits_per_word; 00197 } 00198 00199 //////////////////////////////////////////////////////////////////// 00200 // Function: BitArray::get_bit 00201 // Access: Published 00202 // Description: Returns true if the nth bit is set, false if it is 00203 // cleared. It is valid for n to increase beyond 00204 // get_num_bits(), but the return value get_num_bits() 00205 // will always be the same. 00206 //////////////////////////////////////////////////////////////////// 00207 INLINE bool BitArray:: 00208 get_bit(int index) const { 00209 nassertr(index >= 0, false); 00210 int w = index / num_bits_per_word; 00211 int b = index % num_bits_per_word; 00212 if (w >= get_num_words()) { 00213 return get_highest_bits(); 00214 } else { 00215 return (_array[w].get_bit(b)); 00216 } 00217 } 00218 00219 //////////////////////////////////////////////////////////////////// 00220 // Function: BitArray::set_bit 00221 // Access: Published 00222 // Description: Sets the nth bit on. If n >= get_num_bits(), this 00223 // automatically extends the array. 00224 //////////////////////////////////////////////////////////////////// 00225 INLINE void BitArray:: 00226 set_bit(int index) { 00227 nassertv(index >= 0); 00228 int w = index / num_bits_per_word; 00229 int b = index % num_bits_per_word; 00230 if (w >= get_num_words() && _highest_bits) { 00231 // All the highest bits are already on. 00232 return; 00233 } 00234 ensure_has_word(w); 00235 _array[w].set_bit(b); 00236 normalize(); 00237 } 00238 00239 //////////////////////////////////////////////////////////////////// 00240 // Function: BitArray::clear_bit 00241 // Access: Published 00242 // Description: Sets the nth bit off. If n >= get_num_bits(), this 00243 // automatically extends the array. 00244 //////////////////////////////////////////////////////////////////// 00245 INLINE void BitArray:: 00246 clear_bit(int index) { 00247 nassertv(index >= 0); 00248 int w = index / num_bits_per_word; 00249 int b = index % num_bits_per_word; 00250 if (w >= get_num_words() && !_highest_bits) { 00251 // All the highest bits are already off. 00252 return; 00253 } 00254 ensure_has_word(w); 00255 _array[w].clear_bit(b); 00256 normalize(); 00257 } 00258 00259 //////////////////////////////////////////////////////////////////// 00260 // Function: BitArray::set_bit_to 00261 // Access: Published 00262 // Description: Sets the nth bit either on or off, according to the 00263 // indicated bool value. 00264 //////////////////////////////////////////////////////////////////// 00265 INLINE void BitArray:: 00266 set_bit_to(int index, bool value) { 00267 if (value) { 00268 set_bit(index); 00269 } else { 00270 clear_bit(index); 00271 } 00272 } 00273 00274 //////////////////////////////////////////////////////////////////// 00275 // Function: BitArray::get_highest_bits 00276 // Access: Published 00277 // Description: Returns true if the infinite set of bits beyond 00278 // get_num_bits() are all on, or false of they are all 00279 // off. 00280 //////////////////////////////////////////////////////////////////// 00281 INLINE bool BitArray:: 00282 get_highest_bits() const { 00283 return (_highest_bits != 0); 00284 } 00285 00286 //////////////////////////////////////////////////////////////////// 00287 // Function: BitArray::extract 00288 // Access: Published 00289 // Description: Returns a word that represents only the indicated 00290 // range of bits within this BitArray, shifted to the 00291 // least-significant position. size must be <= 00292 // get_num_bits_per_word(). 00293 //////////////////////////////////////////////////////////////////// 00294 INLINE BitArray::WordType BitArray:: 00295 extract(int low_bit, int size) const { 00296 nassertr(size >= 0 && size <= num_bits_per_word, 0); 00297 int w = low_bit / num_bits_per_word; 00298 int b = low_bit % num_bits_per_word; 00299 00300 if (b + size < num_bits_per_word) { 00301 // The whole thing fits within one word of the array. 00302 return get_word(w).extract(b, size); 00303 00304 } else { 00305 // We have to split it across two words. 00306 int num_lower_bits = num_bits_per_word - b; 00307 int num_higher_bits = size - num_lower_bits; 00308 00309 return get_word(w).extract(b, num_lower_bits) | 00310 (get_word(w + 1).extract(0, num_higher_bits) << num_lower_bits); 00311 } 00312 } 00313 00314 //////////////////////////////////////////////////////////////////// 00315 // Function: BitArray::store 00316 // Access: Published 00317 // Description: Stores the indicated word into the indicated range of 00318 // bits with this BitArray. 00319 //////////////////////////////////////////////////////////////////// 00320 INLINE void BitArray:: 00321 store(WordType value, int low_bit, int size) { 00322 nassertv(size >= 0); 00323 int w = low_bit / num_bits_per_word; 00324 int b = low_bit % num_bits_per_word; 00325 00326 if (b + size < num_bits_per_word) { 00327 // The whole thing fits within one word of the array. 00328 ensure_has_word(w); 00329 _array[w].store(value, b, size); 00330 00331 } else { 00332 // We have to split it across two words. 00333 int num_lower_bits = num_bits_per_word - b; 00334 int num_higher_bits = size - num_lower_bits; 00335 00336 ensure_has_word(w + 1); 00337 _array[w].store(value, b, num_lower_bits); 00338 _array[w + 1].store(value >> num_lower_bits, 0, num_higher_bits); 00339 } 00340 normalize(); 00341 } 00342 00343 //////////////////////////////////////////////////////////////////// 00344 // Function: BitArray::set_range_to 00345 // Access: Published 00346 // Description: Sets the indicated range of bits to either on or off. 00347 //////////////////////////////////////////////////////////////////// 00348 INLINE void BitArray:: 00349 set_range_to(bool value, int low_bit, int size) { 00350 if (value) { 00351 set_range(low_bit, size); 00352 } else { 00353 clear_range(low_bit, size); 00354 } 00355 } 00356 00357 //////////////////////////////////////////////////////////////////// 00358 // Function: BitArray::get_num_words 00359 // Access: Published 00360 // Description: Returns the number of possibly-unique words stored in 00361 // the array. 00362 //////////////////////////////////////////////////////////////////// 00363 INLINE int BitArray:: 00364 get_num_words() const { 00365 return _array.size(); 00366 } 00367 00368 //////////////////////////////////////////////////////////////////// 00369 // Function: BitArray::get_word 00370 // Access: Published 00371 // Description: Returns the nth word in the array. It is valid for n 00372 // to be greater than get_num_words(), but the return 00373 // value beyond get_num_words() will always be the same. 00374 //////////////////////////////////////////////////////////////////// 00375 INLINE BitArray::MaskType BitArray:: 00376 get_word(int n) const { 00377 nassertr(n >= 0, MaskType::all_off()); 00378 if (n < get_num_words()) { 00379 return _array[n]; 00380 } 00381 if (_highest_bits) { 00382 return MaskType::all_on(); 00383 } else { 00384 return MaskType::all_off(); 00385 } 00386 } 00387 00388 //////////////////////////////////////////////////////////////////// 00389 // Function: BitArray::set_word 00390 // Access: Published 00391 // Description: Replaces the nth word in the array. If n >= 00392 // get_num_words(), this automatically extends the 00393 // array. 00394 //////////////////////////////////////////////////////////////////// 00395 INLINE void BitArray:: 00396 set_word(int n, MaskType value) { 00397 nassertv(n >= 0); 00398 ensure_has_word(n); 00399 _array[n] = value; 00400 normalize(); 00401 } 00402 00403 //////////////////////////////////////////////////////////////////// 00404 // Function: BitArray::clear 00405 // Access: Published 00406 // Description: Sets all the bits in the BitArray off. 00407 //////////////////////////////////////////////////////////////////// 00408 void BitArray:: 00409 clear() { 00410 _array.clear(); 00411 _highest_bits = 0; 00412 } 00413 00414 //////////////////////////////////////////////////////////////////// 00415 // Function: BitArray::operator == 00416 // Access: Published 00417 // Description: 00418 //////////////////////////////////////////////////////////////////// 00419 INLINE bool BitArray:: 00420 operator == (const BitArray &other) const { 00421 return compare_to(other) == 0; 00422 } 00423 00424 //////////////////////////////////////////////////////////////////// 00425 // Function: BitArray::operator != 00426 // Access: Published 00427 // Description: 00428 //////////////////////////////////////////////////////////////////// 00429 INLINE bool BitArray:: 00430 operator != (const BitArray &other) const { 00431 return compare_to(other) != 0; 00432 } 00433 00434 //////////////////////////////////////////////////////////////////// 00435 // Function: BitArray::operator < 00436 // Access: Published 00437 // Description: Returns true if the unsigned integer which is 00438 // represented by this BitArray is less than that of the 00439 // other one, false otherwise. 00440 //////////////////////////////////////////////////////////////////// 00441 INLINE bool BitArray:: 00442 operator < (const BitArray &other) const { 00443 return compare_to(other) < 0; 00444 } 00445 00446 //////////////////////////////////////////////////////////////////// 00447 // Function: BitArray::operator & 00448 // Access: Published 00449 // Description: 00450 //////////////////////////////////////////////////////////////////// 00451 INLINE BitArray BitArray:: 00452 operator & (const BitArray &other) const { 00453 BitArray result(*this); 00454 result &= other; 00455 return result; 00456 } 00457 00458 //////////////////////////////////////////////////////////////////// 00459 // Function: BitArray::operator | 00460 // Access: Published 00461 // Description: 00462 //////////////////////////////////////////////////////////////////// 00463 INLINE BitArray BitArray:: 00464 operator | (const BitArray &other) const { 00465 BitArray result(*this); 00466 result |= other; 00467 return result; 00468 } 00469 00470 //////////////////////////////////////////////////////////////////// 00471 // Function: BitArray::operator ^ 00472 // Access: Published 00473 // Description: 00474 //////////////////////////////////////////////////////////////////// 00475 INLINE BitArray BitArray:: 00476 operator ^ (const BitArray &other) const { 00477 BitArray result(*this); 00478 result ^= other; 00479 return result; 00480 } 00481 00482 //////////////////////////////////////////////////////////////////// 00483 // Function: BitArray::operator ~ 00484 // Access: Published 00485 // Description: 00486 //////////////////////////////////////////////////////////////////// 00487 INLINE BitArray BitArray:: 00488 operator ~ () const { 00489 BitArray result(*this); 00490 result.invert_in_place(); 00491 return result; 00492 } 00493 00494 //////////////////////////////////////////////////////////////////// 00495 // Function: BitArray::operator << 00496 // Access: Published 00497 // Description: 00498 //////////////////////////////////////////////////////////////////// 00499 INLINE BitArray BitArray:: 00500 operator << (int shift) const { 00501 BitArray result(*this); 00502 result <<= shift; 00503 return result; 00504 } 00505 00506 //////////////////////////////////////////////////////////////////// 00507 // Function: BitArray::operator >> 00508 // Access: Published 00509 // Description: 00510 //////////////////////////////////////////////////////////////////// 00511 INLINE BitArray BitArray:: 00512 operator >> (int shift) const { 00513 BitArray result(*this); 00514 result >>= shift; 00515 return result; 00516 } 00517 00518 //////////////////////////////////////////////////////////////////// 00519 // Function: BitArray::copy_on_write 00520 // Access: Private 00521 // Description: Called internally just before writing to the _array 00522 // member, this makes a new copy of _array if it appears 00523 // to be shared with any other objects--thus achieving 00524 // copy-on-write. 00525 //////////////////////////////////////////////////////////////////// 00526 INLINE void BitArray:: 00527 copy_on_write() { 00528 if (_array.get_ref_count() > 1) { 00529 PTA(MaskType) new_array; 00530 new_array.v() = _array.v(); 00531 _array = new_array; 00532 } 00533 }