#include <iostream>

#include <cstring>

#include <string>

typedef  unsigned int SIZE_T;

using namespace std;

/** HashMap模板的C++实现，用拉链法解决冲突

*注意：需要为每一种KeyType两个仿函数：HashFunc and EqualKey

*/

template<typename KeyType, typename ValueType, typename HashFunc, typename EqualKey>

class HashMap{

#define DEFAULT_CAPACITY  43 // hash表初始化容量

#define LOADFACTOR 0.7   //负载因子

    class KeyNode{ //存放key value对

    public:

        KeyType key;

        ValueType value;

        KeyNode *next;

        KeyNode(){}

        KeyNode(const KeyNode & rhs){

            Assign(rhs);

        }

        const KeyNode & operator =(const KeyNode & rhs){

            Assign(rhs);

            return *this;

        }

        void Assign(const KeyNode & rhs){

            this->key = rhs.key;

            this->value = rhs.value;

            this->next = rhs.next;

        }

    };

public:

    HashMap(){

        table = new KeyNode* [DEFAULT_CAPACITY];

        ::memset(table,,DEFAULT_CAPACITY * sizeof(KeyNode*));

        size  =;

        capacity = DEFAULT_CAPACITY;

        hash = HashFunc();

        equal = EqualKey();

    }

    bool put(const KeyType & key, const ValueType & value){

        SIZE_T index = hash(key) % capacity;

        if(table[index] == NULL){

            KeyNode *temp = new KeyNode();

            temp->key = key;

            temp->value = value;

            temp->next =NULL;

            table[index] = temp;

        }else{

            KeyNode * pre=table[index];

            while(pre->next != NULL){

                if(equal(pre->key, key)) return false;  //重复

                pre = pre->next;

            }

            if(equal(pre->key, key)) return false;  //重复

            KeyNode *temp = new KeyNode();

            temp->key = key;

            temp->value = value;

            temp->next =NULL;

            pre->next = temp;

        }

        size ++;

        if(size*1.0/capacity > LOADFACTOR) this->rehash();

        return true;

    }

    bool remove(const KeyType & key){

        SIZE_T index = hash(key) % capacity;

        if(table[index] == NULL) return false;

        KeyNode *temp = table[index];

        if(equal(temp->key,key)){

            table[index] = temp->next;

            delete temp;

            size --;

            return true;

        }

        while(temp->next != NULL){

            if(equal(temp->next->key, key)){

                KeyNode * del = temp->next;

                temp->next = del->next;

                delete del;

                size --;

                return true;

            }else{

                temp = temp->next;

            }

        }

        return false;

    }

    bool exist(const KeyType & key)const{

        SIZE_T index = hash(key) % capacity;

        if(table[index] == NULL) return false;

        KeyNode *temp = table[index];

        while(temp!= NULL){

            if(equal(temp->key,key)) return true;

            temp = temp->next;

        }

        return false;

    }

    /*

    KeyNode  find(const KeyType & key){

        SIZE_T index = hash(key) % capacity;

        if(table[index] == NULL) return NULL;

        KeyNode *temp = table[index];

        while(temp!= NULL){

            if(equal(temp->key,key)) return *temp;

            temp = temp->next;

        }

        return NULL;

    }

    */

    ValueType & operator[](const KeyType & key){

        if(!exist(key))    put(key,ValueType());

        return get(key);

    }

    SIZE_T Size(){

        return size;

    }

    void display(){

        cout << "size:"<<size<<endl;

        for(SIZE_T i=;i<this->capacity;i++){

            KeyNode * temp = table[i];

            while(temp != NULL){

             cout <<"("<<temp->key<<","<<temp->value<<") ";

                 temp = temp->next;

            }

            if(table[i]!=NULL) cout << endl;

        }

    }

    ~HashMap(){

        this->destroy(table);

    }

private:

    KeyNode ** table;

    SIZE_T capacity;

    SIZE_T  size;

    HashFunc hash;

    EqualKey equal;

     KeyNode ERROE;

    ValueType & get(const KeyType key){

        SIZE_T index = hash(key) % capacity;

        if(table[index] == NULL) return ERROE.value;

        KeyNode *temp = table[index];

        while(temp!= NULL){

            if(equal(temp->key,key)) return temp->value;

            temp = temp->next;

        }

        return ERROE.value;

    }

    //未实现

    void rehash(){

        //得到一个两倍左右大小的capacity（最好为素数），重新散列

    }

    void destroy(KeyNode ** hashtable){

        for(SIZE_T i=;i<this->capacity;i++){

            KeyNode * temp = hashtable[i];

            while(temp != NULL){

                KeyNode *del = temp;

                 temp = temp->next;

                 delete del;

            }

        }

        delete []hashtable;

    }

};

class HashFuncInt{

public:

    SIZE_T operator()(  int key)const{

        return key;

    }

};

class EqualFuncInt{

public:

    bool operator()(int keyA, int keyB)const{

        return keyA == keyB;

    }

};

int main()

{

   const int scale = ;

    //内存泄露性能测试

    while(false){

        HashMap<int,int,HashFuncInt,EqualFuncInt> hm;

        for(int i=;i<scale;i++){

            hm.put(i,i*(i+));

        }

        hm.display();

        for(int i=;i<scale;i+=)

            hm.remove(i);

        hm.display();

        for(int i=;i<scale;i+=)

            hm[i]=i*;

        hm.display();

    }

    //模板实用性测试

    return ;

}