Regina Calculation Engine
|
A small but extremely fast bitmask class that can store up to 8 * sizeof(T) + 8 * sizeof(U) true-or-false bits. More...
#include <utilities/nbitmask.h>
Public Member Functions | |
NBitmask2 () | |
Creates a new bitmask with all bits set to false . | |
NBitmask2 (unsigned) | |
Creates a new bitmask with all bits set to false . | |
NBitmask2 (const NBitmask2< T, U > &cloneMe) | |
Creates a clone of the given bitmask. | |
void | reset () |
Sets all bits of this bitmask to false . | |
void | reset (unsigned) |
Sets all bits of this bitmask to false . | |
NBitmask2< T, U > & | operator= (const NBitmask2< T, U > &other) |
Sets this bitmask to a copy of the given bitmask. | |
void | truncate (unsigned numBits) |
Leaves the first numBits bits of this bitmask intact, but sets all subsequent bits to false . | |
bool | get (unsigned index) const |
Returns the value of the given bit of this bitmask. | |
void | set (unsigned index, bool value) |
Sets the given bit of this bitmask to the given value. | |
template<typename ForwardIterator > | |
void | set (ForwardIterator indexBegin, ForwardIterator indexEnd, bool value) |
Sets all bits in the given sorted list to the given value. | |
NBitmask2< T, U > & | operator&= (const NBitmask2< T, U > &other) |
Sets this to the intersection of this and the given bitmask. | |
NBitmask2< T, U > & | operator|= (const NBitmask2< T, U > &other) |
Sets this to the union of this and the given bitmask. | |
NBitmask2< T, U > & | operator^= (const NBitmask2< T, U > &other) |
Sets this to the exclusive disjunction (XOR) of this and the given bitmask. | |
NBitmask2< T, U > & | operator-= (const NBitmask2< T, U > &other) |
Sets this to the set difference of this and the given bitmask. | |
void | flip () |
Negates every bit in this bitmask. | |
bool | operator== (const NBitmask2< T, U > &other) const |
Determines whether this and the given bitmask are identical. | |
bool | lessThan (const NBitmask2< T, U > &other) const |
Determines whether this bitmask appears strictly before the given bitmask when bitmasks are sorted in lexicographical order. | |
bool | operator<= (const NBitmask2< T, U > &other) const |
Determines whether this bitmask is entirely contained within the given bitmask. | |
bool | inUnion (const NBitmask2< T, U > &x, const NBitmask2< T, U > &y) const |
Determines whether this bitmask is entirely contained within the union of the two given bitmasks. | |
bool | containsIntn (const NBitmask2< T, U > &x, const NBitmask2< T, U > &y) const |
Determines whether this bitmask contains the intersection of the two given bitmasks. | |
unsigned | bits () const |
Returns the number of bits currently set to true in this bitmask. | |
int | firstBit () const |
Returns the index of the first true bit in this bitmask, or -1 if there are no true bits. | |
int | lastBit () const |
Returns the index of the last true bit in this bitmask, or -1 if there are no true bits. | |
bool | atMostOneBit () const |
Determines whether at most one bit is set to true in this bitmask. | |
Friends | |
template<typename X , typename Y > | |
std::ostream & | operator<< (std::ostream &out, const NBitmask2< X, Y > &mask) |
A small but extremely fast bitmask class that can store up to 8 * sizeof(T) + 8 * sizeof(U) true-or-false bits.
This bitmask packs all of the bits together into a single variable of type T and a single variable of type U. This means that operations on entire bitmasks are extremely fast, because all of the bits can be processed in just two "native" operations.
The downside of course is that the number of bits that can be stored is limited to 8 * sizeof(T) + 8 * sizeof(U), where T and U must be native unsigned integer types (such as unsigned char, unsigned int, or unsigned long long).
For an even faster bitmask class that can only store half as many bits, see NBitmask1. For a bitmask class that can store arbitrarily many bits, see NBitmask.
regina::NBitmask2< T, U >::NBitmask2 | ( | ) | [inline] |
Creates a new bitmask with all bits set to false
.
regina::NBitmask2< T, U >::NBitmask2 | ( | unsigned | ) | [inline] |
Creates a new bitmask with all bits set to false
.
The integer argument is merely for compatibility with the NBitmask constructor, and will be ignored.
regina::NBitmask2< T, U >::NBitmask2 | ( | const NBitmask2< T, U > & | cloneMe | ) | [inline] |
Creates a clone of the given bitmask.
cloneMe | the bitmask to clone. |
bool regina::NBitmask2< T, U >::atMostOneBit | ( | ) | const [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
. unsigned regina::NBitmask2< T, U >::bits | ( | ) | const [inline] |
Returns the number of bits currently set to true
in this bitmask.
true
bits. bool regina::NBitmask2< T, U >::containsIntn | ( | const NBitmask2< T, U > & | x, |
const NBitmask2< T, U > & | y | ||
) | const [inline] |
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. int regina::NBitmask2< T, U >::firstBit | ( | ) | const [inline] |
Returns the index of the first true
bit in this bitmask, or -1 if there are no true
bits.
true
bit. void regina::NBitmask2< T, U >::flip | ( | ) | [inline] |
Negates every bit in this bitmask.
All true
bits will be set to false
and vice versa.
Unlike the more generic NBitmask, this optimised bitmask class does not store a length. This means that all 8 * sizeof(T) + 8 * sizeof(U) possible bits will be negated.
bool regina::NBitmask2< T, U >::get | ( | unsigned | index | ) | const [inline] |
Returns the value of the given bit of this bitmask.
index | indicates which bit to query; this must be between 0 and (8 * sizeof(T) + 8 * sizeof(U) - 1) inclusive. |
bool regina::NBitmask2< T, U >::inUnion | ( | const NBitmask2< T, U > & | x, |
const NBitmask2< T, U > & | y | ||
) | const [inline] |
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. int regina::NBitmask2< T, U >::lastBit | ( | ) | const [inline] |
Returns the index of the last true
bit in this bitmask, or -1 if there are no true
bits.
true
bit. bool regina::NBitmask2< T, U >::lessThan | ( | const NBitmask2< T, U > & | other | ) | const [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. NBitmask2<T, U>& regina::NBitmask2< T, U >::operator&= | ( | const NBitmask2< T, U > & | other | ) | [inline] |
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. |
NBitmask2<T, U>& regina::NBitmask2< T, U >::operator-= | ( | const NBitmask2< T, U > & | other | ) | [inline] |
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. |
bool regina::NBitmask2< T, U >::operator<= | ( | const NBitmask2< T, U > & | other | ) | const [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. NBitmask2<T, U>& regina::NBitmask2< T, U >::operator= | ( | const NBitmask2< T, U > & | other | ) | [inline] |
Sets this bitmask to a copy of the given bitmask.
other | the bitmask to clone. |
bool regina::NBitmask2< T, U >::operator== | ( | const NBitmask2< T, U > & | other | ) | const [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. NBitmask2<T, U>& regina::NBitmask2< T, U >::operator^= | ( | const NBitmask2< T, U > & | other | ) | [inline] |
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. |
NBitmask2<T, U>& regina::NBitmask2< T, U >::operator|= | ( | const NBitmask2< T, U > & | other | ) | [inline] |
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. |
void regina::NBitmask2< T, U >::reset | ( | ) | [inline] |
Sets all bits of this bitmask to false
.
void regina::NBitmask2< T, U >::reset | ( | unsigned | ) | [inline] |
Sets all bits of this bitmask to false
.
The integer argument is merely for compatibility with NBitmask::reset(unsigned), and will be ignored.
void regina::NBitmask2< T, U >::set | ( | unsigned | index, |
bool | value | ||
) | [inline] |
Sets the given bit of this bitmask to the given value.
index | indicates which bit to set; this must be between 0 and (8 * sizeof(T) + 8 * sizeof(U) - 1) inclusive. |
value | the value that will be assigned to the (index)th bit. |
void regina::NBitmask2< T, U >::set | ( | ForwardIterator | indexBegin, |
ForwardIterator | indexEnd, | ||
bool | value | ||
) | [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:
std::vector<unsigned> indices;
indices.push(3); indices.push(5); indices.push(6);
bitmask.set(indices.begin(), indices.end(), true);
Likewise, the following code would set bits 1, 4 and 7 to false:
unsigned indices[3] = { 1, 4, 7 }; bitmask.set(indices, indices + 3, 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. |
void regina::NBitmask2< T, U >::truncate | ( | unsigned | numBits | ) | [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. |