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/bitmask.h>

Public Member Functions
	Bitmask2 ()
	Creates a new bitmask with all bits set to `false`. More...

	Bitmask2 (size_t)
	Creates a new bitmask with all bits set to `false`. More...

	Bitmask2 (const Bitmask2< T, U > &src)=default
	Creates a clone of the given bitmask. More...

void	reset ()
	Sets all bits of this bitmask to `false`. More...

void	reset (size_t)
	Sets all bits of this bitmask to `false`. More...

Bitmask2< T, U > &	operator= (const Bitmask2< T, U > &other)=default
	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...

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

Bitmask2< T, U > &	operator&= (const Bitmask2< T, U > &other)
	Sets this to the intersection of this and the given bitmask. More...

Bitmask2< T, U > &	operator\|= (const Bitmask2< T, U > &other)
	Sets this to the union of this and the given bitmask. More...

Bitmask2< T, U > &	operator^= (const Bitmask2< T, U > &other)
	Sets this to the exclusive disjunction (XOR) of this and the given bitmask. More...

Bitmask2< T, U > &	operator-= (const Bitmask2< T, U > &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 Bitmask2< T, U > &other) const
	Determines whether this and the given bitmask are identical. More...

bool	operator!= (const Bitmask2< T, U > &other) const
	Determines whether this and the given bitmask are different. More...

bool	lessThan (const Bitmask2< T, U > &other) const
	Determines whether this bitmask appears strictly before the given bitmask when bitmasks are sorted in lexicographical order. More...

bool	operator<= (const Bitmask2< T, U > &other) const
	Determines whether this bitmask is entirely contained within the given bitmask. More...

bool	inUnion (const Bitmask2< T, U > &x, const Bitmask2< T, U > &y) const
	Determines whether this bitmask is entirely contained within the union of the two given bitmasks. More...

bool	containsIntn (const Bitmask2< T, U > &x, const Bitmask2< T, U > &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...

ssize_t	firstBit () const
	Returns the index of the first `true` bit in this bitmask, or -1 if there are no `true` bits. More...

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

Static Public Attributes
static constexpr bool	fixedSize = true
	A class constant indicating whether this class stores bitmasks whose sizes are fixed at compile time. More...

Detailed Description

template<typename T, typename U = T>
class regina::Bitmask2< T, U >

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 Bitmask1. For a bitmask class that can store arbitrarily many bits, see Bitmask.

These objects are small enough to pass by value and swap with std::swap(), with no need for any specialised move operations or swap functions.

Precondition: Types T and U are unsigned integral numeric types.

Python: Python does not support templates, and so instead Regina's python interface offers the classes Bitmask8, Bitmask16, Bitmask32, Bitmask64, Bitmask128, and (if the machine supports 128-bit integers) Bitmask256. Each of these will be an optimised bitmask class that can hold the corresponding number of bits, and is guaranteed to be an instance of either the C++ Bitmask1<T> class (where possible) or the C++ Bitmask2<T,U> template class (if necessary).

Constructor & Destructor Documentation

◆ Bitmask2() [1/3]

template<typename T , typename U = T>

regina::Bitmask2< T, U >::Bitmask2 ( )

inline

Creates a new bitmask with all bits set to false.

◆ Bitmask2() [2/3]

template<typename T , typename U = T>

regina::Bitmask2< T, U >::Bitmask2 ( size_t )

inline

Creates a new bitmask with all bits set to false.

The integer argument is merely for compatibility with the Bitmask constructor, and will be ignored.

Warning: This is not a constructor that initialises the bitmask to a given pattern.

◆ Bitmask2() [3/3]

template<typename T , typename U = T>

regina::Bitmask2< T, U >::Bitmask2 ( const Bitmask2< T, U > & src )

inlinedefault

Creates a clone of the given bitmask.

Parameters

src	the bitmask to clone.

Member Function Documentation

◆ atMostOneBit()

template<typename T , typename U = T>

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

Returns: true if and only if at most one bit is set to true.

◆ bits()

template<typename T , typename U = T>

size_t regina::Bitmask2< T, U >::bits ( ) const

inline

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

Returns: the number of true bits.

◆ containsIntn()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::containsIntn	(	const Bitmask2< T, U > &	x,
		const Bitmask2< 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.

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.

◆ firstBit()

template<typename T , typename U = T>

ssize_t regina::Bitmask2< T, U >::firstBit ( ) const

inline

Returns the index of the first true bit in this bitmask, or -1 if there are no true bits.

Returns: the index of the first true bit.

◆ flip()

template<typename T , typename U = T>

void regina::Bitmask2< 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 Bitmask, this optimised bitmask class does not store a length. This means that all 8 * sizeof(T) + 8 * sizeof(U) possible bits will be negated.

◆ get()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::get ( size_t index ) const

inline

Returns the value of the given bit of this bitmask.

Parameters

index indicates which bit to query; this must be between 0 and (8 * sizeof(T) + 8 * sizeof(U) - 1) inclusive.

Returns: the value of the (index)th bit.

◆ inUnion()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::inUnion	(	const Bitmask2< T, U > &	x,
		const Bitmask2< 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.

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.

◆ lastBit()

template<typename T , typename U = T>

ssize_t regina::Bitmask2< T, U >::lastBit ( ) const

inline

Returns the index of the last true bit in this bitmask, or -1 if there are no true bits.

Returns: the index of the last true bit.

◆ lessThan()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::lessThan ( const Bitmask2< 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.

Warning: We do not use < for this operation, since ≤ represents the subset operation.

Parameters

other the bitmask to compare against this.

Returns: true if and only if this is lexicographically strictly smaller than the given bitmask.

◆ operator!=()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::operator!= ( const Bitmask2< T, U > & other ) const

inline

Determines whether this and the given bitmask are different.

Parameters

other the bitmask to compare against this.

Returns: true if and only if this and the given bitmask are different.

◆ operator&=()

template<typename T , typename U = T>

Bitmask2< T, U > & regina::Bitmask2< T, U >::operator&= ( const Bitmask2< 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.

Parameters

other the bitmask to intersect with this.

Returns: a reference to this bitmask.

◆ operator-=()

template<typename T , typename U = T>

Bitmask2< T, U > & regina::Bitmask2< T, U >::operator-= ( const Bitmask2< 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.

Parameters

other the bitmask to XOR with this.

Returns: a reference to this bitmask.

◆ operator<=()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::operator<= ( const Bitmask2< 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.

Warning: This operation does not compare bitmasks lexicographically; moreover, it only describes a partial order, not a total order. To compare bitmasks lexicographically, use lessThan() instead.

Parameters

other the bitmask to compare against this.

Returns: true if and only if this bitmask is entirely contained within the given bitmask.

◆ operator=()

template<typename T , typename U = T>

Bitmask2< T, U > & regina::Bitmask2< T, U >::operator= ( const Bitmask2< T, U > & other )

default

Sets this bitmask to a copy of the given bitmask.

Parameters

other the bitmask to clone.

Returns: a reference to this bitmask.

◆ operator==()

template<typename T , typename U = T>

bool regina::Bitmask2< T, U >::operator== ( const Bitmask2< T, U > & other ) const

inline

Determines whether this and the given bitmask are identical.

Parameters

other the bitmask to compare against this.

Returns: true if and only if this and the given bitmask are identical.

◆ operator^=()

template<typename T , typename U = T>

Bitmask2< T, U > & regina::Bitmask2< T, U >::operator^= ( const Bitmask2< 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.

Parameters

other the bitmask to XOR with this.

Returns: a reference to this bitmask.

◆ operator|=()

template<typename T , typename U = T>

Bitmask2< T, U > & regina::Bitmask2< T, U >::operator|= ( const Bitmask2< 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.

Parameters

other the bitmask to union with this.

Returns: a reference to this bitmask.

◆ reset() [1/2]

template<typename T , typename U = T>

void regina::Bitmask2< T, U >::reset ( )

inline

Sets all bits of this bitmask to false.

◆ reset() [2/2]

template<typename T , typename U = T>

void regina::Bitmask2< T, U >::reset ( size_t )

inline

Sets all bits of this bitmask to false.

The integer argument is merely for compatibility with Bitmask::reset(size_t), and will be ignored.

◆ set() [1/2]

template<typename T , typename U = T>

template<typename ForwardIterator >

void regina::Bitmask2< 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.

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 between 0 and (8 * sizeof(T) + 8 * sizeof(U) - 1) inclusive.

Python: Instead of a pair of iterators, you should pass a Python list (which, as described above, must be a sorted list of indices).

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.

◆ set() [2/2]

template<typename T , typename U = T>

void regina::Bitmask2< T, U >::set	(	size_t	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 between 0 and (8 * sizeof(T) + 8 * sizeof(U) - 1) inclusive.
value	the value that will be assigned to the (index)th bit.

◆ truncate()

template<typename T , typename U = T>

void regina::Bitmask2< T, U >::truncate ( size_t 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()).

Parameters

numBits the number of bits that will not be cleared.

Member Data Documentation

◆ fixedSize

template<typename T , typename U = T>

constexpr bool regina::Bitmask2< T, U >::fixedSize = true

staticconstexpr

A class constant indicating whether this class stores bitmasks whose sizes are fixed at compile time.

For the general Bitmask class, this is false. For the highly optimised Bitmask1 and Bitmask2 template classes, this is true.

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

utilities/bitmask.h

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Bitmask2() [1/3]

◆ Bitmask2() [2/3]

◆ Bitmask2() [3/3]

Member Function Documentation

◆ atMostOneBit()

◆ bits()

◆ containsIntn()

◆ firstBit()

◆ flip()

◆ get()

◆ inUnion()

◆ lastBit()

◆ lessThan()

◆ operator!=()

◆ operator&=()

◆ operator-=()

◆ operator<=()

◆ operator=()

◆ operator==()

◆ operator^=()

◆ operator|=()

◆ reset() [1/2]

◆ reset() [2/2]

◆ set() [1/2]

◆ set() [2/2]

◆ truncate()

Member Data Documentation

◆ fixedSize