Panda3D
bitArray.I
1 // Filename: bitArray.I
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 
16 ////////////////////////////////////////////////////////////////////
17 // Function: BitArray::Constructor
18 // Access: Published
19 // Description:
20 ////////////////////////////////////////////////////////////////////
21 INLINE BitArray::
22 BitArray() {
23  _highest_bits = 0;
24 }
25 
26 ////////////////////////////////////////////////////////////////////
27 // Function: BitArray::Constructor
28 // Access: Published
29 // Description:
30 ////////////////////////////////////////////////////////////////////
31 INLINE BitArray::
32 BitArray(WordType init_value) {
33  if (init_value != 0) {
34  _array.push_back(MaskType(init_value));
35  }
36  _highest_bits = 0;
37 }
38 
39 ////////////////////////////////////////////////////////////////////
40 // Function: BitArray::Copy Constructor
41 // Access: Published
42 // Description:
43 ////////////////////////////////////////////////////////////////////
44 INLINE BitArray::
45 BitArray(const BitArray &copy) :
46  _array(copy._array),
47  _highest_bits(copy._highest_bits)
48 {
49 }
50 
51 ////////////////////////////////////////////////////////////////////
52 // Function: BitArray::Copy Assignment Operator
53 // Access: Published
54 // Description:
55 ////////////////////////////////////////////////////////////////////
56 INLINE BitArray &BitArray::
57 operator = (const BitArray &copy) {
58  _array = copy._array;
59  _highest_bits = copy._highest_bits;
60  return *this;
61 }
62 
63 ////////////////////////////////////////////////////////////////////
64 // Function: BitArray::Named all_on constructor
65 // Access: Published, Static
66 // Description: Returns a BitArray with an infinite array of bits,
67 // all on.
68 ////////////////////////////////////////////////////////////////////
69 INLINE BitArray BitArray::
70 all_on() {
71  BitArray result;
72  result._highest_bits = 1;
73  return result;
74 }
75 
76 ////////////////////////////////////////////////////////////////////
77 // Function: BitArray::Named all_on constructor
78 // Access: Published, Static
79 // Description: Returns a BitArray whose bits are all off.
80 ////////////////////////////////////////////////////////////////////
81 INLINE BitArray BitArray::
83  return BitArray();
84 }
85 
86 ////////////////////////////////////////////////////////////////////
87 // Function: BitArray::Named lower_on constructor
88 // Access: Published, Static
89 // Description: Returns a BitArray whose lower on_bits bits are on.
90 ////////////////////////////////////////////////////////////////////
91 INLINE BitArray BitArray::
92 lower_on(int on_bits) {
93  BitArray result;
94  result.set_range(0, on_bits);
95  return result;
96 }
97 
98 ////////////////////////////////////////////////////////////////////
99 // Function: BitArray::Named bit constructor
100 // Access: Published, Static
101 // Description: Returns a BitArray with only the indicated bit on.
102 ////////////////////////////////////////////////////////////////////
103 INLINE BitArray BitArray::
104 bit(int index) {
105  BitArray result;
106  result.set_bit(index);
107  return result;
108 }
109 
110 ////////////////////////////////////////////////////////////////////
111 // Function: BitArray::Named range constructor
112 // Access: Published, Static
113 // Description: Returns a BitArray whose size bits, beginning at
114 // low_bit, are on.
115 ////////////////////////////////////////////////////////////////////
116 INLINE BitArray BitArray::
117 range(int low_bit, int size) {
118  BitArray result;
119  result.set_range(low_bit, size);
120  return result;
121 }
122 
123 ////////////////////////////////////////////////////////////////////
124 // Function: BitArray::Destructor
125 // Access: Published
126 // Description:
127 ////////////////////////////////////////////////////////////////////
128 INLINE BitArray::
129 ~BitArray() {
130 }
131 
132 ////////////////////////////////////////////////////////////////////
133 // Function: BitArray::has_max_num_bits
134 // Access: Published, Static
135 // Description: Returns true if there is a maximum number of bits
136 // that may be stored in this structure, false
137 // otherwise. If this returns true, the number may be
138 // queried in get_max_num_bits().
139 //
140 // This method always returns false. The BitArray has
141 // no maximum number of bits. This method is defined so
142 // generic programming algorithms can use BitMask or
143 // BitArray interchangeably.
144 ////////////////////////////////////////////////////////////////////
145 CONSTEXPR bool BitArray::
147  return false;
148 }
149 
150 ////////////////////////////////////////////////////////////////////
151 // Function: BitArray::get_max_num_bits
152 // Access: Published, Static
153 // Description: If get_max_num_bits() returned true, this method may
154 // be called to return the maximum number of bits that
155 // may be stored in this structure. It is an error to
156 // call this if get_max_num_bits() return false.
157 //
158 // It is always an error to call this method. The
159 // BitArray has no maximum number of bits. This method
160 // is defined so generic programming algorithms can use
161 // BitMask or BitArray interchangeably.
162 ////////////////////////////////////////////////////////////////////
163 CONSTEXPR int BitArray::
165  return INT_MAX;
166 }
167 
168 ////////////////////////////////////////////////////////////////////
169 // Function: BitArray::get_num_bits_per_word
170 // Access: Published, Static
171 // Description: Returns the number of bits stored per word
172 // internally. This is of interest only in that it
173 // limits the maximum number of bits that may be queried
174 // or set at once by extract() and store().
175 ////////////////////////////////////////////////////////////////////
176 CONSTEXPR int BitArray::
178  return num_bits_per_word;
179 }
180 
181 ////////////////////////////////////////////////////////////////////
182 // Function: BitArray::get_num_bits
183 // Access: Published
184 // Description: Returns the current number of possibly different bits
185 // in this array. There are actually an infinite number
186 // of bits, but every bit higher than this bit will have
187 // the same value, either 0 or 1 (see
188 // get_highest_bits()).
189 //
190 // This number may grow and/or shrink automatically as
191 // needed.
192 ////////////////////////////////////////////////////////////////////
193 INLINE int BitArray::
194 get_num_bits() const {
195  return get_num_words() * num_bits_per_word;
196 }
197 
198 ////////////////////////////////////////////////////////////////////
199 // Function: BitArray::get_bit
200 // Access: Published
201 // Description: Returns true if the nth bit is set, false if it is
202 // cleared. It is valid for n to increase beyond
203 // get_num_bits(), but the return value get_num_bits()
204 // will always be the same.
205 ////////////////////////////////////////////////////////////////////
206 INLINE bool BitArray::
207 get_bit(int index) const {
208  nassertr(index >= 0, false);
209  int w = index / num_bits_per_word;
210  int b = index % num_bits_per_word;
211  if (w >= get_num_words()) {
212  return get_highest_bits();
213  } else {
214  return (_array[w].get_bit(b));
215  }
216 }
217 
218 ////////////////////////////////////////////////////////////////////
219 // Function: BitArray::set_bit
220 // Access: Published
221 // Description: Sets the nth bit on. If n >= get_num_bits(), this
222 // automatically extends the array.
223 ////////////////////////////////////////////////////////////////////
224 INLINE void BitArray::
225 set_bit(int index) {
226  nassertv(index >= 0);
227  int w = index / num_bits_per_word;
228  int b = index % num_bits_per_word;
229  if (w >= get_num_words() && _highest_bits) {
230  // All the highest bits are already on.
231  return;
232  }
233  ensure_has_word(w);
234  _array[w].set_bit(b);
235  normalize();
236 }
237 
238 ////////////////////////////////////////////////////////////////////
239 // Function: BitArray::clear_bit
240 // Access: Published
241 // Description: Sets the nth bit off. If n >= get_num_bits(), this
242 // automatically extends the array.
243 ////////////////////////////////////////////////////////////////////
244 INLINE void BitArray::
245 clear_bit(int index) {
246  nassertv(index >= 0);
247  int w = index / num_bits_per_word;
248  int b = index % num_bits_per_word;
249  if (w >= get_num_words() && !_highest_bits) {
250  // All the highest bits are already off.
251  return;
252  }
253  ensure_has_word(w);
254  _array[w].clear_bit(b);
255  normalize();
256 }
257 
258 ////////////////////////////////////////////////////////////////////
259 // Function: BitArray::set_bit_to
260 // Access: Published
261 // Description: Sets the nth bit either on or off, according to the
262 // indicated bool value.
263 ////////////////////////////////////////////////////////////////////
264 INLINE void BitArray::
265 set_bit_to(int index, bool value) {
266  if (value) {
267  set_bit(index);
268  } else {
269  clear_bit(index);
270  }
271 }
272 
273 ////////////////////////////////////////////////////////////////////
274 // Function: BitArray::get_highest_bits
275 // Access: Published
276 // Description: Returns true if the infinite set of bits beyond
277 // get_num_bits() are all on, or false of they are all
278 // off.
279 ////////////////////////////////////////////////////////////////////
280 INLINE bool BitArray::
282  return (_highest_bits != 0);
283 }
284 
285 ////////////////////////////////////////////////////////////////////
286 // Function: BitArray::extract
287 // Access: Published
288 // Description: Returns a word that represents only the indicated
289 // range of bits within this BitArray, shifted to the
290 // least-significant position. size must be <=
291 // get_num_bits_per_word().
292 ////////////////////////////////////////////////////////////////////
293 INLINE BitArray::WordType BitArray::
294 extract(int low_bit, int size) const {
295  nassertr(size >= 0 && size <= num_bits_per_word, 0);
296  int w = low_bit / num_bits_per_word;
297  int b = low_bit % num_bits_per_word;
298 
299  if (b + size < num_bits_per_word) {
300  // The whole thing fits within one word of the array.
301  return get_word(w).extract(b, size);
302 
303  } else {
304  // We have to split it across two words.
305  int num_lower_bits = num_bits_per_word - b;
306  int num_higher_bits = size - num_lower_bits;
307 
308  return get_word(w).extract(b, num_lower_bits) |
309  (get_word(w + 1).extract(0, num_higher_bits) << num_lower_bits);
310  }
311 }
312 
313 ////////////////////////////////////////////////////////////////////
314 // Function: BitArray::store
315 // Access: Published
316 // Description: Stores the indicated word into the indicated range of
317 // bits with this BitArray.
318 ////////////////////////////////////////////////////////////////////
319 INLINE void BitArray::
320 store(WordType value, int low_bit, int size) {
321  nassertv(size >= 0);
322  int w = low_bit / num_bits_per_word;
323  int b = low_bit % num_bits_per_word;
324 
325  if (b + size < num_bits_per_word) {
326  // The whole thing fits within one word of the array.
327  ensure_has_word(w);
328  _array[w].store(value, b, size);
329 
330  } else {
331  // We have to split it across two words.
332  int num_lower_bits = num_bits_per_word - b;
333  int num_higher_bits = size - num_lower_bits;
334 
335  ensure_has_word(w + 1);
336  _array[w].store(value, b, num_lower_bits);
337  _array[w + 1].store(value >> num_lower_bits, 0, num_higher_bits);
338  }
339  normalize();
340 }
341 
342 ////////////////////////////////////////////////////////////////////
343 // Function: BitArray::set_range_to
344 // Access: Published
345 // Description: Sets the indicated range of bits to either on or off.
346 ////////////////////////////////////////////////////////////////////
347 INLINE void BitArray::
348 set_range_to(bool value, int low_bit, int size) {
349  if (value) {
350  set_range(low_bit, size);
351  } else {
352  clear_range(low_bit, size);
353  }
354 }
355 
356 ////////////////////////////////////////////////////////////////////
357 // Function: BitArray::get_num_words
358 // Access: Published
359 // Description: Returns the number of possibly-unique words stored in
360 // the array.
361 ////////////////////////////////////////////////////////////////////
362 INLINE int BitArray::
363 get_num_words() const {
364  return _array.size();
365 }
366 
367 ////////////////////////////////////////////////////////////////////
368 // Function: BitArray::get_word
369 // Access: Published
370 // Description: Returns the nth word in the array. It is valid for n
371 // to be greater than get_num_words(), but the return
372 // value beyond get_num_words() will always be the same.
373 ////////////////////////////////////////////////////////////////////
374 INLINE BitArray::MaskType BitArray::
375 get_word(int n) const {
376  nassertr(n >= 0, MaskType::all_off());
377  if (n < get_num_words()) {
378  return _array[n];
379  }
380  if (_highest_bits) {
381  return MaskType::all_on();
382  } else {
383  return MaskType::all_off();
384  }
385 }
386 
387 ////////////////////////////////////////////////////////////////////
388 // Function: BitArray::set_word
389 // Access: Published
390 // Description: Replaces the nth word in the array. If n >=
391 // get_num_words(), this automatically extends the
392 // array.
393 ////////////////////////////////////////////////////////////////////
394 INLINE void BitArray::
395 set_word(int n, WordType value) {
396  nassertv(n >= 0);
397  ensure_has_word(n);
398  _array[n] = value;
399  normalize();
400 }
401 
402 ////////////////////////////////////////////////////////////////////
403 // Function: BitArray::clear
404 // Access: Published
405 // Description: Sets all the bits in the BitArray off.
406 ////////////////////////////////////////////////////////////////////
407 void BitArray::
408 clear() {
409  _array.clear();
410  _highest_bits = 0;
411 }
412 
413 ////////////////////////////////////////////////////////////////////
414 // Function: BitArray::operator ==
415 // Access: Published
416 // Description:
417 ////////////////////////////////////////////////////////////////////
418 INLINE bool BitArray::
419 operator == (const BitArray &other) const {
420  return compare_to(other) == 0;
421 }
422 
423 ////////////////////////////////////////////////////////////////////
424 // Function: BitArray::operator !=
425 // Access: Published
426 // Description:
427 ////////////////////////////////////////////////////////////////////
428 INLINE bool BitArray::
429 operator != (const BitArray &other) const {
430  return compare_to(other) != 0;
431 }
432 
433 ////////////////////////////////////////////////////////////////////
434 // Function: BitArray::operator <
435 // Access: Published
436 // Description: Returns true if the unsigned integer which is
437 // represented by this BitArray is less than that of the
438 // other one, false otherwise.
439 ////////////////////////////////////////////////////////////////////
440 INLINE bool BitArray::
441 operator < (const BitArray &other) const {
442  return compare_to(other) < 0;
443 }
444 
445 ////////////////////////////////////////////////////////////////////
446 // Function: BitArray::operator &
447 // Access: Published
448 // Description:
449 ////////////////////////////////////////////////////////////////////
450 INLINE BitArray BitArray::
451 operator & (const BitArray &other) const {
452  BitArray result(*this);
453  result &= other;
454  return result;
455 }
456 
457 ////////////////////////////////////////////////////////////////////
458 // Function: BitArray::operator |
459 // Access: Published
460 // Description:
461 ////////////////////////////////////////////////////////////////////
462 INLINE BitArray BitArray::
463 operator | (const BitArray &other) const {
464  BitArray result(*this);
465  result |= other;
466  return result;
467 }
468 
469 ////////////////////////////////////////////////////////////////////
470 // Function: BitArray::operator ^
471 // Access: Published
472 // Description:
473 ////////////////////////////////////////////////////////////////////
474 INLINE BitArray BitArray::
475 operator ^ (const BitArray &other) const {
476  BitArray result(*this);
477  result ^= other;
478  return result;
479 }
480 
481 ////////////////////////////////////////////////////////////////////
482 // Function: BitArray::operator ~
483 // Access: Published
484 // Description:
485 ////////////////////////////////////////////////////////////////////
486 INLINE BitArray BitArray::
487 operator ~ () const {
488  BitArray result(*this);
489  result.invert_in_place();
490  return result;
491 }
492 
493 ////////////////////////////////////////////////////////////////////
494 // Function: BitArray::operator <<
495 // Access: Published
496 // Description:
497 ////////////////////////////////////////////////////////////////////
498 INLINE BitArray BitArray::
499 operator << (int shift) const {
500  BitArray result(*this);
501  result <<= shift;
502  return result;
503 }
504 
505 ////////////////////////////////////////////////////////////////////
506 // Function: BitArray::operator >>
507 // Access: Published
508 // Description:
509 ////////////////////////////////////////////////////////////////////
510 INLINE BitArray BitArray::
511 operator >> (int shift) const {
512  BitArray result(*this);
513  result >>= shift;
514  return result;
515 }
516 
517 ////////////////////////////////////////////////////////////////////
518 // Function: BitArray::copy_on_write
519 // Access: Private
520 // Description: Called internally just before writing to the _array
521 // member, this makes a new copy of _array if it appears
522 // to be shared with any other objects--thus achieving
523 // copy-on-write.
524 ////////////////////////////////////////////////////////////////////
525 INLINE void BitArray::
526 copy_on_write() {
527  if (_array.get_ref_count() > 1) {
528  PTA(MaskType) new_array;
529  new_array.v() = _array.v();
530  _array = new_array;
531  }
532 }
void invert_in_place()
Inverts all the bits in the BitArray.
Definition: bitArray.cxx:488
void set_bit_to(int index, bool value)
Sets the nth bit either on or off, according to the indicated bool value.
Definition: bitArray.I:265
int get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition: bitArray.I:194
bool get_highest_bits() const
Returns true if the infinite set of bits beyond get_num_bits() are all on, or false of they are all o...
Definition: bitArray.I:281
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition: bitArray.I:207
static BitArray all_on()
Returns a BitArray with an infinite array of bits, all on.
Definition: bitArray.I:70
static CONSTEXPR int get_num_bits_per_word()
Returns the number of bits stored per word internally.
Definition: bitArray.I:177
static BitArray range(int low_bit, int size)
Returns a BitArray whose size bits, beginning at low_bit, are on.
Definition: bitArray.I:117
void set_range_to(bool value, int low_bit, int size)
Sets the indicated range of bits to either on or off.
Definition: bitArray.I:348
void store(WordType value, int low_bit, int size)
Stores the indicated word into the indicated range of bits with this BitArray.
Definition: bitArray.I:320
static CONSTEXPR int get_max_num_bits()
If get_max_num_bits() returned true, this method may be called to return the maximum number of bits t...
Definition: bitArray.I:164
void clear_bit(int index)
Sets the nth bit off.
Definition: bitArray.I:245
A dynamic array with an unlimited number of bits.
Definition: bitArray.h:42
bool operator<(const BitArray &other) const
Returns true if the unsigned integer which is represented by this BitArray is less than that of the o...
Definition: bitArray.I:441
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition: bitArray.cxx:208
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition: bitArray.cxx:260
static CONSTEXPR bool has_max_num_bits()
Returns true if there is a maximum number of bits that may be stored in this structure, false otherwise.
Definition: bitArray.I:146
static BitArray lower_on(int on_bits)
Returns a BitArray whose lower on_bits bits are on.
Definition: bitArray.I:92
void set_bit(int index)
Sets the nth bit on.
Definition: bitArray.I:225
MaskType get_word(int n) const
Returns the nth word in the array.
Definition: bitArray.I:375
int get_num_words() const
Returns the number of possibly-unique words stored in the array.
Definition: bitArray.I:363
void clear()
Sets all the bits in the BitArray off.
Definition: bitArray.I:408
static BitArray all_off()
Returns a BitArray whose bits are all off.
Definition: bitArray.I:82
static BitArray bit(int index)
Returns a BitArray with only the indicated bit on.
Definition: bitArray.I:104
void set_word(int n, WordType value)
Replaces the nth word in the array.
Definition: bitArray.I:395
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 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