#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];
    }

    int 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 -h;
            } else if(getKey(h) == key) {
                return h;
            }
        }
        return -CAPACITY;
    }

    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;
    }

    void add(const K& key, const V& value) {
        int index = searchIndex(key);
        if(index >= 0) {
            getValue(index) = value;
        } else if(index > -CAPACITY) {
            index = -index;
            used[index] = true;
            new (reinterpret_cast<K*> (keys) + index) K(key);
            new (reinterpret_cast<V*> (values) + index) V(value);
        }
    }

    void add(const K& key, const V&& value) {
        int index = searchIndex(key);
        if(index >= 0) {
            getValue(index) = std::move(value);
        } else if(index > -CAPACITY) {
            index = -index;
            used[index] = true;
            new (reinterpret_cast<K*> (keys) + index) K(key);
            new (reinterpret_cast<V*> (values) + index) V(std::move(value));
        }
    }

    const V& search(const K& key, const V& notFound) const {
        int index = searchIndex(key);
        return index < 0 ? notFound : getValue(index);
    }

    V& search(const K& key, V& notFound) {
        int index = searchIndex(key);
        return index < 0 ? notFound : getValue(index);
    }

    bool contains(const K& key) const {
        return searchIndex(key) >= 0;
    }

    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