Panda3D
Loading...
Searching...
No Matches
sparseArray.cxx
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.cxx
10 * @author drose
11 * @date 2007-02-14
12 */
13
14#include "sparseArray.h"
15#include "bitArray.h"
16#include "datagram.h"
17#include "datagramIterator.h"
18
19TypeHandle SparseArray::_type_handle;
20
21/**
22 *
23 */
24SparseArray::
25SparseArray(const BitArray &from) {
26 bool empty_bit = from.get_highest_bits();
27 _inverse = empty_bit;
28
29 size_t begin = 0;
30 bool current_state = from.get_bit(0);
31 size_t i = 0;
32
33 // By including get_num_bits()--one more than the last bit--in this
34 // traversal, we guarantee that we will end on the empty_bit state (because
35 // the last bit we visit will be one of the highest_bits).
36 while (i <= from.get_num_bits()) {
37 if (from.get_bit(i) != current_state) {
38 // End of a run.
39 if (current_state != empty_bit) {
40 Subrange range(begin, i);
41 _subranges.push_back(range);
42 }
43 begin = i;
44 current_state = !current_state;
45 }
46 ++i;
47 }
48
49 nassertv(current_state == empty_bit);
50}
51
52/**
53 * Returns the number of bits that are set to 1 in the array. Returns -1 if
54 * there are an infinite number of 1 bits.
55 */
57get_num_on_bits() const {
58 if (_inverse) {
59 return -1;
60 }
61
62 int result = 0;
63 Subranges::const_iterator si;
64 for (si = _subranges.begin(); si != _subranges.end(); ++si) {
65 result += (*si)._end - (*si)._begin;
66 }
67
68 return result;
69}
70
71/**
72 * Returns the number of bits that are set to 0 in the array. Returns -1 if
73 * there are an infinite number of 0 bits.
74 */
76get_num_off_bits() const {
77 if (!_inverse) {
78 return -1;
79 }
80
81 int result = 0;
82 Subranges::const_iterator si;
83 for (si = _subranges.begin(); si != _subranges.end(); ++si) {
84 result += (*si)._end - (*si)._begin;
85 }
86
87 return result;
88}
89
90/**
91 * Returns the index of the lowest 1 bit in the array. Returns -1 if there
92 * are no 1 bits or if there are an infinite number of 1 bits.
93 */
95get_lowest_on_bit() const {
96 if (_inverse) {
97 return -1;
98 }
99
100 if (_subranges.empty()) {
101 return -1;
102 }
103
104 return _subranges[0]._begin;
105}
106
107/**
108 * Returns the index of the lowest 0 bit in the array. Returns -1 if there
109 * are no 0 bits or if there are an infinite number of 1 bits.
110 */
112get_lowest_off_bit() const {
113 if (!_inverse) {
114 return -1;
115 }
116
117 if (_subranges.empty()) {
118 return -1;
119 }
120
121 return _subranges[0]._begin;
122}
123
124/**
125 * Returns the index of the highest 1 bit in the array. Returns -1 if there
126 * are no 1 bits or if there an infinite number of 1 bits.
127 */
129get_highest_on_bit() const {
130 if (_inverse) {
131 return -1;
132 }
133
134 if (_subranges.empty()) {
135 return -1;
136 }
137
138 return _subranges[_subranges.size() - 1]._end - 1;
139}
140
141/**
142 * Returns the index of the highest 0 bit in the array. Returns -1 if there
143 * are no 0 bits or if there an infinite number of 1 bits.
144 */
146get_highest_off_bit() const {
147 if (!_inverse) {
148 return -1;
149 }
150
151 if (_subranges.empty()) {
152 return -1;
153 }
154
155 return _subranges[_subranges.size() - 1]._end - 1;
156}
157
158/**
159 * Returns the index of the next bit in the array, above low_bit, whose value
160 * is different that the value of low_bit. Returns low_bit again if all bits
161 * higher than low_bit have the same value.
162 *
163 * This can be used to quickly iterate through all of the bits in the array.
164 */
166get_next_higher_different_bit(int low_bit) const {
167 Subrange range(low_bit, low_bit + 1);
168 Subranges::const_iterator si = _subranges.lower_bound(range);
169 if (si == _subranges.end()) {
170 // That was the end of the array.
171 return low_bit;
172 }
173
174 if (low_bit >= (*si)._begin) {
175 return (*si)._end;
176 }
177
178 int next = (*si)._begin;
179
180 if (si != _subranges.begin()) {
181 --si;
182 if (low_bit < (*si)._end) {
183 return (*si)._end;
184 }
185 }
186
187 return next;
188}
189
190/**
191 * Returns true if this SparseArray has any "one" bits in common with the
192 * other one, false otherwise.
193 *
194 * This is equivalent to (array & other) != 0, but may be faster.
195 */
197has_bits_in_common(const SparseArray &other) const {
198 if (_inverse && other._inverse) {
199 // Yup, in fact we have an infinite number of bits in common.
200 return true;
201 }
202
203 if (_inverse != other._inverse) {
204 // We'll handle this tricky case the lazy way.
205 return !(*this & other).is_zero();
206 }
207
208 // Actually, we'll handle this easy case the lazy way too. Maybe later
209 // we'll do this smarter.
210 return !(*this & other).is_zero();
211}
212
213/**
214 *
215 */
216void SparseArray::
217output(std::ostream &out) const {
218 out << "[ ";
219 if (_inverse) {
220 out << "all except: ";
221 }
222 Subranges::const_iterator si;
223 for (si = _subranges.begin(); si != _subranges.end(); ++si) {
224 if ((*si)._end == (*si)._begin + 1) {
225 // A single element.
226 out << (*si)._begin << ", ";
227 } else {
228 // A range of elements.
229 out << (*si)._begin << "-" << ((*si)._end - 1) << ", ";
230 }
231 }
232 out << "]";
233}
234
235/**
236 * Returns a number less than zero if this SparseArray sorts before the
237 * indicated other SparseArray, greater than zero if it sorts after, or 0 if
238 * they are equivalent. This is based on the same ordering defined by
239 * operator <.
240 */
242compare_to(const SparseArray &other) const {
243 if (_inverse != other._inverse) {
244 return _inverse ? 1 : -1;
245 }
246
247 Subranges::const_reverse_iterator ai = _subranges.rbegin();
248 Subranges::const_reverse_iterator bi = other._subranges.rbegin();
249
250 while (ai != _subranges.rend() && bi != other._subranges.rend()) {
251 if ((*ai)._end < (*bi)._end) {
252 // B is higher.
253 return -1;
254 } else if ((*bi)._end < (*ai)._end) {
255 // A is higher.
256 return 1;
257 } else if ((*ai)._begin < (*bi)._begin) {
258 // A is higher.
259 return 1;
260 } else if ((*bi)._begin < (*ai)._begin) {
261 // B is higher.
262 return -1;
263 }
264
265 ++ai;
266 ++bi;
267 }
268
269 if (ai != _subranges.rend()) {
270 // A is higher.
271 return 1;
272 }
273 if (bi != other._subranges.rend()) {
274 // B is higher.
275 return -1;
276 }
277
278 return 0;
279}
280
281/**
282 *
283 */
284void SparseArray::
285operator &= (const SparseArray &other) {
286 // We do this the slow and stupid way. This could be done much better with
287 // a little effort, but I'm not at all sure it's worth the effort. If you
288 // need fast boolean operations, you should probably be using a BitArray.
289
290 if (_inverse && other._inverse) {
291 do_union(other);
292
293 } else if (!_inverse && !other._inverse) {
294 do_intersection(other);
295
296 } else if (_inverse && !other._inverse) {
297 // a & b == b & a
298 (*this) = other & (*this);
299
300 } else if (!_inverse && other._inverse) {
301 do_intersection_neg(other);
302
303 } else {
304 // TODO.
305 nassertv(false);
306 }
307}
308
309/**
310 *
311 */
312void SparseArray::
313operator |= (const SparseArray &other) {
314 // We do this the slow and stupid way. This could be done much better with
315 // a little effort, but I'm not at all sure it's worth the effort. If you
316 // need fast boolean operations, you should probably be using a BitArray.
317
318 if (_inverse && other._inverse) {
319 do_intersection(other);
320
321 } else if (!_inverse && !other._inverse) {
322 do_union(other);
323
324 } else if (_inverse && !other._inverse) {
325 do_intersection_neg(other);
326
327 } else if (!_inverse && other._inverse) {
328 // a | b == b | a
329 (*this) = other | (*this);
330
331 } else {
332 nassertv(false);
333 }
334}
335
336/**
337 *
338 */
339void SparseArray::
340operator ^= (const SparseArray &other) {
341 // We do this the slow and stupid way. This could be done much better with
342 // a little effort, but I'm not at all sure it's worth the effort. If you
343 // need fast boolean operations, you should probably be using a BitArray.
344
345 (*this) = ((*this) | other) & ~((*this) & other);
346}
347
348/**
349 * Adds the consecutive range of integers beginning at begin, but not
350 * including end, to the array. If this range overlaps with another range
351 * already in the array, the result is the union.
352 */
353void SparseArray::
354do_add_range(int begin, int end) {
355 if (begin >= end) {
356 // Empty range.
357 return;
358 }
359
360 Subrange range(begin, end);
361 Subranges::iterator si = _subranges.lower_bound(range);
362 if (si == _subranges.end()) {
363 if (!_subranges.empty()) {
364 si = _subranges.begin() + _subranges.size() - 1;
365 if ((*si)._end >= begin) {
366 // The new range expands the last element of the array to the right.
367 (*si)._end = end;
368 // It might also expand it to the left; fall through.
369 } else {
370 // The new range is completely after the last element of the array.
371 _subranges.push_back(range);
372 return;
373 }
374
375 } else {
376 // The new range is completely after the last element of the array.
377 _subranges.push_back(range);
378 return;
379 }
380 }
381
382 nassertv((*si)._end >= end);
383
384 if ((*si)._begin > end) {
385 if (si != _subranges.begin()) {
386 Subranges::iterator si2 = si;
387 --si2;
388 if ((*si2)._end >= begin) {
389 // The new range expands an element within the array to the right (but
390 // does not intersect the next element).
391 (*si2)._end = end;
392 // It might also expand it to the left; fall through.
393 si = si2;
394 } else {
395 // The new range does not intersect any elements in the array.
396 _subranges.insert_unverified(si, range);
397 return;
398 }
399 } else {
400 // The new range does not intersect any elements in the array.
401 _subranges.insert_unverified(si, range);
402 return;
403 }
404 }
405
406 // Check if the new range overlaps with any elements to the left.
407 while (si != _subranges.begin()) {
408 Subranges::iterator si2 = si;
409 --si2;
410 if ((*si2)._end >= begin) {
411 // The new range straddles two elements, so they get combined.
412 (*si2)._end = (*si)._end;
413 _subranges.erase(si);
414 } else {
415 // Stop here.
416 break;
417 }
418 si = si2;
419 }
420
421 if ((*si)._begin > begin) {
422 // The new range expands an element to the left.
423 (*si)._begin = begin;
424 }
425}
426
427/**
428 * Removes the consecutive range of integers beginning at begin, but not
429 * including end, from the array.
430 */
431void SparseArray::
432do_remove_range(int begin, int end) {
433 if (begin >= end) {
434 // Empty range.
435 return;
436 }
437
438 Subrange range(begin, end);
439 Subranges::iterator si = _subranges.lower_bound(range);
440 if (si == _subranges.end()) {
441 if (!_subranges.empty()) {
442 si = _subranges.begin() + _subranges.size() - 1;
443 if ((*si)._end > begin) {
444 // The new range shortens the last element of the array on the right.
445 end = std::max(begin, (*si)._begin);
446 (*si)._end = end;
447 // It might also shorten it on the left; fall through.
448 } else {
449 // The new range is completely after the last element of the array.
450 return;
451 }
452
453 } else {
454 // The new range is completely after the last element of the array.
455 return;
456 }
457 }
458
459 nassertv((*si)._end >= end);
460
461 if ((*si)._begin > end) {
462 if (si != _subranges.begin()) {
463 Subranges::iterator si2 = si;
464 --si2;
465 if ((*si2)._end > begin) {
466 // The new range shortens an element within the array on the right
467 // (but does not intersect the next element).
468 end = std::max(begin, (*si2)._begin);
469 (*si2)._end = end;
470 // It might also shorten it on the left; fall through.
471 si = si2;
472 } else {
473 // The new range does not intersect any elements in the array.
474 return;
475 }
476 } else {
477 // The new range does not intersect any elements in the array.
478 return;
479 }
480 }
481
482
483 if (end < (*si)._end) {
484 // We must split an element into two.
485 Subrange left_range((*si)._begin, begin);
486 (*si)._begin = end;
487 si = _subranges.insert_unverified(si, left_range);
488 }
489
490 // Check if the new range removes any elements to the left.
491 while (begin <= (*si)._begin || (*si)._begin >= (*si)._end) {
492 if (si == _subranges.begin()) {
493 _subranges.erase(si);
494 return;
495 }
496 Subranges::iterator si2 = si;
497 --si2;
498 _subranges.erase(si);
499 si = si2;
500 }
501
502 (*si)._end = std::min((*si)._end, begin);
503 nassertv((*si)._end > (*si)._begin);
504}
505
506/**
507 * Returns true if any of the consecutive range of integers beginning at
508 * begin, but not including end, appear in the array. Note that this will
509 * return false for an empty range.
510 */
511bool SparseArray::
512do_has_any(int begin, int end) const {
513 if (begin >= end) {
514 // Empty range.
515 return false;
516 }
517
518 Subrange range(begin, end);
519 Subranges::const_iterator si = _subranges.lower_bound(range);
520 if (si != _subranges.end() && end > (*si)._begin) {
521 return true;
522 }
523 if (si != _subranges.begin()) {
524 --si;
525 if (begin < (*si)._end) {
526 return true;
527 }
528 }
529
530 return false;
531}
532
533/**
534 * Returns true if all of the consecutive range of integers beginning at
535 * begin, but not including end, appear in the array. Note that this will
536 * return true for an empty range.
537 */
538bool SparseArray::
539do_has_all(int begin, int end) const {
540 if (begin >= end) {
541 // Empty range.
542 return true;
543 }
544
545 Subrange range(begin, end);
546 Subranges::const_iterator si = _subranges.lower_bound(range);
547 if (si != _subranges.end() && begin >= (*si)._begin) {
548 return true;
549 }
550
551 return false;
552}
553
554/**
555 * Removes from this array all of the elements that do not appear in the other
556 * one.
557 */
558void SparseArray::
559do_intersection(const SparseArray &other) {
560 if (_subranges.empty()) {
561 return;
562 }
563 if (other._subranges.empty()) {
564 _subranges.clear();
565 return;
566 }
567
568 int my_begin = (*_subranges.begin())._begin;
569 int other_begin = (*other._subranges.begin())._begin;
570 do_remove_range(my_begin, other_begin);
571
572 for (size_t i = 0; i < other._subranges.size() - 1; ++i) {
573 do_remove_range(other._subranges[i]._end, other._subranges[i + 1]._begin);
574 }
575
576 int my_end = (*(_subranges.begin() + _subranges.size() - 1))._end;
577 int other_end = (*(other._subranges.begin() + other._subranges.size() - 1))._end;
578 do_remove_range(other_end, my_end);
579}
580
581/**
582 * Adds to this array all of the elements that also appear in the other one.
583 */
584void SparseArray::
585do_union(const SparseArray &other) {
586 Subranges::const_iterator si;
587 for (si = other._subranges.begin(); si != other._subranges.end(); ++si) {
588 do_add_range((*si)._begin, (*si)._end);
589 }
590}
591
592/**
593 * Removes from this array all of the elements that also appear in the other
594 * one.
595 */
596void SparseArray::
597do_intersection_neg(const SparseArray &other) {
598 Subranges::const_iterator si;
599 for (si = other._subranges.begin(); si != other._subranges.end(); ++si) {
600 do_remove_range((*si)._begin, (*si)._end);
601 }
602}
603
604/**
605 * Shifts all the elements in the array by the indicated amount.
606 */
607void SparseArray::
608do_shift(int offset) {
609 if (offset != 0) {
610 Subranges::iterator si;
611 for (si = _subranges.begin(); si != _subranges.end(); ++si) {
612 (*si)._begin += offset;
613 (*si)._end += offset;
614 }
615 }
616}
617
618/**
619 * Writes the contents of this object to the datagram for shipping out to a
620 * Bam file.
621 */
623write_datagram(BamWriter *manager, Datagram &dg) const {
624 dg.add_uint32(_subranges.size());
625 Subranges::const_iterator si;
626 for (si = _subranges.begin(); si != _subranges.end(); ++si) {
627 dg.add_int32((*si)._begin);
628 dg.add_int32((*si)._end);
629 }
630 dg.add_bool(_inverse);
631}
632
633/**
634 * Reads the object that was previously written to a Bam file.
635 */
638 size_t num_subranges = scan.get_uint32();
639 _subranges.reserve(num_subranges);
640 for (size_t i = 0; i < num_subranges; ++i) {
641 int begin = scan.get_int32();
642 int end = scan.get_int32();
643 _subranges.push_back(Subrange(begin, end));
644 }
645 _inverse = scan.get_bool();
646}
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition bamReader.h:110
This is the fundamental interface for writing binary objects to a Bam file, to be extracted later by ...
Definition bamWriter.h:63
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
size_t get_num_bits() const
Returns the current number of possibly different bits in this array.
Definition bitArray.I:89
bool get_bit(int index) const
Returns true if the nth bit is set, false if it is cleared.
Definition bitArray.I:99
A class to retrieve the individual data elements previously stored in a Datagram.
uint32_t get_uint32()
Extracts an unsigned 32-bit integer.
bool get_bool()
Extracts a boolean value.
int32_t get_int32()
Extracts a signed 32-bit integer.
An ordered list of data elements, formatted in memory for transmission over a socket or writing to a ...
Definition datagram.h:38
void add_uint32(uint32_t value)
Adds an unsigned 32-bit integer to the datagram.
Definition datagram.I:94
void add_int32(int32_t value)
Adds a signed 32-bit integer to the datagram.
Definition datagram.I:67
void add_bool(bool value)
Adds a boolean value to the datagram.
Definition datagram.I:34
This class records a set of integers, where each integer is either present or not present in the set.
Definition sparseArray.h:43
int get_highest_on_bit() const
Returns the index of the highest 1 bit in the array.
int get_num_off_bits() const
Returns the number of bits that are set to 0 in the array.
void write_datagram(BamWriter *manager, Datagram &dg) const
Writes the contents of this object to the datagram for shipping out to a Bam file.
void read_datagram(DatagramIterator &scan, BamReader *manager)
Reads the object that was previously written to a Bam file.
int get_lowest_on_bit() const
Returns the index of the lowest 1 bit in the array.
int get_lowest_off_bit() const
Returns the index of the lowest 0 bit in the array.
bool has_bits_in_common(const SparseArray &other) const
Returns true if this SparseArray has any "one" bits in common with the other one, false otherwise.
int compare_to(const SparseArray &other) const
Returns a number less than zero if this SparseArray sorts before the indicated other SparseArray,...
static SparseArray range(int low_bit, int size)
Returns a SparseArray whose size bits, beginning at low_bit, are on.
Definition sparseArray.I:65
int get_highest_off_bit() const
Returns the index of the highest 0 bit in the array.
bool is_zero() const
Returns true if the entire bitmask is zero, false otherwise.
int get_num_on_bits() const
Returns the number of bits that are set to 1 in the array.
int get_next_higher_different_bit(int low_bit) const
Returns the index of the next bit in the array, above low_bit, whose value is different that the valu...
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
void reserve(size_type_0 n)
Informs the vector of a planned change in size; ensures that the capacity of the vector is greater th...
reverse_iterator_0 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
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.
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
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.
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
void clear()
Removes all elements from the ordered vector.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.