8#ifndef META_OCEAN_BASE_HASH_MAP_H
9#define META_OCEAN_BASE_HASH_MAP_H
22template <
typename TKey,
typename T>
30 using Element =
typename std::pair<std::pair<size_t, size_t>, std::pair<TKey, T>>;
71 bool insert(
const TKey& key,
const T&
element,
const bool oneOnly =
true,
const bool extendCapacity =
true);
81 bool insert(TKey&& key, T&&
element,
const bool oneOnly =
true,
const bool extendCapacity =
true);
88 bool remove(
const TKey& key);
95 bool find(
const TKey& key)
const;
103 bool find(
const TKey& key,
const T*&
element)
const;
119 const T&
element(
const TKey& key)
const;
130 inline size_t size()
const;
192template <
typename TKey,
typename T>
201template <
typename TKey,
typename T>
204 size_(hashMap.size_),
210template <
typename TKey,
typename T>
219template <
typename TKey,
typename T>
225 ocean_assert(
capacity >= hashMap.size());
227 for (
Element& hashMapElement : hashMap.elements_)
229 if (hashMapElement.first.first != 0)
231 TKey& key = hashMapElement.second.first;
232 T&
element = hashMapElement.second.second;
239 ocean_assert(
size() == hashMap.size());
245template <
typename TKey,
typename T>
266 for (
size_t n = 0; n <
elements_.size(); ++n)
281 else if (
elements_[value].second.first == key)
284 const size_t startIndex =
function_(key);
286 for (
size_t i = 0; i < n; ++i)
302 for (
size_t n = 0; n <
elements_.size(); ++n)
324 ocean_assert(
false &&
"This must never happen!");
328template <
typename TKey,
typename T>
349 for (
size_t n = 0; n <
elements_.size(); ++n)
358 elements_[value].second.first = std::move(key);
364 else if (
elements_[value].second.first == key)
367 const size_t startIndex =
function_(key);
369 for (
size_t i = 0; i < n; ++i)
385 for (
size_t n = 0; n <
elements_.size(); ++n)
394 elements_[value].second.first = std::move(key);
407 ocean_assert(
false &&
"This must never happen!");
411template <
typename TKey,
typename T>
418 for (
size_t n = 0; n <
elements_.size(); ++n)
431 if (
elements_[value].second.first == key)
434 const size_t startIndex =
function_(key);
436 for (
size_t i = 0; i < n; ++i)
455 ocean_assert(
elements_[value].first.first > 1);
457 size_t elementOffset = 0u;
459 if (
elements_[value].second.first == key)
463 size_t localValue = value;
468 size_t lastOffset = 0;
471 for (
size_t i = 1; i < endLocation; ++i)
473 const size_t testValue = (localValue + i) %
elements_.size();
475 if (
elements_[testValue].first.first >= 1)
477 if (
elements_[testValue].first.second >= i)
483 if (
elements_[testValue].first.first <= 1)
494 ocean_assert(endLocation >= lastOffset);
495 endLocation -= lastOffset;
497 elementOffset += lastOffset;
499 const size_t lastValue = (localValue + lastOffset) %
elements_.size();
507 localValue = lastValue;
509 if (
elements_[lastValue].first.first == 1)
516 const size_t startIndex =
function_(key);
518 for (
size_t i = 0u; i < elementOffset + n; ++i)
534 ocean_assert(
false &&
"This must never happen!");
538template <
typename TKey,
typename T>
545 for (
size_t n = 0; n <
elements_.size(); ++n)
556 if (
elements_[value].second.first == key)
571template <
typename TKey,
typename T>
578 for (
size_t n = 0; n <
elements_.size(); ++n)
589 if (
elements_[value].second.first == key)
605template <
typename TKey,
typename T>
612 for (
size_t n = 0; n <
elements_.size(); ++n)
623 if (
elements_[value].second.first == key)
639template <
typename TKey,
typename T>
646 for (
size_t n = 0; n <
elements_.size(); ++n)
657 if (
elements_[value].second.first == key)
669 ocean_assert(
false &&
"Invalid key!");
670 return elements_.cbegin()->second.second;
673template <
typename TKey,
typename T>
688template <
typename TKey,
typename T>
694template <
typename TKey,
typename T>
700template <
typename TKey,
typename T>
706template <
typename TKey,
typename T>
709 if (
this != &hashMap)
719template <
typename TKey,
typename T>
722 if (
this != &hashMap)
724 elements_ = std::move(hashMap.elements_);
725 size_ = hashMap.size_;
734template <
typename TKey,
typename T>
740template <
typename TKey,
typename T>
746 size_t slotCounters = 0;
747 size_t probeSequenceLengths = 0;
751 slotCounters +=
element.first.first;
756 probeSequenceLengths +=
element.first.second + 1;
760 return count ==
size_ && slotCounters == probeSequenceLengths;
size_t capacity() const
Returns the capacity of this hash map.
Definition HashMap.h:695
bool isConsistent() const
Returns whether this hash map is still consistent.
Definition HashMap.h:741
void clear()
Removes all elements from this has map.
Definition HashMap.h:674
size_t size_
Number of elements this has map holds.
Definition HashMap.h:186
bool isEmpty() const
Returns whether this hash map is empty.
Definition HashMap.h:701
typename std::pair< std::pair< size_t, size_t >, std::pair< TKey, T > > Element
Definition of a pair combining a counter states and an object.
Definition HashMap.h:30
HashMap< TKey, T > & operator=(const HashMap< TKey, T > &hashMap)
Assign operator.
Definition HashMap.h:707
size_t size() const
Returns the number of elements this hash map currently holds.
Definition HashMap.h:689
std::vector< Element > Elements
Definition of a vector holding the map objects.
Definition HashMap.h:35
bool find(const TKey &key) const
Returns whether this hash map holds a given element.
Definition HashMap.h:539
ValueFunction function_
Value function.
Definition HashMap.h:189
const T & element(const TKey &key) const
Returns a specific element of this map.
Definition HashMap.h:640
bool remove(const TKey &key)
Removes an element from this hash map.
Definition HashMap.h:412
static size_t defaultHashFunction(const TKey &key)
Default hash function for elements supporting an cast size_t cast.
Definition HashMap.h:735
bool insert(const TKey &key, const T &element, const bool oneOnly=true, const bool extendCapacity=true)
Adds a new element to this hash map.
Definition HashMap.h:246
size_t(*)(const TKey &key) ValueFunction
Definition of a function pointer returning a hash map value.
Definition HashMap.h:40
HashMap(const HashMap< TKey, T > &hashMap)
Copy constructor.
Definition HashMap.h:193
Elements elements_
Hash map elements.
Definition HashMap.h:183
The namespace covering the entire Ocean framework.
Definition Accessor.h:15