Panda3D
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 
19 TypeHandle SparseArray::_type_handle;
20 
21 /**
22  *
23  */
24 SparseArray::
25 SparseArray(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  */
57 get_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  */
76 get_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  */
95 get_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  */
112 get_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  */
129 get_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  */
146 get_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  */
166 get_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  */
197 has_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  */
216 void SparseArray::
217 output(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  */
242 compare_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  */
284 void SparseArray::
285 operator &= (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  */
312 void SparseArray::
313 operator |= (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  */
339 void SparseArray::
340 operator ^= (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  */
353 void SparseArray::
354 do_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  */
431 void SparseArray::
432 do_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  */
511 bool SparseArray::
512 do_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  */
538 bool SparseArray::
539 do_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  */
558 void SparseArray::
559 do_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  */
584 void SparseArray::
585 do_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  */
596 void SparseArray::
597 do_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  */
607 void SparseArray::
608 do_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  */
623 write_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  */
637 read_datagram(DatagramIterator &scan, BamReader *manager) {
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.
Definition: sparseArray.cxx:76
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.
Definition: sparseArray.cxx:95
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.
Definition: sparseArray.I:170
int get_num_on_bits() const
Returns the number of bits that are set to 1 in the array.
Definition: sparseArray.cxx:57
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.