Panda3D
|
00001 // Filename: bitArray.cxx 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 #include "bitArray.h" 00016 #include "sparseArray.h" 00017 00018 TypeHandle BitArray::_type_handle; 00019 00020 //////////////////////////////////////////////////////////////////// 00021 // Function: BitArray::Constructor (from SparseArray) 00022 // Access: Published 00023 // Description: 00024 //////////////////////////////////////////////////////////////////// 00025 BitArray:: 00026 BitArray(const SparseArray &from) { 00027 _highest_bits = 0; 00028 00029 int num_subranges = from.get_num_subranges(); 00030 for (int i = 0; i < num_subranges; ++i) { 00031 int begin = from.get_subrange_begin(i); 00032 int end = from.get_subrange_end(i); 00033 set_range(begin, end - begin); 00034 } 00035 00036 if (from.is_inverse()) { 00037 invert_in_place(); 00038 } 00039 } 00040 00041 //////////////////////////////////////////////////////////////////// 00042 // Function: BitArray::is_zero 00043 // Access: Published 00044 // Description: Returns true if the entire bitmask is zero, false 00045 // otherwise. 00046 //////////////////////////////////////////////////////////////////// 00047 bool BitArray:: 00048 is_zero() const { 00049 if (_highest_bits) { 00050 // If all the infinite highest bits are set, certainly the bitmask 00051 // is nonzero. 00052 return false; 00053 } 00054 00055 // Start from the high end, since that's more likely to be nonzero. 00056 Array::reverse_iterator ai; 00057 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) { 00058 if (!(*ai).is_zero()) { 00059 return false; 00060 } 00061 } 00062 return true; 00063 } 00064 00065 //////////////////////////////////////////////////////////////////// 00066 // Function: BitArray::is_all_on 00067 // Access: Published 00068 // Description: Returns true if the entire bitmask is one, false 00069 // otherwise. 00070 //////////////////////////////////////////////////////////////////// 00071 bool BitArray:: 00072 is_all_on() const { 00073 if (!_highest_bits) { 00074 // If all the infinite highest bits are not set, certainly the 00075 // bitmask is not all on. 00076 return false; 00077 } 00078 00079 Array::reverse_iterator ai; 00080 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) { 00081 if (!(*ai).is_all_on()) { 00082 return false; 00083 } 00084 } 00085 return true; 00086 } 00087 00088 //////////////////////////////////////////////////////////////////// 00089 // Function: BitArray::has_any_of 00090 // Access: Published 00091 // Description: Returns true if any bit in the indicated range is 00092 // set, false otherwise. 00093 //////////////////////////////////////////////////////////////////// 00094 bool BitArray:: 00095 has_any_of(int low_bit, int size) const { 00096 if ((low_bit + size - 1) / num_bits_per_word >= get_num_words()) { 00097 // This range touches the highest bits. 00098 if (_highest_bits) { 00099 return true; 00100 } 00101 } 00102 00103 int w = low_bit / num_bits_per_word; 00104 int b = low_bit % num_bits_per_word; 00105 00106 if (w >= get_num_words()) { 00107 // This range is entirely among the highest bits. 00108 return (_highest_bits != 0); 00109 } 00110 if (b + size <= num_bits_per_word) { 00111 // The whole thing fits within one word of the array. 00112 return get_word(w).has_any_of(b, size); 00113 } 00114 00115 int num_high_bits = num_bits_per_word - b; 00116 if (_array[w].has_any_of(b, num_high_bits)) { 00117 return true; 00118 } 00119 size -= num_high_bits; 00120 ++w; 00121 00122 while (size > 0) { 00123 if (size <= num_bits_per_word) { 00124 // The remainder fits within one word of the array. 00125 return _array[w].has_any_of(0, size); 00126 } 00127 00128 // Keep going. 00129 if (!_array[w].is_zero()) { 00130 return true; 00131 } 00132 size -= num_bits_per_word; 00133 ++w; 00134 00135 if (w >= get_num_words()) { 00136 // Now we're up to the highest bits. 00137 return (_highest_bits != 0); 00138 } 00139 } 00140 00141 return false; 00142 } 00143 00144 //////////////////////////////////////////////////////////////////// 00145 // Function: BitArray::has_all_of 00146 // Access: Published 00147 // Description: Returns true if all bits in the indicated range are 00148 // set, false otherwise. 00149 //////////////////////////////////////////////////////////////////// 00150 bool BitArray:: 00151 has_all_of(int low_bit, int size) const { 00152 if ((low_bit + size - 1) / num_bits_per_word >= get_num_words()) { 00153 // This range touches the highest bits. 00154 if (!_highest_bits) { 00155 return false; 00156 } 00157 } 00158 00159 int w = low_bit / num_bits_per_word; 00160 int b = low_bit % num_bits_per_word; 00161 00162 if (w >= get_num_words()) { 00163 // This range is entirely among the highest bits. 00164 return (_highest_bits != 0); 00165 } 00166 if (b + size <= num_bits_per_word) { 00167 // The whole thing fits within one word of the array. 00168 return get_word(w).has_all_of(b, size); 00169 } 00170 00171 int num_high_bits = num_bits_per_word - b; 00172 if (!_array[w].has_all_of(b, num_high_bits)) { 00173 return false; 00174 } 00175 size -= num_high_bits; 00176 ++w; 00177 00178 while (size > 0) { 00179 if (size <= num_bits_per_word) { 00180 // The remainder fits within one word of the array. 00181 return _array[w].has_all_of(0, size); 00182 } 00183 00184 // Keep going. 00185 if (!_array[w].is_all_on()) { 00186 return false; 00187 } 00188 size -= num_bits_per_word; 00189 ++w; 00190 00191 if (w >= get_num_words()) { 00192 // Now we're up to the highest bits. 00193 return (_highest_bits != 0); 00194 } 00195 } 00196 00197 return true; 00198 } 00199 00200 //////////////////////////////////////////////////////////////////// 00201 // Function: BitArray::set_range 00202 // Access: Published 00203 // Description: Sets the indicated range of bits on. 00204 //////////////////////////////////////////////////////////////////// 00205 void BitArray:: 00206 set_range(int low_bit, int size) { 00207 int w = low_bit / num_bits_per_word; 00208 int b = low_bit % num_bits_per_word; 00209 00210 if (w >= get_num_words() && _highest_bits) { 00211 // All the highest bits are already on. 00212 return; 00213 } 00214 if (b + size <= num_bits_per_word) { 00215 // The whole thing fits within one word of the array. 00216 ensure_has_word(w); 00217 _array[w].set_range(b, size); 00218 normalize(); 00219 return; 00220 } 00221 00222 ensure_has_word(w); 00223 int num_high_bits = num_bits_per_word - b; 00224 _array[w].set_range(b, num_high_bits); 00225 size -= num_high_bits; 00226 ++w; 00227 00228 while (size > 0) { 00229 if (size <= num_bits_per_word) { 00230 // The remainder fits within one word of the array. 00231 ensure_has_word(w); 00232 _array[w].set_range(0, size); 00233 normalize(); 00234 return; 00235 } 00236 00237 // Keep going. 00238 ensure_has_word(w); 00239 _array[w] = MaskType::all_on(); 00240 size -= num_bits_per_word; 00241 ++w; 00242 00243 if (w >= get_num_words() && _highest_bits) { 00244 // All the highest bits are already on. 00245 normalize(); 00246 return; 00247 } 00248 } 00249 normalize(); 00250 } 00251 00252 //////////////////////////////////////////////////////////////////// 00253 // Function: BitArray::clear_range 00254 // Access: Published 00255 // Description: Sets the indicated range of bits off. 00256 //////////////////////////////////////////////////////////////////// 00257 void BitArray:: 00258 clear_range(int low_bit, int size) { 00259 int w = low_bit / num_bits_per_word; 00260 int b = low_bit % num_bits_per_word; 00261 00262 if (w >= get_num_words() && !_highest_bits) { 00263 // All the highest bits are already off. 00264 return; 00265 } 00266 if (b + size <= num_bits_per_word) { 00267 // The whole thing fits within one word of the array. 00268 ensure_has_word(w); 00269 _array[w].clear_range(b, size); 00270 normalize(); 00271 return; 00272 } 00273 00274 ensure_has_word(w); 00275 int num_high_bits = num_bits_per_word - b; 00276 _array[w].clear_range(b, num_high_bits); 00277 size -= num_high_bits; 00278 ++w; 00279 00280 while (size > 0) { 00281 if (size <= num_bits_per_word) { 00282 // The remainder fits within one word of the array. 00283 ensure_has_word(w); 00284 _array[w].clear_range(0, size); 00285 normalize(); 00286 return; 00287 } 00288 00289 // Keep going. 00290 ensure_has_word(w); 00291 _array[w] = MaskType::all_off(); 00292 size -= num_bits_per_word; 00293 ++w; 00294 00295 if (w >= get_num_words() && !_highest_bits) { 00296 // All the highest bits are already off. 00297 normalize(); 00298 return; 00299 } 00300 } 00301 normalize(); 00302 } 00303 00304 //////////////////////////////////////////////////////////////////// 00305 // Function: BitArray::get_num_on_bits 00306 // Access: Published 00307 // Description: Returns the number of bits that are set to 1 in the 00308 // array. Returns -1 if there are an infinite number of 00309 // 1 bits. 00310 //////////////////////////////////////////////////////////////////// 00311 int BitArray:: 00312 get_num_on_bits() const { 00313 if (_highest_bits) { 00314 return -1; 00315 } 00316 00317 int result = 0; 00318 Array::const_iterator ai; 00319 for (ai = _array.begin(); ai != _array.end(); ++ai) { 00320 result += (*ai).get_num_on_bits(); 00321 } 00322 return result; 00323 } 00324 00325 //////////////////////////////////////////////////////////////////// 00326 // Function: BitArray::get_num_off_bits 00327 // Access: Published 00328 // Description: Returns the number of bits that are set to 0 in the 00329 // array. Returns -1 if there are an infinite number of 00330 // 0 bits. 00331 //////////////////////////////////////////////////////////////////// 00332 int BitArray:: 00333 get_num_off_bits() const { 00334 if (!_highest_bits) { 00335 return -1; 00336 } 00337 00338 int result = 0; 00339 Array::const_iterator ai; 00340 for (ai = _array.begin(); ai != _array.end(); ++ai) { 00341 result += (*ai).get_num_off_bits(); 00342 } 00343 return result; 00344 } 00345 00346 //////////////////////////////////////////////////////////////////// 00347 // Function: BitArray::get_lowest_on_bit 00348 // Access: Published 00349 // Description: Returns the index of the lowest 1 bit in the array. 00350 // Returns -1 if there are no 1 bits. 00351 //////////////////////////////////////////////////////////////////// 00352 int BitArray:: 00353 get_lowest_on_bit() const { 00354 int num_words = get_num_words(); 00355 for (int w = 0; w < num_words; ++w) { 00356 int b = _array[w].get_lowest_on_bit(); 00357 if (b != -1) { 00358 return w * num_bits_per_word + b; 00359 } 00360 } 00361 if (_highest_bits) { 00362 return num_words * num_bits_per_word; 00363 } else { 00364 return -1; 00365 } 00366 } 00367 00368 //////////////////////////////////////////////////////////////////// 00369 // Function: BitArray::get_lowest_off_bit 00370 // Access: Published 00371 // Description: Returns the index of the lowest 0 bit in the array. 00372 // Returns -1 if there are no 0 bits. 00373 //////////////////////////////////////////////////////////////////// 00374 int BitArray:: 00375 get_lowest_off_bit() const { 00376 int num_words = get_num_words(); 00377 for (int w = 0; w < num_words; ++w) { 00378 int b = _array[w].get_lowest_off_bit(); 00379 if (b != -1) { 00380 return w * num_bits_per_word + b; 00381 } 00382 } 00383 if (!_highest_bits) { 00384 return num_words * num_bits_per_word; 00385 } else { 00386 return -1; 00387 } 00388 } 00389 00390 //////////////////////////////////////////////////////////////////// 00391 // Function: BitArray::get_highest_on_bit 00392 // Access: Published 00393 // Description: Returns the index of the highest 1 bit in the array. 00394 // Returns -1 if there are no 1 bits or if there an 00395 // infinite number of 1 bits. 00396 //////////////////////////////////////////////////////////////////// 00397 int BitArray:: 00398 get_highest_on_bit() const { 00399 if (_highest_bits) { 00400 return -1; 00401 } 00402 int num_words = get_num_words(); 00403 for (int w = num_words - 1; w >= 0; --w) { 00404 int b = _array[w].get_highest_on_bit(); 00405 if (b != -1) { 00406 return w * num_bits_per_word + b; 00407 } 00408 } 00409 return -1; 00410 } 00411 00412 //////////////////////////////////////////////////////////////////// 00413 // Function: BitArray::get_highest_off_bit 00414 // Access: Published 00415 // Description: Returns the index of the highest 0 bit in the array. 00416 // Returns -1 if there are no 0 bits or if there an 00417 // infinite number of 1 bits. 00418 //////////////////////////////////////////////////////////////////// 00419 int BitArray:: 00420 get_highest_off_bit() const { 00421 if (!_highest_bits) { 00422 return -1; 00423 } 00424 int num_words = get_num_words(); 00425 for (int w = num_words - 1; w >= 0; --w) { 00426 int b = _array[w].get_highest_off_bit(); 00427 if (b != -1) { 00428 return w * num_bits_per_word + b; 00429 } 00430 } 00431 return -1; 00432 } 00433 00434 //////////////////////////////////////////////////////////////////// 00435 // Function: BitArray::get_next_higher_different_bit 00436 // Access: Published 00437 // Description: Returns the index of the next bit in the array, above 00438 // low_bit, whose value is different that the value of 00439 // low_bit. Returns low_bit again if all bits higher 00440 // than low_bit have the same value. 00441 // 00442 // This can be used to quickly iterate through all of 00443 // the bits in the array. 00444 //////////////////////////////////////////////////////////////////// 00445 int BitArray:: 00446 get_next_higher_different_bit(int low_bit) const { 00447 int w = low_bit / num_bits_per_word; 00448 int b = low_bit % num_bits_per_word; 00449 int num_words = get_num_words(); 00450 if (w >= num_words) { 00451 return low_bit; 00452 } 00453 int b2 = _array[w].get_next_higher_different_bit(b); 00454 if (b2 != b && b2 < num_bits_per_word) { 00455 // The next higher bit is within the same word. 00456 return w * num_bits_per_word + b2; 00457 } 00458 // Look for the next word with anything interesting. 00459 MaskType skip_next = (_array[w].get_bit(b)) ? MaskType::all_on() : MaskType::all_off(); 00460 int w2 = w; 00461 ++w2; 00462 while (w2 < num_words && _array[w2] == skip_next) { 00463 ++w2; 00464 } 00465 if (w2 >= num_words) { 00466 // All bits higher are the same value. 00467 int is_on = _array[w].get_bit(b); 00468 return is_on ? (num_words * num_bits_per_word) : low_bit; 00469 } 00470 if (_array[w2].get_bit(0) != _array[w].get_bit(b)) { 00471 // The first bit of word w2 is different. 00472 return w2 * num_bits_per_word; 00473 } 00474 00475 b2 = _array[w2].get_next_higher_different_bit(0); 00476 return w2 * num_bits_per_word + b2; 00477 } 00478 00479 //////////////////////////////////////////////////////////////////// 00480 // Function: BitArray::invert_in_place 00481 // Access: Published 00482 // Description: Inverts all the bits in the BitArray. This is 00483 // equivalent to array = ~array. 00484 //////////////////////////////////////////////////////////////////// 00485 void BitArray:: 00486 invert_in_place() { 00487 _highest_bits = !_highest_bits; 00488 copy_on_write(); 00489 Array::iterator ai; 00490 for (ai = _array.begin(); ai != _array.end(); ++ai) { 00491 (*ai) = ~(*ai); 00492 } 00493 } 00494 00495 //////////////////////////////////////////////////////////////////// 00496 // Function: BitArray::has_bits_in_common 00497 // Access: Published 00498 // Description: Returns true if this BitArray has any "one" bits in 00499 // common with the other one, false otherwise. 00500 // 00501 // This is equivalent to (array & other) != 0, but may 00502 // be faster. 00503 //////////////////////////////////////////////////////////////////// 00504 bool BitArray:: 00505 has_bits_in_common(const BitArray &other) const { 00506 if (_highest_bits && other._highest_bits) { 00507 // Yup, in fact we have an infinite number of bits in common. 00508 return true; 00509 } 00510 00511 size_t num_common_words = min(_array.size(), other._array.size()); 00512 00513 // Consider the words that are on top of either array. 00514 if (other._array.size() < _array.size() && other._highest_bits) { 00515 // The other array has fewer actual words, and the top n words of 00516 // the other array are all ones. We have bits in common if any of 00517 // our top n words are nonzero. 00518 Array::const_iterator ai; 00519 for (ai = _array.begin() + other._array.size(); 00520 ai != _array.end(); 00521 ++ai) { 00522 if (!(*ai).is_zero()) { 00523 return true; 00524 } 00525 } 00526 00527 } else if (_array.size() < other._array.size() && _highest_bits) { 00528 // This array has fewer actual words, and the top n words of this 00529 // array are all ones. We have bits in common if any of the the 00530 // other's top n words are nonzero. 00531 Array::const_iterator ai; 00532 for (ai = other._array.begin() + _array.size(); 00533 ai != other._array.end(); 00534 ++ai) { 00535 if (!(*ai).is_zero()) { 00536 return true; 00537 } 00538 } 00539 } 00540 00541 // Consider the words that both arrays have in common. 00542 for (size_t i = 0; i < num_common_words; ++i) { 00543 if (!(_array[i] & other._array[i]).is_zero()) { 00544 return true; 00545 } 00546 } 00547 00548 // Nope, nothing. 00549 return false; 00550 } 00551 00552 //////////////////////////////////////////////////////////////////// 00553 // Function: BitArray::output 00554 // Access: Published 00555 // Description: Writes the BitArray out as a hex number. For a 00556 // BitArray, this is always the same as output_hex(); 00557 // it's too confusing for the output format to change 00558 // back and forth at runtime. 00559 //////////////////////////////////////////////////////////////////// 00560 void BitArray:: 00561 output(ostream &out) const { 00562 output_hex(out); 00563 } 00564 00565 //////////////////////////////////////////////////////////////////// 00566 // Function: BitArray::output_binary 00567 // Access: Published 00568 // Description: Writes the BitArray out as a binary number, with 00569 // spaces every four bits. 00570 //////////////////////////////////////////////////////////////////// 00571 void BitArray:: 00572 output_binary(ostream &out, int spaces_every) const { 00573 if (_highest_bits) { 00574 out << "...1 "; 00575 } 00576 int num_bits = max(get_num_bits(), spaces_every); 00577 for (int i = num_bits - 1; i >= 0; i--) { 00578 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) { 00579 out << ' '; 00580 } 00581 out << (get_bit(i) ? '1' : '0'); 00582 } 00583 } 00584 00585 //////////////////////////////////////////////////////////////////// 00586 // Function: BitArray::output_hex 00587 // Access: Published 00588 // Description: Writes the BitArray out as a hexadecimal number, with 00589 // spaces every four digits. 00590 //////////////////////////////////////////////////////////////////// 00591 void BitArray:: 00592 output_hex(ostream &out, int spaces_every) const { 00593 int num_bits = get_num_bits(); 00594 int num_digits = max((num_bits + 3) / 4, spaces_every); 00595 00596 if (_highest_bits) { 00597 out << "...f "; 00598 } 00599 00600 for (int i = num_digits - 1; i >= 0; i--) { 00601 WordType digit = extract(i * 4, 4); 00602 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) { 00603 out << ' '; 00604 } 00605 if (digit > 9) { 00606 out << (char)(digit - 10 + 'a'); 00607 } else { 00608 out << (char)(digit + '0'); 00609 } 00610 } 00611 } 00612 00613 //////////////////////////////////////////////////////////////////// 00614 // Function: BitArray::write 00615 // Access: Published 00616 // Description: Writes the BitArray out as a binary or a hex number, 00617 // according to the number of bits. 00618 //////////////////////////////////////////////////////////////////// 00619 void BitArray:: 00620 write(ostream &out, int indent_level) const { 00621 indent(out, indent_level) << *this << "\n"; 00622 } 00623 00624 //////////////////////////////////////////////////////////////////// 00625 // Function: BitArray::compare_to 00626 // Access: Published 00627 // Description: Returns a number less than zero if this BitArray sorts 00628 // before the indicated other BitArray, greater than zero 00629 // if it sorts after, or 0 if they are equivalent. This 00630 // is based on the same ordering defined by operator <. 00631 //////////////////////////////////////////////////////////////////// 00632 int BitArray:: 00633 compare_to(const BitArray &other) const { 00634 if (_highest_bits != other._highest_bits) { 00635 return _highest_bits ? 1 : -1; 00636 } 00637 00638 int num_words = max(get_num_words(), other.get_num_words()); 00639 00640 // Compare from highest-order to lowest-order word. 00641 for (int i = num_words - 1; i >= 0; --i) { 00642 int compare = get_word(i).compare_to(other.get_word(i)); 00643 if (compare != 0) { 00644 return compare; 00645 } 00646 } 00647 00648 return 0; 00649 } 00650 00651 //////////////////////////////////////////////////////////////////// 00652 // Function: BitArray::operator &= 00653 // Access: Published 00654 // Description: 00655 //////////////////////////////////////////////////////////////////// 00656 void BitArray:: 00657 operator &= (const BitArray &other) { 00658 size_t num_common_words = min(_array.size(), other._array.size()); 00659 00660 copy_on_write(); 00661 00662 // Consider the words that are on top of either array. 00663 if (other._array.size() < _array.size() && !other._highest_bits) { 00664 // The other array has fewer actual words, and the top n words of 00665 // the other array are all zeroes. "mask off" the top n words of 00666 // this array. 00667 _array.erase(_array.begin() + other._array.size(), _array.end()); 00668 00669 } else if (_array.size() < other._array.size() && _highest_bits) { 00670 // This array has fewer actual words, and the top n words of this 00671 // array are all ones. "mask on" the top n words of the other 00672 // array. 00673 Array::const_iterator ai; 00674 for (ai = other._array.begin() + _array.size(); 00675 ai != other._array.end(); 00676 ++ai) { 00677 _array.push_back(*ai); 00678 } 00679 } 00680 00681 // Consider the words that both arrays have in common. 00682 for (size_t i = 0; i < num_common_words; ++i) { 00683 _array[i] &= other._array[i]; 00684 } 00685 00686 _highest_bits &= other._highest_bits; 00687 normalize(); 00688 } 00689 00690 //////////////////////////////////////////////////////////////////// 00691 // Function: BitArray::operator |= 00692 // Access: Published 00693 // Description: 00694 //////////////////////////////////////////////////////////////////// 00695 void BitArray:: 00696 operator |= (const BitArray &other) { 00697 size_t num_common_words = min(_array.size(), other._array.size()); 00698 00699 copy_on_write(); 00700 00701 // Consider the words that are on top of either array. 00702 if (other._array.size() < _array.size() && other._highest_bits) { 00703 // The other array has fewer actual words, and the top n words of 00704 // the other array are all ones. The top n words of this array 00705 // become ones too (which means we can drop them out). 00706 _array.erase(_array.begin() + other._array.size(), _array.end()); 00707 00708 } else if (_array.size() < other._array.size() && !_highest_bits) { 00709 // This array has fewer actual words, and the top n words of this 00710 // array are all zeros. Copy in the top n words of the other 00711 // array. 00712 Array::const_iterator ai; 00713 for (ai = other._array.begin() + _array.size(); 00714 ai != other._array.end(); 00715 ++ai) { 00716 _array.push_back(*ai); 00717 } 00718 } 00719 00720 // Consider the words that both arrays have in common. 00721 for (size_t i = 0; i < num_common_words; ++i) { 00722 _array[i] |= other._array[i]; 00723 } 00724 00725 _highest_bits |= other._highest_bits; 00726 normalize(); 00727 } 00728 00729 //////////////////////////////////////////////////////////////////// 00730 // Function: BitArray::operator ^= 00731 // Access: Published 00732 // Description: 00733 //////////////////////////////////////////////////////////////////// 00734 void BitArray:: 00735 operator ^= (const BitArray &other) { 00736 size_t num_common_words = min(_array.size(), other._array.size()); 00737 00738 copy_on_write(); 00739 00740 // Consider the words that are on top of either array. 00741 if (other._array.size() < _array.size() && other._highest_bits) { 00742 // The other array has fewer actual words, and the top n words of 00743 // the other array are all ones. The top n words of this array 00744 // get inverted. 00745 Array::iterator ai; 00746 for (ai = _array.begin() + other._array.size(); 00747 ai != _array.end(); 00748 ++ai) { 00749 (*ai).invert_in_place(); 00750 } 00751 00752 } else if (_array.size() < other._array.size()) { 00753 if (!_highest_bits) { 00754 // This array has fewer actual words, and the top n words of this 00755 // array are all zeros. Copy in the top n words of the other 00756 // array. 00757 Array::const_iterator ai; 00758 for (ai = other._array.begin() + _array.size(); 00759 ai != other._array.end(); 00760 ++ai) { 00761 _array.push_back(*ai); 00762 } 00763 } else { 00764 // This array has fewer actual words, and the top n words of this 00765 // array are all ones. Copy in the top n words of the other 00766 // array, inverted. 00767 Array::const_iterator ai; 00768 for (ai = other._array.begin() + _array.size(); 00769 ai != other._array.end(); 00770 ++ai) { 00771 _array.push_back(~(*ai)); 00772 } 00773 } 00774 } 00775 00776 // Consider the words that both arrays have in common. 00777 for (size_t i = 0; i < num_common_words; ++i) { 00778 _array[i] ^= other._array[i]; 00779 } 00780 00781 _highest_bits ^= other._highest_bits; 00782 normalize(); 00783 } 00784 00785 //////////////////////////////////////////////////////////////////// 00786 // Function: BitArray::operator <<= 00787 // Access: Published 00788 // Description: Logical left shift. The rightmost bits are filled in 00789 // with zeroes. Since this is an infinite bit array, 00790 // none of the bits on the left are lost. 00791 //////////////////////////////////////////////////////////////////// 00792 void BitArray:: 00793 operator <<= (int shift) { 00794 if (shift == 0 || _array.empty()) { 00795 return; 00796 } 00797 if (shift < 0) { 00798 operator >>= (-shift); 00799 return; 00800 } 00801 00802 int w = shift / num_bits_per_word; 00803 int b = shift % num_bits_per_word; 00804 00805 if (b == 0) { 00806 // Easy case--word-at-a-time. 00807 Array new_array; 00808 new_array.reserve(_array.size() + w); 00809 for (int i = 0; i < w; ++i) { 00810 new_array.push_back(MaskType::all_off()); 00811 } 00812 Array::const_iterator ai; 00813 for (ai = _array.begin(); ai != _array.end(); ++ai) { 00814 new_array.push_back(*ai); 00815 } 00816 _array = new_array; 00817 00818 } else { 00819 // Harder case--we have to shuffle bits between words. 00820 Array new_array; 00821 new_array.reserve(_array.size() + w + 1); 00822 for (int i = 0; i < w; ++i) { 00823 new_array.push_back(MaskType::all_off()); 00824 } 00825 00826 int downshift_count = num_bits_per_word - b; 00827 MaskType lower_mask = MaskType::lower_on(downshift_count); 00828 MaskType upper_mask = ~lower_mask; 00829 00830 Array::const_iterator ai = _array.begin(); 00831 nassertv(ai != _array.end()); 00832 MaskType next_bits = ((*ai) & upper_mask) >> downshift_count; 00833 new_array.push_back(((*ai) & lower_mask) << b); 00834 ++ai; 00835 while (ai != _array.end()) { 00836 new_array.push_back((((*ai) & lower_mask) << b) | next_bits); 00837 next_bits = ((*ai) & upper_mask) >> downshift_count; 00838 ++ai; 00839 } 00840 00841 // Finally, the top n bits. 00842 if (_highest_bits) { 00843 next_bits |= ~MaskType::lower_on(b); 00844 } 00845 new_array.push_back(next_bits); 00846 _array = new_array; 00847 } 00848 00849 normalize(); 00850 } 00851 00852 //////////////////////////////////////////////////////////////////// 00853 // Function: BitArray::operator >>= 00854 // Access: Published 00855 // Description: Logical right shift. The rightmost bits are lost. 00856 // Since this is an infinite bit array, there is no 00857 // question of sign extension; there is no need to 00858 // synthesize bits on the left. 00859 //////////////////////////////////////////////////////////////////// 00860 void BitArray:: 00861 operator >>= (int shift) { 00862 if (shift == 0 || _array.empty()) { 00863 return; 00864 } 00865 if (shift < 0) { 00866 operator <<= (-shift); 00867 return; 00868 } 00869 00870 int w = shift / num_bits_per_word; 00871 int b = shift % num_bits_per_word; 00872 00873 if (w >= (int)_array.size()) { 00874 // Trivial case--shift to nothing. 00875 _array.clear(); 00876 return; 00877 } 00878 00879 if (b == 0) { 00880 // Easy case--word-at-a-time. 00881 Array new_array; 00882 new_array.reserve(_array.size() - w); 00883 Array::const_iterator ai; 00884 for (ai = _array.begin() + w; ai != _array.end(); ++ai) { 00885 new_array.push_back(*ai); 00886 } 00887 _array = new_array; 00888 00889 } else { 00890 // Harder case--we have to shuffle bits between words. 00891 Array new_array; 00892 new_array.reserve(_array.size() - w); 00893 00894 int upshift_count = num_bits_per_word - b; 00895 MaskType lower_mask = MaskType::lower_on(b); 00896 MaskType upper_mask = ~lower_mask; 00897 00898 Array::const_iterator ai = _array.begin() + w; 00899 nassertv(ai < _array.end()); 00900 MaskType next_bits = ((*ai) & upper_mask) >> b; 00901 00902 ++ai; 00903 while (ai != _array.end()) { 00904 new_array.push_back((((*ai) & lower_mask) << upshift_count) | next_bits); 00905 next_bits = ((*ai) & upper_mask) >> b; 00906 ++ai; 00907 } 00908 00909 // Finally, the top n bits. 00910 if (_highest_bits) { 00911 next_bits |= ~MaskType::lower_on(upshift_count); 00912 } 00913 new_array.push_back(next_bits); 00914 _array = new_array; 00915 } 00916 00917 normalize(); 00918 } 00919 00920 //////////////////////////////////////////////////////////////////// 00921 // Function: BitArray::generate_hash 00922 // Access: Public 00923 // Description: Adds the bitmask to the indicated hash generator. 00924 //////////////////////////////////////////////////////////////////// 00925 void BitArray:: 00926 generate_hash(ChecksumHashGenerator &hashgen) const { 00927 hashgen.add_int(_highest_bits); 00928 Array::const_iterator ai; 00929 for (ai = _array.begin(); ai != _array.end(); ++ai) { 00930 hashgen.add_int((*ai).get_word()); 00931 } 00932 } 00933 00934 //////////////////////////////////////////////////////////////////// 00935 // Function: BitArray::ensure_has_word 00936 // Access: Private 00937 // Description: Ensures that at least word n has been allocated into 00938 // the array. 00939 //////////////////////////////////////////////////////////////////// 00940 void BitArray:: 00941 ensure_has_word(int n) { 00942 copy_on_write(); 00943 00944 if (_highest_bits) { 00945 while (n >= (int)_array.size()) { 00946 _array.push_back(MaskType::all_on()); 00947 } 00948 } else { 00949 while (n >= (int)_array.size()) { 00950 _array.push_back(MaskType::all_off()); 00951 } 00952 } 00953 } 00954 00955 //////////////////////////////////////////////////////////////////// 00956 // Function: BitArray::normalize 00957 // Access: Private 00958 // Description: Ensures that the array is the smallest array that 00959 // represents this same value, by removing the topmost 00960 // words that are all bits off (or on). 00961 //////////////////////////////////////////////////////////////////// 00962 void BitArray:: 00963 normalize() { 00964 if (_highest_bits) { 00965 if (!_array.empty() && _array.back() == MaskType::all_on()) { 00966 copy_on_write(); 00967 _array.pop_back(); 00968 while (!_array.empty() && _array.back() == MaskType::all_on()) { 00969 _array.pop_back(); 00970 } 00971 } 00972 } else { 00973 if (!_array.empty() && _array.back().is_zero()) { 00974 copy_on_write(); 00975 _array.pop_back(); 00976 while (!_array.empty() && _array.back().is_zero()) { 00977 _array.pop_back(); 00978 } 00979 } 00980 } 00981 } 00982 00983 //////////////////////////////////////////////////////////////////// 00984 // Function: BitArray::write_datagram 00985 // Access: Public 00986 // Description: Writes the contents of this object to the datagram 00987 // for shipping out to a Bam file. 00988 //////////////////////////////////////////////////////////////////// 00989 void BitArray:: 00990 write_datagram(BamWriter *manager, Datagram &dg) const { 00991 dg.add_uint32(_array.size()); 00992 Array::const_iterator ai; 00993 for (ai = _array.begin(); ai != _array.end(); ++ai) { 00994 dg.add_uint32((*ai).get_word()); 00995 } 00996 dg.add_uint8(_highest_bits); 00997 } 00998 00999 //////////////////////////////////////////////////////////////////// 01000 // Function: BitArray::read_datagram 01001 // Access: Public 01002 // Description: Reads the object that was previously written to a Bam 01003 // file. 01004 //////////////////////////////////////////////////////////////////// 01005 void BitArray:: 01006 read_datagram(DatagramIterator &scan, BamReader *manager) { 01007 size_t num_words = scan.get_uint32(); 01008 _array = Array::empty_array(num_words); 01009 for (size_t i = 0; i < num_words; ++i) { 01010 _array[i] = WordType(scan.get_uint32()); 01011 } 01012 _highest_bits = scan.get_uint8(); 01013 }