BitVector.h

Go to the documentation of this file.

#ifndef STORM_STORAGE_BITVECTOR_H_
#define STORM_STORAGE_BITVECTOR_H_
 
#include <cmath>
#include <cstdint>
#include <functional>
#include <iterator>
#include <ostream>
#include <ranges>
#include <vector>
 
namespace storm {
namespace storage {
 
class BitVector {
   public:
    class const_iterator {
        // Declare the BitVector class as a friend class to access its internal storage.
        friend class BitVector;
 
       public:
        // Define iterator
        using iterator_category = std::forward_iterator_tag;
        using value_type = uint_fast64_t;
        using difference_type = std::ptrdiff_t;
        using pointer = uint_fast64_t*;
        using reference = uint_fast64_t&;
 
        const_iterator();
 
        const_iterator(uint64_t const* dataPtr, uint_fast64_t startIndex, uint_fast64_t endIndex, bool setOnFirstBit = true);
 
        const_iterator(const_iterator const& other);
 
        const_iterator& operator=(const_iterator const& other);
 
        const_iterator& operator++();
 
        const_iterator operator++(int);
 
        const_iterator& operator+=(size_t n);
 
        uint_fast64_t operator*() const;
 
        bool operator!=(const_iterator const& other) const;
 
        bool operator==(const_iterator const& other) const;
 
       private:
        // The underlying bit vector of this iterator.
        uint64_t const* dataPtr;
 
        // The index of the bit this iterator currently points to.
        uint_fast64_t currentIndex;
 
        // The index of the bit that is past the end of the range of this iterator.
        uint_fast64_t endIndex;
    };
    class const_reverse_iterator {
        // Declare the BitVector class as a friend class to access its internal storage.
        friend class BitVector;
 
       public:
        // Define iterator
        using iterator_category = std::forward_iterator_tag;
        using value_type = uint_fast64_t;
        using difference_type = std::ptrdiff_t;
        using pointer = uint_fast64_t*;
        using reference = uint_fast64_t&;
 
        const_reverse_iterator();
        const_reverse_iterator(uint64_t const* dataPtr, uint64_t upperBound, uint64_t lowerBound = 0ull, bool setOnFirstBit = true);
        const_reverse_iterator(const_reverse_iterator const& other);
        const_reverse_iterator& operator=(const_reverse_iterator const& other);
 
        const_reverse_iterator& operator++();
 
        const_reverse_iterator operator++(int);
 
        const_reverse_iterator& operator+=(size_t n);
 
        uint_fast64_t operator*() const;
 
        bool operator!=(const_reverse_iterator const& other) const;
 
        bool operator==(const_reverse_iterator const& other) const;
 
       private:
        uint64_t const* dataPtr;
 
        uint64_t currentIndex;
 
        uint64_t lowerBound;
    };
 
    BitVector();
 
    ~BitVector();
 
    explicit BitVector(uint_fast64_t length, bool init = false);
 
    template<typename InputIterator>
    BitVector(uint_fast64_t length, InputIterator first, InputIterator last);
 
    BitVector(uint_fast64_t length, std::vector<uint_fast64_t> setEntries);
 
    BitVector(BitVector const& other);
 
    BitVector(BitVector&& other);
 
    bool operator==(BitVector const& other) const;
 
    bool operator!=(BitVector const& other) const;
 
    BitVector& operator=(BitVector const& other);
 
    BitVector& operator=(BitVector&& other);
 
    bool operator<(BitVector const& other) const;
 
    void set(uint_fast64_t index, bool value = true);
 
    template<typename InputIterator>
    void set(InputIterator first, InputIterator last, bool value = true);
 
    bool operator[](uint_fast64_t index) const;
 
    bool get(uint_fast64_t index) const;
 
    void resize(uint_fast64_t newLength, bool init = false);
 
    void concat(BitVector const& extension);
 
    /*
     * Expands the size to a multiple of 64.
     */
    void expandSize(bool init = false);
 
    void grow(uint_fast64_t minimumLength, bool init = false);
 
    BitVector operator&(BitVector const& other) const;
 
    BitVector& operator&=(BitVector const& other);
 
    BitVector operator|(BitVector const& other) const;
 
    BitVector& operator|=(BitVector const& other);
 
    BitVector operator^(BitVector const& other) const;
 
    BitVector operator%(BitVector const& filter) const;
 
    BitVector operator~() const;
 
    void complement();
 
    void increment();
 
    BitVector implies(BitVector const& other) const;
 
    bool isSubsetOf(BitVector const& other) const;
 
    bool isDisjointFrom(BitVector const& other) const;
 
    bool matches(uint_fast64_t bitIndex, BitVector const& other) const;
 
    void set(uint_fast64_t bitIndex, BitVector const& other);
 
    void setMultiple(uint64_t bitIndex, uint64_t nrOfBits, bool newValue = true);
 
    BitVector permute(std::vector<uint64_t> const& inversePermutation) const;
 
    BitVector permuteGroupedVector(std::vector<uint64_t> const& inversePermutation, std::vector<uint64_t> const& rowGroupIndices) const;
 
    storm::storage::BitVector get(uint_fast64_t bitIndex, uint_fast64_t numberOfBits) const;
 
    uint_fast64_t getAsInt(uint_fast64_t bitIndex, uint_fast64_t numberOfBits) const;
 
    uint_fast64_t getTwoBitsAligned(uint_fast64_t bitIndex) const;
 
    void setFromInt(uint_fast64_t bitIndex, uint_fast64_t numberOfBits, uint64_t value);
 
    bool empty() const;
 
    bool full() const;
 
    void clear();
 
    void fill();
 
    uint_fast64_t getNumberOfSetBits() const;
 
    uint_fast64_t getNumberOfSetBitsBeforeIndex(uint_fast64_t index) const;
 
    std::vector<uint_fast64_t> getNumberOfSetBitsBeforeIndices() const;
 
    size_t size() const;
 
    std::size_t getSizeInBytes() const;
 
    const_iterator begin() const;
 
    const_iterator begin(uint64_t lowerBound) const;
 
    const_iterator end() const;
 
    const_reverse_iterator rbegin() const;
 
    const_reverse_iterator rbegin(uint64_t upperBound) const;
 
    const_reverse_iterator rend() const;
 
    uint_fast64_t getNextSetIndex(uint_fast64_t startingIndex) const;
 
    uint_fast64_t getNextUnsetIndex(uint_fast64_t startingIndex) const;
 
    uint64_t getStartOfZeroSequenceBefore(uint64_t endIndex) const;
 
    uint64_t getStartOfOneSequenceBefore(uint64_t endIndex) const;
 
    bool compareAndSwap(uint_fast64_t start1, uint_fast64_t start2, uint_fast64_t length);
 
    friend std::ostream& operator<<(std::ostream& out, BitVector const& bitVector);
 
    void store(std::ostream&) const;
    static BitVector load(std::string const& description);
 
    friend struct std::hash<storm::storage::BitVector>;
    friend struct FNV1aBitVectorHash;
 
    template<typename StateType>
    friend struct Murmur3BitVectorHash;
 
   private:
    BitVector(uint_fast64_t bucketCount, uint_fast64_t bitCount);
 
    template<bool Value, bool Backward = false>
    static uint_fast64_t getNextIndexWithValue(uint64_t const* dataPtr, uint_fast64_t startingIndex, uint_fast64_t endIndex);
 
    void truncateLastBucket();
 
    BitVector getAsBitVector(uint_fast64_t start, uint_fast64_t length) const;
 
    void setFromBitVector(uint_fast64_t start, BitVector const& other);
 
    void printBits(std::ostream& out) const;
 
    size_t bucketCount() const;
 
    // The number of bits that this bit vector can hold.
    uint_fast64_t bitCount;
 
    // The underlying storage of 64-bit buckets for all bits of this bit vector.
    uint64_t* buckets;
 
    // A bit mask that can be used to reduce a modulo 64 operation to a logical "and".
    static const uint_fast64_t mod64mask = (1 << 6) - 1;
};
 
static_assert(std::ranges::forward_range<BitVector>);
 
struct FNV1aBitVectorHash {
    std::size_t operator()(storm::storage::BitVector const& bv) const;
};
 
template<typename StateType>
struct Murmur3BitVectorHash {
    StateType operator()(storm::storage::BitVector const& bv) const;
};
 
}  // namespace storage
}  // namespace storm
 
namespace std {
template<>
struct hash<storm::storage::BitVector> {
    std::size_t operator()(storm::storage::BitVector const& bv) const;
};
}  // namespace std
 
#endif  // STORM_STORAGE_BITVECTOR_H_