#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <string>
#include <assert.h>

unsigned int time33(const char* ptr){
    unsigned int hash = 0;
    int i;
    int n = strlen(ptr);

    for(i=0;i<n;i++){
        hash = hash * 33 + ptr[i];
    }

    return hash;
}

////////////////////////////////////////////////////////////////////////

template<class K,class V>
class Comp_t {
public:
    int operator () (const K& k1,const K& k2);
};

/*
 * 模板特化
*/
template<>
class Comp_t<std::string,std::string> {
public:
    int operator () (const std::string& k1,const std::string& k2) {
        return strcmp(k1.c_str(),k2.c_str());
    }
};

template<>
class Comp_t<int,int> {
public:
    int operator () (const int& k1,const int& k2) {
        return k1 - k2;
    }
};

template<>
class Comp_t<unsigned int,unsigned int> {
public:
    int operator () (const unsigned int& k1,const unsigned int& k2) {
        return k1 - k2;
    }
};

template<>
class Comp_t<long,long> {
public:
    int operator () (const long& k1,const long& k2) {
        return k1 - k2;
    }
};

template<>
class Comp_t<unsigned long,unsigned long> {
public:
    int operator () (const unsigned long& k1,const unsigned long& k2) {
        return k1 - k2;
    }
};

template<>
class Comp_t<long long,long long> {
public:
    int operator () (const long long& k1,const long long& k2) {
        return k1 - k2;
    }
};

template<>
class Comp_t<unsigned long long,unsigned long long> {
public:
    int operator () (const long long& k1,const long long& k2) {
        return k1 - k2;
    }
};

template<>
class Comp_t<char,char> {
public:
    int operator () (const char& k1,const char& k2) {
        return (k1 - k2);
    }
};

template<>
class Comp_t<unsigned char,unsigned char> {
public:
    int operator () (const unsigned char& k1,const unsigned char& k2) {
        return (k1 - k2);
    }
};

////////////////////////////////////////////////////////////////////////



////////////////////////////////////////////////////////////////////////

template<class K>
class Hash_t {
public:
    unsigned int operator () (const K& key);
};

/*
 * 模板特化
*/
template<>
class Hash_t<std::string> {
public:
    unsigned int operator () (const std::string& key) {
        return time33(key.c_str());
    }
};

template<>
class Hash_t<int> {
public:
    unsigned int operator () (const int& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<unsigned int> {
public:
    unsigned int operator () (const unsigned int& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<long> {
public:
    unsigned int operator () (const long& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<unsigned long> {
public:
    unsigned int operator () (const unsigned long& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<long long> {
public:
    unsigned int operator () (const long long& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<unsigned long long> {
public:
    unsigned int operator () (const unsigned long long& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<char> {
public:
    unsigned int operator () (const char& key) {
        return (unsigned int)key;
    }
};

template<>
class Hash_t<unsigned char> {
public:
    unsigned int operator () (const unsigned char& key) {
        return (unsigned int)key;
    }
};

////////////////////////////////////////////////////////////////////////

template<class K,class V,class C=Comp_t<K,V>,class H=Hash_t<K> >
class Hashtable
{

public:
    Hashtable(int buckets_size = m_hash_size[0],double load_factor = 0.75f)
        :m_size_index(1),m_buckets_size(buckets_size),m_load_factor(load_factor) {

        m_table = new Entry_t[m_buckets_size];
        memset(m_table,0,sizeof(Entry_t) * m_buckets_size);

        m_element = 0;
        m_max_element = m_load_factor * m_buckets_size;
    }
    ~Hashtable(){
        int i;

        Entry_s* e;
        Node_t* node;
        Node_t* n;

        for(i=0;i<m_buckets_size;i++) {
            e = &m_table[i];

            assert(e != nullptr);

            node = e->next;

            while(node) {
                n = node;
                node = node->next;

                delete n;
            }
        }

        delete [] m_table;
    }

    V* get(const K& k) {
        unsigned int hash = m_hash(k);
        unsigned int index = hash % m_buckets_size;

        Entry_t* e = &m_table[index];

        assert(e != nullptr);

        if(e->next == NULL) {
            return NULL;
        }

        Node_t* node = e->next;
        while(node) {
            if(m_comp(node->key,k) == 0) {
                return &(node->value);
            }
            node = node->next;
        }

        return NULL;
    }

    void __insert(const K& k,const V& v) {
        unsigned int hash;
        unsigned int index;

        hash = m_hash(k);
        index = hash % m_buckets_size;

        Node_t* node = new Node_t();
        node->key = k;
        node->value = v;

        Entry_t* e = &m_table[index];

        assert(e != nullptr);

        //需要处理相同的key
        if(e->next == NULL) {
            e->next = node;
            e->key_hash = hash;

            m_element++;
        }else {
            Node_t* n = e->next;
            if(m_comp(n->key,k) == 0){
                n->value = v;
                return ;
            }else {
                while(n->next) {
                    n = n->next;

                    if(m_comp(n->key,k) == 0){
                        n->value = v;
                        return ;
                    }
                }

                n->next = node;

                m_element++;
            }
        }
    }

    void __expend() {
        std::cout<<"---------------insert expend------------"<<std::endl;

        //hash表扩容
        int buckets_size = m_buckets_size;
        Entry_t* table = m_table;

        m_buckets_size = m_hash_size[m_size_index++];
        m_max_element = m_load_factor * m_buckets_size;

        m_table = new Entry_t[m_buckets_size];

        int i;
        int index;

        for(i=0;i<buckets_size;i++) {
            index = table[i].key_hash % m_buckets_size;

            m_table[index].key_hash = table[i].key_hash;
            if(m_table[index].next == NULL) {
                m_table[index].next = table[i].next;
            }else {
                table[i].next = m_table[index].next;
                m_table[index].next = table[i].next;
            }

        }

        delete [] table;
    }

    void insert(const K& k,const V& v) {
        __insert(k,v);
        if(m_element > m_max_element) {
            __expend();
        }
    }

    void erase(const K& k) {
        unsigned int hash = m_hash(k);
        unsigned int index = hash % m_buckets_size;

        Entry_t* e = &m_table[index];

        assert(e != NULL);

        Node_t* node = e->next;
        Node_t* n;

        if(node == NULL) {
            return ;
        }
        if(m_comp(node->key,k) == 0) {
            e->next = node->next;
            delete node;
            m_element--;
        }else {
            while(node->next) {
                n = node;
                node = node->next;
                if(m_comp(node->key,k) == 0) {
                    n->next = node->next;
                    delete node;
                    m_element--;
                }
            }
        }
    }

    V& operator [] (const K& k) {
        V* v = get(k);
        if(v == NULL) {
            V* v = new V();
            insert(k,*v);
        }

        return reinterpret_cast<V&>(*(get(k)));
    }

    struct Node_s;
    typedef struct Node_s Node_t;

    struct Node_s {
        K key;
        V value;
        Node_t* next;
    } ;

    typedef struct Entry_s {
        int key_hash;
        Node_t* next;
    } Entry_t;

private:
    int m_size_index;
    int m_buckets_size;     //初始桶容量
    double m_load_factor;      //负载因子
    int m_element;
    int m_max_element;
    Entry_t* m_table;
    C m_comp;
    H m_hash;

    enum { __num_primes = 28 };

    static unsigned long m_hash_size[__num_primes];

};

template<class K,class V,class C,class H>
unsigned long Hashtable<K,V,C,H>::m_hash_size[Hashtable<K,V,C,H>::__num_primes] =
{
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
  1610612741ul, 3221225473ul, 4294967291ul
};

#endif // HASHTABLE_H