Loading...
Searching...
No Matches
TfCompressedBits Class Reference

Fast, compressed bit array which is capable of performing logical operations without first decompressing the internal data representation. More...

#include <compressedBits.h>

Classes

struct  FastHash
 A hash functor for TfCompressedBits that is faster than Hash. More...
 
struct  Hash
 Hash for TfCompressedBits. More...
 
class  View
 Iterator support. More...
 

Public Types

enum class  Mode { All , AllSet , AllUnset , Platforms }
 
enum  ComplementTagType { ComplementTag }
 Copy-construct a fixed sized bit array, from the complement of the rhs bitset. More...
 
typedef View< Mode::All > AllView
 Returns an iteratable view for the bits that steps over all bits.
 
typedef View< Mode::AllSet > AllSetView
 Returns an iteratable view for the bits that steps over all set bits.
 
typedef View< Mode::AllUnset > AllUnsetView
 Returns an iteratable view for the bits that steps over all unset bits.
 
typedef View< Mode::Platforms > PlatformsView
 Returns an iteratable view for the bits that steps over all platforms.
 

Public Member Functions

 TfCompressedBits (size_t num=0)
 Constructs a fixed size bit array, clears all bits.
 
 TfCompressedBits (size_t num, size_t first, size_t last)
 Constructs a fixed size bit array, with a range of bits set.
 
 TfCompressedBits (const TfCompressedBits &rhs)
 Copy-constructs a fixed size bit array.
 
 TfCompressedBits (const TfCompressedBits &rhs, ComplementTagType)
 
TF_API TfCompressedBits (const TfBits &bits)
 Construct a TfCompressedBits array from a TfBits array.
 
 TfCompressedBits (TfCompressedBits &&rhs)
 Move Constructor.
 
 ~TfCompressedBits ()
 Destructor.
 
TfCompressedBitsoperator= (const TfCompressedBits &rhs)
 Assignment operator.
 
TfCompressedBitsoperator= (TfCompressedBits &&rhs)
 Move assignment operator.
 
void ResizeKeepContents (size_t num)
 Resize the bitset, while keeping the contents, unless trimmed.
 
void Swap (TfCompressedBits &rhs)
 Provides a fast swap.
 
void ClearAll ()
 Clears all bits to zero.
 
void SetAll ()
 Sets all bits to one.
 
void Clear (size_t index)
 Clears bit # index to zero.
 
void Set (size_t index)
 Sets bit # index to zero.
 
void SetRange (size_t first, size_t last)
 Sets the bit within the range of first and last.
 
void Append (size_t num, bool value)
 Append a number of bits with the given value to this bitset.
 
void Assign (size_t index, bool value)
 Assigns val to bit # index.
 
void ShiftRight (size_t bits)
 Shift this bitset a given number of bits to the right, and extend to the left with zeroes.
 
void ShiftLeft (size_t bits)
 Shift this bitset a given number of bits to the left, and extend the right with zeroes.
 
bool IsSet (size_t index) const
 Returns true, if bit # index is set.
 
size_t FindNthSet (size_t nth) const
 Returns the index of the n-th bit set in this bit set.
 
size_t FindNextSet (size_t index) const
 Find the next bit set that is higher or equal to index.
 
size_t FindPrevSet (size_t index) const
 Finds the next unset bit that has a higher or equal index than index.
 
size_t FindNextUnset (size_t index) const
 Finds the next unset bit that has a higher or equal index than index.
 
void Count (size_t *numSet, size_t *maxGap) const
 Count the bits set, and also return the largest gap between bits.
 
size_t GetSize () const
 Returns the size of the bit array, ie.
 
bool IsEmpty () const
 Returns true if this bit array is empty, i.e.
 
size_t GetFirstSet () const
 Returns the index of the first bit set in the bit array.
 
size_t GetLastSet () const
 Returns the index of the last bit set in the bit array.
 
size_t GetNumSet () const
 Returns the number of bits currently set in this array.
 
size_t GetNumPlatforms () const
 Returns the number of platforms (zeros or ones) in this bitset.
 
size_t GetNumSetPlatforms () const
 Returns the number of set (ones) platforms in this bitset.
 
size_t GetNumUnsetPlatforms () const
 Returns the number of unset (zeros) platforms in this bitset.
 
bool AreAllSet () const
 Returns true, if all the bits in this bit array are set.
 
bool AreAllUnset () const
 Returns true, if all the bits in this bit array are unset.
 
bool IsAnySet () const
 Returns true, if there is at least a single set bit.
 
bool IsAnyUnset () const
 Returns true, if there is at least a single unset bit.
 
bool AreContiguouslySet () const
 Returns true if the set bits in this bit array are contiguous.
 
size_t GetAllocatedSize () const
 Returns the amount of memory this object holds on to.
 
TF_API size_t GetHash () const
 Returns a hash for this instance.
 
TF_API std::string GetAsStringLeftToRight () const
 Returns a string representing the bits for debugging with bits ordered from left to right with increasing indices.
 
TF_API std::string GetAsStringRightToLeft () const
 Returns a string representing the bits for debugging with bits ordered from right to left with increasing indices.
 
TF_API std::string GetAsRLEString () const
 Returns a string representing the bits for debugging with bits represented in run-length encoding form.
 
bool HasNonEmptyIntersection (const TfCompressedBits &rhs) const
 Returns true if the result of the intersection with rhs would be non-zero.
 
bool HasNonEmptyDifference (const TfCompressedBits &rhs) const
 Returns true if the result of an asymmetric set different is non-zero.
 
bool Contains (const TfCompressedBits &rhs) const
 Returns true if this bit array contains rhs by computing: (rhs - this).GetNumSet() == 0.
 
TF_API void Decompress (TfBits *bits) const
 Decompress the bits into a TfBits array.
 
AllView GetAllView () const
 
AllSetView GetAllSetView () const
 
AllUnsetView GetAllUnsetView () const
 
PlatformsView GetPlatformsView () const
 
Operators
bool operator== (const TfCompressedBits &rhs) const
 Returns true if this == rhs.
 
bool operator!= (const TfCompressedBits &rhs) const
 Returns true if this != rhs.
 
TfCompressedBitsoperator&= (const TfCompressedBits &rhs)
 Ands these bits with the rhs bits.
 
TfCompressedBits operator& (const TfCompressedBits &rhs) const
 Returns these bits and'ed with rhs.
 
TfCompressedBitsoperator|= (const TfCompressedBits &rhs)
 Ors these bits with the rhs bits.
 
TfCompressedBits operator| (const TfCompressedBits &rhs) const
 Returns these bits or'ed with the rhs.
 
TfCompressedBitsoperator^= (const TfCompressedBits &rhs)
 Xors these bits with the rhs bits.
 
TfCompressedBits operator^ (const TfCompressedBits &rhs) const
 Returns these bits xor'ed with rhs.
 
TfCompressedBitsoperator-= (const TfCompressedBits &rhs)
 Removes all bits in the rhs bits from these bits.
 
TfCompressedBits operator- (const TfCompressedBits &rhs) const
 Returns bits with all the bits in rhs removed from these bits.
 
TfCompressedBitsComplement ()
 Flips all bits.
 
bool operator[] (size_t index) const
 Returns bit at index.
 
TfCompressedBitsoperator>>= (size_t bits)
 Shifts to the right (see ShiftRight)
 
TfCompressedBits operator>> (size_t bits) const
 Returns bits shifted to the right.
 
TfCompressedBitsoperator<<= (size_t bits)
 Shifts to the left (see ShiftLeft)
 
TfCompressedBits operator<< (size_t bits) const
 Returns bits shifted to the left.
 

Static Public Member Functions

static TF_API TfCompressedBits FromString (const std::string &source)
 Returns a bitset constructed from the supplied string representation.
 
static const TfCompressedBitsGetEmpty ()
 Returns an empty TfBits.
 

Detailed Description

Fast, compressed bit array which is capable of performing logical operations without first decompressing the internal data representation.

The internal data compression is based on a form of RLE, where words are used to indicate the number of bits set to the same value. Each subsequent word denotes that the bit value has changed and a "runningBit" is set internally, in order to denote the bit value for the first word.

Internally, a bitset like this:

111000101000

Will be represented as:

1 331113

i.e., the running bit is '1', and there are 3 of those, followed by 3 zeroes, followed by 1 one, followed by 1 zero, followed by 1 one, followed by three zeroes. Each word is called a "platform".

Compressed bits are very fast when used for logical operations (conjugate, and, or, xor, etc.), and when iterated over. Contains and Overlaps are also very fast. The representation is lightweight in memory and hence very cache efficient.

Whenever indexing, setting and resetting of seemingly random bits is a requirement, however, TfBits will perform better, since finding a specific bit requires a linear search.

Definition at line 61 of file compressedBits.h.

Member Typedef Documentation

◆ AllSetView

typedef View<Mode::AllSet> AllSetView

Returns an iteratable view for the bits that steps over all set bits.

Definition at line 1404 of file compressedBits.h.

◆ AllUnsetView

typedef View<Mode::AllUnset> AllUnsetView

Returns an iteratable view for the bits that steps over all unset bits.

Definition at line 1409 of file compressedBits.h.

◆ AllView

typedef View<Mode::All> AllView

Returns an iteratable view for the bits that steps over all bits.

Definition at line 1399 of file compressedBits.h.

◆ PlatformsView

typedef View<Mode::Platforms> PlatformsView

Returns an iteratable view for the bits that steps over all platforms.

Definition at line 1414 of file compressedBits.h.

Member Enumeration Documentation

◆ ComplementTagType

Copy-construct a fixed sized bit array, from the complement of the rhs bitset.

Definition at line 375 of file compressedBits.h.

◆ Mode

enum class Mode
strong

Definition at line 275 of file compressedBits.h.

Constructor & Destructor Documentation

◆ TfCompressedBits() [1/6]

TfCompressedBits ( size_t  num = 0)
inlineexplicit

Constructs a fixed size bit array, clears all bits.

Definition at line 321 of file compressedBits.h.

◆ TfCompressedBits() [2/6]

TfCompressedBits ( size_t  num,
size_t  first,
size_t  last 
)
inlineexplicit

Constructs a fixed size bit array, with a range of bits set.

Definition at line 329 of file compressedBits.h.

◆ TfCompressedBits() [3/6]

TfCompressedBits ( const TfCompressedBits rhs)
inline

Copy-constructs a fixed size bit array.

Definition at line 367 of file compressedBits.h.

◆ TfCompressedBits() [4/6]

TfCompressedBits ( const TfCompressedBits rhs,
ComplementTagType   
)
inline

Definition at line 376 of file compressedBits.h.

◆ TfCompressedBits() [5/6]

TF_API TfCompressedBits ( const TfBits bits)
explicit

Construct a TfCompressedBits array from a TfBits array.

◆ TfCompressedBits() [6/6]

TfCompressedBits ( TfCompressedBits &&  rhs)
inline

Move Constructor.

Definition at line 392 of file compressedBits.h.

◆ ~TfCompressedBits()

~TfCompressedBits ( )
inline

Destructor.

Definition at line 403 of file compressedBits.h.

Member Function Documentation

◆ Append()

void Append ( size_t  num,
bool  value 
)
inline

Append a number of bits with the given value to this bitset.

This also increases the size of the bitset by the number of bits added.

Definition at line 547 of file compressedBits.h.

◆ AreAllSet()

bool AreAllSet ( ) const
inline

Returns true, if all the bits in this bit array are set.

Definition at line 897 of file compressedBits.h.

◆ AreAllUnset()

bool AreAllUnset ( ) const
inline

Returns true, if all the bits in this bit array are unset.

Definition at line 903 of file compressedBits.h.

◆ AreContiguouslySet()

bool AreContiguouslySet ( ) const
inline

Returns true if the set bits in this bit array are contiguous.

Note: This returns false if there are no set bits.

Definition at line 923 of file compressedBits.h.

◆ Assign()

void Assign ( size_t  index,
bool  value 
)
inline

Assigns val to bit # index.

Definition at line 571 of file compressedBits.h.

◆ Clear()

void Clear ( size_t  index)
inline

Clears bit # index to zero.

Note: This is a slow operation on TfCompressedBits!

Definition at line 511 of file compressedBits.h.

◆ ClearAll()

void ClearAll ( )
inline

Clears all bits to zero.

Definition at line 485 of file compressedBits.h.

◆ Complement()

TfCompressedBits & Complement ( )
inline

Flips all bits.

The resulting bit set is the complement of this bit set.

Definition at line 1223 of file compressedBits.h.

◆ Contains()

bool Contains ( const TfCompressedBits rhs) const
inline

Returns true if this bit array contains rhs by computing: (rhs - this).GetNumSet() == 0.

Ie. it will return true if all bits of rhs are also set in this.

Definition at line 1376 of file compressedBits.h.

◆ Count()

void Count ( size_t *  numSet,
size_t *  maxGap 
) const
inline

Count the bits set, and also return the largest gap between bits.

Definition at line 792 of file compressedBits.h.

◆ Decompress()

TF_API void Decompress ( TfBits bits) const

Decompress the bits into a TfBits array.

◆ FindNextSet()

size_t FindNextSet ( size_t  index) const
inline

Find the next bit set that is higher or equal to index.

If no more set bits are found, index returns 'GetSize()'.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 725 of file compressedBits.h.

◆ FindNextUnset()

size_t FindNextUnset ( size_t  index) const
inline

Finds the next unset bit that has a higher or equal index than index.

If no more set bits are found, index returns 'GetSize()'.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 774 of file compressedBits.h.

◆ FindNthSet()

size_t FindNthSet ( size_t  nth) const
inline

Returns the index of the n-th bit set in this bit set.

This function counts the set bits up to the nth bit, and returns the index of that n-th set bit. If there are less than nth bits set, returns GetSize().

Note: This operation is slower than using an iterator. For forward or reverse iteration, use the iterator instead.

Definition at line 691 of file compressedBits.h.

◆ FindPrevSet()

size_t FindPrevSet ( size_t  index) const
inline

Finds the next unset bit that has a higher or equal index than index.

If no more set bits are found, index returns 'GetSize()'.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 747 of file compressedBits.h.

◆ FromString()

static TF_API TfCompressedBits FromString ( const std::string &  source)
static

Returns a bitset constructed from the supplied string representation.

The string representation can be either a RLE encoded bitset, such as '1x5-0x5-1x100', or a string of zeros and ones, such as '1111100000'. Note that whitespace anywhere in the string representation is ignored.

Any character other than whitespace, a digit, 'x' or '-' in the string representation is considered invalid. Invalid string representations will return an empty bitset. An empty string representation (or a string purely comprised of whitespace), however, is considered a valid representation describing an empty bitset.

◆ GetAllocatedSize()

size_t GetAllocatedSize ( ) const
inline

Returns the amount of memory this object holds on to.

Definition at line 934 of file compressedBits.h.

◆ GetAllSetView()

TfCompressedBits::AllSetView GetAllSetView ( ) const
inline

Definition at line 1922 of file compressedBits.h.

◆ GetAllUnsetView()

TfCompressedBits::AllUnsetView GetAllUnsetView ( ) const
inline

Definition at line 1928 of file compressedBits.h.

◆ GetAllView()

TfCompressedBits::AllView GetAllView ( ) const
inline

Definition at line 1916 of file compressedBits.h.

◆ GetAsRLEString()

TF_API std::string GetAsRLEString ( ) const

Returns a string representing the bits for debugging with bits represented in run-length encoding form.

◆ GetAsStringLeftToRight()

TF_API std::string GetAsStringLeftToRight ( ) const

Returns a string representing the bits for debugging with bits ordered from left to right with increasing indices.

◆ GetAsStringRightToLeft()

TF_API std::string GetAsStringRightToLeft ( ) const

Returns a string representing the bits for debugging with bits ordered from right to left with increasing indices.

◆ GetEmpty()

static const TfCompressedBits & GetEmpty ( )
inlinestatic

Returns an empty TfBits.

Definition at line 1382 of file compressedBits.h.

◆ GetFirstSet()

size_t GetFirstSet ( ) const
inline

Returns the index of the first bit set in the bit array.

If no bits are set, the return value is 'GetSize()'.

Definition at line 827 of file compressedBits.h.

◆ GetHash()

TF_API size_t GetHash ( ) const

Returns a hash for this instance.

◆ GetLastSet()

size_t GetLastSet ( ) const
inline

Returns the index of the last bit set in the bit array.

If no bits are set, the return value is 'GetSize()'.

Definition at line 838 of file compressedBits.h.

◆ GetNumPlatforms()

size_t GetNumPlatforms ( ) const
inline

Returns the number of platforms (zeros or ones) in this bitset.

Definition at line 865 of file compressedBits.h.

◆ GetNumSet()

size_t GetNumSet ( ) const
inline

Returns the number of bits currently set in this array.

Definition at line 855 of file compressedBits.h.

◆ GetNumSetPlatforms()

size_t GetNumSetPlatforms ( ) const
inline

Returns the number of set (ones) platforms in this bitset.

Definition at line 875 of file compressedBits.h.

◆ GetNumUnsetPlatforms()

size_t GetNumUnsetPlatforms ( ) const
inline

Returns the number of unset (zeros) platforms in this bitset.

Definition at line 886 of file compressedBits.h.

◆ GetPlatformsView()

TfCompressedBits::PlatformsView GetPlatformsView ( ) const
inline

Definition at line 1934 of file compressedBits.h.

◆ GetSize()

size_t GetSize ( ) const
inline

Returns the size of the bit array, ie.

the # of bits it can hold.

Definition at line 814 of file compressedBits.h.

◆ HasNonEmptyDifference()

bool HasNonEmptyDifference ( const TfCompressedBits rhs) const
inline

Returns true if the result of an asymmetric set different is non-zero.

This is the equivalent to computing: return (this - rhs).GetNumSet() != 0 but avoids creating temporary copies.

Definition at line 1320 of file compressedBits.h.

◆ HasNonEmptyIntersection()

bool HasNonEmptyIntersection ( const TfCompressedBits rhs) const
inline

Returns true if the result of the intersection with rhs would be non-zero.

This method can be used for efficiency because it doesn't perform the full AND operation on a copy, and it can return early.

Definition at line 1277 of file compressedBits.h.

◆ IsAnySet()

bool IsAnySet ( ) const
inline

Returns true, if there is at least a single set bit.

Definition at line 909 of file compressedBits.h.

◆ IsAnyUnset()

bool IsAnyUnset ( ) const
inline

Returns true, if there is at least a single unset bit.

Definition at line 915 of file compressedBits.h.

◆ IsEmpty()

bool IsEmpty ( ) const
inline

Returns true if this bit array is empty, i.e.

it is of size zero.

Definition at line 820 of file compressedBits.h.

◆ IsSet()

bool IsSet ( size_t  index) const
inline

Returns true, if bit # index is set.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 673 of file compressedBits.h.

◆ operator!=()

bool operator!= ( const TfCompressedBits rhs) const
inline

Returns true if this != rhs.

Definition at line 1015 of file compressedBits.h.

◆ operator&()

TfCompressedBits operator& ( const TfCompressedBits rhs) const
inline

Returns these bits and'ed with rhs.

Definition at line 1066 of file compressedBits.h.

◆ operator&=()

TfCompressedBits & operator&= ( const TfCompressedBits rhs)
inline

Ands these bits with the rhs bits.

The resulting bit set is the intersection of the two bit sets.

Definition at line 1023 of file compressedBits.h.

◆ operator-()

TfCompressedBits operator- ( const TfCompressedBits rhs) const
inline

Returns bits with all the bits in rhs removed from these bits.

Definition at line 1213 of file compressedBits.h.

◆ operator-=()

TfCompressedBits & operator-= ( const TfCompressedBits rhs)
inline

Removes all bits in the rhs bits from these bits.

The resulting bit set is the asymmetric set difference of the two bit sets.

Definition at line 1167 of file compressedBits.h.

◆ operator<<()

TfCompressedBits operator<< ( size_t  bits) const
inline

Returns bits shifted to the left.

Definition at line 1262 of file compressedBits.h.

◆ operator<<=()

TfCompressedBits & operator<<= ( size_t  bits)
inline

Shifts to the left (see ShiftLeft)

Definition at line 1255 of file compressedBits.h.

◆ operator=() [1/2]

TfCompressedBits & operator= ( const TfCompressedBits rhs)
inline

Assignment operator.

Definition at line 407 of file compressedBits.h.

◆ operator=() [2/2]

TfCompressedBits & operator= ( TfCompressedBits &&  rhs)
inline

Move assignment operator.

Definition at line 421 of file compressedBits.h.

◆ operator==()

bool operator== ( const TfCompressedBits rhs) const
inline

Returns true if this == rhs.

Definition at line 987 of file compressedBits.h.

◆ operator>>()

TfCompressedBits operator>> ( size_t  bits) const
inline

Returns bits shifted to the right.

Definition at line 1247 of file compressedBits.h.

◆ operator>>=()

TfCompressedBits & operator>>= ( size_t  bits)
inline

Shifts to the right (see ShiftRight)

Definition at line 1240 of file compressedBits.h.

◆ operator[]()

bool operator[] ( size_t  index) const
inline

Returns bit at index.

Note: This is a slow operation on TfCompressedBits!

Definition at line 1234 of file compressedBits.h.

◆ operator^()

TfCompressedBits operator^ ( const TfCompressedBits rhs) const
inline

Returns these bits xor'ed with rhs.

Definition at line 1156 of file compressedBits.h.

◆ operator^=()

TfCompressedBits & operator^= ( const TfCompressedBits rhs)
inline

Xors these bits with the rhs bits.

The resulting bit set is the union of the two bit sets minus the intersection of the two bit sets.

Definition at line 1134 of file compressedBits.h.

◆ operator|()

TfCompressedBits operator| ( const TfCompressedBits rhs) const
inline

Returns these bits or'ed with the rhs.

Definition at line 1123 of file compressedBits.h.

◆ operator|=()

TfCompressedBits & operator|= ( const TfCompressedBits rhs)
inline

Ors these bits with the rhs bits.

The resulting bit set is the union of the two bit sets.

Definition at line 1076 of file compressedBits.h.

◆ ResizeKeepContents()

void ResizeKeepContents ( size_t  num)
inline

Resize the bitset, while keeping the contents, unless trimmed.

Definition at line 438 of file compressedBits.h.

◆ Set()

void Set ( size_t  index)
inline

Sets bit # index to zero.

Note: This is a slow operation on TfCompressedBits!

Definition at line 525 of file compressedBits.h.

◆ SetAll()

void SetAll ( )
inline

Sets all bits to one.

Definition at line 497 of file compressedBits.h.

◆ SetRange()

void SetRange ( size_t  first,
size_t  last 
)
inline

Sets the bit within the range of first and last.

Note: This is a slow operation on TfCompressedBits!

Definition at line 538 of file compressedBits.h.

◆ ShiftLeft()

void ShiftLeft ( size_t  bits)
inline

Shift this bitset a given number of bits to the left, and extend the right with zeroes.

Definition at line 615 of file compressedBits.h.

◆ ShiftRight()

void ShiftRight ( size_t  bits)
inline

Shift this bitset a given number of bits to the right, and extend to the left with zeroes.

Definition at line 582 of file compressedBits.h.

◆ Swap()

void Swap ( TfCompressedBits rhs)
inline

Provides a fast swap.

Definition at line 477 of file compressedBits.h.


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