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/Types.h"
#include "utils/Utils.h"

#include <unordered_map>

template<typename K, typename V>
struct HashMap final {
    struct Node {
        friend HashMap;
        friend List<Node>;

        const K key;
        V value;

    private:
        int next;

        Node(const K& key, const V& value) : key(key), value(value), next(-1) {
        }

        Node(const K& key, V&& value)
            : key(key), value(std::move(value)), next(-1) {
        }

        template<typename... Args>
        Node(const K& key, Args&&... args)
            : key(key), value(std::forward<Args>(args)...), next(-1) {
        }
    };

private:
    List<int> nodePointers;
    List<Node> nodes;

public:
    HashMap(int minCapacity = 8) {
        nodePointers.resize(1 << Utils::roundUpLog2(minCapacity), -1);
    }

    template<typename... Args>
    bool tryEmplace(const K& key, Args&&... args) {
        int pointer = prepareAdd(key);
        if(pointer == -1) {
            nodes.add(key, std::forward<Args>(args)...);
            return false;
        }
        return true;
    }

    HashMap& add(const K& key, const V& value) {
        int pointer = prepareAdd(key);
        if(pointer != -1) {
            nodes[pointer].value = value;
        } else {
            nodes.add(key, value);
        }
        return *this;
    }

    HashMap& add(const K& key, V&& value) {
        int pointer = prepareAdd(key);
        if(pointer != -1) {
            nodes[pointer].value = std::move(value);
        } else {
            nodes.add(key, std::move(value));
        }
        return *this;
    }

    const V* search(const K& key) const {
        Hash h = hash(key);
        int pointer = nodePointers[h];
        while(pointer != -1) {
            if(nodes[pointer].key == key) {
                return &(nodes[pointer].value);
            }
            pointer = nodes[pointer].next;
        }
        return nullptr;
    }

    V* search(const K& key) {
        return const_cast<V*>(static_cast<const HashMap*>(this)->search(key));
    }

    bool contains(const K& key) const {
        return search(key) != nullptr;
    }

    HashMap& clear() {
        for(int& pointer : nodePointers) {
            pointer = -1;
        }
        nodes.clear();
        return *this;
    }

    Node* begin() {
        return nodes.begin();
    }

    Node* end() {
        return nodes.end();
    }

    const Node* begin() const {
        return nodes.begin();
    }

    const Node* end() const {
        return nodes.end();
    }

    template<int L>
    void toString(StringBuffer<L>& s) const {
        s.append("[");
        bool c = false;
        for(const Node& n : nodes) {
            if(c) {
                s.append(", ");
            }
            s.append(n.key).append(" = ").append(n.value);
            c = true;
        }
        s.append("]");
    }

private:
    template<typename H>
    Hash hash(const H& key) const {
        return fullHash(key) & (nodePointers.getLength() - 1);
    }

    template<typename H>
    Hash fullHash(const H& key) const {
        return key.hashCode();
    }

    Hash fullHash(int key) const {
        return key;
    }

    void rehash() {
        if(nodes.getLength() < nodePointers.getLength()) {
            return;
        }
        HashMap<K, V> map(nodePointers.getLength() * 2);
        for(const Node& n : nodes) {
            map.add(n.key, std::move(n.value));
        }
        *this = std::move(map);
    }

    int prepareAdd(const K& key) {
        rehash();
        Hash h = hash(key);
        int pointer = nodePointers[h];
        if(pointer == -1) {
            nodePointers[h] = nodes.getLength();
            return -1;
        }
        while(true) {
            if(nodes[pointer].key == key) {
                return pointer;
            } else if(nodes[pointer].next == -1) {
                nodes[pointer].next = nodes.getLength();
                return -1;
            }
            pointer = nodes[pointer].next;
        }
    }
};

#endif