Public Types | Public Member Functions | Static Public Member Functions
BitArray Class Reference

A dynamic array with an unlimited number of bits. More...

#include "bitArray.h"

List of all members.

Public Types

enum  { num_bits_per_word = MaskType::num_bits }
typedef BitMaskNative MaskType
typedef MaskType::WordType WordType

Public Member Functions

 BitArray (WordType init_value)
 BitArray (const BitArray &copy)
 BitArray (const SparseArray &from)
void clear ()
 Sets all the bits in the BitArray off.
void clear_bit (int index)
 Sets the nth bit off.
void clear_range (int low_bit, int size)
 Sets the indicated range of bits off.
int compare_to (const BitArray &other) const
 Returns a number less than zero if this BitArray sorts before the indicated other BitArray, greater than zero if it sorts after, or 0 if they are equivalent.
WordType extract (int low_bit, int size) const
 Returns a word that represents only the indicated range of bits within this BitArray, shifted to the least-significant position.
void generate_hash (ChecksumHashGenerator &hashgen) const
 Adds the bitmask to the indicated hash generator.
bool get_bit (int index) const
 Returns true if the nth bit is set, false if it is cleared.
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.
int get_highest_off_bit () const
 Returns the index of the highest 0 bit in the array.
int get_highest_on_bit () const
 Returns the index of the highest 1 bit in the array.
int get_lowest_off_bit () const
 Returns the index of the lowest 0 bit in the array.
int get_lowest_on_bit () const
 Returns the index of the lowest 1 bit 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 value of low_bit.
int get_num_bits () const
 Returns the current number of possibly different bits in this array.
int get_num_off_bits () const
 Returns the number of bits that are set to 0 in the array.
int get_num_on_bits () const
 Returns the number of bits that are set to 1 in the array.
int get_num_words () const
 Returns the number of possibly-unique words stored in the array.
MaskType get_word (int n) const
 Returns the nth word in the array.
bool has_all_of (int low_bit, int size) const
 Returns true if all bits in the indicated range are set, false otherwise.
bool has_any_of (int low_bit, int size) const
 Returns true if any bit in the indicated range is set, false otherwise.
bool has_bits_in_common (const BitArray &other) const
 Returns true if this BitArray has any "one" bits in common with the other one, false otherwise.
void invert_in_place ()
 Inverts all the bits in the BitArray.
bool is_all_on () const
 Returns true if the entire bitmask is one, false otherwise.
bool is_zero () const
 Returns true if the entire bitmask is zero, false otherwise.
bool operator!= (const BitArray &other) const
BitArray operator& (const BitArray &other) const
void operator&= (const BitArray &other)
bool operator< (const BitArray &other) const
 Returns true if the unsigned integer which is represented by this BitArray is less than that of the other one, false otherwise.
BitArray operator<< (int shift) const
void operator<<= (int shift)
 Logical left shift.
BitArray & operator= (const BitArray &copy)
bool operator== (const BitArray &other) const
BitArray operator>> (int shift) const
void operator>>= (int shift)
 Logical right shift.
BitArray operator^ (const BitArray &other) const
void operator^= (const BitArray &other)
BitArray operator| (const BitArray &other) const
void operator|= (const BitArray &other)
BitArray operator~ () const
void output (ostream &out) const
 Writes the BitArray out as a hex number.
void output_binary (ostream &out, int spaces_every=4) const
 Writes the BitArray out as a binary number, with spaces every four bits.
void output_hex (ostream &out, int spaces_every=4) const
 Writes the BitArray out as a hexadecimal number, with spaces every four digits.
void read_datagram (DatagramIterator &scan, BamReader *manager)
 Reads the object that was previously written to a Bam file.
void set_bit (int index)
 Sets the nth bit on.
void set_bit_to (int index, bool value)
 Sets the nth bit either on or off, according to the indicated bool value.
void set_range (int low_bit, int size)
 Sets the indicated range of bits on.
void set_range_to (bool value, int low_bit, int size)
 Sets the indicated range of bits to either on or off.
void set_word (int n, MaskType value)
 Replaces the nth word in the array.
void store (WordType value, int low_bit, int size)
 Stores the indicated word into the indicated range of bits with this BitArray.
void write (ostream &out, int indent_level=0) const
 Writes the BitArray out as a binary or a hex number, according to the number of bits.
void write_datagram (BamWriter *manager, Datagram &dg) const
 Writes the contents of this object to the datagram for shipping out to a Bam file.

Static Public Member Functions

static BitArray all_off ()
 Returns a BitArray whose bits are all off.
static BitArray all_on ()
 Returns a BitArray with an infinite array of bits, all on.
static BitArray bit (int index)
 Returns a BitArray with only the indicated bit on.
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.
static int get_num_bits_per_word ()
 Returns the number of bits stored per word internally.
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.
static void init_type ()
static BitArray lower_on (int on_bits)
 Returns a BitArray whose lower on_bits bits are on.
static BitArray range (int low_bit, int size)
 Returns a BitArray whose size bits, beginning at low_bit, are on.

Detailed Description

A dynamic array with an unlimited number of bits.

This is similar to a BitMask, except it appears to contain an infinite number of bits. You can use it very much as you would use a BitMask.

Definition at line 42 of file bitArray.h.

Member Function Documentation

BitArray BitArray::all_off ( ) [inline, static]

Returns a BitArray whose bits are all off.

Definition at line 82 of file bitArray.I.

Referenced by clear_range(), get_next_higher_different_bit(), and get_word().

BitArray BitArray::all_on ( ) [inline, static]

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

Definition at line 70 of file bitArray.I.

Referenced by PartBundle::do_bind_anim(), get_word(), and set_range().

BitArray BitArray::bit ( int  index) [inline, static]

Returns a BitArray with only the indicated bit on.

Definition at line 104 of file bitArray.I.

References set_bit().

void BitArray::clear ( ) [inline]

Sets all the bits in the BitArray off.

Definition at line 409 of file bitArray.I.

void BitArray::clear_bit ( int  index) [inline]

Sets the nth bit off.

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

Definition at line 246 of file bitArray.I.

References get_num_words().

Referenced by MovingPartBase::bind_hierarchy(), MouseWatcher::do_transmit_data(), and set_bit_to().

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

Sets the indicated range of bits off.

Definition at line 258 of file bitArray.cxx.

References all_off(), and get_num_words().

Referenced by set_range_to().

int BitArray::compare_to ( const BitArray &  other) const

Returns a number less than zero if this BitArray sorts before the indicated other BitArray, 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 633 of file bitArray.cxx.

References get_num_words(), and get_word().

Referenced by operator<().

BitArray::WordType BitArray::extract ( int  low_bit,
int  size 
) const [inline]

Returns a word that represents only the indicated range of bits within this BitArray, shifted to the least-significant position.

size must be <= get_num_bits_per_word().

Definition at line 295 of file bitArray.I.

References get_word().

Referenced by output_hex().

void BitArray::generate_hash ( ChecksumHashGenerator &  hashgen) const

Adds the bitmask to the indicated hash generator.

Definition at line 926 of file bitArray.cxx.

References ChecksumHashGenerator::add_int().

bool BitArray::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 208 of file bitArray.I.

References get_highest_bits(), and get_num_words().

Referenced by PStatClientData::add_collector(), MouseWatcher::do_transmit_data(), get_next_higher_different_bit(), MouseWatcher::is_button_down(), and output_binary().

bool BitArray::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 282 of file bitArray.I.

Referenced by get_bit().

int BitArray::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 420 of file bitArray.cxx.

References get_num_words().

int BitArray::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 398 of file bitArray.cxx.

References get_num_words().

int BitArray::get_lowest_off_bit ( ) const

Returns the index of the lowest 0 bit in the array.

Returns -1 if there are no 0 bits.

Definition at line 375 of file bitArray.cxx.

References get_num_words().

int BitArray::get_lowest_on_bit ( ) const

Returns the index of the lowest 1 bit in the array.

Returns -1 if there are no 1 bits.

Definition at line 353 of file bitArray.cxx.

References get_num_words().

int BitArray::get_max_num_bits ( ) [inline, 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 BitArray has no maximum number of bits. This method is defined so generic programming algorithms can use BitMask or BitArray interchangeably.

Definition at line 164 of file bitArray.I.

int BitArray::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 446 of file bitArray.cxx.

References all_off(), get_bit(), and get_num_words().

int BitArray::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 195 of file bitArray.I.

References get_num_words().

Referenced by PStatClientData::add_collector(), MouseWatcher::do_transmit_data(), output_binary(), and output_hex().

int BitArray::get_num_bits_per_word ( ) [inline, static]

Returns the number of bits stored per word internally.

This is of interest only in that it limits the maximum number of bits that may be queried or set at once by extract() and store().

Definition at line 178 of file bitArray.I.

int BitArray::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 333 of file bitArray.cxx.

int BitArray::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 312 of file bitArray.cxx.

int BitArray::get_num_words ( ) const [inline]

Returns the number of possibly-unique words stored in the array.

Definition at line 364 of file bitArray.I.

Referenced by clear_bit(), clear_range(), compare_to(), get_bit(), get_highest_off_bit(), get_highest_on_bit(), get_lowest_off_bit(), get_lowest_on_bit(), get_next_higher_different_bit(), get_num_bits(), get_word(), has_all_of(), has_any_of(), set_bit(), and set_range().

BitArray::MaskType BitArray::get_word ( int  n) const [inline]

Returns the nth word in the array.

It is valid for n to be greater than get_num_words(), but the return value beyond get_num_words() will always be the same.

Definition at line 376 of file bitArray.I.

References all_off(), all_on(), and get_num_words().

Referenced by compare_to(), extract(), has_all_of(), and has_any_of().

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

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

Definition at line 151 of file bitArray.cxx.

References get_num_words(), get_word(), and is_all_on().

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

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

Definition at line 95 of file bitArray.cxx.

References get_num_words(), get_word(), and is_zero().

bool BitArray::has_bits_in_common ( const BitArray &  other) const

Returns true if this BitArray 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 505 of file bitArray.cxx.

bool BitArray::has_max_num_bits ( ) [inline, 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 BitArray has no maximum number of bits. This method is defined so generic programming algorithms can use BitMask or BitArray interchangeably.

Definition at line 146 of file bitArray.I.

void BitArray::invert_in_place ( )

Inverts all the bits in the BitArray.

This is equivalent to array = ~array.

Definition at line 486 of file bitArray.cxx.

bool BitArray::is_all_on ( ) const

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

Definition at line 72 of file bitArray.cxx.

Referenced by has_all_of().

bool BitArray::is_zero ( ) const

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

Definition at line 48 of file bitArray.cxx.

Referenced by has_any_of().

BitArray BitArray::lower_on ( int  on_bits) [inline, static]

Returns a BitArray whose lower on_bits bits are on.

Definition at line 92 of file bitArray.I.

References set_range().

Referenced by operator<<=(), and operator>>=().

bool BitArray::operator< ( const BitArray &  other) const [inline]

Returns true if the unsigned integer which is represented by this BitArray is less than that of the other one, false otherwise.

Definition at line 442 of file bitArray.I.

References compare_to().

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

Logical left shift.

The rightmost bits are filled in with zeroes. Since this is an infinite bit array, none of the bits on the left are lost.

Definition at line 793 of file bitArray.cxx.

References lower_on(), and operator>>=().

Referenced by operator>>=().

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

Logical right shift.

The rightmost bits are lost. Since this is an infinite bit array, there is no question of sign extension; there is no need to synthesize bits on the left.

Definition at line 861 of file bitArray.cxx.

References lower_on(), and operator<<=().

Referenced by operator<<=().

void BitArray::output ( ostream &  out) const

Writes the BitArray out as a hex number.

For a BitArray, this is always the same as output_hex(); it's too confusing for the output format to change back and forth at runtime.

Definition at line 561 of file bitArray.cxx.

References output_hex().

void BitArray::output_binary ( ostream &  out,
int  spaces_every = 4 
) const

Writes the BitArray out as a binary number, with spaces every four bits.

Definition at line 572 of file bitArray.cxx.

References get_bit(), and get_num_bits().

void BitArray::output_hex ( ostream &  out,
int  spaces_every = 4 
) const

Writes the BitArray out as a hexadecimal number, with spaces every four digits.

Definition at line 592 of file bitArray.cxx.

References extract(), and get_num_bits().

Referenced by output().

BitArray BitArray::range ( int  low_bit,
int  size 
) [inline, static]

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

Definition at line 117 of file bitArray.I.

References set_range().

void BitArray::read_datagram ( DatagramIterator &  scan,
BamReader *  manager 
)

Reads the object that was previously written to a Bam file.

Definition at line 1006 of file bitArray.cxx.

References DatagramIterator::get_uint32(), and DatagramIterator::get_uint8().

void BitArray::set_bit ( int  index) [inline]

Sets the nth bit on.

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

Definition at line 226 of file bitArray.I.

References get_num_words().

Referenced by MovingPartBase::bind_hierarchy(), bit(), MouseWatcher::do_transmit_data(), and set_bit_to().

void BitArray::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 266 of file bitArray.I.

References clear_bit(), and set_bit().

Referenced by MovingPartBase::find_bound_joints().

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

Sets the indicated range of bits on.

Definition at line 206 of file bitArray.cxx.

References all_on(), and get_num_words().

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

void BitArray::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 349 of file bitArray.I.

References clear_range(), and set_range().

void BitArray::set_word ( int  n,
MaskType  value 
) [inline]

Replaces the nth word in the array.

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

Definition at line 396 of file bitArray.I.

void BitArray::store ( WordType  value,
int  low_bit,
int  size 
) [inline]

Stores the indicated word into the indicated range of bits with this BitArray.

Definition at line 321 of file bitArray.I.

void BitArray::write ( ostream &  out,
int  indent_level = 0 
) const

Writes the BitArray out as a binary or a hex number, according to the number of bits.

Definition at line 620 of file bitArray.cxx.

void BitArray::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 990 of file bitArray.cxx.

References Datagram::add_uint32(), and Datagram::add_uint8().

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