BitVectorHashMap.h

Go to the documentation of this file.

#pragma once
 
#include <cstdint>
#include <functional>
 
#include "storm/storage/BitVector.h"
 
namespace storm {
namespace storage {

//        template<typename ValueType, typename Hash = std::hash<storm::storage::BitVector>>
//        template<typename ValueType, typename Hash = FNV1aBitVectorHash>
template<typename ValueType, typename Hash = Murmur3BitVectorHash<ValueType>>
class BitVectorHashMap {
   public:
    class BitVectorHashMapIterator {
       public:
        BitVectorHashMapIterator(BitVectorHashMap const& map, BitVector::const_iterator indexIt);
 
        // Methods to compare two iterators.
        bool operator==(BitVectorHashMapIterator const& other) const;
        bool operator!=(BitVectorHashMapIterator const& other) const;
 
        // Methods to move iterator forward.
        BitVectorHashMapIterator& operator++(int);
        BitVectorHashMapIterator& operator++();
 
        // Method to retrieve the currently pointed-to bit vector and its mapped-to value.
        std::pair<storm::storage::BitVector, ValueType> operator*() const;
 
       private:
        // The map this iterator refers to.
        BitVectorHashMap const& map;
 
        // An iterator to the bucket this iterator points to.
        BitVector::const_iterator indexIt;
    };
 
    typedef BitVectorHashMapIterator const_iterator;

    BitVectorHashMap(uint64_t bucketSize, uint64_t initialSize = 1000, double loadFactor = 0.75);
 
    BitVectorHashMap(BitVectorHashMap const&) = default;
    BitVectorHashMap(BitVectorHashMap&&) = default;
    BitVectorHashMap& operator=(BitVectorHashMap const&) = default;
    BitVectorHashMap& operator=(BitVectorHashMap&&) = default;

    ValueType findOrAdd(storm::storage::BitVector const& key, ValueType const& value);

    std::pair<ValueType, uint64_t> findOrAddAndGetBucket(storm::storage::BitVector const& key, ValueType const& value);

    std::pair<storm::storage::BitVector, ValueType> getBucketAndValue(uint64_t bucket) const;

    ValueType getValue(storm::storage::BitVector const& key) const;

    ValueType getValue(uint64_t bucket) const;

    bool contains(storm::storage::BitVector const& key) const;

    const_iterator begin() const;

    const_iterator end() const;

    uint64_t size() const;

    uint64_t capacity() const;

    void remap(std::function<ValueType(ValueType const&)> const& remapping);
 
   private:
    bool isBucketOccupied(uint_fast64_t bucket) const;

    std::pair<bool, uint64_t> findBucket(storm::storage::BitVector const& key) const;

    void increaseSize();

    bool checkIncreaseSize();

    uint64_t getCurrentShiftWidth() const;
 
    // The load factor determining when the size of the map is increased.
    double loadFactor;
 
    // The size of one bucket.
    uint64_t bucketSize;
 
    // The number of buckets is 2^currentSize.
    uint64_t currentSize;
 
    // The buckets that hold the elements of the map.
    storm::storage::BitVector buckets;
 
    // A bit vector that stores which buckets actually hold a value.
    storm::storage::BitVector occupied;
 
    // A vector of the mapped-to values. The entry at position i is the "target" of the key in bucket i.
    std::vector<ValueType> values;
 
    // The number of elements in this map.
    uint64_t numberOfElements;
 
    // Functor object that are used to perform the actual hashing.
    Hash hasher;
};
 
}  // namespace storage
}  // namespace storm