Panda3D

sparseArray.I

00001 // Filename: sparseArray.I
00002 // Created by:  drose (14Feb07)
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: SparseArray::Constructor
00018 //       Access: Published
00019 //  Description:
00020 ////////////////////////////////////////////////////////////////////
00021 INLINE SparseArray::
00022 SparseArray() : _inverse(false) {
00023 }
00024 
00025 ////////////////////////////////////////////////////////////////////
00026 //     Function: SparseArray::Copy Constructor
00027 //       Access: Published
00028 //  Description:
00029 ////////////////////////////////////////////////////////////////////
00030 INLINE SparseArray::
00031 SparseArray(const SparseArray &copy) :
00032   _subranges(copy._subranges),
00033   _inverse(copy._inverse)
00034 {
00035 }
00036 
00037 ////////////////////////////////////////////////////////////////////
00038 //     Function: SparseArray::Copy Assignment Operator
00039 //       Access: Published
00040 //  Description:
00041 ////////////////////////////////////////////////////////////////////
00042 INLINE SparseArray &SparseArray::
00043 operator = (const SparseArray &copy) {
00044   _subranges = copy._subranges;
00045   _inverse = copy._inverse;
00046   return *this;
00047 }
00048 
00049 ////////////////////////////////////////////////////////////////////
00050 //     Function: SparseArray::Named all_on constructor
00051 //       Access: Published, Static
00052 //  Description: Returns a SparseArray with an infinite array of bits,
00053 //               all on.
00054 ////////////////////////////////////////////////////////////////////
00055 INLINE SparseArray SparseArray::
00056 all_on() {
00057   SparseArray result;
00058   result._inverse = true;
00059   return result;
00060 }
00061 
00062 ////////////////////////////////////////////////////////////////////
00063 //     Function: SparseArray::Named all_on constructor
00064 //       Access: Published, Static
00065 //  Description: Returns a SparseArray whose bits are all off.
00066 ////////////////////////////////////////////////////////////////////
00067 INLINE SparseArray SparseArray::
00068 all_off() {
00069   return SparseArray();
00070 }
00071 
00072 ////////////////////////////////////////////////////////////////////
00073 //     Function: SparseArray::Named lower_on constructor
00074 //       Access: Published, Static
00075 //  Description: Returns a SparseArray whose lower on_bits bits are on.
00076 ////////////////////////////////////////////////////////////////////
00077 INLINE SparseArray SparseArray::
00078 lower_on(int on_bits) {
00079   SparseArray result;
00080   result.set_range(0, on_bits);
00081   return result;
00082 }
00083 
00084 ////////////////////////////////////////////////////////////////////
00085 //     Function: SparseArray::Named bit constructor
00086 //       Access: Published, Static
00087 //  Description: Returns a SparseArray with only the indicated bit on.
00088 ////////////////////////////////////////////////////////////////////
00089 INLINE SparseArray SparseArray::
00090 bit(int index) {
00091   SparseArray result;
00092   result.set_bit(index);
00093   return result;
00094 }
00095 
00096 ////////////////////////////////////////////////////////////////////
00097 //     Function: SparseArray::Named range constructor
00098 //       Access: Published, Static
00099 //  Description: Returns a SparseArray whose size bits, beginning at
00100 //               low_bit, are on.
00101 ////////////////////////////////////////////////////////////////////
00102 INLINE SparseArray SparseArray::
00103 range(int low_bit, int size) {
00104   SparseArray result;
00105   result.set_range(low_bit, size);
00106   return result;
00107 }
00108 
00109 ////////////////////////////////////////////////////////////////////
00110 //     Function: SparseArray::Destructor
00111 //       Access: Published
00112 //  Description:
00113 ////////////////////////////////////////////////////////////////////
00114 INLINE SparseArray::
00115 ~SparseArray() {
00116 }
00117 
00118 ////////////////////////////////////////////////////////////////////
00119 //     Function: SparseArray::has_max_num_bits
00120 //       Access: Published, Static
00121 //  Description: Returns true if there is a maximum number of bits
00122 //               that may be stored in this structure, false
00123 //               otherwise.  If this returns true, the number may be
00124 //               queried in get_max_num_bits().
00125 //
00126 //               This method always returns false.  The SparseArray has
00127 //               no maximum number of bits.  This method is defined so
00128 //               generic programming algorithms can use BitMask or
00129 //               SparseArray interchangeably.
00130 ////////////////////////////////////////////////////////////////////
00131 INLINE bool SparseArray::
00132 has_max_num_bits() {
00133   return false;
00134 }
00135 
00136 ////////////////////////////////////////////////////////////////////
00137 //     Function: SparseArray::get_max_num_bits
00138 //       Access: Published, Static
00139 //  Description: If get_max_num_bits() returned true, this method may
00140 //               be called to return the maximum number of bits that
00141 //               may be stored in this structure.  It is an error to
00142 //               call this if get_max_num_bits() return false.
00143 //
00144 //               It is always an error to call this method.  The
00145 //               SparseArray has no maximum number of bits.  This method
00146 //               is defined so generic programming algorithms can use
00147 //               BitMask or SparseArray interchangeably.
00148 ////////////////////////////////////////////////////////////////////
00149 INLINE int SparseArray::
00150 get_max_num_bits() {
00151   nassertr(false, 0);
00152   return 0;
00153 }
00154 
00155 ////////////////////////////////////////////////////////////////////
00156 //     Function: SparseArray::get_num_bits
00157 //       Access: Published
00158 //  Description: Returns the current number of possibly different bits
00159 //               in this array.  There are actually an infinite number
00160 //               of bits, but every bit higher than this bit will have
00161 //               the same value, either 0 or 1 (see
00162 //               get_highest_bits()).
00163 //
00164 //               This number may grow and/or shrink automatically as
00165 //               needed.
00166 ////////////////////////////////////////////////////////////////////
00167 INLINE int SparseArray::
00168 get_num_bits() const {
00169   if (_subranges.empty()) {
00170     return 0;
00171   } else {
00172     Subranges::const_iterator si = _subranges.begin() + _subranges.size() - 1;
00173     return (*si)._end;
00174   }
00175 }
00176 
00177 ////////////////////////////////////////////////////////////////////
00178 //     Function: SparseArray::get_bit
00179 //       Access: Published
00180 //  Description: Returns true if the nth bit is set, false if it is
00181 //               cleared.  It is valid for n to increase beyond
00182 //               get_num_bits(), but the return value get_num_bits()
00183 //               will always be the same.
00184 ////////////////////////////////////////////////////////////////////
00185 INLINE bool SparseArray::
00186 get_bit(int index) const {
00187   return has_any_of(index, 1);
00188 }
00189 
00190 ////////////////////////////////////////////////////////////////////
00191 //     Function: SparseArray::set_bit
00192 //       Access: Published
00193 //  Description: Sets the nth bit on.  If n >= get_num_bits(), this
00194 //               automatically extends the array.
00195 ////////////////////////////////////////////////////////////////////
00196 INLINE void SparseArray::
00197 set_bit(int index) {
00198   set_range(index, 1);
00199 }
00200 
00201 ////////////////////////////////////////////////////////////////////
00202 //     Function: SparseArray::clear_bit
00203 //       Access: Published
00204 //  Description: Sets the nth bit off.  If n >= get_num_bits(), this
00205 //               automatically extends the array.
00206 ////////////////////////////////////////////////////////////////////
00207 INLINE void SparseArray::
00208 clear_bit(int index) {
00209   clear_range(index, 1);
00210 }
00211 
00212 ////////////////////////////////////////////////////////////////////
00213 //     Function: SparseArray::set_bit_to
00214 //       Access: Published
00215 //  Description: Sets the nth bit either on or off, according to the
00216 //               indicated bool value.
00217 ////////////////////////////////////////////////////////////////////
00218 INLINE void SparseArray::
00219 set_bit_to(int index, bool value) {
00220   if (value) {
00221     set_bit(index);
00222   } else {
00223     clear_bit(index);
00224   }
00225 }
00226 
00227 ////////////////////////////////////////////////////////////////////
00228 //     Function: SparseArray::get_highest_bits
00229 //       Access: Published
00230 //  Description: Returns true if the infinite set of bits beyond
00231 //               get_num_bits() are all on, or false of they are all
00232 //               off.
00233 ////////////////////////////////////////////////////////////////////
00234 INLINE bool SparseArray::
00235 get_highest_bits() const {
00236   return _inverse;
00237 }
00238 
00239 ////////////////////////////////////////////////////////////////////
00240 //     Function: SparseArray::is_zero
00241 //       Access: Published
00242 //  Description: Returns true if the entire bitmask is zero, false
00243 //               otherwise.
00244 ////////////////////////////////////////////////////////////////////
00245 INLINE bool SparseArray::
00246 is_zero() const {
00247   if (_inverse) {
00248     return false;
00249   } else {
00250     return _subranges.empty();
00251   }
00252 }
00253 
00254 ////////////////////////////////////////////////////////////////////
00255 //     Function: SparseArray::is_all_on
00256 //       Access: Published
00257 //  Description: Returns true if the entire bitmask is one, false
00258 //               otherwise.
00259 ////////////////////////////////////////////////////////////////////
00260 bool SparseArray::
00261 is_all_on() const {
00262   if (_inverse) {
00263     return _subranges.empty();
00264   } else {
00265     return false;
00266   }
00267 }
00268 
00269 ////////////////////////////////////////////////////////////////////
00270 //     Function: SparseArray::has_any_of
00271 //       Access: Published
00272 //  Description: Returns true if any bit in the indicated range is
00273 //               set, false otherwise.
00274 ////////////////////////////////////////////////////////////////////
00275 INLINE bool SparseArray::
00276 has_any_of(int low_bit, int size) const {
00277   if (_inverse) {
00278     return !do_has_all(low_bit, low_bit + size);
00279   } else {
00280     return do_has_any(low_bit, low_bit + size);
00281   }
00282 }
00283 
00284 ////////////////////////////////////////////////////////////////////
00285 //     Function: SparseArray::has_all_of
00286 //       Access: Published
00287 //  Description: Returns true if all bits in the indicated range are
00288 //               set, false otherwise.
00289 ////////////////////////////////////////////////////////////////////
00290 INLINE bool SparseArray::
00291 has_all_of(int low_bit, int size) const {
00292   if (_inverse) {
00293     return !do_has_any(low_bit, low_bit + size);
00294   } else {
00295     return do_has_all(low_bit, low_bit + size);
00296   }
00297 }
00298 
00299 ////////////////////////////////////////////////////////////////////
00300 //     Function: SparseArray::set_range
00301 //       Access: Published
00302 //  Description: Sets the indicated range of bits on.
00303 ////////////////////////////////////////////////////////////////////
00304 INLINE void SparseArray::
00305 set_range(int low_bit, int size) {
00306   if (_inverse) {
00307     return do_remove_range(low_bit, low_bit + size);
00308   } else {
00309     return do_add_range(low_bit, low_bit + size);
00310   }
00311 }
00312 
00313 ////////////////////////////////////////////////////////////////////
00314 //     Function: SparseArray::clear_range
00315 //       Access: Published
00316 //  Description: Sets the indicated range of bits off.
00317 ////////////////////////////////////////////////////////////////////
00318 INLINE void SparseArray::
00319 clear_range(int low_bit, int size) {
00320   if (_inverse) {
00321     return do_add_range(low_bit, low_bit + size);
00322   } else {
00323     return do_remove_range(low_bit, low_bit + size);
00324   }
00325 }
00326 
00327 ////////////////////////////////////////////////////////////////////
00328 //     Function: SparseArray::set_range_to
00329 //       Access: Published
00330 //  Description: Sets the indicated range of bits to either on or off.
00331 ////////////////////////////////////////////////////////////////////
00332 INLINE void SparseArray::
00333 set_range_to(bool value, int low_bit, int size) {
00334   if (value) {
00335     set_range(low_bit, size);
00336   } else {
00337     clear_range(low_bit, size);
00338   }
00339 }
00340 
00341 ////////////////////////////////////////////////////////////////////
00342 //     Function: SparseArray::invert_in_place
00343 //       Access: Published
00344 //  Description: Inverts all the bits in the SparseArray.  This is
00345 //               equivalent to array = ~array.
00346 ////////////////////////////////////////////////////////////////////
00347 void SparseArray::
00348 invert_in_place() {
00349   _inverse = !_inverse;
00350 }
00351 
00352 ////////////////////////////////////////////////////////////////////
00353 //     Function: SparseArray::clear
00354 //       Access: Published
00355 //  Description: Sets all the bits in the SparseArray off.
00356 ////////////////////////////////////////////////////////////////////
00357 void SparseArray::
00358 clear() {
00359   _subranges.clear();
00360   _inverse = false;
00361 }
00362 
00363 ////////////////////////////////////////////////////////////////////
00364 //     Function: SparseArray::operator ==
00365 //       Access: Published
00366 //  Description:
00367 ////////////////////////////////////////////////////////////////////
00368 INLINE bool SparseArray::
00369 operator == (const SparseArray &other) const {
00370   return compare_to(other) == 0;
00371 }
00372 
00373 ////////////////////////////////////////////////////////////////////
00374 //     Function: SparseArray::operator !=
00375 //       Access: Published
00376 //  Description:
00377 ////////////////////////////////////////////////////////////////////
00378 INLINE bool SparseArray::
00379 operator != (const SparseArray &other) const {
00380   return compare_to(other) != 0;
00381 }
00382 
00383 ////////////////////////////////////////////////////////////////////
00384 //     Function: SparseArray::operator <
00385 //       Access: Published
00386 //  Description: Returns true if the unsigned integer which is
00387 //               represented by this SparseArray is less than that of the
00388 //               other one, false otherwise.
00389 ////////////////////////////////////////////////////////////////////
00390 INLINE bool SparseArray::
00391 operator < (const SparseArray &other) const {
00392   return compare_to(other) < 0;
00393 }
00394 
00395 ////////////////////////////////////////////////////////////////////
00396 //     Function: SparseArray::operator &
00397 //       Access: Published
00398 //  Description:
00399 ////////////////////////////////////////////////////////////////////
00400 INLINE SparseArray SparseArray::
00401 operator & (const SparseArray &other) const {
00402   SparseArray result(*this);
00403   result &= other;
00404   return result;
00405 }
00406 
00407 ////////////////////////////////////////////////////////////////////
00408 //     Function: SparseArray::operator |
00409 //       Access: Published
00410 //  Description:
00411 ////////////////////////////////////////////////////////////////////
00412 INLINE SparseArray SparseArray::
00413 operator | (const SparseArray &other) const {
00414   SparseArray result(*this);
00415   result |= other;
00416   return result;
00417 }
00418 
00419 ////////////////////////////////////////////////////////////////////
00420 //     Function: SparseArray::operator ^
00421 //       Access: Published
00422 //  Description:
00423 ////////////////////////////////////////////////////////////////////
00424 INLINE SparseArray SparseArray::
00425 operator ^ (const SparseArray &other) const {
00426   SparseArray result(*this);
00427   result ^= other;
00428   return result;
00429 }
00430 
00431 ////////////////////////////////////////////////////////////////////
00432 //     Function: SparseArray::operator ~
00433 //       Access: Published
00434 //  Description:
00435 ////////////////////////////////////////////////////////////////////
00436 INLINE SparseArray SparseArray::
00437 operator ~ () const {
00438   SparseArray result(*this);
00439   result.invert_in_place();
00440   return result;
00441 }
00442 
00443 ////////////////////////////////////////////////////////////////////
00444 //     Function: SparseArray::operator <<
00445 //       Access: Published
00446 //  Description:
00447 ////////////////////////////////////////////////////////////////////
00448 INLINE SparseArray SparseArray::
00449 operator << (int shift) const {
00450   SparseArray result(*this);
00451   result <<= shift;
00452   return result;
00453 }
00454 
00455 ////////////////////////////////////////////////////////////////////
00456 //     Function: SparseArray::operator >>
00457 //       Access: Published
00458 //  Description:
00459 ////////////////////////////////////////////////////////////////////
00460 INLINE SparseArray SparseArray::
00461 operator >> (int shift) const {
00462   SparseArray result(*this);
00463   result >>= shift;
00464   return result;
00465 }
00466 
00467 
00468 ////////////////////////////////////////////////////////////////////
00469 //     Function: SparseArray::operator <<=
00470 //       Access: Published
00471 //  Description: Logical left shift.  Since negative bit positions
00472 //               have meaning in a SparseArray, real bit values are
00473 //               rotated in on the left (not necessarily zero).
00474 ////////////////////////////////////////////////////////////////////
00475 void SparseArray::
00476 operator <<= (int shift) {
00477   do_shift(shift);
00478 }
00479 
00480 ////////////////////////////////////////////////////////////////////
00481 //     Function: SparseArray::operator >>=
00482 //       Access: Published
00483 //  Description: Logical right shift.  The rightmost bits become
00484 //               negative, but are not lost; they will reappear into
00485 //               the zero position if the array is later left-shifted.
00486 ////////////////////////////////////////////////////////////////////
00487 void SparseArray::
00488 operator >>= (int shift) {
00489   do_shift(-shift);
00490 }
00491 
00492 ////////////////////////////////////////////////////////////////////
00493 //     Function: SparseArray::is_inverse
00494 //       Access: Published
00495 //  Description: If this is true, the SparseArray is actually defined
00496 //               as a list of subranges of integers that are *not* in
00497 //               the set.  If this is false (the default), then the
00498 //               subranges define the integers that *are* in the set.
00499 //               This affects the interpretation of the values
00500 //               returned by iterating through get_num_subranges().
00501 ////////////////////////////////////////////////////////////////////
00502 INLINE bool SparseArray::
00503 is_inverse() const {
00504   return _inverse;
00505 }
00506 
00507 ////////////////////////////////////////////////////////////////////
00508 //     Function: SparseArray::get_num_subranges
00509 //       Access: Published
00510 //  Description: Returns the number of separate subranges stored in
00511 //               the SparseArray.  You can use this limit to iterate
00512 //               through the subranges, calling get_subrange_begin()
00513 //               and get_subrange_end() for each one.
00514 //
00515 //               Also see is_inverse().
00516 ////////////////////////////////////////////////////////////////////
00517 INLINE int SparseArray::
00518 get_num_subranges() const {
00519   return _subranges.size();
00520 }
00521 
00522 ////////////////////////////////////////////////////////////////////
00523 //     Function: SparseArray::get_subrange_begin
00524 //       Access: Published
00525 //  Description: Returns the first numeric element in the nth
00526 //               subrange.
00527 //
00528 //               Also see is_inverse().
00529 ////////////////////////////////////////////////////////////////////
00530 INLINE int SparseArray::
00531 get_subrange_begin(int n) const {
00532   nassertr(n >= 0 && n < (int)_subranges.size(), 0);
00533   return _subranges[n]._begin;
00534 }
00535 
00536 ////////////////////////////////////////////////////////////////////
00537 //     Function: SparseArray::get_subrange_end
00538 //       Access: Published
00539 //  Description: Returns the last numeric element, plus one, in the
00540 //               nth subrange.
00541 //
00542 //               Also see is_inverse().
00543 ////////////////////////////////////////////////////////////////////
00544 INLINE int SparseArray::
00545 get_subrange_end(int n) const {
00546   nassertr(n >= 0 && n < (int)_subranges.size(), 0);
00547   return _subranges[n]._end;
00548 }
00549 
00550 ////////////////////////////////////////////////////////////////////
00551 //     Function: SparseArray::Subrange::Constructor
00552 //       Access: Public
00553 //  Description: 
00554 ////////////////////////////////////////////////////////////////////
00555 INLINE SparseArray::Subrange::
00556 Subrange(int begin, int end) :
00557   _begin(begin),
00558   _end(end)
00559 {
00560 }
00561 
00562 ////////////////////////////////////////////////////////////////////
00563 //     Function: SparseArray::Subrange::operator <
00564 //       Access: Public
00565 //  Description: 
00566 ////////////////////////////////////////////////////////////////////
00567 INLINE bool SparseArray::Subrange::
00568 operator < (const SparseArray::Subrange &other) const {
00569   // We compare the end values, rather than the begin values, to make
00570   // lower_bound() sensibly return a possible intersection with the
00571   // indicated Subrange.
00572   return _end < other._end;
00573 }
00574 
 All Classes Functions Variables Enumerations