16 #include "sparseArray.h"
18 #include "datagramIterator.h"
32 for (
int i = 0; i < num_subranges; ++i) {
58 Array::reverse_iterator ai;
59 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
60 if (!(*ai).is_zero()) {
81 Array::reverse_iterator ai;
82 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
83 if (!(*ai).is_all_on()) {
98 if ((low_bit + size - 1) / num_bits_per_word >=
get_num_words()) {
105 int w = low_bit / num_bits_per_word;
106 int b = low_bit % num_bits_per_word;
110 return (_highest_bits != 0);
112 if (b + size <= num_bits_per_word) {
114 return get_word(w).has_any_of(b, size);
117 int num_high_bits = num_bits_per_word - b;
121 size -= num_high_bits;
125 if (size <= num_bits_per_word) {
127 return _array[w].has_any_of(0, size);
134 size -= num_bits_per_word;
139 return (_highest_bits != 0);
154 if ((low_bit + size - 1) / num_bits_per_word >=
get_num_words()) {
156 if (!_highest_bits) {
161 int w = low_bit / num_bits_per_word;
162 int b = low_bit % num_bits_per_word;
166 return (_highest_bits != 0);
168 if (b + size <= num_bits_per_word) {
170 return get_word(w).has_all_of(b, size);
173 int num_high_bits = num_bits_per_word - b;
174 if (!_array[w].
has_all_of(b, num_high_bits)) {
177 size -= num_high_bits;
181 if (size <= num_bits_per_word) {
183 return _array[w].has_all_of(0, size);
190 size -= num_bits_per_word;
195 return (_highest_bits != 0);
209 int w = low_bit / num_bits_per_word;
210 int b = low_bit % num_bits_per_word;
216 if (b + size <= num_bits_per_word) {
219 _array[w].set_range(b, size);
225 int num_high_bits = num_bits_per_word - b;
226 _array[w].set_range(b, num_high_bits);
227 size -= num_high_bits;
231 if (size <= num_bits_per_word) {
234 _array[w].set_range(0, size);
241 _array[w] = MaskType::all_on();
242 size -= num_bits_per_word;
261 int w = low_bit / num_bits_per_word;
262 int b = low_bit % num_bits_per_word;
268 if (b + size <= num_bits_per_word) {
271 _array[w].clear_range(b, size);
277 int num_high_bits = num_bits_per_word - b;
278 _array[w].clear_range(b, num_high_bits);
279 size -= num_high_bits;
283 if (size <= num_bits_per_word) {
286 _array[w].clear_range(0, size);
293 _array[w] = MaskType::all_off();
294 size -= num_bits_per_word;
320 Array::const_iterator ai;
321 for (ai = _array.begin(); ai != _array.end(); ++ai) {
322 result += (*ai).get_num_on_bits();
336 if (!_highest_bits) {
341 Array::const_iterator ai;
342 for (ai = _array.begin(); ai != _array.end(); ++ai) {
343 result += (*ai).get_num_off_bits();
357 for (
int w = 0; w < num_words; ++w) {
358 int b = _array[w].get_lowest_on_bit();
360 return w * num_bits_per_word + b;
364 return num_words * num_bits_per_word;
379 for (
int w = 0; w < num_words; ++w) {
380 int b = _array[w].get_lowest_off_bit();
382 return w * num_bits_per_word + b;
385 if (!_highest_bits) {
386 return num_words * num_bits_per_word;
405 for (
int w = num_words - 1; w >= 0; --w) {
406 int b = _array[w].get_highest_on_bit();
408 return w * num_bits_per_word + b;
423 if (!_highest_bits) {
427 for (
int w = num_words - 1; w >= 0; --w) {
428 int b = _array[w].get_highest_off_bit();
430 return w * num_bits_per_word + b;
449 int w = low_bit / num_bits_per_word;
450 int b = low_bit % num_bits_per_word;
452 if (w >= num_words) {
455 int b2 = _array[w].get_next_higher_different_bit(b);
456 if (b2 != b && b2 < num_bits_per_word) {
458 return w * num_bits_per_word + b2;
461 MaskType skip_next = (_array[w].get_bit(b)) ? MaskType::all_on() : MaskType::all_off();
464 while (w2 < num_words && _array[w2] == skip_next) {
467 if (w2 >= num_words) {
469 int is_on = _array[w].get_bit(b);
470 return is_on ? (num_words * num_bits_per_word) : low_bit;
472 if (_array[w2].
get_bit(0) != _array[w].get_bit(b)) {
474 return w2 * num_bits_per_word;
477 b2 = _array[w2].get_next_higher_different_bit(0);
478 return w2 * num_bits_per_word + b2;
489 _highest_bits = !_highest_bits;
492 for (ai = _array.begin(); ai != _array.end(); ++ai) {
508 if (_highest_bits && other._highest_bits) {
513 size_t num_common_words = min(_array.size(), other._array.size());
516 if (other._array.size() < _array.size() && other._highest_bits) {
520 Array::const_iterator ai;
521 for (ai = _array.begin() + other._array.size();
524 if (!(*ai).is_zero()) {
529 }
else if (_array.size() < other._array.size() && _highest_bits) {
533 Array::const_iterator ai;
534 for (ai = other._array.begin() + _array.size();
535 ai != other._array.end();
537 if (!(*ai).is_zero()) {
544 for (
size_t i = 0; i < num_common_words; ++i) {
545 if (!(_array[i] & other._array[i]).is_zero()) {
579 for (
int i = num_bits - 1; i >= 0; i--) {
580 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
583 out << (
get_bit(i) ?
'1' :
'0');
596 int num_digits = max((num_bits + 3) / 4, spaces_every);
602 for (
int i = num_digits - 1; i >= 0; i--) {
603 WordType digit =
extract(i * 4, 4);
604 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
608 out << (char)(digit - 10 +
'a');
610 out << (char)(digit +
'0');
622 write(ostream &out,
int indent_level)
const {
623 indent(out, indent_level) << *
this <<
"\n";
636 if (_highest_bits != other._highest_bits) {
637 return _highest_bits ? 1 : -1;
643 for (
int i = num_words - 1; i >= 0; --i) {
659 operator &= (
const BitArray &other) {
660 size_t num_common_words = min(_array.size(), other._array.size());
665 if (other._array.size() < _array.size() && !other._highest_bits) {
669 _array.erase(_array.begin() + other._array.size(), _array.end());
671 }
else if (_array.size() < other._array.size() && _highest_bits) {
675 Array::const_iterator ai;
676 for (ai = other._array.begin() + _array.size();
677 ai != other._array.end();
679 _array.push_back(*ai);
684 for (
size_t i = 0; i < num_common_words; ++i) {
685 _array[i] &= other._array[i];
688 _highest_bits &= other._highest_bits;
698 operator |= (
const BitArray &other) {
699 size_t num_common_words = min(_array.size(), other._array.size());
704 if (other._array.size() < _array.size() && other._highest_bits) {
708 _array.erase(_array.begin() + other._array.size(), _array.end());
710 }
else if (_array.size() < other._array.size() && !_highest_bits) {
714 Array::const_iterator ai;
715 for (ai = other._array.begin() + _array.size();
716 ai != other._array.end();
718 _array.push_back(*ai);
723 for (
size_t i = 0; i < num_common_words; ++i) {
724 _array[i] |= other._array[i];
727 _highest_bits |= other._highest_bits;
737 operator ^= (
const BitArray &other) {
738 size_t num_common_words = min(_array.size(), other._array.size());
743 if (other._array.size() < _array.size() && other._highest_bits) {
748 for (ai = _array.begin() + other._array.size();
751 (*ai).invert_in_place();
754 }
else if (_array.size() < other._array.size()) {
755 if (!_highest_bits) {
759 Array::const_iterator ai;
760 for (ai = other._array.begin() + _array.size();
761 ai != other._array.end();
763 _array.push_back(*ai);
769 Array::const_iterator ai;
770 for (ai = other._array.begin() + _array.size();
771 ai != other._array.end();
773 _array.push_back(~(*ai));
779 for (
size_t i = 0; i < num_common_words; ++i) {
780 _array[i] ^= other._array[i];
783 _highest_bits ^= other._highest_bits;
796 if (shift == 0 || _array.empty()) {
804 int w = shift / num_bits_per_word;
805 int b = shift % num_bits_per_word;
810 new_array.reserve(_array.size() + w);
811 for (
int i = 0; i < w; ++i) {
812 new_array.push_back(MaskType::all_off());
814 Array::const_iterator ai;
815 for (ai = _array.begin(); ai != _array.end(); ++ai) {
816 new_array.push_back(*ai);
823 new_array.reserve(_array.size() + w + 1);
824 for (
int i = 0; i < w; ++i) {
825 new_array.push_back(MaskType::all_off());
828 int downshift_count = num_bits_per_word - b;
829 MaskType lower_mask = MaskType::lower_on(downshift_count);
830 MaskType upper_mask = ~lower_mask;
832 Array::const_iterator ai = _array.begin();
833 nassertv(ai != _array.end());
834 MaskType next_bits = ((*ai) & upper_mask) >> downshift_count;
835 new_array.push_back(((*ai) & lower_mask) << b);
837 while (ai != _array.end()) {
838 new_array.push_back((((*ai) & lower_mask) << b) | next_bits);
839 next_bits = ((*ai) & upper_mask) >> downshift_count;
847 new_array.push_back(next_bits);
864 if (shift == 0 || _array.empty()) {
872 int w = shift / num_bits_per_word;
873 int b = shift % num_bits_per_word;
875 if (w >= (
int)_array.size()) {
884 new_array.reserve(_array.size() - w);
885 Array::const_iterator ai;
886 for (ai = _array.begin() + w; ai != _array.end(); ++ai) {
887 new_array.push_back(*ai);
894 new_array.reserve(_array.size() - w);
896 int upshift_count = num_bits_per_word - b;
897 MaskType lower_mask = MaskType::lower_on(b);
898 MaskType upper_mask = ~lower_mask;
900 Array::const_iterator ai = _array.begin() + w;
901 nassertv(ai < _array.end());
902 MaskType next_bits = ((*ai) & upper_mask) >> b;
905 while (ai != _array.end()) {
906 new_array.push_back((((*ai) & lower_mask) << upshift_count) | next_bits);
907 next_bits = ((*ai) & upper_mask) >> b;
913 next_bits |= ~MaskType
::lower_on(upshift_count);
915 new_array.push_back(next_bits);
929 hashgen.
add_int(_highest_bits);
930 Array::const_iterator ai;
931 for (ai = _array.begin(); ai != _array.end(); ++ai) {
932 hashgen.
add_int((*ai).get_word());
943 ensure_has_word(
int n) {
947 while (n >= (
int)_array.size()) {
948 _array.push_back(MaskType::all_on());
951 while (n >= (
int)_array.size()) {
952 _array.push_back(MaskType::all_off());
967 if (!_array.empty() && _array.back() == MaskType::all_on()) {
970 while (!_array.empty() && _array.back() == MaskType::all_on()) {
975 if (!_array.empty() && _array.back().is_zero()) {
978 while (!_array.empty() && _array.back().is_zero()) {
994 Array::const_iterator ai;
995 for (ai = _array.begin(); ai != _array.end(); ++ai) {
1010 _array = Array::empty_array(num_words);
1011 for (
size_t i = 0; i < num_words; ++i) {
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
void invert_in_place()
Inverts all the bits in the BitArray.
This class records a set of integers, where each integer is either present or not present in the set...
void add_uint8(PN_uint8 value)
Adds an unsigned 8-bit integer to the datagram.
This is a specific kind of HashGenerator that simply adds up all of the ints.
int compare_to(const BitArray &other) const
Returns a number less than zero if this BitArray sorts before the indicated other BitArray...
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
void generate_hash(ChecksumHashGenerator &hashgen) const
Adds the bitmask to the indicated hash generator.
void operator<<=(int shift)
Logical left shift.
MaskType get_word(int n) const
Returns the nth word in the array.
int get_highest_off_bit() const
Returns the index of the highest 0 bit in the array.
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
PN_uint8 get_uint8()
Extracts an unsigned 8-bit integer.
int get_lowest_on_bit() const
Returns the index of the lowest 1 bit in the array.
PN_uint32 get_uint32()
Extracts an unsigned 32-bit integer.
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...
void operator>>=(int shift)
Logical right shift.
int get_lowest_off_bit() const
Returns the index of the lowest 0 bit in the array.
A dynamic array with an unlimited number of bits.
int get_subrange_end(int n) const
Returns the last numeric element, plus one, in the nth subrange.
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...
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
bool is_inverse() const
If this is true, the SparseArray is actually defined as a list of subranges of integers that are *not...
int get_highest_on_bit() const
Returns the index of the highest 1 bit in the array.
void write_datagram(BamWriter *manager, Datagram &dg) const
Writes the contents of this object to the datagram for shipping out to a Bam file.
void output(ostream &out) const
Writes the BitArray out as a hex number.
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
static BitArray lower_on(int on_bits)
Returns a BitArray whose lower on_bits bits are on.
void add_int(long num)
Adds another integer to the hash so far.
void read_datagram(DatagramIterator &scan, BamReader *manager)
Reads the object that was previously written to a Bam file.
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_num_subranges() const
Returns the number of separate subranges stored in the SparseArray.
int get_num_bits() const
Returns the current number of possibly different bits in this array.
void add_uint32(PN_uint32 value)
Adds an unsigned 32-bit integer to the datagram.
WordType extract(int low_bit, int size) const
Returns a word that represents only the indicated range of bits within this BitArray, shifted to the least-significant position.
int get_subrange_begin(int n) const
Returns the first numeric element in the nth subrange.
A class to retrieve the individual data elements previously stored in a Datagram. ...
int get_num_on_bits() const
Returns the number of bits that are set to 1 in the array.
void write(ostream &out, int indent_level=0) const
Writes the BitArray out as a binary or a hex number, according to the number of bits.
void output_binary(ostream &out, int spaces_every=4) const
Writes the BitArray out as a binary number, with spaces every four bits.
TypeHandle is the identifier used to differentiate C++ class types.
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
int get_num_off_bits() const
Returns the number of bits that are set to 0 in the array.
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
int get_num_words() const
Returns the number of possibly-unique words stored in the array.
void output_hex(ostream &out, int spaces_every=4) const
Writes the BitArray out as a hexadecimal number, with spaces every four digits.
bool has_any_of(int low_bit, int size) const
Returns true if any bit in the indicated range is set, false otherwise.
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.