//散列表類
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include<iostream>
using namespace std;
const int DefaultSize = 100;
enum KindOfStatus {Active,Empty,Deleted};	//元素分類 (活動/空/刪)
template <class E, class K>
class HashTable {									//散列表類定義
public:
	HashTable(const int d, int sz = DefaultSize); 	//構造函數
	~HashTable() {delete []ht; delete []info;}		//析構函數
	HashTable<E,K>& operator = (const HashTable<E,K>& ht2);
	bool Search(const K k1, E& e1);			//在散列表中搜索k1
	bool Insert(const E& e1);						//在散列表中插入e1
	bool Remove(const K k1, E& e1);					//在散列表中刪除e1
	void makeEmpty();								//置散列表為空
	void show();  //輸出
private:
	int divitor;									//散列函數的除數
	int CurrentSize, TableSize;						//當前桶數及最大桶數
	E *ht;											//散列表存儲數組
	KindOfStatus *info;								//狀態數組
	int FindPos(const K k1) const;					//散列函數:計算初始桶號
	int operator == (E& e1) {return *this == e1;}	//重載函數：元素判等
	int operator != (E& e1) {return *this != e1;}	//重載函數：元素判不等
};

template <class E, class K>
HashTable<E,K>::HashTable(int d, int sz) {			//構造函數
	divitor = 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>
int HashTable<E,K>::FindPos(const K k1)const {
	//搜索在一個散列表中關鍵碼與k1匹配的元素，搜索成功，則函數返回該元素的位置，
	//否則返回插入點（如果有足夠的空間）	
	int i = k1 % divitor;					//計算初始桶號
	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) {
	/*使用線性探查法在散列表ht(每個桶容納一個元素)中搜索k1。如果k1在表中存在, 
	則函數返回true,并用引用參數e1返回找到的元素。如果k1不在表中, 則返回false。*/
	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;
};
template <class E, class K>
bool HashTable<E,K>::Insert(const E& e1) {
	//在ht表中搜索e。若找到則不再插入, 若未找到, 但表已滿, 則不再插入, 返回false;
	//若找到位置的標志是Empty或Deleted, 不論表是否已滿, x插入, 返回true。
	E 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)
	{cout << "表中已有此元素，不能插入！"<< endl; return false;}
	cout << "表已滿，不能插入！"<< endl;  return false;
};

template <class E, class K>
bool HashTable<E,K>::Remove(const K k1, E& e1) {
	//在ht表中刪除元素key。若表中找不到k1, 或雖然找到k1, 但它已經邏輯刪除過, 
	//則返回false,否則在表中刪除元素k1, 返回true, 并在引用參數e1中得到它。
	int i = FindPos(k1);
	if (info[i] == Active) {				//找到要刪元素, 且是活動元素
		info[i] = Deleted;  CurrentSize--; 	//做邏輯刪除標志, 并不真正物理刪除
		return true;					  	//刪除操作完成, 返回成功標志
	}
	else return false;					  	//表中無被刪元素, 返回不成功標志
};


template <class E, class K>
void HashTable<E,K>::show()
{
	for(int i = 0; i<TableSize; i++)
	{
		if(info[i] == Active)
			cout<<"表元素 "<<i<<"  "<<ht[i]<<endl;
		else if (info[i] == Empty)
			cout<<"表元素 "<<i<<"  為空"<<endl;
		else if (info[i] == Deleted)
			cout<<"表元素 "<<i<<"  被刪"<<endl;
	}
}
#endif;