//HashTable.h

#include<iostream>
const int defaultsize = 100;
enum KindOfStatus{ Active,Empty,Deleted};
template<class E,class K>
struct ChainNode
{
    E data;
    ChainNode<E,K> *link;
};
template<class E,class K>
class HashTable
{
private:
    int divisor;                                   //除数，必须是质数
    int CurrentSize,TableSize;                 //当前桶数,最大容量（桶的个数）
    ChainNode<E,K> *ht;                         //散列表存储数组
    KindOfStatus *info;                         //状态数组
    ChainNode<E,K> *FindPos(const K k1);     //散列
    int operator ==(E &e1){ return *this ==e1;}
    int operator !=(E& e1){ return *this !=e1;}
public:
    HashTable(int d,int sz=defaultsize);
    HashTable<E,K>& operator = (const HashTable<E,K> &ht2);
    bool Search(const K k1,E& e1);
    bool Insert(const E& e1);
    bool Remove(const K k1,E& el);
    void MakeEmpty();
    ~HashTable()
    {
        delete [ ]ht; delete [ ]info;
    }
};

/////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////
//HashTable的实现
//HashTable.cpp

#include "HashTable.h"
template<class E,class K>
HashTable<E,K>::HashTable(int d,int sz)
{
    divisor = d;
    TableSize = sz;
    CurrentSize = 0;
    ht = new E[TableSize];
    info = new KindOfStatus[TableSize];
    for (int i=0;i<TableSize;i++)
        info[i] = Empty;
};
//使用线性探查法的搜索法
template<class E,class K>
ChainNode<E,K> *HashTable<E,K>::FindPos(const K k1)
{
    //搜索关键码为K1的元素
    int i = k1%divisor;               //计算初始桶号
    int j = i;                    //j是检测下一空桶下标
    do
    {
        if (info[j] ==Empty ||info[j] ==Active &&ht[j] ==k1) return j;   //找到
        j = (j+1) % TableSize;
    }
    while (j != i);
    return j;
}
template<class E,class K>
bool HashTable<E,K>::Search(const K k1,E &e1)
{
    int i = FindPos(k1);      //搜索
    if (info[i] != Active || ht[i] != k1) return false;
    e1 = ht[i];
    return true;
}

//清除散列表
template<class E,class K>
void HashTable<E,K>::MakeEmpty()
{
    for (int i=0;i<TableSize;i++)
        info[i] = Empty;
    CurrentSize = 0;
}

//重载函数，复制一个散列表ht2
template<class E,class K>
HashTable<E,K>& HashTable<E,K>::operator = (const HashTable<E,K>& ht2)
{
    if(this !=&ht2)
    {
        delete[ ]ht;  delete [ ]info;
        TableSize = ht2.TableSize;
        ht = new E[TableSize];  info = new KindOfStatus[TableSize];
        for(int i=0;i<TableSize;i++)
        {
            ht[i] = ht2.ht[i];             //从源散列表向目的散列表传送
            info[i] = ht2.info[i];
        }
        CurrentSize = ht2.CurrentSize;        //传送当前元素个数
    }
    return *this;                     //返回目标散列表结构指针
};
template<class E,class K>
bool HashTable<E,K>::Insert(const E& e1)
{
    K k1 = e1;            //重载函数，抽取关键码
    int i=FindPos(k1);    //计算桶号
    if (info[i] != Active)  //该桶空，放新元素
    {
        ht[i] = e1;  info[i] = Active;
        CurrentSize++;
        return true;
    }
    if (info[i] ==Active && ht[i] ==e1)
    {
        std::cout<<"表中已有此元素，不能插入！"<<std::endl;
        return false;
    }
    std::cout<<"表已满，不能插入！"<<std::endl;
    return false;
}
template<class E,class K>
bool HashTable<E,K>::Remove(const K k1,E &e1)
{
    int i = FindPos(k1);
    if(info[i] == Active){info[i] =Deleted;  CurrentSize --;   return true;}
    else return false;
}