#include<iostream>
#include<utility>
using namespace std;

/*
假设Key只为int类型
如果Key为其他类型，添加一个hash函数将Key转换为int即可
*/
template<class K,class E>
class arrayHashTable{
private:    
    int divisor;//D in k%D
    int size;//散列大小
    pair<K,E>** table;
public:
    arrayHashTable(int&d);
    ~arrayHashTable();

    bool isEmpty()const{return this->size==0;}
    int getSize()const{return this->size;}
    int search(int&key)const;//查找给定的key桶的位置
    pair<K,E>*find(int&key)const;//查找给定key元素的结果
    void insert(pair<K,E>&pair);
    void erase(int&key);
    void output()const;
};

template<class K,class E>
arrayHashTable<K,E>::arrayHashTable(int&d){
    divisor=d;
    size=0;
    table=new pair<K,E>*[divisor]();
}

template<class K,class E>
arrayHashTable<K,E>::~arrayHashTable(){
    for(int i=0;i<divisor;i++){
        if(table[i]!=NULL){
            delete table[i];
        }
    }
    delete[]table;
}

template<class K,class E>
int arrayHashTable<K,E>::search(int&key)const{
    //查找key对应的元素的位置，如果存在则返回
    /*
    1.从初始桶开始，线性探查找到了对应位置
    2.从初始桶开始，线性探查找到了空桶，key对应的桶不含此元素
    3.从初始桶开始，线性探查回到了起点，则散列表不含此元素
    注意，这里将散列视为环形表
    */
   int start=key%divisor;//起始桶的位置
   int end=start;//探查结束标识，防止无限循环
   do
   {
      if(table[start]==nullptr||table[start]->first==key)
      {
        return start;
      }
      start=(start+1)%divisor;  
   } while (start!=end);
   
   //回到起始位置
   return end;
}

template<class K,class E>
pair<K,E>* arrayHashTable<K,E>::find(int&key)const{
    int target=this->search(key);
    
    //寻找此位置的元素关键字是否对应着key
    if(table[target]==nullptr||table[target]->first!=key)
        return nullptr;
    return table[target];
}

template<class K,class E>
void arrayHashTable<K,E>::insert(std::pair<K,E>&_pair){
    int p=this->search(_pair.first);
    cout<<p<<endl;
    //table[p]==nullptr说明可以插入
    if(table[p]==nullptr){
        table[p]=new std::pair<K,E>(_pair);
        this->size++;
    }
    else{
        //已经存在此关键字，更新element值
        if(table[p]->first==_pair.first)
            table[p]->second=_pair.second;
        else
            cout<<"The table is full."<<endl;
    }
}

template<class K,class E>
void arrayHashTable<K,E>::erase(int&key){
    int p=this->search(key);

    //未寻找到此key值的桶
    if(table[p]==nullptr||table[p]->first!=key){
        cout<<"No such key in HashTable."<<endl;
        return;
    }
    else{
        //这里注意需要将后续桶都向前移动
        delete table[p];
        table[p]=nullptr;
        
        //确定最后一个需要移动的桶在哪
        //由于散列表为环形，end判断条件如下：
        //1.下一个桶为空
        //2.下一个桶的关键字映射后不等于p
        int end=p;
        while(table[(end+1)%divisor]!=nullptr&&
            table[(end+1)%divisor]->first%divisor==p){
            end=(end+1)%divisor;
        }
        while (p!=end)
        {
            table[p]=table[(p+1)%divisor];
            p=(p+1)%divisor;
        }
        table[p]=nullptr;
    }
}

template<class K,class E>
void arrayHashTable<K,E>::output()const{
    for(int i=0;i<divisor;i++){
        if(table[i]!=nullptr){
            cout<<"Key: "<<table[i]->first<<"Element: "<<table[i]->second<<endl;
        }
    }
}

int main(){
    int d=11;
    arrayHashTable<int,int> h(d);
    pair<int,int>p1(2,76);
    pair<int,int>p2(4,91);
    pair<int,int>p3(9,33);
    h.insert(p1);
    h.insert(p2);
    h.insert(p3);
    h.output();

    return 0;
}