#ifndef __HASH_MAP
#define __HASH_MAP


template <class T>
struct default_hash_function
{
    unsigned long operator()(const T& x);
};

template <class T>
inline unsigned long default_hash_function<T>::operator()(const T& x)
{
    return *(reinterpret_cast<const unsigned long*>(&x));
}


template <class K, class V, class HF = default_hash_function<K> >
class hash_map
{
public:
    hash_map(int size = 103);
    ~hash_map();

    void add(const K& key, const V& value);
    void remove(const K& key);
    const V& lookup(const K& key, const V& if_not_found = V());

private:
    // Declared but not defined
    hash_map(const hash_map&);
    hash_map& operator=(const hash_map&);

    struct node
    {
        K key;
        V value;
        node* next;
    };

    node** M;
    int size;
    HF hash;
};


template <class K, class V, class HF>
inline hash_map<K,V,HF>::hash_map(int _size) : size(_size), hash(HF())
{
    M = new node*[size];
    for (int i = 0; i < size; i++)
        M[i] = 0;
}


template <class K, class V, class HF>
hash_map<K,V,HF>::~hash_map()
{
    for (int i = 0; i < size; i++)
    {
        while (M[i])
        {
            node* p = M[i]->next;
            delete M[i];
            M[i] = p;
        }
    }

    delete[] M;
}


template <class K, class V, class HF>
void hash_map<K,V,HF>::add(const K& key, const V& value)
{
    unsigned long i = hash(key) % size;

    node* p = new node;
    p->key = key;
    p->value = value;
    p->next = M[i];
    M[i] = p;
}


template <class K, class V, class HF>
void hash_map<K,V,HF>::remove(const K& key)
{
    unsigned long i = hash(key) % size;

    node* prev = 0;
    for (node* p = M[i]; p; prev = p, p = p->next)
    {
        if (p->key == key)
        {
            (prev ? prev->next : M[i]) = p->next;
            delete p;
            return;
        }
    }
}


template <class K, class V, class HF>
const V& hash_map<K,V,HF>::lookup(const K& key, const V& if_not_found)
{
    unsigned long i = hash(key) % size;

    for (node* p = M[i]; p; p = p->next)
    {
        if (p->key == key)
            return p->value;
    }
	
    return if_not_found;
}


#endif