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 */
24 INLINE SparseArray SparseArray::
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 */
34 INLINE SparseArray SparseArray::
35 all_off() {
36 return SparseArray();
37 }
38
39 /**
40 * Returns a SparseArray whose lower on_bits bits are on.
41 */
42 INLINE SparseArray SparseArray::
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 */
54 INLINE SparseArray SparseArray::
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 */
64 INLINE SparseArray SparseArray::
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::
81 has_max_num_bits() {
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::
95 get_max_num_bits() {
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 */
181 bool SparseArray::
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 */
254 void SparseArray::
255 invert_in_place() {
256 _inverse = !_inverse;
257 }
258
259 /**
260 * Sets all the bits in the SparseArray off.
261 */
262 void SparseArray::
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 */
359 void SparseArray::
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 */
369 void SparseArray::
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 }
SparseArray
This class records a set of integers, where each integer is either present or not present in the set.
Definition: sparseArray.h:43
SparseArray::invert_in_place
void invert_in_place()
Inverts all the bits in the SparseArray.
Definition: sparseArray.I:255
SparseArray::lower_on
static SparseArray lower_on(int on_bits)
Returns a SparseArray whose lower on_bits bits are on.
Definition: sparseArray.I:43
SparseArray::has_any_of
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
SparseArray::get_bit
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition: sparseArray.I:123
SparseArray::clear_range
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition: sparseArray.I:230
SparseArray::clear
void clear()
Sets all the bits in the SparseArray off.
Definition: sparseArray.I:263
SparseArray::operator<
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
SparseArray::get_subrange_begin
int get_subrange_begin(size_t n) const
Returns the first numeric element in the nth subrange.
Definition: sparseArray.I:404
SparseArray::has_all_of
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
SparseArray::operator>>=
void operator>>=(int shift)
Logical right shift.
Definition: sparseArray.I:370
SparseArray::compare_to
int compare_to(const SparseArray &other) const
Returns a number less than zero if this SparseArray sorts before the indicated other SparseArray,...
Definition: sparseArray.cxx:242
SparseArray::has_max_num_bits
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
SparseArray::set_bit_to
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
SparseArray::operator<<=
void operator<<=(int shift)
Logical left shift.
Definition: sparseArray.I:360
SparseArray::set_range
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition: sparseArray.I:218
SparseArray::range
static SparseArray range(int low_bit, int size)
Returns a SparseArray whose size bits, beginning at low_bit, are on.
Definition: sparseArray.I:65
SparseArray::get_max_num_bits
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
SparseArray::get_num_subranges
size_t get_num_subranges() const
Returns the number of separate subranges stored in the SparseArray.
Definition: sparseArray.I:394
SparseArray::get_highest_bits
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
SparseArray::bit
static SparseArray bit(int index)
Returns a SparseArray with only the indicated bit on.
Definition: sparseArray.I:55
SparseArray::get_subrange_end
int get_subrange_end(size_t n) const
Returns the last numeric element, plus one, in the nth subrange.
Definition: sparseArray.I:415
SparseArray::is_zero
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
Definition: sparseArray.I:170
SparseArray::is_inverse
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
SparseArray::is_all_on
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
Definition: sparseArray.I:182
SparseArray::set_bit
void set_bit(int index)
Sets the nth bit on.
Definition: sparseArray.I:132
SparseArray::all_off
static SparseArray all_off()
Returns a SparseArray whose bits are all off.
Definition: sparseArray.I:35
SparseArray::clear_bit
void clear_bit(int index)
Sets the nth bit off.
Definition: sparseArray.I:141
SparseArray::set_range_to
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
SparseArray::get_num_bits
int get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition: sparseArray.I:108
SparseArray::all_on
static SparseArray all_on()
Returns a SparseArray with an infinite array of bits, all on.
Definition: sparseArray.I:25
ordered_vector::begin
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
Definition: ordered_vector.I:41
ordered_vector::push_back
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
Definition: ordered_vector.I:614
ordered_vector::size
size_type_0 size() const
Returns the number of elements in the ordered vector.
Definition: ordered_vector.I:221
ordered_vector::empty
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
Definition: ordered_vector.I:240
ordered_vector::clear
void clear()
Removes all elements from the ordered vector.
Definition: ordered_vector.I:412