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 ©) : 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 ©) { 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