regina::NBitmask Class Reference
[Utilities]

A bitmask that can store arbitrarily many true-or-false bits. More...

#include <nbitmask.h>

List of all members.

Public Member Functions

 NBitmask ()
 Creates a new invalid bitmask.
 NBitmask (unsigned length)
 Creates a new bitmask of the given length with all bits set to false.
 NBitmask (const NBitmask &cloneMe)
 Creates a clone of the given bitmask.
 ~NBitmask ()
 Destroys this bitmask.
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.
void reset ()
 Sets all bits of this bitmask to false.
void reset (unsigned length)
 Resizes this bitmask to the given length and sets all bits to false.
NBitmaskoperator&= (const NBitmask &other)
 Sets this to the intersection of this and the given bitmask.
NBitmaskoperator|= (const NBitmask &other)
 Sets this to the union of this and the given bitmask.
void flip ()
 Negates every bit in this bitmask.
bool operator== (const NBitmask &other) const
 Determines whether this and the given bitmask are identical.
bool operator<= (const NBitmask &other) const
 Determines whether this bitmask is entirely contained within the given bitmask.
bool inUnion (const NBitmask &x, const NBitmask &y) const
 Determines whether this bitmask is entirely contained within the union of the two given bitmasks.
bool containsIntn (const NBitmask &x, const NBitmask &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.
bool atMostOneBit () const
 Determines whether at most one bit is set to true in this bitmask.

Friends

std::ostream & operator<< (std::ostream &out, const NBitmask &mask)

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 NBitmask1 and NBitmask2 classes instead.

Once a bitmask is created, the only way its length (the number of bits) can be changed is by calling reset(unsigned).

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:
Not present.

Constructor & Destructor Documentation

regina::NBitmask::NBitmask (  )  [inline]

Creates a new invalid bitmask.

You must call the one-argument reset(unsigned) 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.

Warning:
No other routines can be used with this bitmask until it has been assigned a length via reset(unsigned). As the single exception, the class destructor is safe to use even if a bitmask has never been initialised.
regina::NBitmask::NBitmask ( unsigned  length  )  [inline]

Creates a new bitmask of the given length with all bits set to false.

Parameters:
length the number of bits stored in this bitmask; this must be at least one.
regina::NBitmask::NBitmask ( const NBitmask cloneMe  )  [inline]

Creates a clone of the given bitmask.

Parameters:
cloneMe the bitmask to clone.
regina::NBitmask::~NBitmask (  )  [inline]

Destroys this bitmask.


Member Function Documentation

bool regina::NBitmask::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.

Returns:
true if and only if at most one bit is set to true.
unsigned regina::NBitmask::bits (  )  const [inline]

Returns the number of bits currently set to true in this bitmask.

Returns:
the number of true bits.
bool regina::NBitmask::containsIntn ( const NBitmask x,
const NBitmask 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.

Precondition:
Both x and y are the same length as this bitmask.
Parameters:
x the first bitmask used to form the intersection.
y the first bitmask used to form the intersection.
Returns:
true if and only if this bitmask entirely contains the intersection of x and y.
void regina::NBitmask::flip (  )  [inline]

Negates every bit in this bitmask.

All true bits will be set to false and vice versa.

Warning:
Because this class may increase the bitmask length (rounding up to the next unit of storage), flip() may set additional 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!
bool regina::NBitmask::get ( unsigned  index  )  const [inline]

Returns the value of the given bit of this bitmask.

Parameters:
index indicates which bit to query; this must be at least zero and strictly less than the length of this bitmask.
Returns:
the value of the (index)th bit.
bool regina::NBitmask::inUnion ( const NBitmask x,
const NBitmask 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.

Precondition:
Both x and y are the same length as this bitmask.
Parameters:
x the first bitmask used to form the union.
y the first bitmask used to form the union.
Returns:
true if and only if this bitmask is entirely contained within the union of x and y.
NBitmask & regina::NBitmask::operator&= ( const NBitmask 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.

Precondition:
This and the given bitmask have the same length.
Parameters:
other the bitmask to intersect with this.
Returns:
a reference to this bitmask.
bool regina::NBitmask::operator<= ( const NBitmask 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.

Precondition:
This and the given bitmask have the same length.
Parameters:
other the bitmask to compare against this.
Returns:
true if and only if this bitmask is entirely contained within the given bitmask.
bool regina::NBitmask::operator== ( const NBitmask other  )  const [inline]

Determines whether this and the given bitmask are identical.

Precondition:
This and the given bitmask have the same length.
Parameters:
other the bitmask to compare against this.
Returns:
true if and only if this and the given bitmask are identical.
NBitmask & regina::NBitmask::operator|= ( const NBitmask 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.

Precondition:
This and the given bitmask have the same length.
Parameters:
other the bitmask to union with this.
Returns:
a reference to this bitmask.
void regina::NBitmask::reset ( unsigned  length  )  [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.

Parameters:
length the number of bits to store in this bitmask; this must be at least one.
void regina::NBitmask::reset (  )  [inline]

Sets all bits of this bitmask to false.

template<typename ForwardIterator >
void regina::NBitmask::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.

Precondition:
ForwardIterator is a forward iterator type that iterates over integer values.
The list of indices described by these iterators is in sorted order. This is to allow optimisations for larger bitmask types.
All indices in the given list are at least zero and strictly less than the length of this bitmask.
Parameters:
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::NBitmask::set ( unsigned  index,
bool  value 
) [inline]

Sets the given bit of this bitmask to the given value.

Parameters:
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.

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

Copyright © 1999-2009, Ben Burton
This software is released under the GNU General Public License.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).