#ifndef HASHMAP_H
#define HASHMAP_H

#include "utils/Array.h"

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

    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;
    Array<K, CAPACITY> keys;
    Array<V, CAPACITY> values;

    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 -1;
            } else if(keys[h] == key) {
                return h;
            }
        }
        return -1;
    }

public:

    HashMap() : used(false) {
    }

    void add(const K& key, const V& value) {
        int base = hash(key);
        for(int i = 0; i < CAPACITY; i++) {
            int h = (base + i) & MASK;
            if(!used[h]) {
                used[h] = true;
                keys[h] = key;
                values[h] = value;
                return;
            } else if(keys[h] == key) {
                values[h] = value;
                return;
            }
        }
    }

    const V& search(const K& key, const V& notFound) const {
        int index = searchIndex(key);
        return index == -1 ? notFound : values[index];
    }

    V& search(const K& key, V& notFound) {
        int index = searchIndex(key);
        return index == -1 ? notFound : values[index];
    }

    bool contains(const K& key) const {
        return searchIndex(key) != -1;
    }

    void clear() {
        used.fill(false);
    }

private:

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

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

#endif