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

template<class K,class E>
struct Node{
    std::pair<K,E>element;
    Node<K,E>*next;
    Node(std::pair<K,E>&pair):element(pair),next(nullptr){};
};

template<class K,class E>
class sortedChain{
private:
    Node<K,E>*head;
    int size;
public:
    sortedChain(){
        head=nullptr;
        size=0;
    };
    ~sortedChain();

    bool isEmpty()const{
        return size==0;
    }
    int getSize()const{
        return size;
    }
    std::pair<K,E>*find(int&key)const;//假设关键字只为int型
    void insert(std::pair<K,E>&p);
    void erase(int&key);
    void output();
};

template<class K,class E>
sortedChain<K,E>::~sortedChain(){
    Node<K,E>*ptr=this->head;
    while(ptr!=nullptr){
        Node<K,E>*cur=ptr;
        ptr=ptr->next;
        delete cur;
    }
}

template<class K,class E>
std::pair<K,E>*sortedChain<K,E>::find(int&key)const{
    //查找关键字为key的桶是否在链表中
    Node<K,E>*ptr=this->head;
    while (ptr!=nullptr)
    {
        if(ptr->element.first==key)
            break;
        ptr=ptr->next;
    }
    if(ptr!=nullptr)
        return &ptr->element;
    return nullptr;
}

template<class K,class E>
void sortedChain<K,E>::insert(std::pair<K,E>&p){
    //按从小到大的顺序插入
    //1.不存在此关键字的节点
    //2.已存在此关键字的节点，更新second值
    if(this->isEmpty()){
        this->head=new Node<K,E>(p);
        this->size++;
        return;
    }
    Node<K,E>*ptr=this->head;
    Node<K,E>*pre=this->head;
    while(ptr!=nullptr&&ptr->element.first<p.first){
        pre=ptr;
        ptr=ptr->next;
    }
    if(ptr!=nullptr&&ptr->element.first==p.first){
        //存在此关键字节点，更新second值
        ptr->element.second=p.second;
    }
    else
    {
        //不存在此关键字节点
        pre->next=new Node<K,E>(p);
        pre->next->next=ptr;
        this->size++;
    }
}

template<class K,class E>
void sortedChain<K,E>::erase(int&key){
    if(this->isEmpty()){
        cout<<"The chain is empty."<<endl;
        return;
    }
    Node<K,E>*ptr=this->head;
    Node<K,E>*pre=nullptr;
    while (ptr!=nullptr&&ptr->element.first!=key)
    {
        pre=ptr;
        ptr=ptr->next;
    }
    if(ptr==nullptr){
        cout<<"No such node in chain."<<endl;
        return;
    }
    if(pre==nullptr){
        this->head=ptr->next;
    }
    else{
        pre->next=ptr->next;
    }
    delete ptr;
    this->size--;
}

template<class K,class E>
void sortedChain<K,E>::output(){
    if(this->isEmpty()){
        cout<<"The chain is empty."<<endl;
        return;
    }
    Node<K,E>*ptr=this->head;
    while(ptr!=nullptr){
        cout<<"(Key: "<<ptr->element.first<<" Element: "<<ptr->element.second<<")->";
        ptr=ptr->next;
    }
}

template<class K,class E>
class chainHashTable{
private:
    sortedChain<K,E>*table;
    int totalSize;
    int divisor;
public:
    chainHashTable(int&d){
        this->divisor=d;
        this->table=new sortedChain<K,E>[this->divisor]();
        this->totalSize=0;
    };
    ~chainHashTable(){
        delete[]table;
    }
    bool isHashEmpty()const{
        return totalSize==0;
    }
    int getTotal()const{
        return totalSize;
    }

    std::pair<K,E>*find(int&key)const;
    void insert(std::pair<K,E>&p);
    void erase(int&key);
    void output()const;
};

template<class K,class E>
std::pair<K,E>*chainHashTable<K,E>::find(int&key)const{
    return table[key%this->divisor].find(key);
}

template<class K,class E>
void chainHashTable<K,E>::insert(std::pair<K,E>&p){
    int bucket=p.first%this->divisor;
    int preSize=table[bucket].getSize();
    table[bucket].insert(p);
    //确认是插入新值还是更新旧值
    if(table[bucket].getSize()>preSize)
        this->totalSize++;
}

template<class K,class E>
void chainHashTable<K,E>::erase(int&key){
    table[key%this->divisor].erase(key);
}

template<class K,class E>
void chainHashTable<K,E>::output()const{
    for(int i=0;i<divisor;i++)
    {
        this->table[i].output();
        cout<<endl;
    }
}

int main(){
    int d=11;
    chainHashTable<int,int>t(d);

    std::pair<int,int>p1(3,99);
    std::pair<int,int>p2(6,73);
    std::pair<int,int>p3(4,55);
    std::pair<int,int>p4(14,29);
    std::pair<int,int>p5(26,78);
    std::pair<int,int>p6(3,12);

    t.insert(p1);
    t.insert(p2);
    t.insert(p3);
    t.insert(p4);
    t.insert(p5);
    t.insert(p6);

    int k=36;
    t.erase(k);

    t.output();
    return 0;
}