A bit vector that is internally represented as a vector of 64-bit values. More...

#include <BitVector.h>

Classes
class	const_iterator
	A class that enables iterating over the indices of the bit vector whose corresponding bits are set to true. More...
class	const_reverse_iterator
	A class that enables iterating over the indices of the bit vector whose corresponding bits are set to true. More...

Public Member Functions
	BitVector ()
	Constructs an empty bit vector of length 0.
	~BitVector ()
	Deconstructs a bit vector by deleting the underlying storage.
	BitVector (uint64_t length, bool init=false)
	Constructs a bit vector which can hold the given number of bits and initializes all bits with the provided truth value.
template<typename InputIterator>
	BitVector (uint64_t length, InputIterator first, InputIterator last)
	Creates a bit vector that has exactly the bits set that are given by the provided input iterator range [first, last).
	BitVector (uint64_t length, std::vector< uint64_t > setEntries)
	Creates a bit vector that has exactly the bits set that are given by the vector.
	BitVector (BitVector const &other)
	Performs a deep copy of the given bit vector.
	BitVector (BitVector &&other)
	Move constructs the bit vector from the given bit vector.
bool	operator== (BitVector const &other) const
	Compares the given bit vector with the current one.
bool	operator!= (BitVector const &other) const
	Compares the given bit vector with the current one.
BitVector &	operator= (BitVector const &other)
	Assigns the contents of the given bit vector to the current bit vector via a deep copy.
BitVector &	operator= (BitVector &&other)
	Move assigns the given bit vector to the current bit vector.
bool	operator< (BitVector const &other) const
	Retrieves whether the current bit vector is (in some order) smaller than the given one.
void	set (uint64_t index, bool value=true)
	Sets the given truth value at the given index.
template<typename InputIterator>
void	set (InputIterator first, InputIterator last, bool value=true)
	Sets all bits in the given iterator range [first, last).
bool	operator[] (uint64_t index) const
	Retrieves the truth value of the bit at the given index.
bool	get (uint64_t index) const
	Retrieves the truth value of the bit at the given index and performs a bound check.
void	resize (uint64_t newLength, bool init=false)
	Resizes the bit vector to hold the given new number of bits.
void	concat (BitVector const &extension)
	Concatenate this bitvector with another bitvector.
void	expandSize (bool init=false)
void	grow (uint64_t minimumLength, bool init=false)
	Enlarges the bit vector such that it holds at least the given number of bits (but possibly more).
BitVector	operator& (BitVector const &other) const
	Performs a logical "and" with the given bit vector.
BitVector &	operator&= (BitVector const &other)
	Performs a logical "and" with the given bit vector and assigns the result to the current bit vector.
BitVector	operator\| (BitVector const &other) const
	Performs a logical "or" with the given bit vector.
BitVector &	operator\|= (BitVector const &other)
	Performs a logical "or" with the given bit vector and assigns the result to the current bit vector.
BitVector	operator^ (BitVector const &other) const
	Performs a logical "xor" with the given bit vector.
BitVector &	operator^= (BitVector const &other)
	Performs a logical "xor" with the given bit vector and assigns the result to the current bit vector.
BitVector	operator% (BitVector const &filter) const
	Computes a bit vector that contains only the values of the bits given by the filter.
BitVector	operator~ () const
	Performs a logical "not" on the bit vector.
void	complement ()
	Negates all bits in the bit vector.
void	increment ()
	Increments the (unsigned) number represented by this BitVector by one.
BitVector	implies (BitVector const &other) const
	Performs a logical "implies" with the given bit vector.
bool	isSubsetOf (BitVector const &other) const
	Checks whether all bits that are set in the current bit vector are also set in the given bit vector.
bool	isDisjointFrom (BitVector const &other) const
	Checks whether none of the bits that are set in the current bit vector are also set in the given bit vector.
bool	matches (uint64_t bitIndex, BitVector const &other) const
	Checks whether the given bit vector matches the bits starting from the given index in the current bit vector.
void	set (uint64_t bitIndex, BitVector const &other)
	Sets the exact bit pattern of the given bit vector starting at the given bit index.
void	setMultiple (uint64_t bitIndex, uint64_t nrOfBits, bool newValue=true)
	Sets multiple bits to the given value.
BitVector	permute (std::vector< uint64_t > const &inversePermutation) const
	Apply a permutation of entries.
BitVector	permuteGroupedVector (std::vector< uint64_t > const &inversePermutation, std::vector< uint64_t > const &rowGroupIndices) const
	Apply a permutation of entries assuming a grouped vector.
storm::storage::BitVector	get (uint64_t bitIndex, uint64_t numberOfBits) const
	Retrieves the content of the current bit vector at the given index for the given number of bits as a new bit vector.
uint64_t	getAsInt (uint64_t bitIndex, uint64_t numberOfBits) const
	Retrieves the content of the current bit vector at the given index for the given number of bits as an unsigned integer value.
uint64_t	getTwoBitsAligned (uint64_t bitIndex) const
void	setFromInt (uint64_t bitIndex, uint64_t numberOfBits, uint64_t value)
	Sets the selected number of lowermost bits of the provided value at the given bit index.
bool	empty () const
	Retrieves whether no bits are set to true in this bit vector.
bool	full () const
	Retrieves whether all bits are set in this bit vector.
void	clear ()
	Removes all set bits from the bit vector.
void	fill ()
	Sets all bits from the bit vector.
uint64_t	getNumberOfSetBits () const
	Returns the number of bits that are set to true in this bit vector.
uint64_t	getNumberOfSetBitsBeforeIndex (uint64_t index) const
	Retrieves the number of bits set in this bit vector with an index strictly smaller than the given one.
std::vector< uint64_t >	getNumberOfSetBitsBeforeIndices () const
	Retrieves a vector that holds at position i the number of bits set before index i.
bool	hasUniqueSetBit () const
size_t	size () const
	Retrieves the number of bits this bit vector can store.
std::size_t	getSizeInBytes () const
	Returns (an approximation of) the size of the bit vector measured in bytes.
size_t	bucketCount () const
	Retrieves the number of buckets of the underlying storage.
void	setBucket (uint64_t bucketIndex, uint64_t value)
	Sets the bits in the given bucket to the given value.
uint64_t	getBucket (uint64_t bucketIndex) const
	Gets the bits in the given bucket.
const_iterator	begin () const
	Returns an iterator to the indices of the set bits in the bit vector.
const_iterator	begin (uint64_t lowerBound) const
	Returns an iterator to the indices of the set bits in the bit vector.
const_iterator	end () const
	Returns an iterator pointing at the element past the back of the bit vector.
const_reverse_iterator	rbegin () const
	Returns a reverse iterator to the indices of the set bits in the bit vector.
const_reverse_iterator	rbegin (uint64_t upperBound) const
	Returns a reverse iterator to the indices of the set bits in the bit vector.
const_reverse_iterator	rend () const
	Returns a reverse iterator pointing at the element past the front of the bit vector.
uint64_t	getNextSetIndex (uint64_t startingIndex) const
	Retrieves the index of the bit that is the next bit set to true in the bit vector.
uint64_t	getNextUnsetIndex (uint64_t startingIndex) const
	Retrieves the index of the bit that is the next bit set to false in the bit vector.
uint64_t	getStartOfZeroSequenceBefore (uint64_t endIndex) const
	Retrieves the smallest index i such that all bits in the range [i,endIndex) are 0.
uint64_t	getStartOfOneSequenceBefore (uint64_t endIndex) const
	Retrieves the smallest index i such that all bits in the range [i,endIndex) are 1.
bool	compareAndSwap (uint64_t start1, uint64_t start2, uint64_t length)
	Compare two intervals [start1, start1+length] and [start2, start2+length] and swap them if the second one is larger than the first one.
void	store (std::ostream &) const

Static Public Member Functions
static BitVector	load (std::string const &description)

Friends
struct	std::hash< storm::storage::BitVector >
struct	FNV1aBitVectorHash
template<typename StateType>
struct	Murmur3BitVectorHash
std::ostream &	operator<< (std::ostream &out, BitVector const &bitVector)

Detailed Description

A bit vector that is internally represented as a vector of 64-bit values.

Definition at line 16 of file BitVector.h.

Constructor & Destructor Documentation

◆ BitVector() [1/6]

storm::storage::BitVector::BitVector ( )

Constructs an empty bit vector of length 0.

Definition at line 132 of file BitVector.cpp.

◆ ~BitVector()

storm::storage::BitVector::~BitVector ( )

Deconstructs a bit vector by deleting the underlying storage.

Definition at line 153 of file BitVector.cpp.

◆ BitVector() [2/6]

storm::storage::BitVector::BitVector	(	uint64_t	length,
		bool	init = false )

explicit

Constructs a bit vector which can hold the given number of bits and initializes all bits with the provided truth value.

Parameters

length	The number of bits the bit vector should be able to hold.
init	The initial value of the first \|length\| bits.

Definition at line 136 of file BitVector.cpp.

◆ BitVector() [3/6]

template<typename InputIterator>

storm::storage::BitVector::BitVector	(	uint64_t	length,
		InputIterator	first,
		InputIterator	last )

Creates a bit vector that has exactly the bits set that are given by the provided input iterator range [first, last).

Parameters

The	length of the bit vector.
first	The begin of the iterator range.
last	The end of the iterator range.

Definition at line 158 of file BitVector.cpp.

◆ BitVector() [4/6]

storm::storage::BitVector::BitVector	(	uint64_t	length,
		std::vector< uint64_t >	setEntries )

Creates a bit vector that has exactly the bits set that are given by the vector.

Definition at line 162 of file BitVector.cpp.

◆ BitVector() [5/6]

storm::storage::BitVector::BitVector ( BitVector const & other )

Performs a deep copy of the given bit vector.

Parameters

other A reference to the bit vector to be copied.

Definition at line 171 of file BitVector.cpp.

◆ BitVector() [6/6]

storm::storage::BitVector::BitVector ( BitVector && other )

Move constructs the bit vector from the given bit vector.

Parameters

other The bit vector from which to move-construct.

Definition at line 213 of file BitVector.cpp.

Member Function Documentation

◆ begin() [1/2]

BitVector::const_iterator storm::storage::BitVector::begin ( ) const

Returns an iterator to the indices of the set bits in the bit vector.

Initially, the iterator points to the smallest index of a bit with value 1

Definition at line 778 of file BitVector.cpp.

◆ begin() [2/2]

BitVector::const_iterator storm::storage::BitVector::begin ( uint64_t lowerBound ) const

Returns an iterator to the indices of the set bits in the bit vector.

Initially, the iterator points to the smallest index that is >= lowerBound

Definition at line 782 of file BitVector.cpp.

◆ bucketCount()

size_t storm::storage::BitVector::bucketCount ( ) const

Retrieves the number of buckets of the underlying storage.

Returns: The number of buckets of the underlying storage.

Definition at line 752 of file BitVector.cpp.

◆ clear()

void storm::storage::BitVector::clear ( )

Removes all set bits from the bit vector.

Calling empty() after this operation will yield true.

Definition at line 689 of file BitVector.cpp.

◆ compareAndSwap()

bool storm::storage::BitVector::compareAndSwap	(	uint64_t	start1,
		uint64_t	start2,
		uint64_t	length )

Compare two intervals [start1, start1+length] and [start2, start2+length] and swap them if the second one is larger than the first one.

After the method the intervals are sorted in decreasing order.

Parameters

start1	Starting index of first interval.
start2	Starting index of second interval.
length	Length of both intervals.

Returns: True, if the intervals were swapped, false if nothing changed.

Definition at line 1070 of file BitVector.cpp.

◆ complement()

void storm::storage::BitVector::complement ( )

Negates all bits in the bit vector.

Definition at line 433 of file BitVector.cpp.

◆ concat()

void storm::storage::BitVector::concat ( BitVector const & extension )

Concatenate this bitvector with another bitvector.

The result is stored in this bitvector. During the operation, the bitvector is extended to match the size of the sum of the two bitvectors The current implementation expects this->size() to be a multiple of 64. This can be ensured by a call to expandSize

Definition at line 324 of file BitVector.cpp.

◆ empty()

bool storm::storage::BitVector::empty ( ) const

Retrieves whether no bits are set to true in this bit vector.

Returns: False iff there is at least one bit set in this vector.

Definition at line 663 of file BitVector.cpp.

◆ end()

BitVector::const_iterator storm::storage::BitVector::end ( ) const

Returns an iterator pointing at the element past the back of the bit vector.

Definition at line 786 of file BitVector.cpp.

◆ expandSize()

void storm::storage::BitVector::expandSize ( bool init = false )

Definition at line 333 of file BitVector.cpp.

◆ fill()

void storm::storage::BitVector::fill ( )

Sets all bits from the bit vector.

Calling full() after this operation will yield true.

Definition at line 693 of file BitVector.cpp.

◆ full()

bool storm::storage::BitVector::full ( ) const

Retrieves whether all bits are set in this bit vector.

If the bit vector has size 0, this method always returns true.

Returns: True iff all bits in the bit vector are set.

Definition at line 669 of file BitVector.cpp.

◆ get() [1/2]

storm::storage::BitVector storm::storage::BitVector::get	(	uint64_t	bitIndex,
		uint64_t	numberOfBits ) const

Retrieves the content of the current bit vector at the given index for the given number of bits as a new bit vector.

Parameters

bitIndex	The index of the first bit to get. This value must be a multiple of 64.
numberOfBits	The number of bits to get. This value must be a multiple of 64.

Returns: A new bit vector holding the selected bits.

Definition at line 572 of file BitVector.cpp.

◆ get() [2/2]

bool storm::storage::BitVector::get ( uint64_t index ) const

Retrieves the truth value of the bit at the given index and performs a bound check.

If the access is out-of-bounds an OutOfBoundsException is thrown.

Parameters

index The index of the bit to access.

Returns: True iff the bit at the given index is set.

Definition at line 270 of file BitVector.cpp.

◆ getAsInt()

uint64_t storm::storage::BitVector::getAsInt	(	uint64_t	bitIndex,
		uint64_t	numberOfBits ) const

Retrieves the content of the current bit vector at the given index for the given number of bits as an unsigned integer value.

Parameters

bitIndex	The index of the first bit to get.
numberOfBits	The number of bits to get. This value must be less or equal than 64.

Definition at line 583 of file BitVector.cpp.

◆ getBucket()

uint64_t storm::storage::BitVector::getBucket ( uint64_t bucketIndex ) const

Gets the bits in the given bucket.

Parameters

bucketIndex The bucket. Bucket index i refers to the 64 bits with index i*64 to i*64+63.

Returns: The values of the bits in the given bucket. The most significant bit is interpreted as the bit with the smallest index, e.g., 2^63 means the bit with index bucketIndex*64 is 1 and all other bits in the bucket are 0. 1 means the bit with index bucketIndex*64+63 is 1 and all other bits in the bucket are 0.

Note: : bucketIndex must be below bucketCount().; If the size of this BitVector is not a multiple of 64, the last bucket with index bucketCount() - 1 contains (64 - size() % 64) many unused bits. These bits are the least significant bits in the bucket and guaranteed to be 0 (false)

Definition at line 768 of file BitVector.cpp.

◆ getNextSetIndex()

uint64_t storm::storage::BitVector::getNextSetIndex ( uint64_t startingIndex ) const

Retrieves the index of the bit that is the next bit set to true in the bit vector.

If there is none, this function returns the number of bits this vector holds in total. Put differently, if the return value is equal to a call to size(), then there is no bit set after the specified position.

Parameters

startingIndex The index at which to start the search for the next bit that is set. The bit at this index itself is included in the search range.

Returns: The index of the next bit that is set after the given index.

Definition at line 801 of file BitVector.cpp.

◆ getNextUnsetIndex()

uint64_t storm::storage::BitVector::getNextUnsetIndex ( uint64_t startingIndex ) const

Retrieves the index of the bit that is the next bit set to false in the bit vector.

If there is none, this function returns the number of bits this vector holds in total. Put differently, if the return value is equal to a call to size(), then there is no unset bit after the specified position.

Parameters

startingIndex The index at which to start the search for the next bit that is not set. The bit at this index itself is included in the search range.

Returns: The index of the next bit that is set after the given index.

Definition at line 805 of file BitVector.cpp.

◆ getNumberOfSetBits()

uint64_t storm::storage::BitVector::getNumberOfSetBits ( ) const

Returns the number of bits that are set to true in this bit vector.

Returns: The number of bits that are set to true in this bit vector.

Definition at line 698 of file BitVector.cpp.

◆ getNumberOfSetBitsBeforeIndex()

uint64_t storm::storage::BitVector::getNumberOfSetBitsBeforeIndex ( uint64_t index ) const

Retrieves the number of bits set in this bit vector with an index strictly smaller than the given one.

Parameters

index The index for which to retrieve the number of set bits with a smaller index.

Returns: The number of bits set in this bit vector with an index strictly smaller than the given one.

Definition at line 702 of file BitVector.cpp.

◆ getNumberOfSetBitsBeforeIndices()

std::vector< uint64_t > storm::storage::BitVector::getNumberOfSetBitsBeforeIndices ( ) const

Retrieves a vector that holds at position i the number of bits set before index i.

Returns: The resulting vector of 'offsets'.

Definition at line 721 of file BitVector.cpp.

◆ getSizeInBytes()

std::size_t storm::storage::BitVector::getSizeInBytes ( ) const

Returns (an approximation of) the size of the bit vector measured in bytes.

Returns: The size of the bit vector measured in bytes.

Definition at line 748 of file BitVector.cpp.

◆ getStartOfOneSequenceBefore()

uint64_t storm::storage::BitVector::getStartOfOneSequenceBefore ( uint64_t endIndex ) const

Retrieves the smallest index i such that all bits in the range [i,endIndex) are 1.

Note: this can be seen as a backward version of getNextUnSetIndex.

Parameters

endIndex The index at which to start the backward search. The bit at this index itself is not included in the search range.

Returns: The smallest index i such that all bits in the range [i,endIndex) are 1.

Definition at line 817 of file BitVector.cpp.

◆ getStartOfZeroSequenceBefore()

uint64_t storm::storage::BitVector::getStartOfZeroSequenceBefore ( uint64_t endIndex ) const

Retrieves the smallest index i such that all bits in the range [i,endIndex) are 0.

Note: this can be seen as a backward version of getNextSetIndex.

Parameters

endIndex The index at which to start the backward search. The bit at this index itself is not included in the search range.

Returns: The smallest index i such that all bits in the range [i,endIndex) are 0.

Definition at line 813 of file BitVector.cpp.

◆ getTwoBitsAligned()

uint64_t storm::storage::BitVector::getTwoBitsAligned ( uint64_t bitIndex ) const

Parameters

bitIndex The index of the first of the two bits to get

Returns: A value between 0 and 3, encoded as a byte.

Definition at line 602 of file BitVector.cpp.

◆ grow()

void storm::storage::BitVector::grow	(	uint64_t	minimumLength,
		bool	init = false )

Enlarges the bit vector such that it holds at least the given number of bits (but possibly more).

This can be used to diminish reallocations when the final size of the bit vector is not known yet. The bit vector does not become smaller. New bits are initialized to the given value.

Parameters

minimumLength	The minimum number of bits that the bit vector should hold.
init	The truth value to which to initialize newly created bits.

Definition at line 341 of file BitVector.cpp.

◆ hasUniqueSetBit()

bool storm::storage::BitVector::hasUniqueSetBit ( ) const

Definition at line 740 of file BitVector.cpp.

◆ implies()

BitVector storm::storage::BitVector::implies ( BitVector const & other ) const

Performs a logical "implies" with the given bit vector.

In case the sizes of the bit vectors do not match, only the matching portion is considered and the overlapping bits are set to 0.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A bit vector corresponding to the logical "implies" of the two bit vectors.

Definition at line 464 of file BitVector.cpp.

◆ increment()

void storm::storage::BitVector::increment ( )

Increments the (unsigned) number represented by this BitVector by one.

Note: Index 0 is assumed to be the least significant bit.; Wraps around, i.e., incrementing 11..1 yields 00..0.

Definition at line 438 of file BitVector.cpp.

◆ isDisjointFrom()

bool storm::storage::BitVector::isDisjointFrom ( BitVector const & other ) const

Checks whether none of the bits that are set in the current bit vector are also set in the given bit vector.

Parameters

other A reference to the bit vector whose bits are (possibly) disjoint from the bits in the current bit vector.

Returns: True iff none of the bits that are set in the current bit vector are also set in the given bit vector.

Definition at line 489 of file BitVector.cpp.

◆ isSubsetOf()

bool storm::storage::BitVector::isSubsetOf ( BitVector const & other ) const

Checks whether all bits that are set in the current bit vector are also set in the given bit vector.

Parameters

other A reference to the bit vector whose bits are (possibly) a superset of the bits of the current bit vector.

Returns: True iff all bits that are set in the current bit vector are also set in the given bit vector.

Definition at line 474 of file BitVector.cpp.

◆ load()

BitVector storm::storage::BitVector::load ( std::string const & description )

static

Definition at line 1396 of file BitVector.cpp.

◆ matches()

bool storm::storage::BitVector::matches	(	uint64_t	bitIndex,
		BitVector const &	other ) const

Checks whether the given bit vector matches the bits starting from the given index in the current bit vector.

Note: the given bit vector must be shorter than the current one minus the given index.

Parameters

bitIndex	The index of the first bit that it supposed to match. This value must be a multiple of 64.
other	The bit vector with which to compare.

Returns: bool True iff the bits match exactly.

Definition at line 504 of file BitVector.cpp.

◆ operator!=()

bool storm::storage::BitVector::operator!= ( BitVector const & other ) const

Compares the given bit vector with the current one.

Parameters

other The bitvector with which to compare the current one.

Returns: True iff the other bit vector is semantically not the same as the current one.

Definition at line 241 of file BitVector.cpp.

◆ operator%()

BitVector storm::storage::BitVector::operator% ( BitVector const & filter ) const

Computes a bit vector that contains only the values of the bits given by the filter.

The returned bit vector is as long as the number of set bits in the given filter. Bit i is set in the returned bit vector iff the i-th set bit of the current bit vector is set in the filter.

For example: 00100110 % 10101010 returns 0101

Parameters

filter A reference bit vector to use as the filter.

Returns: A bit vector that is as long as the number of set bits in the given filter and contains only the values of the bits set in the filter.

Definition at line 398 of file BitVector.cpp.

◆ operator&()

BitVector storm::storage::BitVector::operator& ( BitVector const & other ) const

Performs a logical "and" with the given bit vector.

In case the sizes of the bit vectors do not match, only the matching portion is considered and the overlapping bits are set to 0.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A bit vector corresponding to the logical "and" of the two bit vectors.

Definition at line 353 of file BitVector.cpp.

◆ operator&=()

BitVector & storm::storage::BitVector::operator&= ( BitVector const & other )

Performs a logical "and" with the given bit vector and assigns the result to the current bit vector.

In case the sizes of the bit vectors do not match, only the matching portion is considered and the overlapping bits are set to 0.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A reference to the current bit vector corresponding to the logical "and" of the two bit vectors.

Definition at line 361 of file BitVector.cpp.

◆ operator<()

bool storm::storage::BitVector::operator< ( BitVector const & other ) const

Retrieves whether the current bit vector is (in some order) smaller than the given one.

Parameters

other The other bit vector.

Returns: True iff the current bit vector is smaller than the given one.

Definition at line 192 of file BitVector.cpp.

◆ operator=() [1/2]

BitVector & storm::storage::BitVector::operator= ( BitVector && other )

Move assigns the given bit vector to the current bit vector.

Parameters

other The bit vector whose content is moved to the current bit vector.

Returns: A reference to this bit vector after the contents of the given bit vector have been moved into it.

Definition at line 218 of file BitVector.cpp.

◆ operator=() [2/2]

BitVector & storm::storage::BitVector::operator= ( BitVector const & other )

Assigns the contents of the given bit vector to the current bit vector via a deep copy.

Parameters

other The bit vector to assign to the current bit vector.

Returns: A reference to this bit vector after it has been assigned the given bit vector by means of a deep copy.

Definition at line 176 of file BitVector.cpp.

◆ operator==()

bool storm::storage::BitVector::operator== ( BitVector const & other ) const

Compares the given bit vector with the current one.

Parameters

other The bitvector with which to compare the current one.

Returns: True iff the other bit vector is semantically the same as the current one.

Definition at line 231 of file BitVector.cpp.

◆ operator[]()

bool storm::storage::BitVector::operator[] ( uint64_t index ) const

Retrieves the truth value of the bit at the given index.

Note: this does not check whether the given index is within bounds.

Parameters

index The index of the bit to access.

Returns: True iff the bit at the given index is set.

Definition at line 264 of file BitVector.cpp.

◆ operator^()

BitVector storm::storage::BitVector::operator^ ( BitVector const & other ) const

Performs a logical "xor" with the given bit vector.

The given bit vector has to have the same size as the current one.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A bit vector corresponding to the logical "xor" of the two bit vectors.

Definition at line 383 of file BitVector.cpp.

◆ operator^=()

BitVector & storm::storage::BitVector::operator^= ( BitVector const & other )

Performs a logical "xor" with the given bit vector and assigns the result to the current bit vector.

The given bit vector has to have the same size as the current one.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A reference to the current bit vector corresponding to the logical "xor" of the two bit vectors.

Definition at line 391 of file BitVector.cpp.

◆ operator|()

BitVector storm::storage::BitVector::operator| ( BitVector const & other ) const

Performs a logical "or" with the given bit vector.

In case the sizes of the bit vectors do not match, only the matching portion is considered and the overlapping bits are set to 0.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A bit vector corresponding to the logical "or" of the two bit vectors.

Definition at line 368 of file BitVector.cpp.

◆ operator|=()

BitVector & storm::storage::BitVector::operator|= ( BitVector const & other )

Performs a logical "or" with the given bit vector and assigns the result to the current bit vector.

In case the sizes of the bit vectors do not match, only the matching portion is considered and the overlapping bits are set to 0.

Parameters

other A reference to the bit vector to use for the operation.

Returns: A reference to the current bit vector corresponding to the logical "or" of the two bit vectors.

Definition at line 376 of file BitVector.cpp.

◆ operator~()

BitVector storm::storage::BitVector::operator~ ( ) const

Performs a logical "not" on the bit vector.

Returns: A bit vector corresponding to the logical "not" of the bit vector.

Definition at line 426 of file BitVector.cpp.

◆ permute()

BitVector storm::storage::BitVector::permute ( std::vector< uint64_t > const & inversePermutation ) const

Apply a permutation of entries.

That is, in row i, write the entry of row inversePermutation[i].

Parameters

inversePermutation.

Returns: TODO this operation is slow.

Definition at line 523 of file BitVector.cpp.

◆ permuteGroupedVector()

BitVector storm::storage::BitVector::permuteGroupedVector	(	std::vector< uint64_t > const &	inversePermutation,
		std::vector< uint64_t > const &	rowGroupIndices ) const

Apply a permutation of entries assuming a grouped vector.

That is, in row group i, write the entries of row group inversePermutation[i].

Parameters

inversePermutation.

Returns: TODO this operation is slow.

Definition at line 533 of file BitVector.cpp.

◆ rbegin() [1/2]

BitVector::const_reverse_iterator storm::storage::BitVector::rbegin ( ) const

Returns a reverse iterator to the indices of the set bits in the bit vector.

Initially, the iterator points to the largest index of a bit with value 1

Definition at line 790 of file BitVector.cpp.

◆ rbegin() [2/2]

BitVector::const_reverse_iterator storm::storage::BitVector::rbegin ( uint64_t upperBound ) const

Returns a reverse iterator to the indices of the set bits in the bit vector.

Initially, the iterator points to the largest index that is < upperBound

Definition at line 793 of file BitVector.cpp.

◆ rend()

BitVector::const_reverse_iterator storm::storage::BitVector::rend ( ) const

Returns a reverse iterator pointing at the element past the front of the bit vector.

Definition at line 797 of file BitVector.cpp.

◆ resize()

void storm::storage::BitVector::resize	(	uint64_t	newLength,
		bool	init = false )

Resizes the bit vector to hold the given new number of bits.

If the bit vector becomes smaller this way, the bits are truncated. Otherwise, the new bits are initialized to the given value.

Parameters

newLength	The new number of bits the bit vector can hold.
init	The truth value to which to initialize newly created bits.

Definition at line 275 of file BitVector.cpp.

◆ set() [1/3]

template<typename InputIterator>

void storm::storage::BitVector::set	(	InputIterator	first,
		InputIterator	last,
		bool	value = true )

Sets all bits in the given iterator range [first, last).

Parameters

first	The begin of the iterator range.
last	The element past the last element of the iterator range.

Definition at line 258 of file BitVector.cpp.

◆ set() [2/3]

void storm::storage::BitVector::set	(	uint64_t	bitIndex,
		BitVector const &	other )

Sets the exact bit pattern of the given bit vector starting at the given bit index.

Note: the given bit vector must be shorter than the current one minus the given index.

Parameters

bitIndex	The index of the first bit that it supposed to be set. This value must be a multiple of 64.
other	The bit vector whose pattern to set.

Definition at line 548 of file BitVector.cpp.

◆ set() [3/3]

void storm::storage::BitVector::set	(	uint64_t	index,
		bool	value = true )

Sets the given truth value at the given index.

Parameters

index	The index where to set the truth value.
value	The truth value to set.

Definition at line 245 of file BitVector.cpp.

◆ setBucket()

void storm::storage::BitVector::setBucket	(	uint64_t	bucketIndex,
		uint64_t	value )

Sets the bits in the given bucket to the given value.

Parameters

bucketIndex	The bucket. Bucket index i refers to the 64 bits with index i64 to i64+63.
value	The bit values to set for the bucket. The most significant bit is interpreted as the bit with the smallest index, e.g., value=2^63 sets the bit with index bucketIndex64 to 1 and all other bits in the bucket to 0. value=1 sets the bit with index bucketIndex64+63 to 1 and all other bits in the bucket to 0.

Note: : bucketIndex must be below bucketCount().; : If the size of this BitVector is not a multiple of 64, the last bucket with index bucketCount() - 1 contains (64 - size() % 64) many unused bits. These bits are the least significant bits in the bucket and the value given to these bits is ignored.

Definition at line 760 of file BitVector.cpp.

◆ setFromInt()

void storm::storage::BitVector::setFromInt	(	uint64_t	bitIndex,
		uint64_t	numberOfBits,
		uint64_t	value )

Sets the selected number of lowermost bits of the provided value at the given bit index.

Parameters

bitIndex	The index of the first bit to set.
numberOfBits	The number of bits to set.
value	The integer whose lowermost bits to set.

Definition at line 625 of file BitVector.cpp.

◆ setMultiple()

void storm::storage::BitVector::setMultiple	(	uint64_t	bitIndex,
		uint64_t	nrOfBits,
		bool	newValue = true )

Sets multiple bits to the given value.

Definition at line 564 of file BitVector.cpp.

◆ size()

size_t storm::storage::BitVector::size ( ) const

Retrieves the number of bits this bit vector can store.

Returns: The number of bits this bit vector can hold.

Definition at line 744 of file BitVector.cpp.

◆ store()

void storm::storage::BitVector::store ( std::ostream & os ) const

Definition at line 1389 of file BitVector.cpp.

◆ FNV1aBitVectorHash

friend struct FNV1aBitVectorHash

friend

Definition at line 749 of file BitVector.h.

◆ Murmur3BitVectorHash

template<typename StateType>

friend struct Murmur3BitVectorHash

friend

Definition at line 752 of file BitVector.h.

◆ operator<<

std::ostream & operator<<	(	std::ostream &	out,
		BitVector const &	bitVector )

friend

Definition at line 1138 of file BitVector.cpp.

◆ std::hash< storm::storage::BitVector >

friend struct std::hash< storm::storage::BitVector >

friend

Definition at line 746 of file BitVector.h.

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

src/storm/storage/BitVector.h
src/storm/storage/BitVector.cpp

Classes

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ BitVector() [1/6]

◆ ~BitVector()

◆ BitVector() [2/6]

◆ BitVector() [3/6]

◆ BitVector() [4/6]

◆ BitVector() [5/6]

◆ BitVector() [6/6]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ bucketCount()

◆ clear()

◆ compareAndSwap()

◆ complement()

◆ concat()

◆ empty()

◆ end()

◆ expandSize()

◆ fill()

◆ full()

◆ get() [1/2]

◆ get() [2/2]

◆ getAsInt()

◆ getBucket()

◆ getNextSetIndex()

◆ getNextUnsetIndex()

◆ getNumberOfSetBits()

◆ getNumberOfSetBitsBeforeIndex()

◆ getNumberOfSetBitsBeforeIndices()

◆ getSizeInBytes()

◆ getStartOfOneSequenceBefore()

◆ getStartOfZeroSequenceBefore()

◆ getTwoBitsAligned()

◆ grow()

◆ hasUniqueSetBit()

◆ implies()

◆ increment()

◆ isDisjointFrom()

◆ isSubsetOf()

◆ load()

◆ matches()

◆ operator!=()

◆ operator%()

◆ operator&()

◆ operator&=()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ operator^()

◆ operator^=()

◆ operator|()

◆ operator|=()

◆ operator~()

◆ permute()

◆ permuteGroupedVector()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend()

◆ resize()

◆ set() [1/3]

◆ set() [2/3]

◆ set() [3/3]

◆ setBucket()

◆ setFromInt()

◆ setMultiple()

◆ size()

◆ store()

Friends And Related Symbol Documentation

◆ FNV1aBitVectorHash

◆ Murmur3BitVectorHash

◆ operator<<

◆ std::hash< storm::storage::BitVector >