33 for (
int i = 0; i < num_subranges; ++i) {
56 Array::reverse_iterator ai;
57 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
58 if (!(*ai).is_zero()) {
76 Array::reverse_iterator ai;
77 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
78 if (!(*ai).is_all_on()) {
97 int w = low_bit / num_bits_per_word;
98 int b = low_bit % num_bits_per_word;
102 return (_highest_bits != 0);
104 if (b + size <= num_bits_per_word) {
106 return get_word(w).has_any_of(b, size);
109 int num_high_bits = num_bits_per_word - b;
113 size -= num_high_bits;
119 return (_highest_bits != 0);
122 if (size <= num_bits_per_word) {
124 return _array[w].has_any_of(0, size);
131 size -= num_bits_per_word;
145 if (!_highest_bits) {
150 int w = low_bit / num_bits_per_word;
151 int b = low_bit % num_bits_per_word;
155 return (_highest_bits != 0);
157 if (b + size <= num_bits_per_word) {
159 return get_word(w).has_all_of(b, size);
162 int num_high_bits = num_bits_per_word - b;
163 if (!_array[w].
has_all_of(b, num_high_bits)) {
166 size -= num_high_bits;
170 if (size <= num_bits_per_word) {
172 return _array[w].has_all_of(0, size);
179 size -= num_bits_per_word;
184 return (_highest_bits != 0);
196 int w = low_bit / num_bits_per_word;
197 int b = low_bit % num_bits_per_word;
203 if (b + size <= num_bits_per_word) {
206 _array[w].set_range(b, size);
212 int num_high_bits = num_bits_per_word - b;
213 _array[w].set_range(b, num_high_bits);
214 size -= num_high_bits;
218 if (size <= num_bits_per_word) {
221 _array[w].set_range(0, size);
228 _array[w] = MaskType::all_on();
229 size -= num_bits_per_word;
246 int w = low_bit / num_bits_per_word;
247 int b = low_bit % num_bits_per_word;
253 if (b + size <= num_bits_per_word) {
256 _array[w].clear_range(b, size);
262 int num_high_bits = num_bits_per_word - b;
263 _array[w].clear_range(b, num_high_bits);
264 size -= num_high_bits;
268 if (size <= num_bits_per_word) {
271 _array[w].clear_range(0, size);
278 _array[w] = MaskType::all_off();
279 size -= num_bits_per_word;
302 Array::const_iterator ai;
303 for (ai = _array.begin(); ai != _array.end(); ++ai) {
304 result += (*ai).get_num_on_bits();
315 if (!_highest_bits) {
320 Array::const_iterator ai;
321 for (ai = _array.begin(); ai != _array.end(); ++ai) {
322 result += (*ai).get_num_off_bits();
334 for (
int w = 0; w < num_words; ++w) {
335 int b = _array[w].get_lowest_on_bit();
337 return w * num_bits_per_word + b;
341 return num_words * num_bits_per_word;
354 for (
int w = 0; w < num_words; ++w) {
355 int b = _array[w].get_lowest_off_bit();
357 return w * num_bits_per_word + b;
360 if (!_highest_bits) {
361 return num_words * num_bits_per_word;
377 for (
int w = num_words - 1; w >= 0; --w) {
378 int b = _array[w].get_highest_on_bit();
380 return w * num_bits_per_word + b;
392 if (!_highest_bits) {
396 for (
int w = num_words - 1; w >= 0; --w) {
397 int b = _array[w].get_highest_off_bit();
399 return w * num_bits_per_word + b;
414 int w = low_bit / num_bits_per_word;
415 int b = low_bit % num_bits_per_word;
417 if (w >= num_words) {
420 int b2 = _array[w].get_next_higher_different_bit(b);
421 if (b2 != b && b2 < num_bits_per_word) {
423 return w * num_bits_per_word + b2;
426 MaskType skip_next = (_array[w].get_bit(b)) ? MaskType::all_on() : MaskType::all_off();
429 while (w2 < num_words && _array[w2] == skip_next) {
432 if (w2 >= num_words) {
434 int is_on = _array[w].get_bit(b);
435 return is_on ? (num_words * num_bits_per_word) : low_bit;
437 if (_array[w2].
get_bit(0) != _array[w].get_bit(b)) {
439 return w2 * num_bits_per_word;
442 b2 = _array[w2].get_next_higher_different_bit(0);
443 return w2 * num_bits_per_word + b2;
452 _highest_bits = !_highest_bits;
455 for (ai = _array.begin(); ai != _array.end(); ++ai) {
468 if (_highest_bits && other._highest_bits) {
473 size_t num_common_words = min(_array.size(), other._array.size());
476 if (other._array.size() < _array.size() && other._highest_bits) {
480 Array::const_iterator ai;
481 for (ai = _array.begin() + other._array.size();
484 if (!(*ai).is_zero()) {
489 }
else if (_array.size() < other._array.size() && _highest_bits) {
493 Array::const_iterator ai;
494 for (ai = other._array.begin() + _array.size();
495 ai != other._array.end();
497 if (!(*ai).is_zero()) {
504 for (
size_t i = 0; i < num_common_words; ++i) {
505 if (!(_array[i] & other._array[i]).is_zero()) {
520 output(ostream &out)
const {
533 for (
int i = num_bits - 1; i >= 0; i--) {
534 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
537 out << (
get_bit(i) ?
'1' :
'0');
546 output_hex(ostream &out,
int spaces_every)
const {
548 int num_digits = max((num_bits + 3) / 4, spaces_every);
554 for (
int i = num_digits - 1; i >= 0; i--) {
555 WordType digit =
extract(i * 4, 4);
556 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
560 out << (char)(digit - 10 +
'a');
562 out << (char)(digit +
'0');
572 write(ostream &out,
int indent_level)
const {
573 indent(out, indent_level) << *
this <<
"\n";
583 if (_highest_bits != other._highest_bits) {
584 return _highest_bits ? 1 : -1;
590 for (
int i = num_words - 1; i >= 0; --i) {
604 operator &= (
const BitArray &other) {
605 size_t num_common_words = min(_array.size(), other._array.size());
610 if (other._array.size() < _array.size() && !other._highest_bits) {
613 _array.erase(_array.begin() + other._array.size(), _array.end());
615 }
else if (_array.size() < other._array.size() && _highest_bits) {
618 Array::const_iterator ai;
619 for (ai = other._array.begin() + _array.size();
620 ai != other._array.end();
622 _array.push_back(*ai);
627 for (
size_t i = 0; i < num_common_words; ++i) {
628 _array[i] &= other._array[i];
631 _highest_bits &= other._highest_bits;
639 operator |= (
const BitArray &other) {
640 size_t num_common_words = min(_array.size(), other._array.size());
645 if (other._array.size() < _array.size() && other._highest_bits) {
649 _array.erase(_array.begin() + other._array.size(), _array.end());
651 }
else if (_array.size() < other._array.size() && !_highest_bits) {
654 Array::const_iterator ai;
655 for (ai = other._array.begin() + _array.size();
656 ai != other._array.end();
658 _array.push_back(*ai);
663 for (
size_t i = 0; i < num_common_words; ++i) {
664 _array[i] |= other._array[i];
667 _highest_bits |= other._highest_bits;
675 operator ^= (
const BitArray &other) {
676 size_t num_common_words = min(_array.size(), other._array.size());
681 if (other._array.size() < _array.size() && other._highest_bits) {
685 for (ai = _array.begin() + other._array.size();
688 (*ai).invert_in_place();
691 }
else if (_array.size() < other._array.size()) {
692 if (!_highest_bits) {
695 Array::const_iterator ai;
696 for (ai = other._array.begin() + _array.size();
697 ai != other._array.end();
699 _array.push_back(*ai);
704 Array::const_iterator ai;
705 for (ai = other._array.begin() + _array.size();
706 ai != other._array.end();
708 _array.push_back(~(*ai));
714 for (
size_t i = 0; i < num_common_words; ++i) {
715 _array[i] ^= other._array[i];
718 _highest_bits ^= other._highest_bits;
728 if (shift == 0 || _array.empty()) {
736 int w = shift / num_bits_per_word;
737 int b = shift % num_bits_per_word;
742 new_array.reserve(_array.size() + w);
743 for (
int i = 0; i < w; ++i) {
744 new_array.push_back(MaskType::all_off());
746 Array::const_iterator ai;
747 for (ai = _array.begin(); ai != _array.end(); ++ai) {
748 new_array.push_back(*ai);
755 new_array.reserve(_array.size() + w + 1);
756 for (
int i = 0; i < w; ++i) {
757 new_array.push_back(MaskType::all_off());
760 int downshift_count = num_bits_per_word - b;
761 MaskType lower_mask = MaskType::lower_on(downshift_count);
762 MaskType upper_mask = ~lower_mask;
764 Array::const_iterator ai = _array.begin();
765 nassertv(ai != _array.end());
766 MaskType next_bits = ((*ai) & upper_mask) >> downshift_count;
767 new_array.push_back(((*ai) & lower_mask) << b);
769 while (ai != _array.end()) {
770 new_array.push_back((((*ai) & lower_mask) << b) | next_bits);
771 next_bits = ((*ai) & upper_mask) >> downshift_count;
779 new_array.push_back(next_bits);
793 if (shift == 0 || _array.empty()) {
801 int w = shift / num_bits_per_word;
802 int b = shift % num_bits_per_word;
804 if (w >= (
int)_array.size()) {
813 new_array.reserve(_array.size() - w);
814 Array::const_iterator ai;
815 for (ai = _array.begin() + w; ai != _array.end(); ++ai) {
816 new_array.push_back(*ai);
823 new_array.reserve(_array.size() - w);
825 int upshift_count = num_bits_per_word - b;
826 MaskType lower_mask = MaskType::lower_on(b);
827 MaskType upper_mask = ~lower_mask;
829 Array::const_iterator ai = _array.begin() + w;
830 nassertv(ai < _array.end());
831 MaskType next_bits = ((*ai) & upper_mask) >> b;
834 while (ai != _array.end()) {
835 new_array.push_back((((*ai) & lower_mask) << upshift_count) | next_bits);
836 next_bits = ((*ai) & upper_mask) >> b;
842 next_bits |= ~MaskType
::lower_on(upshift_count);
844 new_array.push_back(next_bits);
856 hashgen.
add_int(_highest_bits);
857 Array::const_iterator ai;
858 for (ai = _array.begin(); ai != _array.end(); ++ai) {
859 hashgen.
add_int((*ai).get_word());
867 ensure_has_word(
int n) {
871 while ((
size_t)n >= _array.size()) {
872 _array.push_back(MaskType::all_on());
875 while ((
size_t)n >= _array.size()) {
876 _array.push_back(MaskType::all_off());
888 if (!_array.empty() && _array.back() == MaskType::all_on()) {
891 while (!_array.empty() && _array.back() == MaskType::all_on()) {
896 if (!_array.empty() && _array.back().is_zero()) {
899 while (!_array.empty() && _array.back().is_zero()) {
913 Array::const_iterator ai;
914 for (ai = _array.begin(); ai != _array.end(); ++ai) {
926 _array = Array::empty_array(num_words);
927 for (
size_t i = 0; i < num_words; ++i) {