Panda3D
Public Member Functions | Static Public Member Functions | List of all members
SparseArray Class Reference

This class records a set of integers, where each integer is either present or not present in the set. More...

Public Member Functions

 __init__ ()
 
 __init__ (const BitArray from)
 
 __init__ (const SparseArray)
 
 clear ()
 Sets all the bits in the SparseArray off. More...
 
 clearBit (int index)
 Sets the nth bit off. More...
 
 clearRange (int low_bit, int size)
 Sets the indicated range of bits off. More...
 
int compareTo (const SparseArray other)
 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 getBit (int index)
 Returns true if the nth bit is set, false if it is cleared. More...
 
bool getHighestBits ()
 Returns true if the infinite set of bits beyond get_num_bits() are all on, or false of they are all off. More...
 
int getHighestOffBit ()
 Returns the index of the highest 0 bit in the array. More...
 
int getHighestOnBit ()
 Returns the index of the highest 1 bit in the array. More...
 
int getLowestOffBit ()
 Returns the index of the lowest 0 bit in the array. More...
 
int getLowestOnBit ()
 Returns the index of the lowest 1 bit in the array. More...
 
int getNextHigherDifferentBit (int low_bit)
 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 getNumBits ()
 Returns the current number of possibly different bits in this array. More...
 
int getNumOffBits ()
 Returns the number of bits that are set to 0 in the array. More...
 
int getNumOnBits ()
 Returns the number of bits that are set to 1 in the array. More...
 
int getNumSubranges ()
 Returns the number of separate subranges stored in the SparseArray. More...
 
int getSubrangeBegin (int n)
 Returns the first numeric element in the nth subrange. More...
 
int getSubrangeEnd (int n)
 Returns the last numeric element, plus one, in the nth subrange. More...
 
bool hasAllOf (int low_bit, int size)
 Returns true if all bits in the indicated range are set, false otherwise. More...
 
bool hasAnyOf (int low_bit, int size)
 Returns true if any bit in the indicated range is set, false otherwise. More...
 
bool hasBitsInCommon (const SparseArray other)
 Returns true if this SparseArray has any "one" bits in common with the other one, false otherwise. More...
 
 invertInPlace ()
 Inverts all the bits in the SparseArray. More...
 
bool isAllOn ()
 Returns true if the entire bitmask is one, false otherwise. More...
 
bool isInverse ()
 If this is true, the SparseArray is actually defined as a list of subranges of integers that are not in the set. More...
 
bool isZero ()
 Returns true if the entire bitmask is zero, false otherwise. More...
 
bool operator != (const SparseArray other)
 
SparseArray operator & (const SparseArray other)
 
SparseArray operator &= (const SparseArray other)
 
SparseArray operator >> (int shift)
 
SparseArray operator >>= (int shift)
 
SparseArray operator ^ (const SparseArray other)
 
SparseArray operator ^= (const SparseArray other)
 
SparseArray operator ~ ()
 
bool operator< (const SparseArray other)
 
SparseArray operator<< (int shift)
 
SparseArray operator<<= (int shift)
 
bool operator== (const SparseArray other)
 
SparseArray operator| (const SparseArray other)
 
SparseArray operator|= (const SparseArray other)
 
 output (Ostream out)
 
 setBit (int index)
 Sets the nth bit on. More...
 
 setBitTo (int index, bool value)
 Sets the nth bit either on or off, according to the indicated bool value. More...
 
 setRange (int low_bit, int size)
 Sets the indicated range of bits on. More...
 
 setRangeTo (bool value, int low_bit, int size)
 Sets the indicated range of bits to either on or off. More...
 

Static Public Member Functions

static SparseArray allOff ()
 Returns a SparseArray whose bits are all off. More...
 
static SparseArray allOn ()
 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 getClassType ()
 
static int getMaxNumBits ()
 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 hasMaxNumBits ()
 Returns true if there is a maximum number of bits that may be stored in this structure, false otherwise. More...
 
static SparseArray lowerOn (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...
 

Detailed Description

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.

Member Function Documentation

◆ __init__() [1/3]

__init__ ( )

◆ __init__() [2/3]

__init__ ( const BitArray  from)

◆ __init__() [3/3]

__init__ ( const  SparseArray)

◆ allOff()

static SparseArray allOff ( )
static

Returns a SparseArray whose bits are all off.

◆ allOn()

static SparseArray allOn ( )
static

Returns a SparseArray with an infinite array of bits, all on.

◆ bit()

static SparseArray bit ( int  index)
static

Returns a SparseArray with only the indicated bit on.

◆ clear()

clear ( )

Sets all the bits in the SparseArray off.

◆ clearBit()

clearBit ( int  index)

Sets the nth bit off.

If n >= get_num_bits(), this automatically extends the array.

◆ clearRange()

clearRange ( int  low_bit,
int  size 
)

Sets the indicated range of bits off.

◆ compareTo()

int compareTo ( const SparseArray  other)

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 <.

◆ getBit()

bool getBit ( int  index)

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.

◆ getClassType()

static TypeHandle getClassType ( )
static

◆ getHighestBits()

bool getHighestBits ( )

Returns true if the infinite set of bits beyond get_num_bits() are all on, or false of they are all off.

◆ getHighestOffBit()

int getHighestOffBit ( )

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.

◆ getHighestOnBit()

int getHighestOnBit ( )

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.

◆ getLowestOffBit()

int getLowestOffBit ( )

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.

◆ getLowestOnBit()

int getLowestOnBit ( )

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.

◆ getMaxNumBits()

static int getMaxNumBits ( )
static

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.

◆ getNextHigherDifferentBit()

int getNextHigherDifferentBit ( int  low_bit)

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.

◆ getNumBits()

int getNumBits ( )

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.

◆ getNumOffBits()

int getNumOffBits ( )

Returns the number of bits that are set to 0 in the array.

Returns -1 if there are an infinite number of 0 bits.

◆ getNumOnBits()

int getNumOnBits ( )

Returns the number of bits that are set to 1 in the array.

Returns -1 if there are an infinite number of 1 bits.

◆ getNumSubranges()

int getNumSubranges ( )

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().

◆ getSubrangeBegin()

int getSubrangeBegin ( int  n)

Returns the first numeric element in the nth subrange.

Also see is_inverse().

◆ getSubrangeEnd()

int getSubrangeEnd ( int  n)

Returns the last numeric element, plus one, in the nth subrange.

Also see is_inverse().

◆ hasAllOf()

bool hasAllOf ( int  low_bit,
int  size 
)

Returns true if all bits in the indicated range are set, false otherwise.

◆ hasAnyOf()

bool hasAnyOf ( int  low_bit,
int  size 
)

Returns true if any bit in the indicated range is set, false otherwise.

◆ hasBitsInCommon()

bool hasBitsInCommon ( const SparseArray  other)

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.

◆ hasMaxNumBits()

static bool hasMaxNumBits ( )
static

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.

◆ invertInPlace()

invertInPlace ( )

Inverts all the bits in the SparseArray.

This is equivalent to array = ~array.

◆ isAllOn()

bool isAllOn ( )

Returns true if the entire bitmask is one, false otherwise.

◆ isInverse()

bool isInverse ( )

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().

◆ isZero()

bool isZero ( )

Returns true if the entire bitmask is zero, false otherwise.

◆ lowerOn()

static SparseArray lowerOn ( int  on_bits)
static

Returns a SparseArray whose lower on_bits bits are on.

◆ operator !=()

bool operator != ( const SparseArray  other)

◆ operator &()

SparseArray operator & ( const SparseArray  other)

◆ operator &=()

SparseArray operator &= ( const SparseArray  other)

◆ operator >>()

SparseArray operator >> ( int  shift)

◆ operator >>=()

SparseArray operator >>= ( int  shift)

◆ operator ^()

SparseArray operator ^ ( const SparseArray  other)

◆ operator ^=()

SparseArray operator ^= ( const SparseArray  other)

◆ operator ~()

SparseArray operator ~ ( )

◆ operator<()

bool operator< ( const SparseArray  other)

◆ operator<<()

SparseArray operator<< ( int  shift)

◆ operator<<=()

SparseArray operator<<= ( int  shift)

◆ operator==()

bool operator== ( const SparseArray  other)

◆ operator|()

SparseArray operator| ( const SparseArray  other)

◆ operator|=()

SparseArray operator|= ( const SparseArray  other)

◆ output()

output ( Ostream  out)

◆ range()

static SparseArray range ( int  low_bit,
int  size 
)
static

Returns a SparseArray whose size bits, beginning at low_bit, are on.

◆ setBit()

setBit ( int  index)

Sets the nth bit on.

If n >= get_num_bits(), this automatically extends the array.

◆ setBitTo()

setBitTo ( int  index,
bool  value 
)

Sets the nth bit either on or off, according to the indicated bool value.

◆ setRange()

setRange ( int  low_bit,
int  size 
)

Sets the indicated range of bits on.

◆ setRangeTo()

setRangeTo ( bool  value,
int  low_bit,
int  size 
)

Sets the indicated range of bits to either on or off.