Panda3D
Loading...
Searching...
No Matches
bitArray.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 bitArray.I
10 * @author drose
11 * @date 2006-01-20
12 */
13
14/**
15 *
16 */
17INLINE BitArray::
18BitArray() {
19 _highest_bits = 0;
20}
21
22/**
23 *
24 */
25INLINE BitArray::
26BitArray(WordType init_value) {
27 if (init_value != 0) {
28 _array.push_back(MaskType(init_value));
29 }
30 _highest_bits = 0;
31}
32
33/**
34 * Returns a BitArray with an infinite array of bits, all on.
35 */
37all_on() {
38 BitArray result;
39 result._highest_bits = 1;
40 return result;
41}
42
43/**
44 * Returns a BitArray whose bits are all off.
45 */
47all_off() {
48 return BitArray();
49}
50
51/**
52 * Returns a BitArray whose lower on_bits bits are on.
53 */
55lower_on(int on_bits) {
56 BitArray result;
57 result.set_range(0, on_bits);
58 return result;
59}
60
61/**
62 * Returns a BitArray with only the indicated bit on.
63 */
65bit(int index) {
66 BitArray result;
67 result.set_bit(index);
68 return result;
69}
70
71/**
72 * Returns a BitArray whose size bits, beginning at low_bit, are on.
73 */
75range(int low_bit, int size) {
76 BitArray result;
77 result.set_range(low_bit, size);
78 return result;
79}
80
81/**
82 * Returns the current number of possibly different bits in this array. There
83 * are actually an infinite number of bits, but every bit higher than this bit
84 * will have the same value, either 0 or 1 (see get_highest_bits()).
85 *
86 * This number may grow and/or shrink automatically as needed.
87 */
88INLINE size_t BitArray::
89get_num_bits() const {
90 return get_num_words() * (size_t)num_bits_per_word;
91}
92
93/**
94 * Returns true if the nth bit is set, false if it is cleared. It is valid
95 * for n to increase beyond get_num_bits(), but the return value
96 * get_num_bits() will always be the same.
97 */
98INLINE bool BitArray::
99get_bit(int index) const {
100 nassertr(index >= 0, false);
101 int w = index / num_bits_per_word;
102 int b = index % num_bits_per_word;
103 if ((size_t)w >= get_num_words()) {
104 return get_highest_bits();
105 } else {
106 return (_array[w].get_bit(b));
107 }
108}
109
110/**
111 * Sets the nth bit on. If n >= get_num_bits(), this automatically extends
112 * the array.
113 */
114INLINE void BitArray::
115set_bit(int index) {
116 nassertv(index >= 0);
117 int w = index / num_bits_per_word;
118 int b = index % num_bits_per_word;
119 if ((size_t)w >= get_num_words() && _highest_bits) {
120 // All the highest bits are already on.
121 return;
122 }
123 ensure_has_word(w);
124 _array[w].set_bit(b);
125 normalize();
126}
127
128/**
129 * Sets the nth bit off. If n >= get_num_bits(), this automatically extends
130 * the array.
131 */
132INLINE void BitArray::
133clear_bit(int index) {
134 nassertv(index >= 0);
135 int w = index / num_bits_per_word;
136 int b = index % num_bits_per_word;
137 if ((size_t)w >= get_num_words() && !_highest_bits) {
138 // All the highest bits are already off.
139 return;
140 }
141 ensure_has_word(w);
142 _array[w].clear_bit(b);
143 normalize();
144}
145
146/**
147 * Sets the nth bit either on or off, according to the indicated bool value.
148 */
149INLINE void BitArray::
150set_bit_to(int index, bool value) {
151 if (value) {
152 set_bit(index);
153 } else {
154 clear_bit(index);
155 }
156}
157
158/**
159 * Returns true if the infinite set of bits beyond get_num_bits() are all on,
160 * or false of they are all off.
161 */
162INLINE bool BitArray::
163get_highest_bits() const {
164 return (_highest_bits != 0);
165}
166
167/**
168 * Returns a word that represents only the indicated range of bits within this
169 * BitArray, shifted to the least-significant position. size must be <=
170 * get_num_bits_per_word().
171 */
172INLINE BitArray::WordType BitArray::
173extract(int low_bit, int size) const {
174 nassertr(size >= 0 && size <= num_bits_per_word, 0);
175 int w = low_bit / num_bits_per_word;
176 int b = low_bit % num_bits_per_word;
177
178 if (b + size < num_bits_per_word) {
179 // The whole thing fits within one word of the array.
180 return get_word(w).extract(b, size);
181
182 } else {
183 // We have to split it across two words.
184 int num_lower_bits = num_bits_per_word - b;
185 int num_higher_bits = size - num_lower_bits;
186
187 return get_word(w).extract(b, num_lower_bits) |
188 (get_word(w + 1).extract(0, num_higher_bits) << num_lower_bits);
189 }
190}
191
192/**
193 * Stores the indicated word into the indicated range of bits with this
194 * BitArray.
195 */
196INLINE void BitArray::
197store(WordType value, int low_bit, int size) {
198 nassertv(size >= 0);
199 int w = low_bit / num_bits_per_word;
200 int b = low_bit % num_bits_per_word;
201
202 if (b + size < num_bits_per_word) {
203 // The whole thing fits within one word of the array.
204 ensure_has_word(w);
205 _array[w].store(value, b, size);
206
207 } else {
208 // We have to split it across two words.
209 int num_lower_bits = num_bits_per_word - b;
210 int num_higher_bits = size - num_lower_bits;
211
212 ensure_has_word(w + 1);
213 _array[w].store(value, b, num_lower_bits);
214 _array[w + 1].store(value >> num_lower_bits, 0, num_higher_bits);
215 }
216 normalize();
217}
218
219/**
220 * Sets the indicated range of bits to either on or off.
221 */
222INLINE void BitArray::
223set_range_to(bool value, int low_bit, int size) {
224 if (value) {
225 set_range(low_bit, size);
226 } else {
227 clear_range(low_bit, size);
228 }
229}
230
231/**
232 * Returns the number of possibly-unique words stored in the array.
233 */
234INLINE size_t BitArray::
235get_num_words() const {
236 return _array.size();
237}
238
239/**
240 * Returns the nth word in the array. It is valid for n to be greater than
241 * get_num_words(), but the return value beyond get_num_words() will always be
242 * the same.
243 */
244INLINE BitArray::MaskType BitArray::
245get_word(size_t n) const {
246 nassertr(n >= 0, MaskType::all_off());
247 if (n < get_num_words()) {
248 return _array[n];
249 }
250 if (_highest_bits) {
251 return MaskType::all_on();
252 } else {
253 return MaskType::all_off();
254 }
255}
256
257/**
258 * Replaces the nth word in the array. If n >= get_num_words(), this
259 * automatically extends the array.
260 */
261INLINE void BitArray::
262set_word(size_t n, WordType value) {
263 ensure_has_word(n);
264 _array[n] = value;
265 normalize();
266}
267
268/**
269 * Sets all the bits in the BitArray off.
270 */
272clear() {
273 _array.clear();
274 _highest_bits = 0;
275}
276
277/**
278 *
279 */
280INLINE bool BitArray::
281operator == (const BitArray &other) const {
282 return compare_to(other) == 0;
283}
284
285/**
286 *
287 */
288INLINE bool BitArray::
289operator != (const BitArray &other) const {
290 return compare_to(other) != 0;
291}
292
293/**
294 * Returns true if the unsigned integer which is represented by this BitArray
295 * is less than that of the other one, false otherwise.
296 */
297INLINE bool BitArray::
298operator < (const BitArray &other) const {
299 return compare_to(other) < 0;
300}
301
302/**
303 *
304 */
305INLINE BitArray BitArray::
306operator & (const BitArray &other) const {
307 BitArray result(*this);
308 result &= other;
309 return result;
310}
311
312/**
313 *
314 */
315INLINE BitArray BitArray::
316operator | (const BitArray &other) const {
317 BitArray result(*this);
318 result |= other;
319 return result;
320}
321
322/**
323 *
324 */
325INLINE BitArray BitArray::
326operator ^ (const BitArray &other) const {
327 BitArray result(*this);
328 result ^= other;
329 return result;
330}
331
332/**
333 *
334 */
335INLINE BitArray BitArray::
336operator ~ () const {
337 BitArray result(*this);
338 result.invert_in_place();
339 return result;
340}
341
342/**
343 *
344 */
345INLINE BitArray BitArray::
346operator << (int shift) const {
347 BitArray result(*this);
348 result <<= shift;
349 return result;
350}
351
352/**
353 *
354 */
355INLINE BitArray BitArray::
356operator >> (int shift) const {
357 BitArray result(*this);
358 result >>= shift;
359 return result;
360}
361
362/**
363 * Called internally just before writing to the _array member, this makes a
364 * new copy of _array if it appears to be shared with any other objects--thus
365 * achieving copy-on-write.
366 */
367INLINE void BitArray::
368copy_on_write() {
369 if (_array.get_ref_count() > 1) {
370 PTA(MaskType) new_array;
371 new_array.v() = _array.v();
372 _array = new_array;
373 }
374}
A dynamic array with an unlimited number of bits.
Definition bitArray.h:40
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 bitArray.I:163
void clear_bit(int index)
Sets the nth bit off.
Definition bitArray.I:133
void set_bit_to(int index, bool value)
Sets the nth bit either on or off, according to the indicated bool value.
Definition bitArray.I:150
void set_word(size_t n, WordType value)
Replaces the nth word in the array.
Definition bitArray.I:262
MaskType get_word(size_t n) const
Returns the nth word in the array.
Definition bitArray.I:245
int compare_to(const BitArray &other) const
Returns a number less than zero if this BitArray sorts before the indicated other BitArray,...
Definition bitArray.cxx:582
static BitArray all_off()
Returns a BitArray whose bits are all off.
Definition bitArray.I:47
size_t get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition bitArray.I:89
static BitArray lower_on(int on_bits)
Returns a BitArray whose lower on_bits bits are on.
Definition bitArray.I:55
void set_range(int low_bit, int size)
Sets the indicated range of bits on.
Definition bitArray.cxx:195
bool operator<(const BitArray &other) const
Returns true if the unsigned integer which is represented by this BitArray is less than that of the o...
Definition bitArray.I:298
void clear()
Sets all the bits in the BitArray off.
Definition bitArray.I:272
static BitArray range(int low_bit, int size)
Returns a BitArray whose size bits, beginning at low_bit, are on.
Definition bitArray.I:75
void set_bit(int index)
Sets the nth bit on.
Definition bitArray.I:115
static BitArray all_on()
Returns a BitArray with an infinite array of bits, all on.
Definition bitArray.I:37
WordType extract(int low_bit, int size) const
Returns a word that represents only the indicated range of bits within this BitArray,...
Definition bitArray.I:173
void store(WordType value, int low_bit, int size)
Stores the indicated word into the indicated range of bits with this BitArray.
Definition bitArray.I:197
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition bitArray.I:99
void set_range_to(bool value, int low_bit, int size)
Sets the indicated range of bits to either on or off.
Definition bitArray.I:223
static BitArray bit(int index)
Returns a BitArray with only the indicated bit on.
Definition bitArray.I:65
void clear_range(int low_bit, int size)
Sets the indicated range of bits off.
Definition bitArray.cxx:245
size_t get_num_words() const
Returns the number of possibly-unique words stored in the array.
Definition bitArray.I:235