Panda3D

Loading...
Searching...
No Matches
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 */
17INLINE SparseArray::
18SparseArray() : _inverse(false) {
19}
20
21/**
22 * Returns a SparseArray with an infinite array of bits, all on.
23 */
24INLINE 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 */
34INLINE SparseArray SparseArray::
35 all_off() {
36 return SparseArray();
37}
38
39/**
40 * Returns a SparseArray whose lower on_bits bits are on.
41 */
42INLINE 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 */
54INLINE 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 */
64INLINE 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 */
80INLINE 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 */
94INLINE 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 */
107INLINE 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 */
122INLINE 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 */
131INLINE 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 */
140INLINE 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 */
148INLINE 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 */
161INLINE 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 */
169INLINE 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 */
193INLINE 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 */
205INLINE 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 */
217INLINE 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 */
229INLINE 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 */
241INLINE 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 */
271INLINE bool SparseArray::
272operator == (const SparseArray &other) const {
273 return compare_to(other) == 0;
274}
275
276/**
277 *
278 */
279INLINE bool SparseArray::
280operator != (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 */
288INLINE bool SparseArray::
289 operator < (const SparseArray &other) const {
290 return compare_to(other) < 0;
291}
292
293/**
294 *
295 */
296INLINE SparseArray SparseArray::
297operator & (const SparseArray &other) const {
298 SparseArray result(*this);
299 result &= other;
300 return result;
301}
302
303/**
304 *
305 */
306INLINE SparseArray SparseArray::
307operator | (const SparseArray &other) const {
308 SparseArray result(*this);
309 result |= other;
310 return result;
311}
312
313/**
314 *
315 */
316INLINE SparseArray SparseArray::
317operator ^ (const SparseArray &other) const {
318 SparseArray result(*this);
319 result ^= other;
320 return result;
321}
322
323/**
324 *
325 */
326INLINE SparseArray SparseArray::
327operator ~ () const {
328 SparseArray result(*this);
329 result.invert_in_place();
330 return result;
331}
332
333/**
334 *
335 */
336INLINE SparseArray SparseArray::
337operator << (int shift) const {
338 SparseArray result(*this);
339 result <<= shift;
340 return result;
341}
342
343/**
344 *
345 */
346INLINE SparseArray SparseArray::
347operator >> (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 */
381INLINE 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 */
393INLINE 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 */
403INLINE 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 */
414INLINE 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 */
423INLINE SparseArray::Subrange::
424Subrange(int begin, int end) :
425 _begin(begin),
426 _end(end)
427{
428}
429
430/**
431 *
432 */
433INLINE bool SparseArray::Subrange::
434operator < (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:250
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::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