Panda3D
 All Classes Functions Variables Enumerations
sparseArray.I
1 // Filename: sparseArray.I
2 // Created by: drose (14Feb07)
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: SparseArray::Constructor
18 // Access: Published
19 // Description:
20 ////////////////////////////////////////////////////////////////////
21 INLINE SparseArray::
22 SparseArray() : _inverse(false) {
23 }
24 
25 ////////////////////////////////////////////////////////////////////
26 // Function: SparseArray::Copy Constructor
27 // Access: Published
28 // Description:
29 ////////////////////////////////////////////////////////////////////
30 INLINE SparseArray::
31 SparseArray(const SparseArray &copy) :
32  _subranges(copy._subranges),
33  _inverse(copy._inverse)
34 {
35 }
36 
37 ////////////////////////////////////////////////////////////////////
38 // Function: SparseArray::Copy Assignment Operator
39 // Access: Published
40 // Description:
41 ////////////////////////////////////////////////////////////////////
42 INLINE SparseArray &SparseArray::
43 operator = (const SparseArray &copy) {
44  _subranges = copy._subranges;
45  _inverse = copy._inverse;
46  return *this;
47 }
48 
49 ////////////////////////////////////////////////////////////////////
50 // Function: SparseArray::Named all_on constructor
51 // Access: Published, Static
52 // Description: Returns a SparseArray with an infinite array of bits,
53 // all on.
54 ////////////////////////////////////////////////////////////////////
56 all_on() {
57  SparseArray result;
58  result._inverse = true;
59  return result;
60 }
61 
62 ////////////////////////////////////////////////////////////////////
63 // Function: SparseArray::Named all_on constructor
64 // Access: Published, Static
65 // Description: Returns a SparseArray whose bits are all off.
66 ////////////////////////////////////////////////////////////////////
69  return SparseArray();
70 }
71 
72 ////////////////////////////////////////////////////////////////////
73 // Function: SparseArray::Named lower_on constructor
74 // Access: Published, Static
75 // Description: Returns a SparseArray whose lower on_bits bits are on.
76 ////////////////////////////////////////////////////////////////////
78 lower_on(int on_bits) {
79  SparseArray result;
80  result.set_range(0, on_bits);
81  return result;
82 }
83 
84 ////////////////////////////////////////////////////////////////////
85 // Function: SparseArray::Named bit constructor
86 // Access: Published, Static
87 // Description: Returns a SparseArray with only the indicated bit on.
88 ////////////////////////////////////////////////////////////////////
90 bit(int index) {
91  SparseArray result;
92  result.set_bit(index);
93  return result;
94 }
95 
96 ////////////////////////////////////////////////////////////////////
97 // Function: SparseArray::Named range constructor
98 // Access: Published, Static
99 // Description: Returns a SparseArray whose size bits, beginning at
100 // low_bit, are on.
101 ////////////////////////////////////////////////////////////////////
103 range(int low_bit, int size) {
104  SparseArray result;
105  result.set_range(low_bit, size);
106  return result;
107 }
108 
109 ////////////////////////////////////////////////////////////////////
110 // Function: SparseArray::Destructor
111 // Access: Published
112 // Description:
113 ////////////////////////////////////////////////////////////////////
114 INLINE SparseArray::
115 ~SparseArray() {
116 }
117 
118 ////////////////////////////////////////////////////////////////////
119 // Function: SparseArray::has_max_num_bits
120 // Access: Published, Static
121 // Description: Returns true if there is a maximum number of bits
122 // that may be stored in this structure, false
123 // otherwise. If this returns true, the number may be
124 // queried in get_max_num_bits().
125 //
126 // This method always returns false. The SparseArray has
127 // no maximum number of bits. This method is defined so
128 // generic programming algorithms can use BitMask or
129 // SparseArray interchangeably.
130 ////////////////////////////////////////////////////////////////////
131 INLINE bool SparseArray::
133  return false;
134 }
135 
136 ////////////////////////////////////////////////////////////////////
137 // Function: SparseArray::get_max_num_bits
138 // Access: Published, Static
139 // Description: If get_max_num_bits() returned true, this method may
140 // be called to return the maximum number of bits that
141 // may be stored in this structure. It is an error to
142 // call this if get_max_num_bits() return false.
143 //
144 // It is always an error to call this method. The
145 // SparseArray has no maximum number of bits. This method
146 // is defined so generic programming algorithms can use
147 // BitMask or SparseArray interchangeably.
148 ////////////////////////////////////////////////////////////////////
149 INLINE int SparseArray::
151  nassertr(false, 0);
152  return 0;
153 }
154 
155 ////////////////////////////////////////////////////////////////////
156 // Function: SparseArray::get_num_bits
157 // Access: Published
158 // Description: Returns the current number of possibly different bits
159 // in this array. There are actually an infinite number
160 // of bits, but every bit higher than this bit will have
161 // the same value, either 0 or 1 (see
162 // get_highest_bits()).
163 //
164 // This number may grow and/or shrink automatically as
165 // needed.
166 ////////////////////////////////////////////////////////////////////
167 INLINE int SparseArray::
168 get_num_bits() const {
169  if (_subranges.empty()) {
170  return 0;
171  } else {
172  Subranges::const_iterator si = _subranges.begin() + _subranges.size() - 1;
173  return (*si)._end;
174  }
175 }
176 
177 ////////////////////////////////////////////////////////////////////
178 // Function: SparseArray::get_bit
179 // Access: Published
180 // Description: Returns true if the nth bit is set, false if it is
181 // cleared. It is valid for n to increase beyond
182 // get_num_bits(), but the return value get_num_bits()
183 // will always be the same.
184 ////////////////////////////////////////////////////////////////////
185 INLINE bool SparseArray::
186 get_bit(int index) const {
187  return has_any_of(index, 1);
188 }
189 
190 ////////////////////////////////////////////////////////////////////
191 // Function: SparseArray::set_bit
192 // Access: Published
193 // Description: Sets the nth bit on. If n >= get_num_bits(), this
194 // automatically extends the array.
195 ////////////////////////////////////////////////////////////////////
196 INLINE void SparseArray::
197 set_bit(int index) {
198  set_range(index, 1);
199 }
200 
201 ////////////////////////////////////////////////////////////////////
202 // Function: SparseArray::clear_bit
203 // Access: Published
204 // Description: Sets the nth bit off. If n >= get_num_bits(), this
205 // automatically extends the array.
206 ////////////////////////////////////////////////////////////////////
207 INLINE void SparseArray::
208 clear_bit(int index) {
209  clear_range(index, 1);
210 }
211 
212 ////////////////////////////////////////////////////////////////////
213 // Function: SparseArray::set_bit_to
214 // Access: Published
215 // Description: Sets the nth bit either on or off, according to the
216 // indicated bool value.
217 ////////////////////////////////////////////////////////////////////
218 INLINE void SparseArray::
219 set_bit_to(int index, bool value) {
220  if (value) {
221  set_bit(index);
222  } else {
223  clear_bit(index);
224  }
225 }
226 
227 ////////////////////////////////////////////////////////////////////
228 // Function: SparseArray::get_highest_bits
229 // Access: Published
230 // Description: Returns true if the infinite set of bits beyond
231 // get_num_bits() are all on, or false of they are all
232 // off.
233 ////////////////////////////////////////////////////////////////////
234 INLINE bool SparseArray::
236  return _inverse;
237 }
238 
239 ////////////////////////////////////////////////////////////////////
240 // Function: SparseArray::is_zero
241 // Access: Published
242 // Description: Returns true if the entire bitmask is zero, false
243 // otherwise.
244 ////////////////////////////////////////////////////////////////////
245 INLINE bool SparseArray::
246 is_zero() const {
247  if (_inverse) {
248  return false;
249  } else {
250  return _subranges.empty();
251  }
252 }
253 
254 ////////////////////////////////////////////////////////////////////
255 // Function: SparseArray::is_all_on
256 // Access: Published
257 // Description: Returns true if the entire bitmask is one, false
258 // otherwise.
259 ////////////////////////////////////////////////////////////////////
260 bool SparseArray::
261 is_all_on() const {
262  if (_inverse) {
263  return _subranges.empty();
264  } else {
265  return false;
266  }
267 }
268 
269 ////////////////////////////////////////////////////////////////////
270 // Function: SparseArray::has_any_of
271 // Access: Published
272 // Description: Returns true if any bit in the indicated range is
273 // set, false otherwise.
274 ////////////////////////////////////////////////////////////////////
275 INLINE bool SparseArray::
276 has_any_of(int low_bit, int size) const {
277  if (_inverse) {
278  return !do_has_all(low_bit, low_bit + size);
279  } else {
280  return do_has_any(low_bit, low_bit + size);
281  }
282 }
283 
284 ////////////////////////////////////////////////////////////////////
285 // Function: SparseArray::has_all_of
286 // Access: Published
287 // Description: Returns true if all bits in the indicated range are
288 // set, false otherwise.
289 ////////////////////////////////////////////////////////////////////
290 INLINE bool SparseArray::
291 has_all_of(int low_bit, int size) const {
292  if (_inverse) {
293  return !do_has_any(low_bit, low_bit + size);
294  } else {
295  return do_has_all(low_bit, low_bit + size);
296  }
297 }
298 
299 ////////////////////////////////////////////////////////////////////
300 // Function: SparseArray::set_range
301 // Access: Published
302 // Description: Sets the indicated range of bits on.
303 ////////////////////////////////////////////////////////////////////
304 INLINE void SparseArray::
305 set_range(int low_bit, int size) {
306  if (_inverse) {
307  return do_remove_range(low_bit, low_bit + size);
308  } else {
309  return do_add_range(low_bit, low_bit + size);
310  }
311 }
312 
313 ////////////////////////////////////////////////////////////////////
314 // Function: SparseArray::clear_range
315 // Access: Published
316 // Description: Sets the indicated range of bits off.
317 ////////////////////////////////////////////////////////////////////
318 INLINE void SparseArray::
319 clear_range(int low_bit, int size) {
320  if (_inverse) {
321  return do_add_range(low_bit, low_bit + size);
322  } else {
323  return do_remove_range(low_bit, low_bit + size);
324  }
325 }
326 
327 ////////////////////////////////////////////////////////////////////
328 // Function: SparseArray::set_range_to
329 // Access: Published
330 // Description: Sets the indicated range of bits to either on or off.
331 ////////////////////////////////////////////////////////////////////
332 INLINE void SparseArray::
333 set_range_to(bool value, int low_bit, int size) {
334  if (value) {
335  set_range(low_bit, size);
336  } else {
337  clear_range(low_bit, size);
338  }
339 }
340 
341 ////////////////////////////////////////////////////////////////////
342 // Function: SparseArray::invert_in_place
343 // Access: Published
344 // Description: Inverts all the bits in the SparseArray. This is
345 // equivalent to array = ~array.
346 ////////////////////////////////////////////////////////////////////
347 void SparseArray::
349  _inverse = !_inverse;
350 }
351 
352 ////////////////////////////////////////////////////////////////////
353 // Function: SparseArray::clear
354 // Access: Published
355 // Description: Sets all the bits in the SparseArray off.
356 ////////////////////////////////////////////////////////////////////
357 void SparseArray::
358 clear() {
359  _subranges.clear();
360  _inverse = false;
361 }
362 
363 ////////////////////////////////////////////////////////////////////
364 // Function: SparseArray::operator ==
365 // Access: Published
366 // Description:
367 ////////////////////////////////////////////////////////////////////
368 INLINE bool SparseArray::
369 operator == (const SparseArray &other) const {
370  return compare_to(other) == 0;
371 }
372 
373 ////////////////////////////////////////////////////////////////////
374 // Function: SparseArray::operator !=
375 // Access: Published
376 // Description:
377 ////////////////////////////////////////////////////////////////////
378 INLINE bool SparseArray::
379 operator != (const SparseArray &other) const {
380  return compare_to(other) != 0;
381 }
382 
383 ////////////////////////////////////////////////////////////////////
384 // Function: SparseArray::operator <
385 // Access: Published
386 // Description: Returns true if the unsigned integer which is
387 // represented by this SparseArray is less than that of the
388 // other one, false otherwise.
389 ////////////////////////////////////////////////////////////////////
390 INLINE bool SparseArray::
391 operator < (const SparseArray &other) const {
392  return compare_to(other) < 0;
393 }
394 
395 ////////////////////////////////////////////////////////////////////
396 // Function: SparseArray::operator &
397 // Access: Published
398 // Description:
399 ////////////////////////////////////////////////////////////////////
400 INLINE SparseArray SparseArray::
401 operator & (const SparseArray &other) const {
402  SparseArray result(*this);
403  result &= other;
404  return result;
405 }
406 
407 ////////////////////////////////////////////////////////////////////
408 // Function: SparseArray::operator |
409 // Access: Published
410 // Description:
411 ////////////////////////////////////////////////////////////////////
412 INLINE SparseArray SparseArray::
413 operator | (const SparseArray &other) const {
414  SparseArray result(*this);
415  result |= other;
416  return result;
417 }
418 
419 ////////////////////////////////////////////////////////////////////
420 // Function: SparseArray::operator ^
421 // Access: Published
422 // Description:
423 ////////////////////////////////////////////////////////////////////
424 INLINE SparseArray SparseArray::
425 operator ^ (const SparseArray &other) const {
426  SparseArray result(*this);
427  result ^= other;
428  return result;
429 }
430 
431 ////////////////////////////////////////////////////////////////////
432 // Function: SparseArray::operator ~
433 // Access: Published
434 // Description:
435 ////////////////////////////////////////////////////////////////////
436 INLINE SparseArray SparseArray::
437 operator ~ () const {
438  SparseArray result(*this);
439  result.invert_in_place();
440  return result;
441 }
442 
443 ////////////////////////////////////////////////////////////////////
444 // Function: SparseArray::operator <<
445 // Access: Published
446 // Description:
447 ////////////////////////////////////////////////////////////////////
448 INLINE SparseArray SparseArray::
449 operator << (int shift) const {
450  SparseArray result(*this);
451  result <<= shift;
452  return result;
453 }
454 
455 ////////////////////////////////////////////////////////////////////
456 // Function: SparseArray::operator >>
457 // Access: Published
458 // Description:
459 ////////////////////////////////////////////////////////////////////
460 INLINE SparseArray SparseArray::
461 operator >> (int shift) const {
462  SparseArray result(*this);
463  result >>= shift;
464  return result;
465 }
466 
467 
468 ////////////////////////////////////////////////////////////////////
469 // Function: SparseArray::operator <<=
470 // Access: Published
471 // Description: Logical left shift. Since negative bit positions
472 // have meaning in a SparseArray, real bit values are
473 // rotated in on the left (not necessarily zero).
474 ////////////////////////////////////////////////////////////////////
475 void SparseArray::
476 operator <<= (int shift) {
477  do_shift(shift);
478 }
479 
480 ////////////////////////////////////////////////////////////////////
481 // Function: SparseArray::operator >>=
482 // Access: Published
483 // Description: Logical right shift. The rightmost bits become
484 // negative, but are not lost; they will reappear into
485 // the zero position if the array is later left-shifted.
486 ////////////////////////////////////////////////////////////////////
487 void SparseArray::
488 operator >>= (int shift) {
489  do_shift(-shift);
490 }
491 
492 ////////////////////////////////////////////////////////////////////
493 // Function: SparseArray::is_inverse
494 // Access: Published
495 // Description: If this is true, the SparseArray is actually defined
496 // as a list of subranges of integers that are *not* in
497 // the set. If this is false (the default), then the
498 // subranges define the integers that *are* in the set.
499 // This affects the interpretation of the values
500 // returned by iterating through get_num_subranges().
501 ////////////////////////////////////////////////////////////////////
502 INLINE bool SparseArray::
503 is_inverse() const {
504  return _inverse;
505 }
506 
507 ////////////////////////////////////////////////////////////////////
508 // Function: SparseArray::get_num_subranges
509 // Access: Published
510 // Description: Returns the number of separate subranges stored in
511 // the SparseArray. You can use this limit to iterate
512 // through the subranges, calling get_subrange_begin()
513 // and get_subrange_end() for each one.
514 //
515 // Also see is_inverse().
516 ////////////////////////////////////////////////////////////////////
517 INLINE int SparseArray::
519  return _subranges.size();
520 }
521 
522 ////////////////////////////////////////////////////////////////////
523 // Function: SparseArray::get_subrange_begin
524 // Access: Published
525 // Description: Returns the first numeric element in the nth
526 // subrange.
527 //
528 // Also see is_inverse().
529 ////////////////////////////////////////////////////////////////////
530 INLINE int SparseArray::
531 get_subrange_begin(int n) const {
532  nassertr(n >= 0 && n < (int)_subranges.size(), 0);
533  return _subranges[n]._begin;
534 }
535 
536 ////////////////////////////////////////////////////////////////////
537 // Function: SparseArray::get_subrange_end
538 // Access: Published
539 // Description: Returns the last numeric element, plus one, in the
540 // nth subrange.
541 //
542 // Also see is_inverse().
543 ////////////////////////////////////////////////////////////////////
544 INLINE int SparseArray::
545 get_subrange_end(int n) const {
546  nassertr(n >= 0 && n < (int)_subranges.size(), 0);
547  return _subranges[n]._end;
548 }
549 
550 ////////////////////////////////////////////////////////////////////
551 // Function: SparseArray::Subrange::Constructor
552 // Access: Public
553 // Description:
554 ////////////////////////////////////////////////////////////////////
555 INLINE SparseArray::Subrange::
556 Subrange(int begin, int end) :
557  _begin(begin),
558  _end(end)
559 {
560 }
561 
562 ////////////////////////////////////////////////////////////////////
563 // Function: SparseArray::Subrange::operator <
564 // Access: Public
565 // Description:
566 ////////////////////////////////////////////////////////////////////
567 INLINE bool SparseArray::Subrange::
568 operator < (const SparseArray::Subrange &other) const {
569  // We compare the end values, rather than the begin values, to make
570  // lower_bound() sensibly return a possible intersection with the
571  // indicated Subrange.
572  return _end < other._end;
573 }
574 
void set_bit_to(int index, bool value)
Sets the nth bit either on or off, according to the indicated bool value.
Definition: sparseArray.I:219
static 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: sparseArray.I:150
This class records a set of integers, where each integer is either present or not present in the set...
Definition: sparseArray.h:49
static SparseArray all_off()
Returns a SparseArray whose bits are all off.
Definition: sparseArray.I:68
void set_range_to(bool value, int low_bit, int size)
Sets the indicated range of bits to either on or off.
Definition: sparseArray.I:333
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
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: sparseArray.I:235
void clear()
Removes all elements from the ordered vector.
void set_bit(int index)
Sets the nth bit on.
Definition: sparseArray.I:197
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition: sparseArray.I:319
int get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition: sparseArray.I:168
void clear_bit(int index)
Sets the nth bit off.
Definition: sparseArray.I:208
int get_subrange_end(int n) const
Returns the last numeric element, plus one, in the nth subrange.
Definition: sparseArray.I:545
static SparseArray all_on()
Returns a SparseArray with an infinite array of bits, all on.
Definition: sparseArray.I:56
int compare_to(const SparseArray &other) const
Returns a number less than zero if this SparseArray sorts before the indicated other SparseArray...
static 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: sparseArray.I:132
void operator>>=(int shift)
Logical right shift.
Definition: sparseArray.I:488
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
bool has_all_of(int low_bit, int size) const
Returns true if all bits in the indicated range are set, false otherwise.
Definition: sparseArray.I:291
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
Definition: sparseArray.I:246
bool operator<(const SparseArray &other) const
Returns true if the unsigned integer which is represented by this SparseArray is less than that of th...
Definition: sparseArray.I:391
static SparseArray bit(int index)
Returns a SparseArray with only the indicated bit on.
Definition: sparseArray.I:90
static SparseArray range(int low_bit, int size)
Returns a SparseArray whose size bits, beginning at low_bit, are on.
Definition: sparseArray.I:103
static SparseArray lower_on(int on_bits)
Returns a SparseArray whose lower on_bits bits are on.
Definition: sparseArray.I:78
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition: sparseArray.I:305
int get_num_subranges() const
Returns the number of separate subranges stored in the SparseArray.
Definition: sparseArray.I:518
void invert_in_place()
Inverts all the bits in the SparseArray.
Definition: sparseArray.I:348
size_type_0 size() const
Returns the number of elements in the ordered vector.
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition: sparseArray.I:186
int get_subrange_begin(int n) const
Returns the first numeric element in the nth subrange.
Definition: sparseArray.I:531
bool has_any_of(int low_bit, int size) const
Returns true if any bit in the indicated range is set, false otherwise.
Definition: sparseArray.I:276
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
Definition: sparseArray.I:261
void clear()
Sets all the bits in the SparseArray off.
Definition: sparseArray.I:358
void operator<<=(int shift)
Logical left shift.
Definition: sparseArray.I:476