gaming-core/utils/HashMap.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include "utils/Array.h"
#include "utils/List.h"
#include "utils/StringBuffer.h"
#include "utils/Utils.h"

template<typename K, typename V, int N_MIN>
class HashMap final {
    static constexpr int CAPACITY = 1 << Utils::roundUpLog2(N_MIN);
    static constexpr int MASK = CAPACITY - 1;

    Array<int, CAPACITY> used;
    List<K, CAPACITY> keys;
    List<V, CAPACITY> values;

    enum SearchResult { FREE_INDEX_FOUND, KEY_FOUND, NOTHING_FOUND };

    struct Search {
        int index;
        SearchResult result;

        Search(int index, SearchResult result) : index(index), result(result) {
        }
    };

    Search searchIndex(const K& key) const {
        int base = hash(key);
        for(int i = 0; i < CAPACITY; i++) {
            int h = (base + i) & MASK;
            if(used[h] == -1) {
                return Search(h, FREE_INDEX_FOUND);
            } else if(keys[used[h]] == key) {
                return Search(h, KEY_FOUND);
            }
        }
        return Search(-1, NOTHING_FOUND);
    }

    template<typename H>
    static int hash(const H& key) {
        return key.hashCode();
    }

    static int hash(int key) {
        return key;
    }

public:
    HashMap() : used(-1) {
    }

    HashMap(const HashMap& other) : used(other.used), keys(other.keys), values(other.values) {
    }

    HashMap& operator=(const HashMap& other) {
        if(&other != this) {
            used = other.used;
            keys = other.keys;
            values = other.values;
        }
        return *this;
    }

    HashMap(HashMap&& other) : used(other.used), keys(std::move(other.keys)), values(std::move(other.values)) {
        other.used.fill(-1);
    }

    HashMap& operator=(HashMap&& other) {
        if(&other != this) {
            used = std::move(other.used);
            keys = std::move(other.keys);
            values = std::move(other.values);
            other.used.fill(-1);
        }
        return *this;
    }

    template<typename... Args>
    bool tryEmplace(const K& key, Args&&... args) {
        Search s = searchIndex(key);
        if(s.result == FREE_INDEX_FOUND) {
            used[s.index] = keys.getLength();
            keys.add(key);
            values.add(std::forward<Args>(args)...);
            return false;
        }
        return true;
    }

    HashMap& add(const K& key, const V& value) {
        Search s = searchIndex(key);
        if(s.result == KEY_FOUND) {
            values[used[s.index]] = value;
        } else if(s.result == FREE_INDEX_FOUND) {
            used[s.index] = keys.getLength();
            keys.add(key);
            values.add(value);
        }
        return *this;
    }

    HashMap& add(const K& key, const V&& value) {
        Search s = searchIndex(key);
        if(s.result == KEY_FOUND) {
            values[used[s.index]] = std::move(value);
        } else if(s.result == FREE_INDEX_FOUND) {
            used[s.index] = keys.getLength();
            keys.add(key);
            values.add(std::move(value));
        }
        return *this;
    }

    const V& search(const K& key, const V& notFound) const {
        Search s = searchIndex(key);
        return s.result == KEY_FOUND ? values[used[s.index]] : notFound;
    }

    V& search(const K& key, V& notFound) {
        Search s = searchIndex(key);
        return s.result == KEY_FOUND ? values[used[s.index]] : notFound;
    }

    bool contains(const K& key) const {
        return searchIndex(key).result == KEY_FOUND;
    }

    HashMap& clear() {
        keys.clear();
        values.clear();
        used.fill(-1);
        return *this;
    }

    template<int L>
    void toString(StringBuffer<L>& s) const {
        s.append("[");
        bool c = false;
        for(int i = 0; i < CAPACITY; i++) {
            if(used[i] == -1) {
                continue;
            } else if(c) {
                s.append(", ");
            }
            s.append(keys[used[i]]).append(" = ").append(values[used[i]]);
            c = true;
        }
        s.append("]");
    }

    V* begin() {
        return values.begin();
    }

    V* end() {
        return values.end();
    }

    const V* begin() const {
        return values.begin();
    }

    const V* end() const {
        return values.end();
    }
};

#endif