Panda3D
|
00001 // Filename: sparseArray.cxx 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 #include "sparseArray.h" 00016 #include "bitArray.h" 00017 00018 TypeHandle SparseArray::_type_handle; 00019 00020 //////////////////////////////////////////////////////////////////// 00021 // Function: SparseArray::Constructor (from BitArray) 00022 // Access: Published 00023 // Description: 00024 //////////////////////////////////////////////////////////////////// 00025 SparseArray:: 00026 SparseArray(const BitArray &from) { 00027 bool empty_bit = from.get_highest_bits(); 00028 _inverse = empty_bit; 00029 00030 int begin = 0; 00031 bool current_state = from.get_bit(0); 00032 int i = 0; 00033 00034 // By including get_num_bits()--one more than the last bit--in this 00035 // traversal, we guarantee that we will end on the empty_bit state 00036 // (because the last bit we visit will be one of the highest_bits). 00037 while (i <= from.get_num_bits()) { 00038 if (from.get_bit(i) != current_state) { 00039 // End of a run. 00040 if (current_state != empty_bit) { 00041 Subrange range(begin, i); 00042 _subranges.push_back(range); 00043 } 00044 begin = i; 00045 current_state = !current_state; 00046 } 00047 ++i; 00048 } 00049 00050 nassertv(current_state == empty_bit); 00051 } 00052 00053 //////////////////////////////////////////////////////////////////// 00054 // Function: SparseArray::get_num_on_bits 00055 // Access: Published 00056 // Description: Returns the number of bits that are set to 1 in the 00057 // array. Returns -1 if there are an infinite number of 00058 // 1 bits. 00059 //////////////////////////////////////////////////////////////////// 00060 int SparseArray:: 00061 get_num_on_bits() const { 00062 if (_inverse) { 00063 return -1; 00064 } 00065 00066 int result = 0; 00067 Subranges::const_iterator si; 00068 for (si = _subranges.begin(); si != _subranges.end(); ++si) { 00069 result += (*si)._end - (*si)._begin; 00070 } 00071 00072 return result; 00073 } 00074 00075 //////////////////////////////////////////////////////////////////// 00076 // Function: SparseArray::get_num_off_bits 00077 // Access: Published 00078 // Description: Returns the number of bits that are set to 0 in the 00079 // array. Returns -1 if there are an infinite number of 00080 // 0 bits. 00081 //////////////////////////////////////////////////////////////////// 00082 int SparseArray:: 00083 get_num_off_bits() const { 00084 if (!_inverse) { 00085 return -1; 00086 } 00087 00088 int result = 0; 00089 Subranges::const_iterator si; 00090 for (si = _subranges.begin(); si != _subranges.end(); ++si) { 00091 result += (*si)._end - (*si)._begin; 00092 } 00093 00094 return result; 00095 } 00096 00097 //////////////////////////////////////////////////////////////////// 00098 // Function: SparseArray::get_lowest_on_bit 00099 // Access: Published 00100 // Description: Returns the index of the lowest 1 bit in the array. 00101 // Returns -1 if there are no 1 bits or if there are an 00102 // infinite number of 1 bits. 00103 //////////////////////////////////////////////////////////////////// 00104 int SparseArray:: 00105 get_lowest_on_bit() const { 00106 if (_inverse) { 00107 return -1; 00108 } 00109 00110 if (_subranges.empty()) { 00111 return -1; 00112 } 00113 00114 return _subranges[0]._begin; 00115 } 00116 00117 //////////////////////////////////////////////////////////////////// 00118 // Function: SparseArray::get_lowest_off_bit 00119 // Access: Published 00120 // Description: Returns the index of the lowest 0 bit in the array. 00121 // Returns -1 if there are no 0 bits or if there are an 00122 // infinite number of 1 bits. 00123 //////////////////////////////////////////////////////////////////// 00124 int SparseArray:: 00125 get_lowest_off_bit() const { 00126 if (!_inverse) { 00127 return -1; 00128 } 00129 00130 if (_subranges.empty()) { 00131 return -1; 00132 } 00133 00134 return _subranges[0]._begin; 00135 } 00136 00137 //////////////////////////////////////////////////////////////////// 00138 // Function: SparseArray::get_highest_on_bit 00139 // Access: Published 00140 // Description: Returns the index of the highest 1 bit in the array. 00141 // Returns -1 if there are no 1 bits or if there an 00142 // infinite number of 1 bits. 00143 //////////////////////////////////////////////////////////////////// 00144 int SparseArray:: 00145 get_highest_on_bit() const { 00146 if (_inverse) { 00147 return -1; 00148 } 00149 00150 if (_subranges.empty()) { 00151 return -1; 00152 } 00153 00154 return _subranges[_subranges.size() - 1]._end - 1; 00155 } 00156 00157 //////////////////////////////////////////////////////////////////// 00158 // Function: SparseArray::get_highest_off_bit 00159 // Access: Published 00160 // Description: Returns the index of the highest 0 bit in the array. 00161 // Returns -1 if there are no 0 bits or if there an 00162 // infinite number of 1 bits. 00163 //////////////////////////////////////////////////////////////////// 00164 int SparseArray:: 00165 get_highest_off_bit() const { 00166 if (!_inverse) { 00167 return -1; 00168 } 00169 00170 if (_subranges.empty()) { 00171 return -1; 00172 } 00173 00174 return _subranges[_subranges.size() - 1]._end - 1; 00175 } 00176 00177 //////////////////////////////////////////////////////////////////// 00178 // Function: SparseArray::get_next_higher_different_bit 00179 // Access: Published 00180 // Description: Returns the index of the next bit in the array, above 00181 // low_bit, whose value is different that the value of 00182 // low_bit. Returns low_bit again if all bits higher 00183 // than low_bit have the same value. 00184 // 00185 // This can be used to quickly iterate through all of 00186 // the bits in the array. 00187 //////////////////////////////////////////////////////////////////// 00188 int SparseArray:: 00189 get_next_higher_different_bit(int low_bit) const { 00190 Subrange range(low_bit, low_bit + 1); 00191 Subranges::const_iterator si = _subranges.lower_bound(range); 00192 if (si == _subranges.end()) { 00193 // That was the end of the array. 00194 return low_bit; 00195 } 00196 00197 if (low_bit >= (*si)._begin) { 00198 return (*si)._end; 00199 } 00200 00201 int next = (*si)._begin; 00202 00203 if (si != _subranges.begin()) { 00204 --si; 00205 if (low_bit < (*si)._end) { 00206 return (*si)._end; 00207 } 00208 } 00209 00210 return next; 00211 } 00212 00213 //////////////////////////////////////////////////////////////////// 00214 // Function: SparseArray::has_bits_in_common 00215 // Access: Published 00216 // Description: Returns true if this SparseArray has any "one" bits in 00217 // common with the other one, false otherwise. 00218 // 00219 // This is equivalent to (array & other) != 0, but may 00220 // be faster. 00221 //////////////////////////////////////////////////////////////////// 00222 bool SparseArray:: 00223 has_bits_in_common(const SparseArray &other) const { 00224 if (_inverse && other._inverse) { 00225 // Yup, in fact we have an infinite number of bits in common. 00226 return true; 00227 } 00228 00229 if (_inverse != other._inverse) { 00230 // We'll handle this tricky case the lazy way. 00231 return !(*this & other).is_zero(); 00232 } 00233 00234 // Actually, we'll handle this easy case the lazy way too. Maybe 00235 // later we'll do this smarter. 00236 return !(*this & other).is_zero(); 00237 } 00238 00239 //////////////////////////////////////////////////////////////////// 00240 // Function: SparseArray::output 00241 // Access: Published 00242 // Description: 00243 //////////////////////////////////////////////////////////////////// 00244 void SparseArray:: 00245 output(ostream &out) const { 00246 out << "[ "; 00247 if (_inverse) { 00248 out << "all except: "; 00249 } 00250 Subranges::const_iterator si; 00251 for (si = _subranges.begin(); si != _subranges.end(); ++si) { 00252 if ((*si)._end == (*si)._begin + 1) { 00253 // A single element. 00254 out << (*si)._begin << ", "; 00255 } else { 00256 // A range of elements. 00257 out << (*si)._begin << "-" << ((*si)._end - 1) << ", "; 00258 } 00259 } 00260 out << "]"; 00261 } 00262 00263 //////////////////////////////////////////////////////////////////// 00264 // Function: SparseArray::compare_to 00265 // Access: Published 00266 // Description: Returns a number less than zero if this SparseArray 00267 // sorts before the indicated other SparseArray, greater 00268 // than zero if it sorts after, or 0 if they are 00269 // equivalent. This is based on the same ordering 00270 // defined by operator <. 00271 //////////////////////////////////////////////////////////////////// 00272 int SparseArray:: 00273 compare_to(const SparseArray &other) const { 00274 if (_inverse != other._inverse) { 00275 return _inverse ? 1 : -1; 00276 } 00277 00278 Subranges::const_reverse_iterator ai = _subranges.rbegin(); 00279 Subranges::const_reverse_iterator bi = other._subranges.rbegin(); 00280 00281 while (ai != _subranges.rend() && bi != other._subranges.rend()) { 00282 if ((*ai)._end < (*bi)._end) { 00283 // B is higher. 00284 return -1; 00285 } else if ((*bi)._end < (*ai)._end) { 00286 // A is higher. 00287 return 1; 00288 } else if ((*ai)._begin < (*bi)._begin) { 00289 // A is higher. 00290 return 1; 00291 } else if ((*bi)._begin < (*ai)._begin) { 00292 // B is higher. 00293 return -1; 00294 } 00295 00296 --ai; 00297 --bi; 00298 } 00299 00300 if (ai != _subranges.rend()) { 00301 // A is higher. 00302 return 1; 00303 } 00304 if (bi != other._subranges.rend()) { 00305 // B is higher. 00306 return -1; 00307 } 00308 00309 return 0; 00310 } 00311 00312 //////////////////////////////////////////////////////////////////// 00313 // Function: SparseArray::operator &= 00314 // Access: Published 00315 // Description: 00316 //////////////////////////////////////////////////////////////////// 00317 void SparseArray:: 00318 operator &= (const SparseArray &other) { 00319 // We do this the slow and stupid way. This could be done much 00320 // better with a little effort, but I'm not at all sure it's worth 00321 // the effort. If you need fast boolean operations, you should 00322 // probably be using a BitArray. 00323 00324 if (_inverse && other._inverse) { 00325 do_union(other); 00326 00327 } else if (!_inverse && !other._inverse) { 00328 do_intersection(other); 00329 00330 } else if (_inverse && !other._inverse) { 00331 // a & b == b & a 00332 (*this) = other & (*this); 00333 00334 } else if (!_inverse && other._inverse) { 00335 do_intersection_neg(other); 00336 00337 } else { 00338 // TODO. 00339 nassertv(false); 00340 } 00341 } 00342 00343 //////////////////////////////////////////////////////////////////// 00344 // Function: SparseArray::operator |= 00345 // Access: Published 00346 // Description: 00347 //////////////////////////////////////////////////////////////////// 00348 void SparseArray:: 00349 operator |= (const SparseArray &other) { 00350 // We do this the slow and stupid way. This could be done much 00351 // better with a little effort, but I'm not at all sure it's worth 00352 // the effort. If you need fast boolean operations, you should 00353 // probably be using a BitArray. 00354 00355 if (_inverse && other._inverse) { 00356 do_intersection(other); 00357 00358 } else if (!_inverse && !other._inverse) { 00359 do_union(other); 00360 00361 } else if (_inverse && !other._inverse) { 00362 do_intersection_neg(other); 00363 00364 } else if (!_inverse && other._inverse) { 00365 // a | b == b | a 00366 (*this) = other | (*this); 00367 00368 } else { 00369 nassertv(false); 00370 } 00371 } 00372 00373 //////////////////////////////////////////////////////////////////// 00374 // Function: SparseArray::operator ^= 00375 // Access: Published 00376 // Description: 00377 //////////////////////////////////////////////////////////////////// 00378 void SparseArray:: 00379 operator ^= (const SparseArray &other) { 00380 // We do this the slow and stupid way. This could be done much 00381 // better with a little effort, but I'm not at all sure it's worth 00382 // the effort. If you need fast boolean operations, you should 00383 // probably be using a BitArray. 00384 00385 (*this) = ((*this) | other) & ~((*this) & other); 00386 } 00387 00388 //////////////////////////////////////////////////////////////////// 00389 // Function: SparseArray::do_add_range 00390 // Access: Private 00391 // Description: Adds the consecutive range of integers beginning at 00392 // begin, but not including end, to the array. If this 00393 // range overlaps with another range already in the 00394 // array, the result is the union. 00395 //////////////////////////////////////////////////////////////////// 00396 void SparseArray:: 00397 do_add_range(int begin, int end) { 00398 if (begin >= end) { 00399 // Empty range. 00400 return; 00401 } 00402 00403 Subrange range(begin, end); 00404 Subranges::iterator si = _subranges.lower_bound(range); 00405 if (si == _subranges.end()) { 00406 if (!_subranges.empty()) { 00407 si = _subranges.begin() + _subranges.size() - 1; 00408 if ((*si)._end >= begin) { 00409 // The new range expands the last element of the array to the right. 00410 (*si)._end = end; 00411 // It might also expand it to the left; fall through. 00412 } else { 00413 // The new range is completely after the last element of the array. 00414 _subranges.push_back(range); 00415 return; 00416 } 00417 00418 } else { 00419 // The new range is completely after the last element of the array. 00420 _subranges.push_back(range); 00421 return; 00422 } 00423 } 00424 00425 nassertv((*si)._end >= end); 00426 00427 if ((*si)._begin > end) { 00428 if (si != _subranges.begin()) { 00429 Subranges::iterator si2 = si; 00430 --si2; 00431 if ((*si2)._end >= begin) { 00432 // The new range expands an element within the array to the 00433 // right (but does not intersect the next element). 00434 (*si2)._end = end; 00435 // It might also expand it to the left; fall through. 00436 si = si2; 00437 } else { 00438 // The new range does not intersect any elements in the array. 00439 _subranges.insert_unverified(si, range); 00440 return; 00441 } 00442 } else { 00443 // The new range does not intersect any elements in the array. 00444 _subranges.insert_unverified(si, range); 00445 return; 00446 } 00447 } 00448 00449 // Check if the new range overlaps with any elements to the left. 00450 while (si != _subranges.begin()) { 00451 Subranges::iterator si2 = si; 00452 --si2; 00453 if ((*si2)._end >= begin) { 00454 // The new range straddles two elements, so they get combined. 00455 (*si2)._end = (*si)._end; 00456 _subranges.erase(si); 00457 } else { 00458 // Stop here. 00459 break; 00460 } 00461 si = si2; 00462 } 00463 00464 if ((*si)._begin > begin) { 00465 // The new range expands an element to the left. 00466 (*si)._begin = begin; 00467 } 00468 } 00469 00470 //////////////////////////////////////////////////////////////////// 00471 // Function: SparseArray::do_remove_range 00472 // Access: Private 00473 // Description: Removes the consecutive range of integers beginning 00474 // at begin, but not including end, from the array. 00475 //////////////////////////////////////////////////////////////////// 00476 void SparseArray:: 00477 do_remove_range(int begin, int end) { 00478 if (begin >= end) { 00479 // Empty range. 00480 return; 00481 } 00482 00483 Subrange range(begin, end); 00484 Subranges::iterator si = _subranges.lower_bound(range); 00485 if (si == _subranges.end()) { 00486 if (!_subranges.empty()) { 00487 si = _subranges.begin() + _subranges.size() - 1; 00488 if ((*si)._end >= begin) { 00489 // The new range shortens the last element of the array on the right. 00490 end = min(end, (*si)._begin); 00491 (*si)._end = end; 00492 // It might also shorten it on the left; fall through. 00493 } else { 00494 // The new range is completely after the last element of the array. 00495 return; 00496 } 00497 00498 } else { 00499 // The new range is completely after the last element of the array. 00500 return; 00501 } 00502 } 00503 00504 nassertv((*si)._end >= end); 00505 00506 if ((*si)._begin > end) { 00507 if (si != _subranges.begin()) { 00508 Subranges::iterator si2 = si; 00509 --si2; 00510 if ((*si2)._end >= begin) { 00511 // The new range shortens an element within the array on the 00512 // right (but does not intersect the next element). 00513 end = min(end, (*si2)._begin); 00514 (*si2)._end = end; 00515 // It might also shorten it on the left; fall through. 00516 si = si2; 00517 } else { 00518 // The new range does not intersect any elements in the array. 00519 return; 00520 } 00521 } else { 00522 // The new range does not intersect any elements in the array. 00523 return; 00524 } 00525 } 00526 00527 00528 if (end < (*si)._end) { 00529 // We must split an element into two. 00530 Subrange left_range((*si)._begin, begin); 00531 (*si)._begin = end; 00532 si = _subranges.insert_unverified(si, left_range); 00533 } 00534 00535 // Check if the new range removes any elements to the left. 00536 while (begin <= (*si)._begin) { 00537 if (si == _subranges.begin()) { 00538 _subranges.erase(si); 00539 return; 00540 } 00541 Subranges::iterator si2 = si; 00542 --si2; 00543 _subranges.erase(si); 00544 si = si2; 00545 } 00546 00547 (*si)._end = min((*si)._end, begin); 00548 } 00549 00550 //////////////////////////////////////////////////////////////////// 00551 // Function: SparseArray::do_has_any 00552 // Access: Private 00553 // Description: Returns true if any of the consecutive range of 00554 // integers beginning at begin, but not including end, 00555 // appear in the array. Note that this will return 00556 // false for an empty range. 00557 //////////////////////////////////////////////////////////////////// 00558 bool SparseArray:: 00559 do_has_any(int begin, int end) const { 00560 if (begin >= end) { 00561 // Empty range. 00562 return false; 00563 } 00564 00565 Subrange range(begin, end); 00566 Subranges::const_iterator si = _subranges.lower_bound(range); 00567 if (si != _subranges.end() && end > (*si)._begin) { 00568 return true; 00569 } 00570 if (si != _subranges.begin()) { 00571 --si; 00572 if (begin < (*si)._end) { 00573 return true; 00574 } 00575 } 00576 00577 return false; 00578 } 00579 00580 //////////////////////////////////////////////////////////////////// 00581 // Function: SparseArray::do_has_all 00582 // Access: Private 00583 // Description: Returns true if all of the consecutive range of 00584 // integers beginning at begin, but not including end, 00585 // appear in the array. Note that this will return 00586 // true for an empty range. 00587 //////////////////////////////////////////////////////////////////// 00588 bool SparseArray:: 00589 do_has_all(int begin, int end) const { 00590 if (begin >= end) { 00591 // Empty range. 00592 return true; 00593 } 00594 00595 Subrange range(begin, end); 00596 Subranges::const_iterator si = _subranges.lower_bound(range); 00597 if (si != _subranges.end() && begin >= (*si)._begin) { 00598 return true; 00599 } 00600 00601 return false; 00602 } 00603 00604 //////////////////////////////////////////////////////////////////// 00605 // Function: SparseArray::do_intersection 00606 // Access: Private 00607 // Description: Removes from this array all of the elements that do 00608 // not appear in the other one. 00609 //////////////////////////////////////////////////////////////////// 00610 void SparseArray:: 00611 do_intersection(const SparseArray &other) { 00612 if (_subranges.empty()) { 00613 return; 00614 } 00615 if (other._subranges.empty()) { 00616 _subranges.clear(); 00617 return; 00618 } 00619 00620 int my_begin = (*_subranges.begin())._begin; 00621 int other_begin = (*other._subranges.begin())._begin; 00622 do_remove_range(my_begin, other_begin); 00623 00624 for (size_t i = 0; i < other._subranges.size() - 1; ++i) { 00625 do_remove_range(other._subranges[i]._end, other._subranges[i + 1]._begin); 00626 } 00627 00628 int my_end = (*(_subranges.begin() + _subranges.size() - 1))._end; 00629 int other_end = (*(other._subranges.begin() + other._subranges.size() - 1))._end; 00630 do_remove_range(other_end, my_end); 00631 } 00632 00633 //////////////////////////////////////////////////////////////////// 00634 // Function: SparseArray::do_union 00635 // Access: Private 00636 // Description: Adds to this array all of the elements that also 00637 // appear in the other one. 00638 //////////////////////////////////////////////////////////////////// 00639 void SparseArray:: 00640 do_union(const SparseArray &other) { 00641 Subranges::const_iterator si; 00642 for (si = other._subranges.begin(); si != other._subranges.end(); ++si) { 00643 do_add_range((*si)._begin, (*si)._end); 00644 } 00645 } 00646 00647 //////////////////////////////////////////////////////////////////// 00648 // Function: SparseArray::do_intersection_neg 00649 // Access: Private 00650 // Description: Removes from this array all of the elements that also 00651 // appear in the other one. 00652 //////////////////////////////////////////////////////////////////// 00653 void SparseArray:: 00654 do_intersection_neg(const SparseArray &other) { 00655 Subranges::const_iterator si; 00656 for (si = other._subranges.begin(); si != other._subranges.end(); ++si) { 00657 do_remove_range((*si)._begin, (*si)._end); 00658 } 00659 } 00660 00661 //////////////////////////////////////////////////////////////////// 00662 // Function: SparseArray::do_shift 00663 // Access: Private 00664 // Description: Shifts all the elements in the array by the indicated 00665 // amount. 00666 //////////////////////////////////////////////////////////////////// 00667 void SparseArray:: 00668 do_shift(int offset) { 00669 if (offset != 0) { 00670 Subranges::iterator si; 00671 for (si = _subranges.begin(); si != _subranges.end(); ++si) { 00672 (*si)._begin += offset; 00673 (*si)._end += offset; 00674 } 00675 } 00676 } 00677 00678 //////////////////////////////////////////////////////////////////// 00679 // Function: SparseArray::write_datagram 00680 // Access: Public 00681 // Description: Writes the contents of this object to the datagram 00682 // for shipping out to a Bam file. 00683 //////////////////////////////////////////////////////////////////// 00684 void SparseArray:: 00685 write_datagram(BamWriter *manager, Datagram &dg) const { 00686 dg.add_uint32(_subranges.size()); 00687 Subranges::const_iterator si; 00688 for (si = _subranges.begin(); si != _subranges.end(); ++si) { 00689 dg.add_int32((*si)._begin); 00690 dg.add_int32((*si)._end); 00691 } 00692 dg.add_bool(_inverse); 00693 } 00694 00695 //////////////////////////////////////////////////////////////////// 00696 // Function: SparseArray::read_datagram 00697 // Access: Public 00698 // Description: Reads the object that was previously written to a Bam 00699 // file. 00700 //////////////////////////////////////////////////////////////////// 00701 void SparseArray:: 00702 read_datagram(DatagramIterator &scan, BamReader *manager) { 00703 size_t num_subranges = scan.get_uint32(); 00704 _subranges.reserve(num_subranges); 00705 for (size_t i = 0; i < num_subranges; ++i) { 00706 int begin = scan.get_int32(); 00707 int end = scan.get_int32(); 00708 _subranges.push_back(Subrange(begin, end)); 00709 } 00710 _inverse = scan.get_bool(); 00711 }