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)

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

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\| (const SparseArray &other) const

void	operator\|= (const SparseArray &other)

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

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.

Definition at line 42 of file sparseArray.h.

Member Function Documentation

◆ all_off()

SparseArray SparseArray::all_off ( )

inlinestatic

Returns a SparseArray whose bits are all off.

Definition at line 35 of file sparseArray.I.

◆ all_on()

SparseArray SparseArray::all_on ( )

inlinestatic

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

Definition at line 25 of file sparseArray.I.

◆ bit()

SparseArray SparseArray::bit ( int index )

inlinestatic

Returns a SparseArray with only the indicated bit on.

Definition at line 55 of file sparseArray.I.

References set_bit().

◆ clear()

void SparseArray::clear ( )

inline

Sets all the bits in the SparseArray off.

Definition at line 263 of file sparseArray.I.

References ordered_vector< Key, Compare, Vector >::clear().

◆ clear_bit()

void SparseArray::clear_bit ( int index )

inline

Sets the nth bit off.

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

Definition at line 141 of file sparseArray.I.

References clear_range().

Referenced by set_bit_to().

◆ clear_range()

void SparseArray::clear_range	(	int	low_bit,
		int	size
	)

inline

Sets the indicated range of bits off.

Definition at line 230 of file sparseArray.I.

Referenced by clear_bit(), and set_range_to().

◆ compare_to()

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 242 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::rbegin(), and ordered_vector< Key, Compare, Vector >::rend().

Referenced by operator<().

◆ get_bit()

bool SparseArray::get_bit ( int index ) const

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 123 of file sparseArray.I.

References has_any_of().

◆ get_highest_bits()

bool SparseArray::get_highest_bits ( ) const

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 162 of file sparseArray.I.

◆ get_highest_off_bit()

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 146 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::empty(), and ordered_vector< Key, Compare, Vector >::size().

◆ get_highest_on_bit()

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 129 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::empty(), and ordered_vector< Key, Compare, Vector >::size().

◆ get_lowest_off_bit()

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 112 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::empty().

◆ get_lowest_on_bit()

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 95 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::empty().

◆ get_max_num_bits()

int SparseArray::get_max_num_bits ( )

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 95 of file sparseArray.I.

◆ get_next_higher_different_bit()

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 166 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::begin(), ordered_vector< Key, Compare, Vector >::end(), and range().

◆ get_num_bits()

int SparseArray::get_num_bits ( ) const

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 108 of file sparseArray.I.

References ordered_vector< Key, Compare, Vector >::begin(), ordered_vector< Key, Compare, Vector >::empty(), and ordered_vector< Key, Compare, Vector >::size().

◆ get_num_off_bits()

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 76 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::begin(), and ordered_vector< Key, Compare, Vector >::end().

◆ get_num_on_bits()

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 57 of file sparseArray.cxx.

References ordered_vector< Key, Compare, Vector >::begin(), and ordered_vector< Key, Compare, Vector >::end().

◆ get_num_subranges()

size_t SparseArray::get_num_subranges ( ) const

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 394 of file sparseArray.I.

References ordered_vector< Key, Compare, Vector >::size().

◆ get_subrange_begin()

int SparseArray::get_subrange_begin ( size_t n ) const

inline

Returns the first numeric element in the nth subrange.

Also see is_inverse().

Definition at line 404 of file sparseArray.I.

◆ get_subrange_end()

int SparseArray::get_subrange_end ( size_t n ) const

inline

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

Also see is_inverse().

Definition at line 415 of file sparseArray.I.

◆ has_all_of()

bool SparseArray::has_all_of	(	int	low_bit,
		int	size
	)		const

inline

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

Definition at line 206 of file sparseArray.I.

◆ has_any_of()

bool SparseArray::has_any_of	(	int	low_bit,
		int	size
	)		const

inline

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

Definition at line 194 of file sparseArray.I.

Referenced by get_bit().

◆ has_bits_in_common()

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 197 of file sparseArray.cxx.

References is_zero().

◆ has_max_num_bits()

bool SparseArray::has_max_num_bits ( )

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 81 of file sparseArray.I.

◆ invert_in_place()

void SparseArray::invert_in_place ( )

inline

Inverts all the bits in the SparseArray.

This is equivalent to array = ~array.

Definition at line 255 of file sparseArray.I.

◆ is_all_on()

bool SparseArray::is_all_on ( ) const

inline

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

Definition at line 182 of file sparseArray.I.

References ordered_vector< Key, Compare, Vector >::empty().

◆ is_inverse()

bool SparseArray::is_inverse ( ) const

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 382 of file sparseArray.I.

◆ is_zero()

bool SparseArray::is_zero ( ) const

inline

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

Definition at line 170 of file sparseArray.I.

References ordered_vector< Key, Compare, Vector >::empty().

Referenced by has_bits_in_common().

◆ lower_on()

SparseArray SparseArray::lower_on ( int on_bits )

inlinestatic

Returns a SparseArray whose lower on_bits bits are on.

Definition at line 43 of file sparseArray.I.

References ordered_vector< Key, Compare, Vector >::push_back().

◆ operator >>=()

void SparseArray::operator >>= ( int shift )

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 370 of file sparseArray.I.

◆ operator<()

bool SparseArray::operator< ( const SparseArray & other ) const

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 289 of file sparseArray.I.

References compare_to().

◆ operator<<=()

void SparseArray::operator<<= ( int shift )

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 360 of file sparseArray.I.

◆ range()

SparseArray SparseArray::range	(	int	low_bit,
		int	size
	)

inlinestatic

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

Definition at line 65 of file sparseArray.I.

References set_range().

Referenced by get_next_higher_different_bit(), and PT().

◆ read_datagram()

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

◆ set_bit()

void SparseArray::set_bit ( int index )

inline

Sets the nth bit on.

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

Definition at line 132 of file sparseArray.I.

References set_range().

Referenced by bit(), and set_bit_to().

◆ set_bit_to()

void SparseArray::set_bit_to	(	int	index,
		bool	value
	)

inline

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

Definition at line 149 of file sparseArray.I.

References clear_bit(), and set_bit().

◆ set_range()

void SparseArray::set_range	(	int	low_bit,
		int	size
	)

inline

Sets the indicated range of bits on.

Definition at line 218 of file sparseArray.I.

Referenced by range(), set_bit(), and set_range_to().

◆ set_range_to()

void SparseArray::set_range_to	(	bool	value,
		int	low_bit,
		int	size
	)

inline

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

Definition at line 242 of file sparseArray.I.

References clear_range(), and set_range().

◆ write_datagram()

void SparseArray::write_datagram	(	BamWriter *	manager,
		Datagram &	dg
	)		const

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

The documentation for this class was generated from the following files:

panda/src/putil/sparseArray.h
panda/src/putil/sparseArray.cxx
panda/src/putil/sparseArray.I

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ all_off()

◆ all_on()

◆ bit()

◆ clear()

◆ clear_bit()

◆ clear_range()

◆ compare_to()

◆ get_bit()

◆ get_highest_bits()

◆ get_highest_off_bit()

◆ get_highest_on_bit()

◆ get_lowest_off_bit()

◆ get_lowest_on_bit()

◆ get_max_num_bits()

◆ get_next_higher_different_bit()

◆ get_num_bits()

◆ get_num_off_bits()

◆ get_num_on_bits()

◆ get_num_subranges()

◆ get_subrange_begin()

◆ get_subrange_end()

◆ has_all_of()

◆ has_any_of()

◆ has_bits_in_common()

◆ has_max_num_bits()

◆ invert_in_place()

◆ is_all_on()

◆ is_inverse()

◆ is_zero()

◆ lower_on()

◆ operator >>=()

◆ operator<()

◆ operator<<=()

◆ range()

◆ read_datagram()

◆ set_bit()

◆ set_bit_to()

◆ set_range()

◆ set_range_to()

◆ write_datagram()