00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "bitArray.h"
00016 #include "sparseArray.h"
00017
00018 TypeHandle BitArray::_type_handle;
00019
00020
00021
00022
00023
00024
00025 BitArray::
00026 BitArray(const SparseArray &from) {
00027 _highest_bits = 0;
00028
00029 int num_subranges = from.get_num_subranges();
00030 for (int i = 0; i < num_subranges; ++i) {
00031 int begin = from.get_subrange_begin(i);
00032 int end = from.get_subrange_end(i);
00033 set_range(begin, end - begin);
00034 }
00035
00036 if (from.is_inverse()) {
00037 invert_in_place();
00038 }
00039 }
00040
00041
00042
00043
00044
00045
00046
00047 bool BitArray::
00048 is_zero() const {
00049 if (_highest_bits) {
00050
00051
00052 return false;
00053 }
00054
00055
00056 Array::reverse_iterator ai;
00057 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
00058 if (!(*ai).is_zero()) {
00059 return false;
00060 }
00061 }
00062 return true;
00063 }
00064
00065
00066
00067
00068
00069
00070
00071 bool BitArray::
00072 is_all_on() const {
00073 if (!_highest_bits) {
00074
00075
00076 return false;
00077 }
00078
00079 Array::reverse_iterator ai;
00080 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
00081 if (!(*ai).is_all_on()) {
00082 return false;
00083 }
00084 }
00085 return true;
00086 }
00087
00088
00089
00090
00091
00092
00093
00094 bool BitArray::
00095 has_any_of(int low_bit, int size) const {
00096 if ((low_bit + size - 1) / num_bits_per_word >= get_num_words()) {
00097
00098 if (_highest_bits) {
00099 return true;
00100 }
00101 }
00102
00103 int w = low_bit / num_bits_per_word;
00104 int b = low_bit % num_bits_per_word;
00105
00106 if (w >= get_num_words()) {
00107
00108 return (_highest_bits != 0);
00109 }
00110 if (b + size <= num_bits_per_word) {
00111
00112 return get_word(w).has_any_of(b, size);
00113 }
00114
00115 int num_high_bits = num_bits_per_word - b;
00116 if (_array[w].has_any_of(b, num_high_bits)) {
00117 return true;
00118 }
00119 size -= num_high_bits;
00120 ++w;
00121
00122 while (size > 0) {
00123 if (size <= num_bits_per_word) {
00124
00125 return _array[w].has_any_of(0, size);
00126 }
00127
00128
00129 if (!_array[w].is_zero()) {
00130 return true;
00131 }
00132 size -= num_bits_per_word;
00133 ++w;
00134
00135 if (w >= get_num_words()) {
00136
00137 return (_highest_bits != 0);
00138 }
00139 }
00140
00141 return false;
00142 }
00143
00144
00145
00146
00147
00148
00149
00150 bool BitArray::
00151 has_all_of(int low_bit, int size) const {
00152 if ((low_bit + size - 1) / num_bits_per_word >= get_num_words()) {
00153
00154 if (!_highest_bits) {
00155 return false;
00156 }
00157 }
00158
00159 int w = low_bit / num_bits_per_word;
00160 int b = low_bit % num_bits_per_word;
00161
00162 if (w >= get_num_words()) {
00163
00164 return (_highest_bits != 0);
00165 }
00166 if (b + size <= num_bits_per_word) {
00167
00168 return get_word(w).has_all_of(b, size);
00169 }
00170
00171 int num_high_bits = num_bits_per_word - b;
00172 if (!_array[w].has_all_of(b, num_high_bits)) {
00173 return false;
00174 }
00175 size -= num_high_bits;
00176 ++w;
00177
00178 while (size > 0) {
00179 if (size <= num_bits_per_word) {
00180
00181 return _array[w].has_all_of(0, size);
00182 }
00183
00184
00185 if (!_array[w].is_all_on()) {
00186 return false;
00187 }
00188 size -= num_bits_per_word;
00189 ++w;
00190
00191 if (w >= get_num_words()) {
00192
00193 return (_highest_bits != 0);
00194 }
00195 }
00196
00197 return true;
00198 }
00199
00200
00201
00202
00203
00204
00205 void BitArray::
00206 set_range(int low_bit, int size) {
00207 int w = low_bit / num_bits_per_word;
00208 int b = low_bit % num_bits_per_word;
00209
00210 if (w >= get_num_words() && _highest_bits) {
00211
00212 return;
00213 }
00214 if (b + size <= num_bits_per_word) {
00215
00216 ensure_has_word(w);
00217 _array[w].set_range(b, size);
00218 normalize();
00219 return;
00220 }
00221
00222 ensure_has_word(w);
00223 int num_high_bits = num_bits_per_word - b;
00224 _array[w].set_range(b, num_high_bits);
00225 size -= num_high_bits;
00226 ++w;
00227
00228 while (size > 0) {
00229 if (size <= num_bits_per_word) {
00230
00231 ensure_has_word(w);
00232 _array[w].set_range(0, size);
00233 normalize();
00234 return;
00235 }
00236
00237
00238 ensure_has_word(w);
00239 _array[w] = MaskType::all_on();
00240 size -= num_bits_per_word;
00241 ++w;
00242
00243 if (w >= get_num_words() && _highest_bits) {
00244
00245 normalize();
00246 return;
00247 }
00248 }
00249 normalize();
00250 }
00251
00252
00253
00254
00255
00256
00257 void BitArray::
00258 clear_range(int low_bit, int size) {
00259 int w = low_bit / num_bits_per_word;
00260 int b = low_bit % num_bits_per_word;
00261
00262 if (w >= get_num_words() && !_highest_bits) {
00263
00264 return;
00265 }
00266 if (b + size <= num_bits_per_word) {
00267
00268 ensure_has_word(w);
00269 _array[w].clear_range(b, size);
00270 normalize();
00271 return;
00272 }
00273
00274 ensure_has_word(w);
00275 int num_high_bits = num_bits_per_word - b;
00276 _array[w].clear_range(b, num_high_bits);
00277 size -= num_high_bits;
00278 ++w;
00279
00280 while (size > 0) {
00281 if (size <= num_bits_per_word) {
00282
00283 ensure_has_word(w);
00284 _array[w].clear_range(0, size);
00285 normalize();
00286 return;
00287 }
00288
00289
00290 ensure_has_word(w);
00291 _array[w] = MaskType::all_off();
00292 size -= num_bits_per_word;
00293 ++w;
00294
00295 if (w >= get_num_words() && !_highest_bits) {
00296
00297 normalize();
00298 return;
00299 }
00300 }
00301 normalize();
00302 }
00303
00304
00305
00306
00307
00308
00309
00310
00311 int BitArray::
00312 get_num_on_bits() const {
00313 if (_highest_bits) {
00314 return -1;
00315 }
00316
00317 int result = 0;
00318 Array::const_iterator ai;
00319 for (ai = _array.begin(); ai != _array.end(); ++ai) {
00320 result += (*ai).get_num_on_bits();
00321 }
00322 return result;
00323 }
00324
00325
00326
00327
00328
00329
00330
00331
00332 int BitArray::
00333 get_num_off_bits() const {
00334 if (!_highest_bits) {
00335 return -1;
00336 }
00337
00338 int result = 0;
00339 Array::const_iterator ai;
00340 for (ai = _array.begin(); ai != _array.end(); ++ai) {
00341 result += (*ai).get_num_off_bits();
00342 }
00343 return result;
00344 }
00345
00346
00347
00348
00349
00350
00351
00352 int BitArray::
00353 get_lowest_on_bit() const {
00354 int num_words = get_num_words();
00355 for (int w = 0; w < num_words; ++w) {
00356 int b = _array[w].get_lowest_on_bit();
00357 if (b != -1) {
00358 return w * num_bits_per_word + b;
00359 }
00360 }
00361 if (_highest_bits) {
00362 return num_words * num_bits_per_word;
00363 } else {
00364 return -1;
00365 }
00366 }
00367
00368
00369
00370
00371
00372
00373
00374 int BitArray::
00375 get_lowest_off_bit() const {
00376 int num_words = get_num_words();
00377 for (int w = 0; w < num_words; ++w) {
00378 int b = _array[w].get_lowest_off_bit();
00379 if (b != -1) {
00380 return w * num_bits_per_word + b;
00381 }
00382 }
00383 if (!_highest_bits) {
00384 return num_words * num_bits_per_word;
00385 } else {
00386 return -1;
00387 }
00388 }
00389
00390
00391
00392
00393
00394
00395
00396
00397 int BitArray::
00398 get_highest_on_bit() const {
00399 if (_highest_bits) {
00400 return -1;
00401 }
00402 int num_words = get_num_words();
00403 for (int w = num_words - 1; w >= 0; --w) {
00404 int b = _array[w].get_highest_on_bit();
00405 if (b != -1) {
00406 return w * num_bits_per_word + b;
00407 }
00408 }
00409 return -1;
00410 }
00411
00412
00413
00414
00415
00416
00417
00418
00419 int BitArray::
00420 get_highest_off_bit() const {
00421 if (!_highest_bits) {
00422 return -1;
00423 }
00424 int num_words = get_num_words();
00425 for (int w = num_words - 1; w >= 0; --w) {
00426 int b = _array[w].get_highest_off_bit();
00427 if (b != -1) {
00428 return w * num_bits_per_word + b;
00429 }
00430 }
00431 return -1;
00432 }
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445 int BitArray::
00446 get_next_higher_different_bit(int low_bit) const {
00447 int w = low_bit / num_bits_per_word;
00448 int b = low_bit % num_bits_per_word;
00449 int num_words = get_num_words();
00450 if (w >= num_words) {
00451 return low_bit;
00452 }
00453 int b2 = _array[w].get_next_higher_different_bit(b);
00454 if (b2 != b && b2 < num_bits_per_word) {
00455
00456 return w * num_bits_per_word + b2;
00457 }
00458
00459 MaskType skip_next = (_array[w].get_bit(b)) ? MaskType::all_on() : MaskType::all_off();
00460 int w2 = w;
00461 ++w2;
00462 while (w2 < num_words && _array[w2] == skip_next) {
00463 ++w2;
00464 }
00465 if (w2 >= num_words) {
00466
00467 int is_on = _array[w].get_bit(b);
00468 return is_on ? (num_words * num_bits_per_word) : low_bit;
00469 }
00470 if (_array[w2].get_bit(0) != _array[w].get_bit(b)) {
00471
00472 return w2 * num_bits_per_word;
00473 }
00474
00475 b2 = _array[w2].get_next_higher_different_bit(0);
00476 return w2 * num_bits_per_word + b2;
00477 }
00478
00479
00480
00481
00482
00483
00484
00485 void BitArray::
00486 invert_in_place() {
00487 _highest_bits = !_highest_bits;
00488 copy_on_write();
00489 Array::iterator ai;
00490 for (ai = _array.begin(); ai != _array.end(); ++ai) {
00491 (*ai) = ~(*ai);
00492 }
00493 }
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504 bool BitArray::
00505 has_bits_in_common(const BitArray &other) const {
00506 if (_highest_bits && other._highest_bits) {
00507
00508 return true;
00509 }
00510
00511 size_t num_common_words = min(_array.size(), other._array.size());
00512
00513
00514 if (other._array.size() < _array.size() && other._highest_bits) {
00515
00516
00517
00518 Array::const_iterator ai;
00519 for (ai = _array.begin() + other._array.size();
00520 ai != _array.end();
00521 ++ai) {
00522 if (!(*ai).is_zero()) {
00523 return true;
00524 }
00525 }
00526
00527 } else if (_array.size() < other._array.size() && _highest_bits) {
00528
00529
00530
00531 Array::const_iterator ai;
00532 for (ai = other._array.begin() + _array.size();
00533 ai != other._array.end();
00534 ++ai) {
00535 if (!(*ai).is_zero()) {
00536 return true;
00537 }
00538 }
00539 }
00540
00541
00542 for (size_t i = 0; i < num_common_words; ++i) {
00543 if (!(_array[i] & other._array[i]).is_zero()) {
00544 return true;
00545 }
00546 }
00547
00548
00549 return false;
00550 }
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560 void BitArray::
00561 output(ostream &out) const {
00562 output_hex(out);
00563 }
00564
00565
00566
00567
00568
00569
00570
00571 void BitArray::
00572 output_binary(ostream &out, int spaces_every) const {
00573 if (_highest_bits) {
00574 out << "...1 ";
00575 }
00576 int num_bits = max(get_num_bits(), spaces_every);
00577 for (int i = num_bits - 1; i >= 0; i--) {
00578 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
00579 out << ' ';
00580 }
00581 out << (get_bit(i) ? '1' : '0');
00582 }
00583 }
00584
00585
00586
00587
00588
00589
00590
00591 void BitArray::
00592 output_hex(ostream &out, int spaces_every) const {
00593 int num_bits = get_num_bits();
00594 int num_digits = max((num_bits + 3) / 4, spaces_every);
00595
00596 if (_highest_bits) {
00597 out << "...f ";
00598 }
00599
00600 for (int i = num_digits - 1; i >= 0; i--) {
00601 WordType digit = extract(i * 4, 4);
00602 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
00603 out << ' ';
00604 }
00605 if (digit > 9) {
00606 out << (char)(digit - 10 + 'a');
00607 } else {
00608 out << (char)(digit + '0');
00609 }
00610 }
00611 }
00612
00613
00614
00615
00616
00617
00618
00619 void BitArray::
00620 write(ostream &out, int indent_level) const {
00621 indent(out, indent_level) << *this << "\n";
00622 }
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632 int BitArray::
00633 compare_to(const BitArray &other) const {
00634 if (_highest_bits != other._highest_bits) {
00635 return _highest_bits ? 1 : -1;
00636 }
00637
00638 int num_words = max(get_num_words(), other.get_num_words());
00639
00640
00641 for (int i = num_words - 1; i >= 0; --i) {
00642 int compare = get_word(i).compare_to(other.get_word(i));
00643 if (compare != 0) {
00644 return compare;
00645 }
00646 }
00647
00648 return 0;
00649 }
00650
00651
00652
00653
00654
00655
00656 void BitArray::
00657 operator &= (const BitArray &other) {
00658 size_t num_common_words = min(_array.size(), other._array.size());
00659
00660 copy_on_write();
00661
00662
00663 if (other._array.size() < _array.size() && !other._highest_bits) {
00664
00665
00666
00667 _array.erase(_array.begin() + other._array.size(), _array.end());
00668
00669 } else if (_array.size() < other._array.size() && _highest_bits) {
00670
00671
00672
00673 Array::const_iterator ai;
00674 for (ai = other._array.begin() + _array.size();
00675 ai != other._array.end();
00676 ++ai) {
00677 _array.push_back(*ai);
00678 }
00679 }
00680
00681
00682 for (size_t i = 0; i < num_common_words; ++i) {
00683 _array[i] &= other._array[i];
00684 }
00685
00686 _highest_bits &= other._highest_bits;
00687 normalize();
00688 }
00689
00690
00691
00692
00693
00694
00695 void BitArray::
00696 operator |= (const BitArray &other) {
00697 size_t num_common_words = min(_array.size(), other._array.size());
00698
00699 copy_on_write();
00700
00701
00702 if (other._array.size() < _array.size() && other._highest_bits) {
00703
00704
00705
00706 _array.erase(_array.begin() + other._array.size(), _array.end());
00707
00708 } else if (_array.size() < other._array.size() && !_highest_bits) {
00709
00710
00711
00712 Array::const_iterator ai;
00713 for (ai = other._array.begin() + _array.size();
00714 ai != other._array.end();
00715 ++ai) {
00716 _array.push_back(*ai);
00717 }
00718 }
00719
00720
00721 for (size_t i = 0; i < num_common_words; ++i) {
00722 _array[i] |= other._array[i];
00723 }
00724
00725 _highest_bits |= other._highest_bits;
00726 normalize();
00727 }
00728
00729
00730
00731
00732
00733
00734 void BitArray::
00735 operator ^= (const BitArray &other) {
00736 size_t num_common_words = min(_array.size(), other._array.size());
00737
00738 copy_on_write();
00739
00740
00741 if (other._array.size() < _array.size() && other._highest_bits) {
00742
00743
00744
00745 Array::iterator ai;
00746 for (ai = _array.begin() + other._array.size();
00747 ai != _array.end();
00748 ++ai) {
00749 (*ai).invert_in_place();
00750 }
00751
00752 } else if (_array.size() < other._array.size()) {
00753 if (!_highest_bits) {
00754
00755
00756
00757 Array::const_iterator ai;
00758 for (ai = other._array.begin() + _array.size();
00759 ai != other._array.end();
00760 ++ai) {
00761 _array.push_back(*ai);
00762 }
00763 } else {
00764
00765
00766
00767 Array::const_iterator ai;
00768 for (ai = other._array.begin() + _array.size();
00769 ai != other._array.end();
00770 ++ai) {
00771 _array.push_back(~(*ai));
00772 }
00773 }
00774 }
00775
00776
00777 for (size_t i = 0; i < num_common_words; ++i) {
00778 _array[i] ^= other._array[i];
00779 }
00780
00781 _highest_bits ^= other._highest_bits;
00782 normalize();
00783 }
00784
00785
00786
00787
00788
00789
00790
00791
00792 void BitArray::
00793 operator <<= (int shift) {
00794 if (shift == 0 || _array.empty()) {
00795 return;
00796 }
00797 if (shift < 0) {
00798 operator >>= (-shift);
00799 return;
00800 }
00801
00802 int w = shift / num_bits_per_word;
00803 int b = shift % num_bits_per_word;
00804
00805 if (b == 0) {
00806
00807 Array new_array;
00808 new_array.reserve(_array.size() + w);
00809 for (int i = 0; i < w; ++i) {
00810 new_array.push_back(MaskType::all_off());
00811 }
00812 Array::const_iterator ai;
00813 for (ai = _array.begin(); ai != _array.end(); ++ai) {
00814 new_array.push_back(*ai);
00815 }
00816 _array = new_array;
00817
00818 } else {
00819
00820 Array new_array;
00821 new_array.reserve(_array.size() + w + 1);
00822 for (int i = 0; i < w; ++i) {
00823 new_array.push_back(MaskType::all_off());
00824 }
00825
00826 int downshift_count = num_bits_per_word - b;
00827 MaskType lower_mask = MaskType::lower_on(downshift_count);
00828 MaskType upper_mask = ~lower_mask;
00829
00830 Array::const_iterator ai = _array.begin();
00831 nassertv(ai != _array.end());
00832 MaskType next_bits = ((*ai) & upper_mask) >> downshift_count;
00833 new_array.push_back(((*ai) & lower_mask) << b);
00834 ++ai;
00835 while (ai != _array.end()) {
00836 new_array.push_back((((*ai) & lower_mask) << b) | next_bits);
00837 next_bits = ((*ai) & upper_mask) >> downshift_count;
00838 ++ai;
00839 }
00840
00841
00842 if (_highest_bits) {
00843 next_bits |= ~MaskType::lower_on(b);
00844 }
00845 new_array.push_back(next_bits);
00846 _array = new_array;
00847 }
00848
00849 normalize();
00850 }
00851
00852
00853
00854
00855
00856
00857
00858
00859
00860 void BitArray::
00861 operator >>= (int shift) {
00862 if (shift == 0 || _array.empty()) {
00863 return;
00864 }
00865 if (shift < 0) {
00866 operator <<= (-shift);
00867 return;
00868 }
00869
00870 int w = shift / num_bits_per_word;
00871 int b = shift % num_bits_per_word;
00872
00873 if (w >= (int)_array.size()) {
00874
00875 _array.clear();
00876 return;
00877 }
00878
00879 if (b == 0) {
00880
00881 Array new_array;
00882 new_array.reserve(_array.size() - w);
00883 Array::const_iterator ai;
00884 for (ai = _array.begin() + w; ai != _array.end(); ++ai) {
00885 new_array.push_back(*ai);
00886 }
00887 _array = new_array;
00888
00889 } else {
00890
00891 Array new_array;
00892 new_array.reserve(_array.size() - w);
00893
00894 int upshift_count = num_bits_per_word - b;
00895 MaskType lower_mask = MaskType::lower_on(b);
00896 MaskType upper_mask = ~lower_mask;
00897
00898 Array::const_iterator ai = _array.begin() + w;
00899 nassertv(ai < _array.end());
00900 MaskType next_bits = ((*ai) & upper_mask) >> b;
00901
00902 ++ai;
00903 while (ai != _array.end()) {
00904 new_array.push_back((((*ai) & lower_mask) << upshift_count) | next_bits);
00905 next_bits = ((*ai) & upper_mask) >> b;
00906 ++ai;
00907 }
00908
00909
00910 if (_highest_bits) {
00911 next_bits |= ~MaskType::lower_on(upshift_count);
00912 }
00913 new_array.push_back(next_bits);
00914 _array = new_array;
00915 }
00916
00917 normalize();
00918 }
00919
00920
00921
00922
00923
00924
00925 void BitArray::
00926 generate_hash(ChecksumHashGenerator &hashgen) const {
00927 hashgen.add_int(_highest_bits);
00928 Array::const_iterator ai;
00929 for (ai = _array.begin(); ai != _array.end(); ++ai) {
00930 hashgen.add_int((*ai).get_word());
00931 }
00932 }
00933
00934
00935
00936
00937
00938
00939
00940 void BitArray::
00941 ensure_has_word(int n) {
00942 copy_on_write();
00943
00944 if (_highest_bits) {
00945 while (n >= (int)_array.size()) {
00946 _array.push_back(MaskType::all_on());
00947 }
00948 } else {
00949 while (n >= (int)_array.size()) {
00950 _array.push_back(MaskType::all_off());
00951 }
00952 }
00953 }
00954
00955
00956
00957
00958
00959
00960
00961
00962 void BitArray::
00963 normalize() {
00964 if (_highest_bits) {
00965 if (!_array.empty() && _array.back() == MaskType::all_on()) {
00966 copy_on_write();
00967 _array.pop_back();
00968 while (!_array.empty() && _array.back() == MaskType::all_on()) {
00969 _array.pop_back();
00970 }
00971 }
00972 } else {
00973 if (!_array.empty() && _array.back().is_zero()) {
00974 copy_on_write();
00975 _array.pop_back();
00976 while (!_array.empty() && _array.back().is_zero()) {
00977 _array.pop_back();
00978 }
00979 }
00980 }
00981 }
00982
00983
00984
00985
00986
00987
00988
00989 void BitArray::
00990 write_datagram(BamWriter *manager, Datagram &dg) const {
00991 dg.add_uint32(_array.size());
00992 Array::const_iterator ai;
00993 for (ai = _array.begin(); ai != _array.end(); ++ai) {
00994 dg.add_uint32((*ai).get_word());
00995 }
00996 dg.add_uint8(_highest_bits);
00997 }
00998
00999
01000
01001
01002
01003
01004
01005 void BitArray::
01006 read_datagram(DatagramIterator &scan, BamReader *manager) {
01007 size_t num_words = scan.get_uint32();
01008 _array = Array::empty_array(num_words);
01009 for (size_t i = 0; i < num_words; ++i) {
01010 _array[i] = WordType(scan.get_uint32());
01011 }
01012 _highest_bits = scan.get_uint8();
01013 }