Regina Calculation Engine
|
A bitmask that can store arbitrarily many true-or-false bits.
More...
#include <utilities/bitmask.h>
Public Member Functions | |
Bitmask () | |
Creates a new invalid bitmask. More... | |
Bitmask (size_t length) | |
Creates a new bitmask of the given length with all bits set to false . More... | |
Bitmask (const Bitmask &cloneMe) | |
Creates a clone of the given bitmask. More... | |
~Bitmask () | |
Destroys this bitmask. More... | |
bool | get (size_t index) const |
Returns the value of the given bit of this bitmask. More... | |
void | set (size_t index, bool value) |
Sets the given bit of this bitmask to the given value. More... | |
template<typename ForwardIterator > | |
void | set (ForwardIterator indexBegin, ForwardIterator indexEnd, bool value) |
Sets all bits in the given sorted list to the given value. More... | |
void | reset () |
Sets all bits of this bitmask to false . More... | |
void | reset (size_t length) |
Resizes this bitmask to the given length and sets all bits to false . More... | |
Bitmask & | operator= (const Bitmask &other) |
Sets this bitmask to a copy of the given bitmask. More... | |
void | truncate (size_t numBits) |
Leaves the first numBits bits of this bitmask intact, but sets all subsequent bits to false . More... | |
Bitmask & | operator&= (const Bitmask &other) |
Sets this to the intersection of this and the given bitmask. More... | |
Bitmask & | operator|= (const Bitmask &other) |
Sets this to the union of this and the given bitmask. More... | |
Bitmask & | operator^= (const Bitmask &other) |
Sets this to the exclusive disjunction (XOR) of this and the given bitmask. More... | |
Bitmask & | operator-= (const Bitmask &other) |
Sets this to the set difference of this and the given bitmask. More... | |
void | flip () |
Negates every bit in this bitmask. More... | |
bool | operator== (const Bitmask &other) const |
Determines whether this and the given bitmask are identical. More... | |
bool | lessThan (const Bitmask &other) const |
Determines whether this bitmask appears strictly before the given bitmask when bitmasks are sorted in lexicographical order. More... | |
bool | operator<= (const Bitmask &other) const |
Determines whether this bitmask is entirely contained within the given bitmask. More... | |
bool | inUnion (const Bitmask &x, const Bitmask &y) const |
Determines whether this bitmask is entirely contained within the union of the two given bitmasks. More... | |
bool | containsIntn (const Bitmask &x, const Bitmask &y) const |
Determines whether this bitmask contains the intersection of the two given bitmasks. More... | |
size_t | bits () const |
Returns the number of bits currently set to true in this bitmask. More... | |
long | firstBit () const |
Returns the index of the first true bit in this bitmask, or -1 if there are no true bits. More... | |
long | lastBit () const |
Returns the index of the last true bit in this bitmask, or -1 if there are no true bits. More... | |
bool | atMostOneBit () const |
Determines whether at most one bit is set to true in this bitmask. More... | |
Friends | |
std::ostream & | operator<< (std::ostream &out, const Bitmask &mask) |
Writes the given bitmask to the given output stream as a sequence of zeroes and ones. More... | |
A bitmask that can store arbitrarily many true-or-false bits.
This bitmask packs the bits together, so that (unlike an array of bools) many bits can be stored in a single byte. As a result, operations on this class are fast because the CPU can work on many bits simultaneously.
Nevertheless, this class still has overhead because the bits must be allocated on the heap, and because every operation requires looping through the individual bytes. For reasonably small bitmasks, see the highly optimised Bitmask1 and Bitmask2 classes instead.
Once a bitmask is created, the only way its length (the number of bits) can be changed is by calling reset(size_t).
The length of the bitmask is not actually stored in this structure. This means that, upon construction (or reset), the length will be automatically rounded up to the next "raw unit of storage".
true
bits in the "dead space" between the intended length and the actual length, and this may have a flow-on effect for other operations (such as subset testing, bit counting and so on). Be careful!
|
inline |
Creates a new invalid bitmask.
You must call the one-argument reset(size_t) or use the assignment operator to give the bitmask a length before it can be used.
Use of this default constructor is discouraged. The only reason it exists is to support arrays and containers of bitmasks, where the bitmasks must be created in bulk and then individually assigned lengths.
|
inline |
Creates a new bitmask of the given length with all bits set to false
.
length | the number of bits stored in this bitmask; this must be at least one. |
|
inline |
Creates a clone of the given bitmask.
It is fine if the given bitmask is invalid (but in this case, the new bitmask will be invalid also). Invalid bitmasks must be assigned a length using reset(size_t) or the assignment operator.
cloneMe | the bitmask to clone. |
|
inline |
Destroys this bitmask.
|
inline |
Determines whether at most one bit is set to true
in this bitmask.
If this bitmask is entirely false
or if only one bit is set to true
, then this routine will return true
. Otherwise this routine will return false
.
true
if and only if at most one bit is set to true
.
|
inline |
Returns the number of bits currently set to true
in this bitmask.
true
bits. Determines whether this bitmask contains the intersection of the two given bitmasks.
For this routine to return true
, every bit that is set in both x and y must be set in this bitmask also.
x | the first bitmask used to form the intersection. |
y | the first bitmask used to form the intersection. |
true
if and only if this bitmask entirely contains the intersection of x and y.
|
inline |
Returns the index of the first true
bit in this bitmask, or -1 if there are no true
bits.
true
bit.
|
inline |
Negates every bit in this bitmask.
All true
bits will be set to false
and vice versa.
true
bits in the "dead space" between the intended length and the actual length. This may cause unexpected results for routines such as subset testing, bit counting and so on. Be careful!
|
inline |
Returns the value of the given bit of this bitmask.
index | indicates which bit to query; this must be at least zero and strictly less than the length of this bitmask. |
Determines whether this bitmask is entirely contained within the union of the two given bitmasks.
For this routine to return true
, every bit that is set in this bitmask must also be set in either x or y.
x | the first bitmask used to form the union. |
y | the first bitmask used to form the union. |
true
if and only if this bitmask is entirely contained within the union of x and y.
|
inline |
Returns the index of the last true
bit in this bitmask, or -1 if there are no true
bits.
true
bit.
|
inline |
Determines whether this bitmask appears strictly before the given bitmask when bitmasks are sorted in lexicographical order.
Here the bit at index 0 is least significant, and the bit at index length-1 is most significant.
other | the bitmask to compare against this. |
true
if and only if this is lexicographically strictly smaller than the given bitmask. Sets this to the intersection of this and the given bitmask.
Every bit that is unset in other will be unset in this bitmask.
other | the bitmask to intersect with this. |
Sets this to the set difference of this and the given bitmask.
Every bit that is set in other will be cleared in this bitmask.
other | the bitmask to XOR with this. |
|
inline |
Determines whether this bitmask is entirely contained within the given bitmask.
For this routine to return true
, every bit that is set in this bitmask must also be set in the given bitmask.
other | the bitmask to compare against this. |
true
if and only if this bitmask is entirely contained within the given bitmask. Sets this bitmask to a copy of the given bitmask.
If this bitmask is invalid, this assignment operator can be used to initialise it with a length.
If this bitmask has already been initialised to a different length from that of the given bitmask, the length of this bitmask will be changed accordingly.
If the given bitmask is invalid, this bitmask will become invalid also. Invalid bitmasks must be assigned a length using reset(size_t) or this assignment operator.
other | the bitmask to clone. |
|
inline |
Determines whether this and the given bitmask are identical.
other | the bitmask to compare against this. |
true
if and only if this and the given bitmask are identical. Sets this to the exclusive disjunction (XOR) of this and the given bitmask.
Every bit that is set in other will be flipped in this bitmask.
other | the bitmask to XOR with this. |
Sets this to the union of this and the given bitmask.
Every bit that is set in other will be set in this bitmask.
other | the bitmask to union with this. |
|
inline |
Sets all bits of this bitmask to false
.
|
inline |
Resizes this bitmask to the given length and sets all bits to false
.
This routine can be used to change the length (number of bits) of the bitmask if desired.
length | the number of bits to store in this bitmask; this must be at least one. |
|
inline |
Sets the given bit of this bitmask to the given value.
index | indicates which bit to set; this must be at least zero and strictly less than the length of this bitmask. |
value | the value that will be assigned to the (index)th bit. |
|
inline |
Sets all bits in the given sorted list to the given value.
This is a convenience routine for setting many bits at once. The indices of the bits to set should be sorted and stored in some container, such as a std::set or a C-style array. This routine takes iterators over this container, and sets the bits at the corresponding indices to the given value.
For example, the following code would set bits 3, 5 and 6 to true:
Likewise, the following code would set bits 1, 4 and 7 to false:
All other bits of this bitmask are unaffected by this routine.
indexBegin | the beginning of the iterator range containing the sorted indices of the bits to set. |
indexEnd | the end of the iterator range containing the sorted indices of the bits to set. |
value | the value that will be assigned to each of the corresponding bits. |
|
inline |
Leaves the first numBits bits of this bitmask intact, but sets all subsequent bits to false
.
In other words, this routine "truncates" this bitmask to the given number of bits.
This routine does not change the length of this bitmask (as passed to the contructor or to reset()).
numBits | the number of bits that will not be cleared. |
|
friend |
Writes the given bitmask to the given output stream as a sequence of zeroes and ones.
Since the length of the bitmask is not stored, the number of bits written might be greater than the length initially assigned to this bitmask (specifically, the length will be rounded up to the next "raw unit of storage").
out | the output stream to which to write. |
mask | the bitmask to write. |