00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "sparseArray.h"
00016 #include "bitArray.h"
00017
00018 TypeHandle SparseArray::_type_handle;
00019
00020
00021
00022
00023
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
00035
00036
00037 while (i <= from.get_num_bits()) {
00038 if (from.get_bit(i) != current_state) {
00039
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
00055
00056
00057
00058
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
00077
00078
00079
00080
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
00099
00100
00101
00102
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
00119
00120
00121
00122
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
00139
00140
00141
00142
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
00159
00160
00161
00162
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
00179
00180
00181
00182
00183
00184
00185
00186
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
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
00215
00216
00217
00218
00219
00220
00221
00222 bool SparseArray::
00223 has_bits_in_common(const SparseArray &other) const {
00224 if (_inverse && other._inverse) {
00225
00226 return true;
00227 }
00228
00229 if (_inverse != other._inverse) {
00230
00231 return !(*this & other).is_zero();
00232 }
00233
00234
00235
00236 return !(*this & other).is_zero();
00237 }
00238
00239
00240
00241
00242
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
00254 out << (*si)._begin << ", ";
00255 } else {
00256
00257 out << (*si)._begin << "-" << ((*si)._end - 1) << ", ";
00258 }
00259 }
00260 out << "]";
00261 }
00262
00263
00264
00265
00266
00267
00268
00269
00270
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
00284 return -1;
00285 } else if ((*bi)._end < (*ai)._end) {
00286
00287 return 1;
00288 } else if ((*ai)._begin < (*bi)._begin) {
00289
00290 return 1;
00291 } else if ((*bi)._begin < (*ai)._begin) {
00292
00293 return -1;
00294 }
00295
00296 --ai;
00297 --bi;
00298 }
00299
00300 if (ai != _subranges.rend()) {
00301
00302 return 1;
00303 }
00304 if (bi != other._subranges.rend()) {
00305
00306 return -1;
00307 }
00308
00309 return 0;
00310 }
00311
00312
00313
00314
00315
00316
00317 void SparseArray::
00318 operator &= (const SparseArray &other) {
00319
00320
00321
00322
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
00332 (*this) = other & (*this);
00333
00334 } else if (!_inverse && other._inverse) {
00335 do_intersection_neg(other);
00336
00337 } else {
00338
00339 nassertv(false);
00340 }
00341 }
00342
00343
00344
00345
00346
00347
00348 void SparseArray::
00349 operator |= (const SparseArray &other) {
00350
00351
00352
00353
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
00366 (*this) = other | (*this);
00367
00368 } else {
00369 nassertv(false);
00370 }
00371 }
00372
00373
00374
00375
00376
00377
00378 void SparseArray::
00379 operator ^= (const SparseArray &other) {
00380
00381
00382
00383
00384
00385 (*this) = ((*this) | other) & ~((*this) & other);
00386 }
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396 void SparseArray::
00397 do_add_range(int begin, int end) {
00398 if (begin >= end) {
00399
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
00410 (*si)._end = end;
00411
00412 } else {
00413
00414 _subranges.push_back(range);
00415 return;
00416 }
00417
00418 } else {
00419
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
00433
00434 (*si2)._end = end;
00435
00436 si = si2;
00437 } else {
00438
00439 _subranges.insert_unverified(si, range);
00440 return;
00441 }
00442 } else {
00443
00444 _subranges.insert_unverified(si, range);
00445 return;
00446 }
00447 }
00448
00449
00450 while (si != _subranges.begin()) {
00451 Subranges::iterator si2 = si;
00452 --si2;
00453 if ((*si2)._end >= begin) {
00454
00455 (*si2)._end = (*si)._end;
00456 _subranges.erase(si);
00457 } else {
00458
00459 break;
00460 }
00461 si = si2;
00462 }
00463
00464 if ((*si)._begin > begin) {
00465
00466 (*si)._begin = begin;
00467 }
00468 }
00469
00470
00471
00472
00473
00474
00475
00476 void SparseArray::
00477 do_remove_range(int begin, int end) {
00478 if (begin >= end) {
00479
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
00490 end = min(end, (*si)._begin);
00491 (*si)._end = end;
00492
00493 } else {
00494
00495 return;
00496 }
00497
00498 } else {
00499
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
00512
00513 end = min(end, (*si2)._begin);
00514 (*si2)._end = end;
00515
00516 si = si2;
00517 } else {
00518
00519 return;
00520 }
00521 } else {
00522
00523 return;
00524 }
00525 }
00526
00527
00528 if (end < (*si)._end) {
00529
00530 Subrange left_range((*si)._begin, begin);
00531 (*si)._begin = end;
00532 si = _subranges.insert_unverified(si, left_range);
00533 }
00534
00535
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
00552
00553
00554
00555
00556
00557
00558 bool SparseArray::
00559 do_has_any(int begin, int end) const {
00560 if (begin >= end) {
00561
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
00582
00583
00584
00585
00586
00587
00588 bool SparseArray::
00589 do_has_all(int begin, int end) const {
00590 if (begin >= end) {
00591
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
00606
00607
00608
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
00635
00636
00637
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
00649
00650
00651
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
00663
00664
00665
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
00680
00681
00682
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
00697
00698
00699
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 }