BitVector.h

Go to the documentation of this file.

#pragma once
 
#include <cmath>
#include <cstdint>
#include <functional>
#include <iterator>
#include <ostream>
#include <ranges>
#include <vector>
 
namespace storm::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 = uint64_t;
        using difference_type = std::ptrdiff_t;
        using pointer = uint64_t*;
        using reference = uint64_t&;
 
        const_iterator();

        const_iterator(uint64_t const* dataPtr, uint64_t startIndex, uint64_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);

        uint64_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.
        uint64_t currentIndex;
 
        // The index of the bit that is past the end of the range of this iterator.
        uint64_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 = uint64_t;
        using difference_type = std::ptrdiff_t;
        using pointer = uint64_t*;
        using reference = uint64_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);

        uint64_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(uint64_t length, bool init = false);

    template<typename InputIterator>
    BitVector(uint64_t length, InputIterator first, InputIterator last);

    BitVector(uint64_t length, std::vector<uint64_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(uint64_t index, bool value = true);

    template<typename InputIterator>
    void set(InputIterator first, InputIterator last, bool value = true);

    bool operator[](uint64_t index) const;

    bool get(uint64_t index) const;

    void resize(uint64_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(uint64_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& other);

    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(uint64_t bitIndex, BitVector const& other) const;

    void set(uint64_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(uint64_t bitIndex, uint64_t numberOfBits) const;

    uint64_t getAsInt(uint64_t bitIndex, uint64_t numberOfBits) const;

    uint64_t getTwoBitsAligned(uint64_t bitIndex) const;

    void setFromInt(uint64_t bitIndex, uint64_t numberOfBits, uint64_t value);

    bool empty() const;

    bool full() const;

    void clear();

    void fill();

    uint64_t getNumberOfSetBits() const;

    uint64_t getNumberOfSetBitsBeforeIndex(uint64_t index) const;

    std::vector<uint64_t> getNumberOfSetBitsBeforeIndices() const;
 
    /*
     * @return True, if the number of set bits is 1, false otherwise.
     */
    bool hasUniqueSetBit() const;

    size_t size() const;

    std::size_t getSizeInBytes() const;

    size_t bucketCount() const;

    void setBucket(uint64_t bucketIndex, uint64_t value);

    uint64_t getBucket(uint64_t bucketIndex) 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;

    uint64_t getNextSetIndex(uint64_t startingIndex) const;

    uint64_t getNextUnsetIndex(uint64_t startingIndex) const;

    uint64_t getStartOfZeroSequenceBefore(uint64_t endIndex) const;

    uint64_t getStartOfOneSequenceBefore(uint64_t endIndex) const;

    bool compareAndSwap(uint64_t start1, uint64_t start2, uint64_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(uint64_t bucketCount, uint64_t bitCount);

    template<bool Value, bool Backward = false>
    static uint64_t getNextIndexWithValue(uint64_t const* dataPtr, uint64_t startingIndex, uint64_t endIndex);

    void truncateLastBucket();

    BitVector getAsBitVector(uint64_t start, uint64_t length) const;

    void setFromBitVector(uint64_t start, BitVector const& other);

    void printBits(std::ostream& out) const;
 
    // The number of bits that this bit vector can hold.
    uint64_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 uint64_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 storm::storage
 
namespace std {
template<>
struct hash<storm::storage::BitVector> {
    std::size_t operator()(storm::storage::BitVector const& bv) const;
};
}  // namespace std