Panda3D
 All Classes Functions Variables Enumerations
bitArray.I
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 &copy) :
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 &copy) {
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 }
 All Classes Functions Variables Enumerations