Panda3D
sparseArray.I
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 sparseArray.I
10  * @author drose
11  * @date 2007-02-14
12  */
13 
14 /**
15  *
16  */
17 INLINE SparseArray::
18 SparseArray() : _inverse(false) {
19 }
20 
21 /**
22  * Returns a SparseArray with an infinite array of bits, all on.
23  */
25 all_on() {
26  SparseArray result;
27  result._inverse = true;
28  return result;
29 }
30 
31 /**
32  * Returns a SparseArray whose bits are all off.
33  */
35 all_off() {
36  return SparseArray();
37 }
38 
39 /**
40  * Returns a SparseArray whose lower on_bits bits are on.
41  */
43 lower_on(int on_bits) {
44  SparseArray result;
45  if (on_bits > 0) {
46  result._subranges.push_back(Subrange(0, on_bits));
47  }
48  return result;
49 }
50 
51 /**
52  * Returns a SparseArray with only the indicated bit on.
53  */
55 bit(int index) {
56  SparseArray result;
57  result.set_bit(index);
58  return result;
59 }
60 
61 /**
62  * Returns a SparseArray whose size bits, beginning at low_bit, are on.
63  */
65 range(int low_bit, int size) {
66  SparseArray result;
67  result.set_range(low_bit, size);
68  return result;
69 }
70 
71 /**
72  * Returns true if there is a maximum number of bits that may be stored in
73  * this structure, false otherwise. If this returns true, the number may be
74  * queried in get_max_num_bits().
75  *
76  * This method always returns false. The SparseArray has no maximum number of
77  * bits. This method is defined so generic programming algorithms can use
78  * BitMask or SparseArray interchangeably.
79  */
80 INLINE bool SparseArray::
82  return false;
83 }
84 
85 /**
86  * If get_max_num_bits() returned true, this method may be called to return
87  * the maximum number of bits that may be stored in this structure. It is an
88  * error to call this if get_max_num_bits() return false.
89  *
90  * It is always an error to call this method. The SparseArray has no maximum
91  * number of bits. This method is defined so generic programming algorithms
92  * can use BitMask or SparseArray interchangeably.
93  */
94 INLINE int SparseArray::
96  nassert_raise("SparseArray has no maximum bit count");
97  return 0;
98 }
99 
100 /**
101  * Returns the current number of possibly different bits in this array. There
102  * are actually an infinite number of bits, but every bit higher than this bit
103  * will have the same value, either 0 or 1 (see get_highest_bits()).
104  *
105  * This number may grow and/or shrink automatically as needed.
106  */
107 INLINE int SparseArray::
108 get_num_bits() const {
109  if (_subranges.empty()) {
110  return 0;
111  } else {
112  Subranges::const_iterator si = _subranges.begin() + _subranges.size() - 1;
113  return (*si)._end;
114  }
115 }
116 
117 /**
118  * Returns true if the nth bit is set, false if it is cleared. It is valid
119  * for n to increase beyond get_num_bits(), but the return value
120  * get_num_bits() will always be the same.
121  */
122 INLINE bool SparseArray::
123 get_bit(int index) const {
124  return has_any_of(index, 1);
125 }
126 
127 /**
128  * Sets the nth bit on. If n >= get_num_bits(), this automatically extends
129  * the array.
130  */
131 INLINE void SparseArray::
132 set_bit(int index) {
133  set_range(index, 1);
134 }
135 
136 /**
137  * Sets the nth bit off. If n >= get_num_bits(), this automatically extends
138  * the array.
139  */
140 INLINE void SparseArray::
141 clear_bit(int index) {
142  clear_range(index, 1);
143 }
144 
145 /**
146  * Sets the nth bit either on or off, according to the indicated bool value.
147  */
148 INLINE void SparseArray::
149 set_bit_to(int index, bool value) {
150  if (value) {
151  set_bit(index);
152  } else {
153  clear_bit(index);
154  }
155 }
156 
157 /**
158  * Returns true if the infinite set of bits beyond get_num_bits() are all on,
159  * or false of they are all off.
160  */
161 INLINE bool SparseArray::
162 get_highest_bits() const {
163  return _inverse;
164 }
165 
166 /**
167  * Returns true if the entire bitmask is zero, false otherwise.
168  */
169 INLINE bool SparseArray::
170 is_zero() const {
171  if (_inverse) {
172  return false;
173  } else {
174  return _subranges.empty();
175  }
176 }
177 
178 /**
179  * Returns true if the entire bitmask is one, false otherwise.
180  */
182 is_all_on() const {
183  if (_inverse) {
184  return _subranges.empty();
185  } else {
186  return false;
187  }
188 }
189 
190 /**
191  * Returns true if any bit in the indicated range is set, false otherwise.
192  */
193 INLINE bool SparseArray::
194 has_any_of(int low_bit, int size) const {
195  if (_inverse) {
196  return !do_has_all(low_bit, low_bit + size);
197  } else {
198  return do_has_any(low_bit, low_bit + size);
199  }
200 }
201 
202 /**
203  * Returns true if all bits in the indicated range are set, false otherwise.
204  */
205 INLINE bool SparseArray::
206 has_all_of(int low_bit, int size) const {
207  if (_inverse) {
208  return !do_has_any(low_bit, low_bit + size);
209  } else {
210  return do_has_all(low_bit, low_bit + size);
211  }
212 }
213 
214 /**
215  * Sets the indicated range of bits on.
216  */
217 INLINE void SparseArray::
218 set_range(int low_bit, int size) {
219  if (_inverse) {
220  return do_remove_range(low_bit, low_bit + size);
221  } else {
222  return do_add_range(low_bit, low_bit + size);
223  }
224 }
225 
226 /**
227  * Sets the indicated range of bits off.
228  */
229 INLINE void SparseArray::
230 clear_range(int low_bit, int size) {
231  if (_inverse) {
232  return do_add_range(low_bit, low_bit + size);
233  } else {
234  return do_remove_range(low_bit, low_bit + size);
235  }
236 }
237 
238 /**
239  * Sets the indicated range of bits to either on or off.
240  */
241 INLINE void SparseArray::
242 set_range_to(bool value, int low_bit, int size) {
243  if (value) {
244  set_range(low_bit, size);
245  } else {
246  clear_range(low_bit, size);
247  }
248 }
249 
250 /**
251  * Inverts all the bits in the SparseArray. This is equivalent to array =
252  * ~array.
253  */
255 invert_in_place() {
256  _inverse = !_inverse;
257 }
258 
259 /**
260  * Sets all the bits in the SparseArray off.
261  */
263 clear() {
264  _subranges.clear();
265  _inverse = false;
266 }
267 
268 /**
269  *
270  */
271 INLINE bool SparseArray::
272 operator == (const SparseArray &other) const {
273  return compare_to(other) == 0;
274 }
275 
276 /**
277  *
278  */
279 INLINE bool SparseArray::
280 operator != (const SparseArray &other) const {
281  return compare_to(other) != 0;
282 }
283 
284 /**
285  * Returns true if the unsigned integer which is represented by this
286  * SparseArray is less than that of the other one, false otherwise.
287  */
288 INLINE bool SparseArray::
289 operator < (const SparseArray &other) const {
290  return compare_to(other) < 0;
291 }
292 
293 /**
294  *
295  */
296 INLINE SparseArray SparseArray::
297 operator & (const SparseArray &other) const {
298  SparseArray result(*this);
299  result &= other;
300  return result;
301 }
302 
303 /**
304  *
305  */
306 INLINE SparseArray SparseArray::
307 operator | (const SparseArray &other) const {
308  SparseArray result(*this);
309  result |= other;
310  return result;
311 }
312 
313 /**
314  *
315  */
316 INLINE SparseArray SparseArray::
317 operator ^ (const SparseArray &other) const {
318  SparseArray result(*this);
319  result ^= other;
320  return result;
321 }
322 
323 /**
324  *
325  */
326 INLINE SparseArray SparseArray::
327 operator ~ () const {
328  SparseArray result(*this);
329  result.invert_in_place();
330  return result;
331 }
332 
333 /**
334  *
335  */
336 INLINE SparseArray SparseArray::
337 operator << (int shift) const {
338  SparseArray result(*this);
339  result <<= shift;
340  return result;
341 }
342 
343 /**
344  *
345  */
346 INLINE SparseArray SparseArray::
347 operator >> (int shift) const {
348  SparseArray result(*this);
349  result >>= shift;
350  return result;
351 }
352 
353 
354 /**
355  * Logical left shift. Since negative bit positions have meaning in a
356  * SparseArray, real bit values are rotated in on the left (not necessarily
357  * zero).
358  */
360 operator <<= (int shift) {
361  do_shift(shift);
362 }
363 
364 /**
365  * Logical right shift. The rightmost bits become negative, but are not lost;
366  * they will reappear into the zero position if the array is later left-
367  * shifted.
368  */
370 operator >>= (int shift) {
371  do_shift(-shift);
372 }
373 
374 /**
375  * If this is true, the SparseArray is actually defined as a list of subranges
376  * of integers that are *not* in the set. If this is false (the default),
377  * then the subranges define the integers that *are* in the set. This affects
378  * the interpretation of the values returned by iterating through
379  * get_num_subranges().
380  */
381 INLINE bool SparseArray::
382 is_inverse() const {
383  return _inverse;
384 }
385 
386 /**
387  * Returns the number of separate subranges stored in the SparseArray. You
388  * can use this limit to iterate through the subranges, calling
389  * get_subrange_begin() and get_subrange_end() for each one.
390  *
391  * Also see is_inverse().
392  */
393 INLINE size_t SparseArray::
394 get_num_subranges() const {
395  return _subranges.size();
396 }
397 
398 /**
399  * Returns the first numeric element in the nth subrange.
400  *
401  * Also see is_inverse().
402  */
403 INLINE int SparseArray::
404 get_subrange_begin(size_t n) const {
405  nassertr(n < _subranges.size(), 0);
406  return _subranges[n]._begin;
407 }
408 
409 /**
410  * Returns the last numeric element, plus one, in the nth subrange.
411  *
412  * Also see is_inverse().
413  */
414 INLINE int SparseArray::
415 get_subrange_end(size_t n) const {
416  nassertr(n < _subranges.size(), 0);
417  return _subranges[n]._end;
418 }
419 
420 /**
421  *
422  */
423 INLINE SparseArray::Subrange::
424 Subrange(int begin, int end) :
425  _begin(begin),
426  _end(end)
427 {
428 }
429 
430 /**
431  *
432  */
433 INLINE bool SparseArray::Subrange::
434 operator < (const SparseArray::Subrange &other) const {
435  // We compare the end values, rather than the begin values, to make
436  // lower_bound() sensibly return a possible intersection with the indicated
437  // Subrange.
438  return _end < other._end;
439 }
This class records a set of integers, where each integer is either present or not present in the set.
Definition: sparseArray.h:43
void invert_in_place()
Inverts all the bits in the SparseArray.
Definition: sparseArray.I:255
static SparseArray lower_on(int on_bits)
Returns a SparseArray whose lower on_bits bits are on.
Definition: sparseArray.I:43
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:194
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition: sparseArray.I:123
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition: sparseArray.I:230
void clear()
Sets all the bits in the SparseArray off.
Definition: sparseArray.I:263
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:289
int get_subrange_begin(size_t n) const
Returns the first numeric element in the nth subrange.
Definition: sparseArray.I:404
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:206
void operator>>=(int shift)
Logical right shift.
Definition: sparseArray.I:370
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,...
Definition: sparseArray.I:81
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:149
void operator<<=(int shift)
Logical left shift.
Definition: sparseArray.I:360
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition: sparseArray.I:218
static SparseArray range(int low_bit, int size)
Returns a SparseArray whose size bits, beginning at low_bit, are on.
Definition: sparseArray.I:65
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:95
size_t get_num_subranges() const
Returns the number of separate subranges stored in the SparseArray.
Definition: sparseArray.I:394
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:162
static SparseArray bit(int index)
Returns a SparseArray with only the indicated bit on.
Definition: sparseArray.I:55
int get_subrange_end(size_t n) const
Returns the last numeric element, plus one, in the nth subrange.
Definition: sparseArray.I:415
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
Definition: sparseArray.I:170
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:382
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
Definition: sparseArray.I:182
void set_bit(int index)
Sets the nth bit on.
Definition: sparseArray.I:132
static SparseArray all_off()
Returns a SparseArray whose bits are all off.
Definition: sparseArray.I:35
void clear_bit(int index)
Sets the nth bit off.
Definition: sparseArray.I:141
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:242
int get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition: sparseArray.I:108
static SparseArray all_on()
Returns a SparseArray with an infinite array of bits, all on.
Definition: sparseArray.I:25
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
size_type_0 size() const
Returns the number of elements in the ordered vector.
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
void clear()
Removes all elements from the ordered vector.