Panda3D
|
This class records a set of integers, where each integer is either present or not present in the set. More...
#include "sparseArray.h"
Public Member Functions | |
SparseArray (const BitArray &from) | |
void | clear () |
Sets all the bits in the SparseArray off. More... | |
void | clear_bit (int index) |
Sets the nth bit off. More... | |
void | clear_range (int low_bit, int size) |
Sets the indicated range of bits off. More... | |
int | compare_to (const SparseArray &other) const |
Returns a number less than zero if this SparseArray sorts before the indicated other SparseArray, greater than zero if it sorts after, or 0 if they are equivalent. More... | |
bool | get_bit (int index) const |
Returns true if the nth bit is set, false if it is cleared. More... | |
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 off. More... | |
int | get_highest_off_bit () const |
Returns the index of the highest 0 bit in the array. More... | |
int | get_highest_on_bit () const |
Returns the index of the highest 1 bit in the array. More... | |
int | get_lowest_off_bit () const |
Returns the index of the lowest 0 bit in the array. More... | |
int | get_lowest_on_bit () const |
Returns the index of the lowest 1 bit in the array. More... | |
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 value of low_bit. More... | |
int | get_num_bits () const |
Returns the current number of possibly different bits in this array. More... | |
int | get_num_off_bits () const |
Returns the number of bits that are set to 0 in the array. More... | |
int | get_num_on_bits () const |
Returns the number of bits that are set to 1 in the array. More... | |
size_t | get_num_subranges () const |
Returns the number of separate subranges stored in the SparseArray. More... | |
int | get_subrange_begin (size_t n) const |
Returns the first numeric element in the nth subrange. More... | |
int | get_subrange_end (size_t n) const |
Returns the last numeric element, plus one, in the nth subrange. More... | |
bool | has_all_of (int low_bit, int size) const |
Returns true if all bits in the indicated range are set, false otherwise. More... | |
bool | has_any_of (int low_bit, int size) const |
Returns true if any bit in the indicated range is set, false otherwise. More... | |
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. More... | |
void | invert_in_place () |
Inverts all the bits in the SparseArray. More... | |
bool | is_all_on () const |
Returns true if the entire bitmask is one, false otherwise. More... | |
bool | is_inverse () const |
If this is true, the SparseArray is actually defined as a list of subranges of integers that are *not* in the set. More... | |
bool | is_zero () const |
Returns true if the entire bitmask is zero, false otherwise. More... | |
bool | operator!= (const SparseArray &other) const |
SparseArray | operator& (const SparseArray &other) const |
void | operator&= (const SparseArray &other) |
bool | operator< (const SparseArray &other) const |
Returns true if the unsigned integer which is represented by this SparseArray is less than that of the other one, false otherwise. More... | |
SparseArray | operator<< (int shift) const |
void | operator<<= (int shift) |
Logical left shift. More... | |
bool | operator== (const SparseArray &other) const |
SparseArray | operator>> (int shift) const |
void | operator>>= (int shift) |
Logical right shift. More... | |
SparseArray | operator^ (const SparseArray &other) const |
void | operator^= (const SparseArray &other) |
SparseArray | operator| (const SparseArray &other) const |
void | operator|= (const SparseArray &other) |
SparseArray | operator~ () const |
void | output (std::ostream &out) const |
void | read_datagram (DatagramIterator &scan, BamReader *manager) |
Reads the object that was previously written to a Bam file. More... | |
void | set_bit (int index) |
Sets the nth bit on. More... | |
void | set_bit_to (int index, bool value) |
Sets the nth bit either on or off, according to the indicated bool value. More... | |
void | set_range (int low_bit, int size) |
Sets the indicated range of bits on. More... | |
void | set_range_to (bool value, int low_bit, int size) |
Sets the indicated range of bits to either on or off. More... | |
void | write_datagram (BamWriter *manager, Datagram &dg) const |
Writes the contents of this object to the datagram for shipping out to a Bam file. More... | |
Static Public Member Functions | |
static SparseArray | all_off () |
Returns a SparseArray whose bits are all off. More... | |
static SparseArray | all_on () |
Returns a SparseArray with an infinite array of bits, all on. More... | |
static SparseArray | bit (int index) |
Returns a SparseArray with only the indicated bit on. More... | |
static TypeHandle | get_class_type () |
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 that may be stored in this structure. More... | |
static bool | has_max_num_bits () |
Returns true if there is a maximum number of bits that may be stored in this structure, false otherwise. More... | |
static void | init_type () |
static SparseArray | lower_on (int on_bits) |
Returns a SparseArray whose lower on_bits bits are on. More... | |
static SparseArray | range (int low_bit, int size) |
Returns a SparseArray whose size bits, beginning at low_bit, are on. More... | |
Friends | |
class | Extension< SparseArray > |
This class records a set of integers, where each integer is either present or not present in the set.
It is similar in principle and in interface to a BitArray (which can be thought of as a set of integers, one integer corresponding to each different bit position), but the SparseArray is implemented as a list of min/max subrange lists, rather than as a bitmask.
This makes it particularly efficient for storing sets which consist of large sections of consecutively included or consecutively excluded elements, with arbitrarily large integers, but particularly inefficient for doing boolean operations such as & or |.
Also, unlike BitArray, the SparseArray can store negative integers.
Definition at line 43 of file sparseArray.h.
|
inlinestatic |
Returns a SparseArray whose bits are all off.
Definition at line 34 of file sparseArray.I.
|
inlinestatic |
Returns a SparseArray with an infinite array of bits, all on.
Definition at line 24 of file sparseArray.I.
|
inlinestatic |
Returns a SparseArray with only the indicated bit on.
Definition at line 54 of file sparseArray.I.
|
inline |
Sets all the bits in the SparseArray off.
Definition at line 262 of file sparseArray.I.
References ordered_vector< Key, Compare, Vector >::clear().
|
inline |
Sets the nth bit off.
If n >= get_num_bits(), this automatically extends the array.
Definition at line 140 of file sparseArray.I.
|
inline |
Sets the indicated range of bits off.
Definition at line 229 of file sparseArray.I.
int SparseArray::compare_to | ( | const SparseArray & | other | ) | const |
Returns a number less than zero if this SparseArray sorts before the indicated other SparseArray, greater than zero if it sorts after, or 0 if they are equivalent.
This is based on the same ordering defined by operator <.
Definition at line 241 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::rbegin(), and ordered_vector< Key, Compare, Vector >::rend().
|
inline |
Returns true if the nth bit is set, false if it is cleared.
It is valid for n to increase beyond get_num_bits(), but the return value get_num_bits() will always be the same.
Definition at line 122 of file sparseArray.I.
|
inline |
Returns true if the infinite set of bits beyond get_num_bits() are all on, or false of they are all off.
Definition at line 161 of file sparseArray.I.
int SparseArray::get_highest_off_bit | ( | ) | const |
Returns the index of the highest 0 bit in the array.
Returns -1 if there are no 0 bits or if there an infinite number of 1 bits.
Definition at line 145 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::empty(), and ordered_vector< Key, Compare, Vector >::size().
int SparseArray::get_highest_on_bit | ( | ) | const |
Returns the index of the highest 1 bit in the array.
Returns -1 if there are no 1 bits or if there an infinite number of 1 bits.
Definition at line 128 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::empty(), and ordered_vector< Key, Compare, Vector >::size().
int SparseArray::get_lowest_off_bit | ( | ) | const |
Returns the index of the lowest 0 bit in the array.
Returns -1 if there are no 0 bits or if there are an infinite number of 1 bits.
Definition at line 111 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::empty().
int SparseArray::get_lowest_on_bit | ( | ) | const |
Returns the index of the lowest 1 bit in the array.
Returns -1 if there are no 1 bits or if there are an infinite number of 1 bits.
Definition at line 94 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::empty().
|
inlinestatic |
If get_max_num_bits() returned true, this method may be called to return the maximum number of bits that may be stored in this structure.
It is an error to call this if get_max_num_bits() return false.
It is always an error to call this method. The SparseArray has no maximum number of bits. This method is defined so generic programming algorithms can use BitMask or SparseArray interchangeably.
Definition at line 94 of file sparseArray.I.
int SparseArray::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 value of low_bit.
Returns low_bit again if all bits higher than low_bit have the same value.
This can be used to quickly iterate through all of the bits in the array.
Definition at line 165 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::begin(), ordered_vector< Key, Compare, Vector >::end(), and range().
|
inline |
Returns the current number of possibly different bits in this array.
There are actually an infinite number of bits, but every bit higher than this bit will have the same value, either 0 or 1 (see get_highest_bits()).
This number may grow and/or shrink automatically as needed.
Definition at line 107 of file sparseArray.I.
int SparseArray::get_num_off_bits | ( | ) | const |
Returns the number of bits that are set to 0 in the array.
Returns -1 if there are an infinite number of 0 bits.
Definition at line 75 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::begin(), and ordered_vector< Key, Compare, Vector >::end().
int SparseArray::get_num_on_bits | ( | ) | const |
Returns the number of bits that are set to 1 in the array.
Returns -1 if there are an infinite number of 1 bits.
Definition at line 56 of file sparseArray.cxx.
References ordered_vector< Key, Compare, Vector >::begin(), and ordered_vector< Key, Compare, Vector >::end().
|
inline |
Returns the number of separate subranges stored in the SparseArray.
You can use this limit to iterate through the subranges, calling get_subrange_begin() and get_subrange_end() for each one.
Also see is_inverse().
Definition at line 393 of file sparseArray.I.
|
inline |
Returns the first numeric element in the nth subrange.
Also see is_inverse().
Definition at line 403 of file sparseArray.I.
|
inline |
Returns the last numeric element, plus one, in the nth subrange.
Also see is_inverse().
Definition at line 414 of file sparseArray.I.
|
inline |
Returns true if all bits in the indicated range are set, false otherwise.
Definition at line 205 of file sparseArray.I.
|
inline |
Returns true if any bit in the indicated range is set, false otherwise.
Definition at line 193 of file sparseArray.I.
bool SparseArray::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.
This is equivalent to (array & other) != 0, but may be faster.
Definition at line 196 of file sparseArray.cxx.
References is_zero().
|
inlinestatic |
Returns true if there is a maximum number of bits that may be stored in this structure, false otherwise.
If this returns true, the number may be queried in get_max_num_bits().
This method always returns false. The SparseArray has no maximum number of bits. This method is defined so generic programming algorithms can use BitMask or SparseArray interchangeably.
Definition at line 80 of file sparseArray.I.
|
inline |
Inverts all the bits in the SparseArray.
This is equivalent to array = ~array.
Definition at line 254 of file sparseArray.I.
|
inline |
Returns true if the entire bitmask is one, false otherwise.
Definition at line 181 of file sparseArray.I.
References ordered_vector< Key, Compare, Vector >::empty().
|
inline |
If this is true, the SparseArray is actually defined as a list of subranges of integers that are *not* in the set.
If this is false (the default), then the subranges define the integers that *are* in the set. This affects the interpretation of the values returned by iterating through get_num_subranges().
Definition at line 381 of file sparseArray.I.
|
inline |
Returns true if the entire bitmask is zero, false otherwise.
Definition at line 169 of file sparseArray.I.
Referenced by has_bits_in_common().
|
inlinestatic |
Returns a SparseArray whose lower on_bits bits are on.
Definition at line 42 of file sparseArray.I.
|
inline |
Returns true if the unsigned integer which is represented by this SparseArray is less than that of the other one, false otherwise.
Definition at line 288 of file sparseArray.I.
|
inline |
Logical left shift.
Since negative bit positions have meaning in a SparseArray, real bit values are rotated in on the left (not necessarily zero).
Definition at line 359 of file sparseArray.I.
|
inline |
Logical right shift.
The rightmost bits become negative, but are not lost; they will reappear into the zero position if the array is later left- shifted.
Definition at line 369 of file sparseArray.I.
|
inlinestatic |
Returns a SparseArray whose size bits, beginning at low_bit, are on.
Definition at line 64 of file sparseArray.I.
Referenced by get_next_higher_different_bit(), and PT().
void SparseArray::read_datagram | ( | DatagramIterator & | scan, |
BamReader * | manager | ||
) |
Reads the object that was previously written to a Bam file.
Definition at line 636 of file sparseArray.cxx.
References DatagramIterator::get_uint32(), and ordered_vector< Key, Compare, Vector >::reserve().
|
inline |
Sets the nth bit on.
If n >= get_num_bits(), this automatically extends the array.
Definition at line 131 of file sparseArray.I.
|
inline |
Sets the nth bit either on or off, according to the indicated bool value.
Definition at line 148 of file sparseArray.I.
|
inline |
Sets the indicated range of bits on.
Definition at line 217 of file sparseArray.I.
|
inline |
Sets the indicated range of bits to either on or off.
Definition at line 241 of file sparseArray.I.
Writes the contents of this object to the datagram for shipping out to a Bam file.
Definition at line 622 of file sparseArray.cxx.
References Datagram::add_bool(), Datagram::add_int32(), Datagram::add_uint32(), ordered_vector< Key, Compare, Vector >::begin(), ordered_vector< Key, Compare, Vector >::end(), and ordered_vector< Key, Compare, Vector >::size().
Referenced by TransformBlendTable::write_datagram().