Panda3D

sparseArray.cxx

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 }
 All Classes Functions Variables Enumerations