![]() |
|
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. | |
| TfCompressedBits & | operator= (const TfCompressedBits &rhs) |
| Assignment operator. | |
| TfCompressedBits & | operator= (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. | |
| TfCompressedBits & | operator&= (const TfCompressedBits &rhs) |
Ands these bits with the rhs bits. | |
| TfCompressedBits | operator& (const TfCompressedBits &rhs) const |
Returns these bits and'ed with rhs. | |
| TfCompressedBits & | operator|= (const TfCompressedBits &rhs) |
Ors these bits with the rhs bits. | |
| TfCompressedBits | operator| (const TfCompressedBits &rhs) const |
Returns these bits or'ed with the rhs. | |
| TfCompressedBits & | operator^= (const TfCompressedBits &rhs) |
Xors these bits with the rhs bits. | |
| TfCompressedBits | operator^ (const TfCompressedBits &rhs) const |
Returns these bits xor'ed with rhs. | |
| TfCompressedBits & | operator-= (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. | |
| TfCompressedBits & | Complement () |
| Flips all bits. | |
| bool | operator[] (size_t index) const |
Returns bit at index. | |
| TfCompressedBits & | operator>>= (size_t bits) |
| Shifts to the right (see ShiftRight) | |
| TfCompressedBits | operator>> (size_t bits) const |
| Returns bits shifted to the right. | |
| TfCompressedBits & | operator<<= (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 TfCompressedBits & | GetEmpty () |
| Returns an empty TfBits. | |
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.
| 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.
| 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.
Returns an iteratable view for the bits that steps over all bits.
Definition at line 1399 of file compressedBits.h.
| 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.
| enum ComplementTagType |
Copy-construct a fixed sized bit array, from the complement of the rhs bitset.
Definition at line 375 of file compressedBits.h.
|
strong |
Definition at line 275 of file compressedBits.h.
|
inlineexplicit |
Constructs a fixed size bit array, clears all bits.
Definition at line 321 of file compressedBits.h.
|
inlineexplicit |
Constructs a fixed size bit array, with a range of bits set.
Definition at line 329 of file compressedBits.h.
|
inline |
Copy-constructs a fixed size bit array.
Definition at line 367 of file compressedBits.h.
|
inline |
Definition at line 376 of file compressedBits.h.
|
explicit |
Construct a TfCompressedBits array from a TfBits array.
|
inline |
Move Constructor.
Definition at line 392 of file compressedBits.h.
|
inline |
Destructor.
Definition at line 403 of file compressedBits.h.
|
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.
|
inline |
Returns true, if all the bits in this bit array are set.
Definition at line 897 of file compressedBits.h.
|
inline |
Returns true, if all the bits in this bit array are unset.
Definition at line 903 of file compressedBits.h.
|
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.
|
inline |
Assigns val to bit # index.
Definition at line 571 of file compressedBits.h.
|
inline |
Clears bit # index to zero.
Note: This is a slow operation on TfCompressedBits!
Definition at line 511 of file compressedBits.h.
|
inline |
Clears all bits to zero.
Definition at line 485 of file compressedBits.h.
|
inline |
Flips all bits.
The resulting bit set is the complement of this bit set.
Definition at line 1223 of file compressedBits.h.
|
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.
|
inline |
Count the bits set, and also return the largest gap between bits.
Definition at line 792 of file compressedBits.h.
|
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.
|
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.
|
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.
|
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.
|
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.
|
inline |
Returns the amount of memory this object holds on to.
Definition at line 934 of file compressedBits.h.
|
inline |
Definition at line 1922 of file compressedBits.h.
|
inline |
Definition at line 1928 of file compressedBits.h.
|
inline |
Definition at line 1916 of file compressedBits.h.
| TF_API std::string GetAsRLEString | ( | ) | const |
Returns a string representing the bits for debugging with bits represented in run-length encoding form.
| 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.
|
inlinestatic |
Returns an empty TfBits.
Definition at line 1382 of file compressedBits.h.
|
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.
| TF_API size_t GetHash | ( | ) | const |
Returns a hash for this instance.
|
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.
|
inline |
Returns the number of platforms (zeros or ones) in this bitset.
Definition at line 865 of file compressedBits.h.
|
inline |
Returns the number of bits currently set in this array.
Definition at line 855 of file compressedBits.h.
|
inline |
Returns the number of set (ones) platforms in this bitset.
Definition at line 875 of file compressedBits.h.
|
inline |
Returns the number of unset (zeros) platforms in this bitset.
Definition at line 886 of file compressedBits.h.
|
inline |
Definition at line 1934 of file compressedBits.h.
|
inline |
Returns the size of the bit array, ie.
the # of bits it can hold.
Definition at line 814 of file compressedBits.h.
|
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.
|
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.
|
inline |
Returns true, if there is at least a single set bit.
Definition at line 909 of file compressedBits.h.
|
inline |
Returns true, if there is at least a single unset bit.
Definition at line 915 of file compressedBits.h.
|
inline |
Returns true if this bit array is empty, i.e.
it is of size zero.
Definition at line 820 of file compressedBits.h.
|
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.
|
inline |
Returns true if this != rhs.
Definition at line 1015 of file compressedBits.h.
|
inline |
Returns these bits and'ed with rhs.
Definition at line 1066 of file compressedBits.h.
|
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.
|
inline |
Returns bits with all the bits in rhs removed from these bits.
Definition at line 1213 of file compressedBits.h.
|
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.
|
inline |
Returns bits shifted to the left.
Definition at line 1262 of file compressedBits.h.
|
inline |
Shifts to the left (see ShiftLeft)
Definition at line 1255 of file compressedBits.h.
|
inline |
Assignment operator.
Definition at line 407 of file compressedBits.h.
|
inline |
Move assignment operator.
Definition at line 421 of file compressedBits.h.
|
inline |
Returns true if this == rhs.
Definition at line 987 of file compressedBits.h.
|
inline |
Returns bits shifted to the right.
Definition at line 1247 of file compressedBits.h.
|
inline |
Shifts to the right (see ShiftRight)
Definition at line 1240 of file compressedBits.h.
|
inline |
Returns bit at index.
Note: This is a slow operation on TfCompressedBits!
Definition at line 1234 of file compressedBits.h.
|
inline |
Returns these bits xor'ed with rhs.
Definition at line 1156 of file compressedBits.h.
|
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.
|
inline |
Returns these bits or'ed with the rhs.
Definition at line 1123 of file compressedBits.h.
|
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.
|
inline |
Resize the bitset, while keeping the contents, unless trimmed.
Definition at line 438 of file compressedBits.h.
|
inline |
Sets bit # index to zero.
Note: This is a slow operation on TfCompressedBits!
Definition at line 525 of file compressedBits.h.
|
inline |
Sets all bits to one.
Definition at line 497 of file compressedBits.h.
|
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.
|
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.
|
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.
|
inline |
Provides a fast swap.
Definition at line 477 of file compressedBits.h.