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 */
25all_on() {
26 SparseArray result;
27 result._inverse = true;
28 return result;
29}
30
31/**
32 * Returns a SparseArray whose bits are all off.
33 */
35all_off() {
36 return SparseArray();
37}
38
39/**
40 * Returns a SparseArray whose lower on_bits bits are on.
41 */
43lower_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 */
55bit(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 */
65range(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::
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::
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 */
108get_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::
123get_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::
132set_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::
141clear_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::
149set_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::
162get_highest_bits() const {
163 return _inverse;
164}
165
166/**
167 * Returns true if the entire bitmask is zero, false otherwise.
168 */
169INLINE bool SparseArray::
170is_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 */
182is_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::
194has_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::
206has_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::
218set_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::
230clear_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::
242set_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 */
256 _inverse = !_inverse;
257}
258
259/**
260 * Sets all the bits in the SparseArray off.
261 */
263clear() {
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::
289operator < (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 */
360operator <<= (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 */
370operator >>= (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::
382is_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::
394get_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 */
404get_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 */
415get_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}
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.
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.
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
void clear()
Sets all the bits in the SparseArray off.
bool operator<(const SparseArray &other) const
Returns true if the unsigned integer which is represented by this SparseArray is less than that of th...
int get_subrange_begin(size_t n) const
Returns the first numeric element in the nth subrange.
bool has_all_of(int low_bit, int size) const
Returns true if all bits in the indicated range are set, false otherwise.
void operator>>=(int shift)
Logical right shift.
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.
void operator<<=(int shift)
Logical left shift.
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
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.
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...
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.
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
bool is_inverse() const
If this is true, the SparseArray is actually defined as a list of subranges of integers that are *not...
bool is_all_on() const
Returns true if the entire bitmask is one, false otherwise.
void set_bit(int index)
Sets the nth bit on.
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.
void set_range_to(bool value, int low_bit, int size)
Sets the indicated range of bits to either on or off.
int get_num_bits() const
Returns the current number of possibly different bits in this array.
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.