gaming-core/utils/HashMap.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include <iostream>

#include "utils/Array.h"

template<typename K, typename V, int N_MIN>
class HashMap final {

    static constexpr int getCapacity() {
        int i = 1;
        while(i < N_MIN) {
            i <<= 1;
        }
        return i;
    }

    static constexpr int CAPACITY = getCapacity();
    static constexpr int MASK = CAPACITY - 1;

    Array<bool, CAPACITY> used;
    char keys[sizeof (K) * CAPACITY];
    char values[sizeof (V) * CAPACITY];

    const K& getKey(int index) const {
        return reinterpret_cast<const K*> (keys)[index];
    }

    V& getValue(int index) {
        return reinterpret_cast<V*> (values)[index];
    }

    const V& getValue(int index) const {
        return reinterpret_cast<const V*> (values)[index];
    }

    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]) {
                return Search(h, FREE_INDEX_FOUND);
            } else if(getKey(h) == key) {
                return Search(h, KEY_FOUND);
            }
        }
        return Search(-1, NOTHING_FOUND);
    }

    void copy(const HashMap& other) {
        for(int i = 0; i < other.CAPACITY; i++) {
            if(other.used[i]) {
                used[i] = true;
                new (reinterpret_cast<K*> (keys) + i) K(other.getKey(i));
                new (reinterpret_cast<V*> (values) + i) V(other.getValue(i));
            }
        }
    }

    void move(HashMap& other) {
        for(int i = 0; i < other.CAPACITY; i++) {
            if(other.used[i]) {
                used[i] = true;
                new (reinterpret_cast<K*> (keys) + i) K(std::move(other.getKey(i)));
                new (reinterpret_cast<V*> (values) + i) V(std::move(other.getValue(i)));
            }
        }
        other.clear();
    }

public:

    HashMap() : used(false) {
    }

    ~HashMap() {
        clear();
    }

    HashMap(const HashMap& other) : used(false) {
        copy(other);
    }

    HashMap& operator=(const HashMap& other) {
        clear();
        copy(other);
        return *this;
    }

    HashMap(HashMap&& other) : used(false) {
        move(other);
    }

    HashMap& operator=(HashMap&& other) {
        clear();
        move(other);
        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] = true;
            new (reinterpret_cast<K*> (keys) + s.index) K(key);
            new (reinterpret_cast<V*> (values) + s.index) V(args...);
            return false;
        }
        return true;
    }

    void add(const K& key, const V& value) {
        Search s = searchIndex(key);
        if(s.result == KEY_FOUND) {
            getValue(s.index) = value;
        } else if(s.result == FREE_INDEX_FOUND) {
            used[s.index] = true;
            new (reinterpret_cast<K*> (keys) + s.index) K(key);
            new (reinterpret_cast<V*> (values) + s.index) V(value);
        }
    }

    void add(const K& key, const V&& value) {
        Search s = searchIndex(key);
        if(s.result == KEY_FOUND) {
            getValue(s.index) = std::move(value);
        } else if(s.result == FREE_INDEX_FOUND) {
            used[s.index] = true;
            new (reinterpret_cast<K*> (keys) + s.index) K(key);
            new (reinterpret_cast<V*> (values) + s.index) V(std::move(value));
        }
    }

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

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

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

    void clear() {
        K* k = reinterpret_cast<K*> (keys);
        V* v = reinterpret_cast<V*> (values);
        for(int i = 0; i < CAPACITY; i++) {
            if(used[i]) {
                k[i].~K();
                v[i].~V();
            }
        }
        used.fill(false);
    }

private:

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

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

#endif