Panda3D
Loading...
Searching...
No Matches
bitArray.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file bitArray.cxx
10 * @author drose
11 * @date 2006-01-20
12 */
13
14#include "bitArray.h"
15#include "sparseArray.h"
16#include "datagram.h"
17#include "datagramIterator.h"
18
19using std::max;
20using std::min;
21using std::ostream;
22
23TypeHandle BitArray::_type_handle;
24
25/**
26 *
27 */
28BitArray::
29BitArray(const SparseArray &from) {
30 _highest_bits = 0;
31
32 int num_subranges = from.get_num_subranges();
33 for (int i = 0; i < num_subranges; ++i) {
34 int begin = from.get_subrange_begin(i);
35 int end = from.get_subrange_end(i);
36 set_range(begin, end - begin);
37 }
38
39 if (from.is_inverse()) {
41 }
42}
43
44/**
45 * Returns true if the entire bitmask is zero, false otherwise.
46 */
48is_zero() const {
49 if (_highest_bits) {
50 // If all the infinite highest bits are set, certainly the bitmask is
51 // nonzero.
52 return false;
53 }
54
55 // Start from the high end, since that's more likely to be nonzero.
56 Array::reverse_iterator ai;
57 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
58 if (!(*ai).is_zero()) {
59 return false;
60 }
61 }
62 return true;
63}
64
65/**
66 * Returns true if the entire bitmask is one, false otherwise.
67 */
69is_all_on() const {
70 if (!_highest_bits) {
71 // If all the infinite highest bits are not set, certainly the bitmask is
72 // not all on.
73 return false;
74 }
75
76 Array::reverse_iterator ai;
77 for (ai = _array.rbegin(); ai != _array.rend(); ++ai) {
78 if (!(*ai).is_all_on()) {
79 return false;
80 }
81 }
82 return true;
83}
84
85/**
86 * Returns true if any bit in the indicated range is set, false otherwise.
87 */
89has_any_of(int low_bit, int size) const {
90 if ((size_t)(low_bit + size) > get_num_bits()) {
91 // This range touches the highest bits.
92 if (_highest_bits) {
93 return true;
94 }
95 }
96
97 int w = low_bit / num_bits_per_word;
98 int b = low_bit % num_bits_per_word;
99
100 if (w >= (int)get_num_words()) {
101 // This range is entirely among the highest bits.
102 return (_highest_bits != 0);
103 }
104 if (b + size <= num_bits_per_word) {
105 // The whole thing fits within one word of the array.
106 return get_word(w).has_any_of(b, size);
107 }
108
109 int num_high_bits = num_bits_per_word - b;
110 if (_array[w].has_any_of(b, num_high_bits)) {
111 return true;
112 }
113 size -= num_high_bits;
114 ++w;
115
116 while (size > 0) {
117 if ((size_t)w >= get_num_words()) {
118 // Now we're up to the highest bits.
119 return (_highest_bits != 0);
120 }
121
122 if (size <= num_bits_per_word) {
123 // The remainder fits within one word of the array.
124 return _array[w].has_any_of(0, size);
125 }
126
127 // Keep going.
128 if (!_array[w].is_zero()) {
129 return true;
130 }
131 size -= num_bits_per_word;
132 ++w;
133 }
134
135 return false;
136}
137
138/**
139 * Returns true if all bits in the indicated range are set, false otherwise.
140 */
142has_all_of(int low_bit, int size) const {
143 if ((size_t)(low_bit + size) > get_num_bits()) {
144 // This range touches the highest bits.
145 if (!_highest_bits) {
146 return false;
147 }
148 }
149
150 int w = low_bit / num_bits_per_word;
151 int b = low_bit % num_bits_per_word;
152
153 if (w >= (int)get_num_words()) {
154 // This range is entirely among the highest bits.
155 return (_highest_bits != 0);
156 }
157 if (b + size <= num_bits_per_word) {
158 // The whole thing fits within one word of the array.
159 return get_word(w).has_all_of(b, size);
160 }
161
162 int num_high_bits = num_bits_per_word - b;
163 if (!_array[w].has_all_of(b, num_high_bits)) {
164 return false;
165 }
166 size -= num_high_bits;
167 ++w;
168
169 while (size > 0) {
170 if (size <= num_bits_per_word) {
171 // The remainder fits within one word of the array.
172 return _array[w].has_all_of(0, size);
173 }
174
175 // Keep going.
176 if (!_array[w].is_all_on()) {
177 return false;
178 }
179 size -= num_bits_per_word;
180 ++w;
181
182 if (w >= (int)get_num_words()) {
183 // Now we're up to the highest bits.
184 return (_highest_bits != 0);
185 }
186 }
187
188 return true;
189}
190
191/**
192 * Sets the indicated range of bits on.
193 */
195set_range(int low_bit, int size) {
196 int w = low_bit / num_bits_per_word;
197 int b = low_bit % num_bits_per_word;
198
199 if (w >= (int)get_num_words() && _highest_bits) {
200 // All the highest bits are already on.
201 return;
202 }
203 if (b + size <= num_bits_per_word) {
204 // The whole thing fits within one word of the array.
205 ensure_has_word(w);
206 _array[w].set_range(b, size);
207 normalize();
208 return;
209 }
210
211 ensure_has_word(w);
212 int num_high_bits = num_bits_per_word - b;
213 _array[w].set_range(b, num_high_bits);
214 size -= num_high_bits;
215 ++w;
216
217 while (size > 0) {
218 if (size <= num_bits_per_word) {
219 // The remainder fits within one word of the array.
220 ensure_has_word(w);
221 _array[w].set_range(0, size);
222 normalize();
223 return;
224 }
225
226 // Keep going.
227 ensure_has_word(w);
228 _array[w] = MaskType::all_on();
229 size -= num_bits_per_word;
230 ++w;
231
232 if (w >= (int)get_num_words() && _highest_bits) {
233 // All the highest bits are already on.
234 normalize();
235 return;
236 }
237 }
238 normalize();
239}
240
241/**
242 * Sets the indicated range of bits off.
243 */
245clear_range(int low_bit, int size) {
246 int w = low_bit / num_bits_per_word;
247 int b = low_bit % num_bits_per_word;
248
249 if (w >= (int)get_num_words() && !_highest_bits) {
250 // All the highest bits are already off.
251 return;
252 }
253 if (b + size <= num_bits_per_word) {
254 // The whole thing fits within one word of the array.
255 ensure_has_word(w);
256 _array[w].clear_range(b, size);
257 normalize();
258 return;
259 }
260
261 ensure_has_word(w);
262 int num_high_bits = num_bits_per_word - b;
263 _array[w].clear_range(b, num_high_bits);
264 size -= num_high_bits;
265 ++w;
266
267 while (size > 0) {
268 if (size <= num_bits_per_word) {
269 // The remainder fits within one word of the array.
270 ensure_has_word(w);
271 _array[w].clear_range(0, size);
272 normalize();
273 return;
274 }
275
276 // Keep going.
277 ensure_has_word(w);
278 _array[w] = MaskType::all_off();
279 size -= num_bits_per_word;
280 ++w;
281
282 if (w >= (int)get_num_words() && !_highest_bits) {
283 // All the highest bits are already off.
284 normalize();
285 return;
286 }
287 }
288 normalize();
289}
290
291/**
292 * Returns the number of bits that are set to 1 in the array. Returns -1 if
293 * there are an infinite number of 1 bits.
294 */
296get_num_on_bits() const {
297 if (_highest_bits) {
298 return -1;
299 }
300
301 int result = 0;
302 Array::const_iterator ai;
303 for (ai = _array.begin(); ai != _array.end(); ++ai) {
304 result += (*ai).get_num_on_bits();
305 }
306 return result;
307}
308
309/**
310 * Returns the number of bits that are set to 0 in the array. Returns -1 if
311 * there are an infinite number of 0 bits.
312 */
314get_num_off_bits() const {
315 if (!_highest_bits) {
316 return -1;
317 }
318
319 int result = 0;
320 Array::const_iterator ai;
321 for (ai = _array.begin(); ai != _array.end(); ++ai) {
322 result += (*ai).get_num_off_bits();
323 }
324 return result;
325}
326
327/**
328 * Returns the index of the lowest 1 bit in the array. Returns -1 if there
329 * are no 1 bits.
330 */
332get_lowest_on_bit() const {
333 int num_words = get_num_words();
334 for (int w = 0; w < num_words; ++w) {
335 int b = _array[w].get_lowest_on_bit();
336 if (b != -1) {
337 return w * num_bits_per_word + b;
338 }
339 }
340 if (_highest_bits) {
341 return num_words * num_bits_per_word;
342 } else {
343 return -1;
344 }
345}
346
347/**
348 * Returns the index of the lowest 0 bit in the array. Returns -1 if there
349 * are no 0 bits.
350 */
352get_lowest_off_bit() const {
353 int num_words = get_num_words();
354 for (int w = 0; w < num_words; ++w) {
355 int b = _array[w].get_lowest_off_bit();
356 if (b != -1) {
357 return w * num_bits_per_word + b;
358 }
359 }
360 if (!_highest_bits) {
361 return num_words * num_bits_per_word;
362 } else {
363 return -1;
364 }
365}
366
367/**
368 * Returns the index of the highest 1 bit in the array. Returns -1 if there
369 * are no 1 bits or if there an infinite number of 1 bits.
370 */
372get_highest_on_bit() const {
373 if (_highest_bits) {
374 return -1;
375 }
376 int num_words = get_num_words();
377 for (int w = num_words - 1; w >= 0; --w) {
378 int b = _array[w].get_highest_on_bit();
379 if (b != -1) {
380 return w * num_bits_per_word + b;
381 }
382 }
383 return -1;
384}
385
386/**
387 * Returns the index of the highest 0 bit in the array. Returns -1 if there
388 * are no 0 bits or if there an infinite number of 1 bits.
389 */
391get_highest_off_bit() const {
392 if (!_highest_bits) {
393 return -1;
394 }
395 int num_words = get_num_words();
396 for (int w = num_words - 1; w >= 0; --w) {
397 int b = _array[w].get_highest_off_bit();
398 if (b != -1) {
399 return w * num_bits_per_word + b;
400 }
401 }
402 return -1;
403}
404
405/**
406 * Returns the index of the next bit in the array, above low_bit, whose value
407 * is different that the value of low_bit. Returns low_bit again if all bits
408 * higher than low_bit have the same value.
409 *
410 * This can be used to quickly iterate through all of the bits in the array.
411 */
413get_next_higher_different_bit(int low_bit) const {
414 int w = low_bit / num_bits_per_word;
415 int b = low_bit % num_bits_per_word;
416 int num_words = get_num_words();
417 if (w >= num_words) {
418 return low_bit;
419 }
420 int b2 = _array[w].get_next_higher_different_bit(b);
421 if (b2 != b && b2 < num_bits_per_word) {
422 // The next higher bit is within the same word.
423 return w * num_bits_per_word + b2;
424 }
425 // Look for the next word with anything interesting.
426 MaskType skip_next = (_array[w].get_bit(b)) ? MaskType::all_on() : MaskType::all_off();
427 int w2 = w;
428 ++w2;
429 while (w2 < num_words && _array[w2] == skip_next) {
430 ++w2;
431 }
432 if (w2 >= num_words) {
433 // All bits higher are the same value.
434 int is_on = _array[w].get_bit(b);
435 return is_on ? (num_words * num_bits_per_word) : low_bit;
436 }
437 if (_array[w2].get_bit(0) != _array[w].get_bit(b)) {
438 // The first bit of word w2 is different.
439 return w2 * num_bits_per_word;
440 }
441
442 b2 = _array[w2].get_next_higher_different_bit(0);
443 return w2 * num_bits_per_word + b2;
444}
445
446/**
447 * Inverts all the bits in the BitArray. This is equivalent to array =
448 * ~array.
449 */
452 _highest_bits = !_highest_bits;
453 copy_on_write();
454 Array::iterator ai;
455 for (ai = _array.begin(); ai != _array.end(); ++ai) {
456 (*ai) = ~(*ai);
457 }
458}
459
460/**
461 * Returns true if this BitArray has any "one" bits in common with the other
462 * one, false otherwise.
463 *
464 * This is equivalent to (array & other) != 0, but may be faster.
465 */
467has_bits_in_common(const BitArray &other) const {
468 if (_highest_bits && other._highest_bits) {
469 // Yup, in fact we have an infinite number of bits in common.
470 return true;
471 }
472
473 size_t num_common_words = min(_array.size(), other._array.size());
474
475 // Consider the words that are on top of either array.
476 if (other._array.size() < _array.size() && other._highest_bits) {
477 // The other array has fewer actual words, and the top n words of the
478 // other array are all ones. We have bits in common if any of our top n
479 // words are nonzero.
480 Array::const_iterator ai;
481 for (ai = _array.begin() + other._array.size();
482 ai != _array.end();
483 ++ai) {
484 if (!(*ai).is_zero()) {
485 return true;
486 }
487 }
488
489 } else if (_array.size() < other._array.size() && _highest_bits) {
490 // This array has fewer actual words, and the top n words of this array
491 // are all ones. We have bits in common if any of the the other's top n
492 // words are nonzero.
493 Array::const_iterator ai;
494 for (ai = other._array.begin() + _array.size();
495 ai != other._array.end();
496 ++ai) {
497 if (!(*ai).is_zero()) {
498 return true;
499 }
500 }
501 }
502
503 // Consider the words that both arrays have in common.
504 for (size_t i = 0; i < num_common_words; ++i) {
505 if (!(_array[i] & other._array[i]).is_zero()) {
506 return true;
507 }
508 }
509
510 // Nope, nothing.
511 return false;
512}
513
514/**
515 * Writes the BitArray out as a hex number. For a BitArray, this is always
516 * the same as output_hex(); it's too confusing for the output format to
517 * change back and forth at runtime.
518 */
520output(ostream &out) const {
521 output_hex(out);
522}
523
524/**
525 * Writes the BitArray out as a binary number, with spaces every four bits.
526 */
528output_binary(ostream &out, int spaces_every) const {
529 if (_highest_bits) {
530 out << "...1 ";
531 }
532 int num_bits = max((int)get_num_bits(), spaces_every);
533 for (int i = num_bits - 1; i >= 0; i--) {
534 if (spaces_every != 0 && ((i % spaces_every) == spaces_every - 1)) {
535 out << ' ';
536 }
537 out << (get_bit(i) ? '1' : '0');
538 }
539}
540
541/**
542 * Writes the BitArray out as a hexadecimal number, with spaces every four
543 * digits.
544 */
546output_hex(ostream &out, int spaces_every) const {
547 int num_bits = get_num_bits();
548 int num_digits = max((num_bits + 3) / 4, spaces_every);
549
550 if (_highest_bits) {
551 out << "...f ";
552 }
553
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)) {
557 out << ' ';
558 }
559 if (digit > 9) {
560 out << (char)(digit - 10 + 'a');
561 } else {
562 out << (char)(digit + '0');
563 }
564 }
565}
566
567/**
568 * Writes the BitArray out as a binary or a hex number, according to the
569 * number of bits.
570 */
572write(ostream &out, int indent_level) const {
573 indent(out, indent_level) << *this << "\n";
574}
575
576/**
577 * Returns a number less than zero if this BitArray sorts before the indicated
578 * other BitArray, greater than zero if it sorts after, or 0 if they are
579 * equivalent. This is based on the same ordering defined by operator <.
580 */
582compare_to(const BitArray &other) const {
583 if (_highest_bits != other._highest_bits) {
584 return _highest_bits ? 1 : -1;
585 }
586
587 int num_words = max(get_num_words(), other.get_num_words());
588
589 // Compare from highest-order to lowest-order word.
590 for (int i = num_words - 1; i >= 0; --i) {
591 int compare = get_word(i).compare_to(other.get_word(i));
592 if (compare != 0) {
593 return compare;
594 }
595 }
596
597 return 0;
598}
599
600/**
601 *
602 */
603void BitArray::
604operator &= (const BitArray &other) {
605 size_t num_common_words = min(_array.size(), other._array.size());
606
607 copy_on_write();
608
609 // Consider the words that are on top of either array.
610 if (other._array.size() < _array.size() && !other._highest_bits) {
611 // The other array has fewer actual words, and the top n words of the
612 // other array are all zeroes. "mask off" the top n words of this array.
613 _array.erase(_array.begin() + other._array.size(), _array.end());
614
615 } else if (_array.size() < other._array.size() && _highest_bits) {
616 // This array has fewer actual words, and the top n words of this array
617 // are all ones. "mask on" the top n words of the other array.
618 Array::const_iterator ai;
619 for (ai = other._array.begin() + _array.size();
620 ai != other._array.end();
621 ++ai) {
622 _array.push_back(*ai);
623 }
624 }
625
626 // Consider the words that both arrays have in common.
627 for (size_t i = 0; i < num_common_words; ++i) {
628 _array[i] &= other._array[i];
629 }
630
631 _highest_bits &= other._highest_bits;
632 normalize();
633}
634
635/**
636 *
637 */
638void BitArray::
639operator |= (const BitArray &other) {
640 size_t num_common_words = min(_array.size(), other._array.size());
641
642 copy_on_write();
643
644 // Consider the words that are on top of either array.
645 if (other._array.size() < _array.size() && other._highest_bits) {
646 // The other array has fewer actual words, and the top n words of the
647 // other array are all ones. The top n words of this array become ones
648 // too (which means we can drop them out).
649 _array.erase(_array.begin() + other._array.size(), _array.end());
650
651 } else if (_array.size() < other._array.size() && !_highest_bits) {
652 // This array has fewer actual words, and the top n words of this array
653 // are all zeros. Copy in the top n words of the other array.
654 Array::const_iterator ai;
655 for (ai = other._array.begin() + _array.size();
656 ai != other._array.end();
657 ++ai) {
658 _array.push_back(*ai);
659 }
660 }
661
662 // Consider the words that both arrays have in common.
663 for (size_t i = 0; i < num_common_words; ++i) {
664 _array[i] |= other._array[i];
665 }
666
667 _highest_bits |= other._highest_bits;
668 normalize();
669}
670
671/**
672 *
673 */
674void BitArray::
675operator ^= (const BitArray &other) {
676 size_t num_common_words = min(_array.size(), other._array.size());
677
678 copy_on_write();
679
680 // Consider the words that are on top of either array.
681 if (other._array.size() < _array.size() && other._highest_bits) {
682 // The other array has fewer actual words, and the top n words of the
683 // other array are all ones. The top n words of this array get inverted.
684 Array::iterator ai;
685 for (ai = _array.begin() + other._array.size();
686 ai != _array.end();
687 ++ai) {
688 (*ai).invert_in_place();
689 }
690
691 } else if (_array.size() < other._array.size()) {
692 if (!_highest_bits) {
693 // This array has fewer actual words, and the top n words of this array
694 // are all zeros. Copy in the top n words of the other array.
695 Array::const_iterator ai;
696 for (ai = other._array.begin() + _array.size();
697 ai != other._array.end();
698 ++ai) {
699 _array.push_back(*ai);
700 }
701 } else {
702 // This array has fewer actual words, and the top n words of this array
703 // are all ones. Copy in the top n words of the other array, inverted.
704 Array::const_iterator ai;
705 for (ai = other._array.begin() + _array.size();
706 ai != other._array.end();
707 ++ai) {
708 _array.push_back(~(*ai));
709 }
710 }
711 }
712
713 // Consider the words that both arrays have in common.
714 for (size_t i = 0; i < num_common_words; ++i) {
715 _array[i] ^= other._array[i];
716 }
717
718 _highest_bits ^= other._highest_bits;
719 normalize();
720}
721
722/**
723 * Logical left shift. The rightmost bits are filled in with zeroes. Since
724 * this is an infinite bit array, none of the bits on the left are lost.
725 */
727operator <<= (int shift) {
728 if (shift == 0 || _array.empty()) {
729 return;
730 }
731 if (shift < 0) {
732 operator >>= (-shift);
733 return;
734 }
735
736 int w = shift / num_bits_per_word;
737 int b = shift % num_bits_per_word;
738
739 if (b == 0) {
740 // Easy case--word-at-a-time.
741 Array new_array;
742 new_array.reserve(_array.size() + w);
743 for (int i = 0; i < w; ++i) {
744 new_array.push_back(MaskType::all_off());
745 }
746 Array::const_iterator ai;
747 for (ai = _array.begin(); ai != _array.end(); ++ai) {
748 new_array.push_back(*ai);
749 }
750 _array = new_array;
751
752 } else {
753 // Harder case--we have to shuffle bits between words.
754 Array new_array;
755 new_array.reserve(_array.size() + w + 1);
756 for (int i = 0; i < w; ++i) {
757 new_array.push_back(MaskType::all_off());
758 }
759
760 int downshift_count = num_bits_per_word - b;
761 MaskType lower_mask = MaskType::lower_on(downshift_count);
762 MaskType upper_mask = ~lower_mask;
763
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);
768 ++ai;
769 while (ai != _array.end()) {
770 new_array.push_back((((*ai) & lower_mask) << b) | next_bits);
771 next_bits = ((*ai) & upper_mask) >> downshift_count;
772 ++ai;
773 }
774
775 // Finally, the top n bits.
776 if (_highest_bits) {
777 next_bits |= ~MaskType::lower_on(b);
778 }
779 new_array.push_back(next_bits);
780 _array = new_array;
781 }
782
783 normalize();
784}
785
786/**
787 * Logical right shift. The rightmost bits are lost. Since this is an
788 * infinite bit array, there is no question of sign extension; there is no
789 * need to synthesize bits on the left.
790 */
792operator >>= (int shift) {
793 if (shift == 0 || _array.empty()) {
794 return;
795 }
796 if (shift < 0) {
797 operator <<= (-shift);
798 return;
799 }
800
801 int w = shift / num_bits_per_word;
802 int b = shift % num_bits_per_word;
803
804 if (w >= (int)_array.size()) {
805 // Trivial case--shift to nothing.
806 _array.clear();
807 return;
808 }
809
810 if (b == 0) {
811 // Easy case--word-at-a-time.
812 Array new_array;
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);
817 }
818 _array = new_array;
819
820 } else {
821 // Harder case--we have to shuffle bits between words.
822 Array new_array;
823 new_array.reserve(_array.size() - w);
824
825 int upshift_count = num_bits_per_word - b;
826 MaskType lower_mask = MaskType::lower_on(b);
827 MaskType upper_mask = ~lower_mask;
828
829 Array::const_iterator ai = _array.begin() + w;
830 nassertv(ai < _array.end());
831 MaskType next_bits = ((*ai) & upper_mask) >> b;
832
833 ++ai;
834 while (ai != _array.end()) {
835 new_array.push_back((((*ai) & lower_mask) << upshift_count) | next_bits);
836 next_bits = ((*ai) & upper_mask) >> b;
837 ++ai;
838 }
839
840 // Finally, the top n bits.
841 if (_highest_bits) {
842 next_bits |= ~MaskType::lower_on(upshift_count);
843 }
844 new_array.push_back(next_bits);
845 _array = new_array;
846 }
847
848 normalize();
849}
850
851/**
852 * Adds the bitmask to the indicated hash generator.
853 */
855generate_hash(ChecksumHashGenerator &hashgen) const {
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());
860 }
861}
862
863/**
864 * Ensures that at least word n has been allocated into the array.
865 */
866void BitArray::
867ensure_has_word(int n) {
868 copy_on_write();
869
870 if (_highest_bits) {
871 while ((size_t)n >= _array.size()) {
872 _array.push_back(MaskType::all_on());
873 }
874 } else {
875 while ((size_t)n >= _array.size()) {
876 _array.push_back(MaskType::all_off());
877 }
878 }
879}
880
881/**
882 * Ensures that the array is the smallest array that represents this same
883 * value, by removing the topmost words that are all bits off (or on).
884 */
885void BitArray::
886normalize() {
887 if (_highest_bits) {
888 if (!_array.empty() && _array.back() == MaskType::all_on()) {
889 copy_on_write();
890 _array.pop_back();
891 while (!_array.empty() && _array.back() == MaskType::all_on()) {
892 _array.pop_back();
893 }
894 }
895 } else {
896 if (!_array.empty() && _array.back().is_zero()) {
897 copy_on_write();
898 _array.pop_back();
899 while (!_array.empty() && _array.back().is_zero()) {
900 _array.pop_back();
901 }
902 }
903 }
904}
905
906/**
907 * Writes the contents of this object to the datagram for shipping out to a
908 * Bam file.
909 */
911write_datagram(BamWriter *manager, Datagram &dg) const {
912 dg.add_uint32(_array.size() * (num_bits_per_word >> 5));
913
914 for (MaskType &item : _array) {
915 WordType word = item.get_word();
916 for (size_t i = 0; i < num_bits_per_word; i += 32) {
917 dg.add_uint32(word);
918 word >>= 32;
919 }
920 }
921 dg.add_uint8(_highest_bits);
922}
923
924/**
925 * Reads the object that was previously written to a Bam file.
926 */
929 size_t num_words32 = scan.get_uint32();
930 size_t num_bits = num_words32 << 5;
931
932 _array = Array::empty_array((num_bits + num_bits_per_word - 1) / num_bits_per_word);
933
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;
937
938 _array[w].store(scan.get_uint32(), b, 32);
939 }
940 _highest_bits = scan.get_uint8();
941}
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...
Definition bamReader.h:110
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
Definition bamWriter.h:63
A dynamic array with an unlimited number of bits.
Definition bitArray.h:40
void output_hex(std::ostream &out, int spaces_every=4) const
Writes the BitArray out as a hexadecimal number, with spaces every four digits.
Definition bitArray.cxx:546
int get_num_on_bits() const
Returns the number of bits that are set to 1 in the array.
Definition bitArray.cxx:296
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...
Definition bitArray.cxx:413
MaskType get_word(size_t n) const
Returns the nth word in the array.
Definition bitArray.I:245
bool has_any_of(int low_bit, int size) const
Returns true if any bit in the indicated range is set, false otherwise.
Definition bitArray.cxx:89
int compare_to(const BitArray &other) const
Returns a number less than zero if this BitArray sorts before the indicated other BitArray,...
Definition bitArray.cxx:582
int get_highest_off_bit() const
Returns the index of the highest 0 bit in the array.
Definition bitArray.cxx:391
void generate_hash(ChecksumHashGenerator &hashgen) const
Adds the bitmask to the indicated hash generator.
Definition bitArray.cxx:855
void invert_in_place()
Inverts all the bits in the BitArray.
Definition bitArray.cxx:451
int get_lowest_on_bit() const
Returns the index of the lowest 1 bit in the array.
Definition bitArray.cxx:332
bool has_all_of(int low_bit, int size) const
Returns true if all bits in the indicated range are set, false otherwise.
Definition bitArray.cxx:142
int get_lowest_off_bit() const
Returns the index of the lowest 0 bit in the array.
Definition bitArray.cxx:352
void read_datagram(DatagramIterator &scan, BamReader *manager)
Reads the object that was previously written to a Bam file.
Definition bitArray.cxx:928
size_t get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition bitArray.I:89
static BitArray lower_on(int on_bits)
Returns a BitArray whose lower on_bits bits are on.
Definition bitArray.I:55
void operator>>=(int shift)
Logical right shift.
Definition bitArray.cxx:792
void output(std::ostream &out) const
Writes the BitArray out as a hex number.
Definition bitArray.cxx:520
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition bitArray.cxx:195
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.
Definition bitArray.cxx:467
WordType extract(int low_bit, int size) const
Returns a word that represents only the indicated range of bits within this BitArray,...
Definition bitArray.I:173
void write_datagram(BamWriter *manager, Datagram &dg) const
Writes the contents of this object to the datagram for shipping out to a Bam file.
Definition bitArray.cxx:911
int get_num_off_bits() const
Returns the number of bits that are set to 0 in the array.
Definition bitArray.cxx:314
void output_binary(std::ostream &out, int spaces_every=4) const
Writes the BitArray out as a binary number, with spaces every four bits.
Definition bitArray.cxx:528
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
Definition bitArray.cxx:48
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition bitArray.I:99
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.
Definition bitArray.cxx:572
int get_highest_on_bit() const
Returns the index of the highest 1 bit in the array.
Definition bitArray.cxx:372
void operator<<=(int shift)
Logical left shift.
Definition bitArray.cxx:727
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition bitArray.cxx:245
size_t get_num_words() const
Returns the number of possibly-unique words stored in the array.
Definition bitArray.I:235
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
Definition bitArray.cxx:69
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 ...
Definition datagram.h:38
void add_uint32(uint32_t value)
Adds an unsigned 32-bit integer to the datagram.
Definition datagram.I:94
void add_uint8(uint8_t value)
Adds an unsigned 8-bit integer to the datagram.
Definition datagram.I:50
This class records a set of integers, where each integer is either present or not present in the set.
Definition sparseArray.h:43
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.
Definition typeHandle.h:81
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.
Definition indent.cxx:20
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.