47 const_iterator(uint64_t
const* dataPtr, uint64_t startIndex, uint64_t endIndex,
bool setOnFirstBit =
true);
110 uint64_t
const* dataPtr;
113 uint64_t currentIndex;
146 const_reverse_iterator(uint64_t
const* dataPtr, uint64_t upperBound, uint64_t lowerBound = 0ull,
bool setOnFirstBit =
true);
192 uint64_t
const* dataPtr;
195 uint64_t currentIndex;
218 explicit BitVector(uint64_t length,
bool init =
false);
228 template<
typename InputIterator>
229 BitVector(uint64_t length, InputIterator first, InputIterator last);
234 BitVector(uint64_t length, std::vector<uint64_t> setEntries);
298 void set(uint64_t index,
bool value =
true);
306 template<
typename InputIterator>
307 void set(InputIterator first, InputIterator last,
bool value =
true);
325 bool get(uint64_t index)
const;
334 void resize(uint64_t newLength,
bool init =
false);
358 void grow(uint64_t minimumLength,
bool init =
false);
494 void setMultiple(uint64_t bitIndex, uint64_t nrOfBits,
bool newValue =
true);
529 uint64_t
getAsInt(uint64_t bitIndex, uint64_t numberOfBits)
const;
545 void setFromInt(uint64_t bitIndex, uint64_t numberOfBits, uint64_t value);
700 bool compareAndSwap(uint64_t start1, uint64_t start2, uint64_t length);
704 void store(std::ostream&)
const;
710 template<typename StateType>
720 BitVector(uint64_t bucketCount, uint64_t bitCount);
735 template<bool Value, bool Backward = false>
736 static uint64_t getNextIndexWithValue(uint64_t const* dataPtr, uint64_t startingIndex, uint64_t endIndex);
741 void truncateLastBucket();
750 BitVector getAsBitVector(uint64_t start, uint64_t length) const;
759 void setFromBitVector(uint64_t start, BitVector const& other);
766 void printBits(std::ostream& out) const;
773 size_t bucketCount() const;
782 static const uint64_t mod64mask = (1 << 6) - 1;
785static_assert(std::ranges::forward_range<BitVector>);
787struct FNV1aBitVectorHash {
788 std::size_t operator()(storm::storage::BitVector const& bv) const;
791template<typename StateType>
792struct Murmur3BitVectorHash {
793 StateType operator()(storm::storage::BitVector const& bv) const;
800struct hash<storm::storage::BitVector> {
801 std::size_t operator()(storm::storage::BitVector const& bv) const;
A class that enables iterating over the indices of the bit vector whose corresponding bits are set to...
uint64_t operator*() const
Returns the index of the current bit to which this iterator points.
const_iterator & operator++()
Increases the position of the iterator to the position of the next bit that is set to true in the und...
bool operator==(const_iterator const &other) const
Compares the iterator with another iterator for equality.
std::ptrdiff_t difference_type
const_iterator & operator+=(size_t n)
Increases the position of the iterator to the position of the n'th next bit that is set to true in th...
const_iterator & operator=(const_iterator const &other)
Assigns the contents of the given iterator to the current one via copying the former's contents.
std::forward_iterator_tag iterator_category
bool operator!=(const_iterator const &other) const
Compares the iterator with another iterator for inequality.
A class that enables iterating over the indices of the bit vector whose corresponding bits are set to...
bool operator==(const_reverse_iterator const &other) const
Compares the iterator with another iterator for equality.
uint64_t operator*() const
Returns the index of the current bit to which this iterator points.
const_reverse_iterator()
Constructs a reverse iterator over the indices of the set bits in the given bit vector,...
const_reverse_iterator & operator+=(size_t n)
Lets the iterator point to the n'th previous bit with value 1.
std::forward_iterator_tag iterator_category
const_reverse_iterator & operator++()
Lets the iterator point to the previous bit with value 1.
const_reverse_iterator & operator=(const_reverse_iterator const &other)
std::ptrdiff_t difference_type
bool operator!=(const_reverse_iterator const &other) const
Compares the iterator with another iterator for inequality.
A bit vector that is internally represented as a vector of 64-bit values.
~BitVector()
Deconstructs a bit vector by deleting the underlying storage.
void complement()
Negates all bits in the 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.
void setMultiple(uint64_t bitIndex, uint64_t nrOfBits, bool newValue=true)
Sets multiple bits to the given value.
bool operator<(BitVector const &other) const
Retrieves whether the current bit vector is (in some order) smaller than the given one.
const_reverse_iterator rbegin() const
Returns a reverse iterator to the indices of the set bits in the bit vector.
void fill()
Sets all bits from 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 getTwoBitsAligned(uint64_t bitIndex) const
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 ...
bool full() const
Retrieves whether all bits are set in this bit vector.
std::vector< uint64_t > getNumberOfSetBitsBeforeIndices() const
Retrieves a vector that holds at position i the number of bits set before index i.
const_reverse_iterator rend() const
Returns a reverse iterator pointing at the element past the front of the bit vector.
bool hasUniqueSetBit() const
BitVector()
Constructs an empty bit vector of length 0.
const_iterator end() const
Returns an iterator pointing at the element past the back of the bit vector.
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).
void store(std::ostream &) const
BitVector operator%(BitVector const &filter) const
Computes a bit vector that contains only the values of the bits given by the filter.
BitVector operator|(BitVector const &other) const
Performs a logical "or" with the given bit vector.
bool empty() const
Retrieves whether no bits are set to true in this bit vector.
std::size_t getSizeInBytes() const
Returns (an approximation of) the size of the bit vector measured in bytes.
void clear()
Removes all set bits from the 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.
BitVector implies(BitVector const &other) const
Performs a logical "implies" with the given bit vector.
BitVector & operator=(BitVector const &other)
Assigns the contents of the given bit vector to the current bit vector via a deep copy.
uint64_t getNumberOfSetBits() const
Returns the number of bits that are set to true in this 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.
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...
BitVector operator&(BitVector const &other) const
Performs a logical "and" with the given bit vector.
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.
BitVector permute(std::vector< uint64_t > const &inversePermutation) const
Apply a permutation of entries.
void set(uint64_t index, bool value=true)
Sets the given truth value at the given index.
void increment()
Increments the (unsigned) number represented by this BitVector by one.
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...
const_iterator begin() const
Returns an iterator to the indices of the set bits 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 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...
friend std::ostream & operator<<(std::ostream &out, BitVector const &bitVector)
BitVector operator~() const
Performs a logical "not" on the bit vector.
bool operator!=(BitVector const &other) const
Compares the given bit vector with the current one.
size_t size() const
Retrieves the number of bits this bit vector can store.
void resize(uint64_t newLength, bool init=false)
Resizes the bit vector to hold the given new number of bits.
BitVector & operator&=(BitVector const &other)
Performs a logical "and" with the given bit vector and assigns the result to the current bit vector.
static BitVector load(std::string const &description)
void expandSize(bool init=false)
bool get(uint64_t index) const
Retrieves the truth value of the bit at the given index and performs a bound check.
bool operator==(BitVector const &other) const
Compares the given bit vector with the current one.
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...
BitVector permuteGroupedVector(std::vector< uint64_t > const &inversePermutation, std::vector< uint64_t > const &rowGroupIndices) const
Apply a permutation of entries assuming a grouped vector.
uint64_t getStartOfOneSequenceBefore(uint64_t endIndex) const
Retrieves the smallest index i such that all bits in the range [i,endIndex) are 1.
bool operator[](uint64_t index) const
Retrieves the truth value of the bit at the given index.
void concat(BitVector const &extension)
Concatenate this bitvector with another bitvector.