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