Regina Calculation Engine
Public Member Functions | Friends | List of all members
regina::Bitmask Class Reference

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...
 
Bitmaskoperator= (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...
 
Bitmaskoperator&= (const Bitmask &other)
 Sets this to the intersection of this and the given bitmask. More...
 
Bitmaskoperator|= (const Bitmask &other)
 Sets this to the union of this and the given bitmask. More...
 
Bitmaskoperator^= (const Bitmask &other)
 Sets this to the exclusive disjunction (XOR) of this and the given bitmask. More...
 
Bitmaskoperator-= (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...
 

Detailed Description

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".

Todo:
Optimise: Insist that sizeof(Piece) is a power of two, and replace expensive division/mod operations with cheap bit operations.
Warning
Because this class may increase the length of the bitmask (rounding up to the next unit of storage), bitwise computations may not give the results that you expect. In particular, flip() may set additional 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!
Python:\n Not present.

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

Copyright © 1999-2018, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).