#ifndef HASHTABLE_H
#define HASHTABLE_H

#include<iostream.h>
#include<stdlib.h>
#include<cmath>

enum Status{Active,Empty,Deleted};//散列表桶的状态

#define DefaultSize 100

///////////////////////////////////////////////////
//HashTable  哈希表类模板声明和定义
///////////////////////////////////////////////////
template<class T>
class HashTable
{
private:
    int divitor;                //散列函数除留取余的除数
    int CurrentSize;            //当前桶的个数
    int TableSize;              //最大的桶数
    T*  ht;                     //散列表的存储数组
    Status* info;               //用于存放每个桶的状态的数组

    int Hash(const T k)const;   //散列函数根据关键码计算初始桶号
    int FindPos(const T k)const;//根据关键码计算要插入的位置
    int FindPosDoubleProb(const T k)const;//二次探查法搜索

public:
    //构造函数
    HashTable(const int d,int sz=DefaultSize);
    //析构函数
    ~HashTable(){delete [] ht;delete [] info;};
    //在散列表中搜索k
    bool Search(const T k,int& loc)const;
    //在散列表中插入一个元素k
    bool Insert(const T k);
    //通过二次探查法实现的散列表的插入
    bool DoubleProbInsert(const T k);

    //删除指定关键码的元素
    bool Remove(const T k);
    //显示当前散列表的桶号,内容,和状态
    void Display();    
};
////////////////////////////HashTable类模板声明结束

///////////////////////////////////////////////////
//构造函数
//初始化的数据是除留的余数和存储数组的大小
///////////////////////////////////////////////////
template<class T>
HashTable<T>::HashTable(const int d,int sz)
{
    divitor=d;                 //除留的余数
    CurrentSize=0;             //初始元素的个数
    TableSize=sz;              //最大桶的个数
    ht=new T[TableSize];       //分配桶的数组空间
    if(ht==NULL)
    {
        cout<<"桶的内存分配出错!"<<endl;
        exit(1);
    };
    //把ht数组初始化为-1
    for(int i=0;i<TableSize;i++)
        ht[i]=-1;
    info=new Status[TableSize];//分配状态数组内存
    if(info==NULL)
    {
        cout<<"桶的内存分配出错!"<<endl;
        exit(1);
    };
    //初始化状态数组的内容,初始化为空
    for(i=0;i<TableSize;i++)
        info[i]=Empty;
};
///////////////////////////////////////构造函数结束

///////////////////////////////////////////////////
//Hash()私有成员函数,散列函数
//根据关键码K计算初始的桶的位置
///////////////////////////////////////////////////
template<class T>
int HashTable<T>::Hash(const T k)const
{
    //采用除留取余法计算桶的初始位置
    return k%divitor;
};
/////////////////////////////////////Hash()函数结束

///////////////////////////////////////////////////
//FindPos()公有成员函数
//根据给定的关键码找出其所在的最可能的桶号
///////////////////////////////////////////////////
template<class T>
int HashTable<T>::FindPos(const T k)const
{
    //本函数的功能是，假设搜索到的桶号是i
    //应该满足一下几个要求：
    //(1)如果info[i]==Active,且ht[i]==k,则说明找到
    //(2)如果info[i]==Active,且ht[i]!=k,则说明表满,并且说明也不存在
    //(3)如果info[i]!=Active,则说明要找的元素不在，并把k插入到第i号桶中
   
    int i=Hash(k);              //通过Hash()计算桶的初始位置
    int p=i;                    //游标指针从桶的初始位置i开始找
    do
    {
        //如果当前元素有而且等于k则说明找到
        if(info[p]==Active && ht[p]==k
        //或者如果当前的桶是空的,说明元素不存在
        || info[p]==Empty)
            //返回当前的桶号
            return p;
        p=(p+1)%TableSize;
    }while(p!=i);               //如果p==i,说明已经绕一圈了也没找到
    return p;                   //p又回到了起点i说明表已经满了,查找失败
};
//////////////////////////////////FindPos()函数结束

///////////////////////////////////////////////////
//FindPosDoubleProb()私有成员函数
//采用二次探查法寻找指定关键码的元素最可能在的桶号
///////////////////////////////////////////////////
template<class T>
int HashTable<T>::FindPosDoubleProb(const T k)const
{
    //通过二次探查法,若查到i是k的最可能的桶号
    //如果info[i]==Active && ht[i]==k,说明找到
    //如果info[i]==Active && ht![i]=k,说明表满,也不存在
    //如果info[i]!=Active,则说明元素不存在

    //计算初始桶号,并以初始桶号为基点开始查找
    int begin=k%divitor;
    //游标指针
    int p=begin;
    //用于只是加i^2还是减i^2的标记
    //0表示加,1表示减
    int flag=0;
    //探查的次数
    int count=1;

    //二次探查法的过程
    do
    {
        //如果找到的话就返回桶号
        if(info[p]==Active && ht[p]==k
        //或者该桶为空则结束也返回
        ||info[p]==Empty)
            return p;
        
        //如果不停止游标,p指向下个桶号
        if(flag==0)
        {
            //加
            p=(p+int(pow(count,2)))%TableSize;
            flag=1;
        }
        else
        {
            //减
            p=(p-int(pow(count,2)))%TableSize;
            flag=0;
            //如果游标p小于0
            if(p<0)
                p=p+TableSize;
            count++;
        }
    }
    while(p!=begin);//如果游标又回到原处则结束
    return p;       //p又回到了起点说明查找失败
};
/////////////////////////FinPosDoubleProb()函数结束

///////////////////////////////////////////////////
//Search()公有成员函数
//在散列表中搜索k,并把k所在的桶号通过loc返回
///////////////////////////////////////////////////
template<class T>
bool HashTable<T>::Search(const T k,int& loc)const
{
    //计算出k最可能在的桶号
    int i=FindPos(k);
    //已经找到
    if(info[i]==Active && ht[i]==k)
    {
        //记录下元素位置
        loc=i;
        //返回真
        return true;
    }
    //最可能的位置已经被占,表满
    else if(info[i]==Active && ht[i]!=k)
    {
        //要找的位置不存在
        loc=-1;
        return false;
    }
    //要找的元素不在，但有空位置
    else if(info[i]==Empty)
    {
        //返回空着的位置
        loc=i;
        return false;
    }
};
///////////////////////////////////Search()函数结束

///////////////////////////////////////////////////
//Insert公有成员函数
//把关键码为k的元素插入到散列中去
///////////////////////////////////////////////////
template<class T>
bool HashTable<T>::Insert(const T k)
{
    //搜索k最可能出现的位置p
    int p=FindPos(k);
    //如果p位置有元素而且就是k,则说明找到了
    if(info[p]==Active && ht[p]==k)
    {
        cout<<"散列表中已经存在该元素,不用插入了!"<<endl;
        //不用插入,即插入失败
        return false;
    }
    //如果有元素，但不是k,说明表已经满了
    else if(info[p]==Active && ht[p]!=k)
    {
        cout<<"散列表已经满了,不用插入了!"<<endl;
        //插入失败
        return false;
    }
    //找到插入的位置了
    else if(info[p]!=Active)
    {
        //插入元素
        ht[p]=k;CurrentSize++;
        //把对应的状态设为Active
        info[p]=Active;
        //插入成功
        return true;
    };
};
///////////////////////////////////Insert()函数结束

///////////////////////////////////////////////////
//公有成员函数DoubleProInsert()函数
//采用二次探查法把关键码为k的元素插入到散列中去
///////////////////////////////////////////////////
template<class T>
bool HashTable<T>::DoubleProbInsert(const T k)
{
    //搜索k最可能出现的位置p
    int p=FindPosDoubleProb(k);
    //如果p位置有元素而且就是k,则说明找到了
    if(info[p]==Active && ht[p]==k)
    {
        cout<<"散列表中已经存在该元素,不用插入了!"<<endl;
        //不用插入,即插入失败
        return false;
    }
    //如果有元素，但不是k,说明表已经满了
    else if(info[p]==Active && ht[p]!=k)
    {
        cout<<"散列表已经满了,不用插入了!"<<endl;
        //插入失败
        return false;
    }
    //找到插入的位置了
    else if(info[p]!=Active)
    {
        //插入元素
        ht[p]=k;CurrentSize++;
        //把对应的状态设为Active
        info[p]=Active;
        //插入成功
        return true;
    };
};
//////////////////////////DoubleProInsert()函数结束

///////////////////////////////////////////////////
//Remove()公有成员函数
//删除指定关键码的散列中的元素
///////////////////////////////////////////////////
template<class T>
bool HashTable<T>::Remove(const T k)
{
    //首先看k在散列表中是否存在,如果存在就可以删除
    //先得到k最可能所在的桶号
    int p=FindPos(k);
    if(info[p]==Active && ht[p]==k)
    {
        //得到k的桶号
        int p=FindPos(k);
        //逻辑删除该元素
        info[p]=Deleted;
        //当前元素少一个
        CurrentSize--;
        //删除成功
        return true;
    }
    else
        //删除失败
        return false;
};
///////////////////////////////////Remove()函数结束

///////////////////////////////////////////////////
//Display()公有成员函数
//显示当前散列表的桶号,内容,和状态
///////////////////////////////////////////////////
template<class T>
void HashTable<T>::Display()
{
    //分别显示散列表的桶号,内容,和状态
    for(int i=0;i<TableSize;i++)
        cout<<i<<":   "<<ht[i]<<":   "<<info[i]<<endl;
};
//////////////////////////////////Display()函数结束

#endif