cube-game-plus-plus/data/HashMap.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include <iostream>

constexpr static int NUMBER_OF_PRIMES = 26;
constexpr static int PRIMES[26] = 
{
    17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719,
    175447, 350899, 701819, 1403641, 2807303, 5614657, 11229331, 22458671,
    44917381, 89834777, 179669557, 359339171, 718678369
};

template<class K, class V>
class HashMap
{
public:
    HashMap(int initialLoad, unsigned int (*hasher)(K)) : hasher(hasher)
    {
        primeIndex = getHigherPrimeIndex(initialLoad);
        capacity = PRIMES[primeIndex];
        resizeCap = (capacity >> 2) * 3;
        
        data = new Node*[capacity];
        for(int i = 0; i < capacity; i++)
        {
            data[i] = nullptr;
        }
        entries = 0;
    }
    
    ~HashMap()
    {
        for(int i = 0; i < capacity; i++)
        {
            Node* n = data[i];
            while(n != nullptr)
            {
                Node* next = n->next;
                delete n;
                n = next;
            }
        }
        delete[] data;
    }
    
    int getCapacity() const
    {
        return capacity;
    }
    
    int getSize() const
    {
        return entries;
    }
    
    void put(K k, V v)
    {
        ensureCapacity();
        unsigned int hash = hasher(k) % capacity;
        if(data[hash] == nullptr)
        {
            data[hash] = new Node(k, v);
            entries++;
        }
        else
        {
            Node* n = data[hash];
            while(true)
            {
                if(n->k == k)
                {
                    n->v = v;
                    break;
                }
                else if(n->next == nullptr)
                {
                    n->next = new Node(k, v);
                    entries++;
                    break;
                }
                n = n->next;
            }
        }
    }
    
    V remove(K k, V notFound)
    {
        unsigned int hash = hasher(k) % capacity;
        if(data[hash] == nullptr)
        {
            return notFound;
        }
        else
        {
            Node* n = data[hash];
            if(n->k == k)
            {
                V v = n->v;
                data[hash] = n->next;
                delete n;
                entries--;
                return v;
            }
            
            while(n->next != nullptr)
            {
                if(n->next->k == k)
                {
                    Node* n = n->next;
                    n->next = n->next->next;
                    V v = n->v;
                    delete n;
                    entries--;
                    return v;
                }
            }
            return notFound;
        }
    }
    
    bool remove(K k)
    {
        unsigned int hash = hasher(k) % capacity;
        if(data[hash] == nullptr)
        {
            return false;
        }
        else
        {
            Node* n = data[hash];
            if(n->k == k)
            {
                data[hash] = n->next;
                delete n;
                entries--;
                return true;
            }
            
            while(n->next != nullptr)
            {
                if(n->next->k == k)
                {
                    Node* n = n->next;
                    n->next = n->next->next;
                    delete n;
                    entries--;
                    return true;
                }
            }
            return false;
        }
    }
    
    V get(K k, V error) const
    {
        unsigned int hash = hasher(k) % capacity;
        if(data[hash] == nullptr)
        {
            return error;
        }
        else
        {
            for(Node* n = data[hash]; n != nullptr; n = n->next)
            {
                if(n->k == k)
                {
                    return n->v;
                }
            }
            return error;
        }
    }
    
    void clear()
    {
        for(int i = 0; i < capacity; i++)
        {
            Node* n = data[i];
            while(n != nullptr)
            {
                Node* next = n->next;
                delete n;
                n = next;
            }
            data[i] = nullptr;
        }
        entries = 0;
    }
    
    void print() const
    {
        for(int i = 0; i < capacity; i++)
        {
            Node* n = data[i];
            std::cout << i << ": ";
            if(n != nullptr)
            {
                std::cout << "(" << n->k << " = " << n->v << ")";
                while(n->next != nullptr)
                {
                    n = n->next;
                    std::cout << " -> (" << n->k << " = " << n->v << ")";
                }
            }
            std::cout << std::endl;
        }
    }
    
    void printStats() const
    {
        int fill = capacity;
        int cells = capacity;
        for(int i = 0; i < capacity; i++)
        {
            Node* n = data[i];
            if(n != nullptr)
            {
                while(n->next != nullptr)
                {
                    fill++;
                    n = n->next;
                }
            }
        }
        std::cout << (double) fill / cells << std::endl;
    }
    
private:
    class Node
    {
    public:
        Node* next = nullptr;
        K k;
        V v;
        
        Node(K k, V v) : k(k), v(v) 
        {
        }
    };  
    
    int getHigherPrimeIndex(int lower) const
    {
        int low = 0;
        int high = NUMBER_OF_PRIMES - 1;
        int mid;
        while(true)
        {
            if(low == high)
            {
                return low;
            }
            mid = (high + low) >> 1;
            if(PRIMES[mid] >= lower)
            {
                high = mid;
            }
            else
            {
                low = mid + 1;
            }
        }
    }
    
    void ensureCapacity()
    {
        if(entries < resizeCap)
        {
            return;
        }
        
        primeIndex++;
        if(primeIndex >= NUMBER_OF_PRIMES)
        {
            return;
        }
        
        int oldCapacity = capacity;
        capacity = PRIMES[primeIndex];
        
        //std::cout << "resize from " << oldCapacity << " to " << capacity << std::endl; 
        
        resizeCap = (capacity >> 2) * 3;
        
        Node** newData = new Node*[capacity];
        for(int i = 0; i < capacity; i++)
        {
            newData[i] = nullptr;
        }
        
        for(int i = 0; i < oldCapacity; i++)
        {
            Node* old = data[i];
            if(old != nullptr)
            {
                unsigned int hash = hasher(old->k) % capacity;
                Node* n = newData[hash];
                if(n == nullptr)
                {
                    newData[hash] = old;
                }
                else
                {
                    while(n->next != nullptr)
                    {
                        n = n->next;
                    }
                    n->next = old;
                }
                
                while(old->next != nullptr)
                {
                    n = old->next;
                    old->next = nullptr;
                    hash = hasher(n->k) % capacity;
                    Node* m = newData[hash];
                    if(m == nullptr)
                    {
                        newData[hash] = n;
                    }
                    else
                    {
                        while(m->next != nullptr)
                        {
                            m = m->next;
                        }
                        m->next = n;
                    }
                    old = n;
                }
            }
        }
        
        delete[] data;
        data = newData;
    }
    
    unsigned int (*hasher)(K); 
    
    int primeIndex;
    int capacity;
    int resizeCap;
    
    Node** data;
    int entries;
};

#endif