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()) {
912 dg.
add_uint32(_array.size() * (num_bits_per_word >> 5));
914 for (MaskType &item : _array) {
915 WordType word = item.get_word();
916 for (
size_t i = 0; i < num_bits_per_word; i += 32) {
930 size_t num_bits = num_words32 << 5;
932 _array = Array::empty_array((num_bits + num_bits_per_word - 1) / num_bits_per_word);
934 for (
size_t i = 0; i < num_bits; i += 32) {
935 int w = i / num_bits_per_word;
936 int b = i % num_bits_per_word;
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
A dynamic array with an unlimited number of bits.
void output_hex(std::ostream &out, int spaces_every=4) const
Writes the BitArray out as a hexadecimal number, with spaces every four digits.
int get_num_on_bits() const
Returns the number of bits that are set to 1 in the array.
int get_next_higher_different_bit(int low_bit) const
Returns the index of the next bit in the array, above low_bit, whose value is different that the valu...
MaskType get_word(size_t n) const
Returns the nth word in the array.
bool has_any_of(int low_bit, int size) const
Returns true if any bit in the indicated range is set, false otherwise.
int compare_to(const BitArray &other) const
Returns a number less than zero if this BitArray sorts before the indicated other BitArray,...
int get_highest_off_bit() const
Returns the index of the highest 0 bit in the array.
void generate_hash(ChecksumHashGenerator &hashgen) const
Adds the bitmask to the indicated hash generator.
void invert_in_place()
Inverts all the bits in the BitArray.
int get_lowest_on_bit() const
Returns the index of the lowest 1 bit in the array.
bool has_all_of(int low_bit, int size) const
Returns true if all bits in the indicated range are set, false otherwise.
int get_lowest_off_bit() const
Returns the index of the lowest 0 bit in the array.
void read_datagram(DatagramIterator &scan, BamReader *manager)
Reads the object that was previously written to a Bam file.
size_t get_num_bits() const
Returns the current number of possibly different bits in this array.
static BitArray lower_on(int on_bits)
Returns a BitArray whose lower on_bits bits are on.
void operator>>=(int shift)
Logical right shift.
void output(std::ostream &out) const
Writes the BitArray out as a hex number.
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
bool has_bits_in_common(const BitArray &other) const
Returns true if this BitArray has any "one" bits in common with the other one, false otherwise.
WordType extract(int low_bit, int size) const
Returns a word that represents only the indicated range of bits within this BitArray,...
void write_datagram(BamWriter *manager, Datagram &dg) const
Writes the contents of this object to the datagram for shipping out to a Bam file.
int get_num_off_bits() const
Returns the number of bits that are set to 0 in the array.
void output_binary(std::ostream &out, int spaces_every=4) const
Writes the BitArray out as a binary number, with spaces every four bits.
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
void write(std::ostream &out, int indent_level=0) const
Writes the BitArray out as a binary or a hex number, according to the number of bits.
int get_highest_on_bit() const
Returns the index of the highest 1 bit in the array.
void operator<<=(int shift)
Logical left shift.
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
size_t get_num_words() const
Returns the number of possibly-unique words stored in the array.
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
This is a specific kind of HashGenerator that simply adds up all of the ints.
void add_int(long num)
Adds another integer to the hash so far.
A class to retrieve the individual data elements previously stored in a Datagram.
uint8_t get_uint8()
Extracts an unsigned 8-bit integer.
uint32_t get_uint32()
Extracts an unsigned 32-bit integer.
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
void add_uint32(uint32_t value)
Adds an unsigned 32-bit integer to the datagram.
void add_uint8(uint8_t value)
Adds an unsigned 8-bit integer to the datagram.
This class records a set of integers, where each integer is either present or not present in the set.
int get_subrange_begin(size_t n) const
Returns the first numeric element in the nth subrange.
size_t get_num_subranges() const
Returns the number of separate subranges stored in the SparseArray.
int get_subrange_end(size_t n) const
Returns the last numeric element, plus one, in the nth subrange.
bool is_inverse() const
If this is true, the SparseArray is actually defined as a list of subranges of integers that are *not...
TypeHandle is the identifier used to differentiate C++ class types.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.