Panda3D
 All Classes Functions Variables Enumerations
bitArray.cxx
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 }
 All Classes Functions Variables Enumerations