#ifndef HASH_TABLE_CLASS
#define HASH_TABLE_CLASS

#include <stdlib.h>
#include "array.h"
#include "dclinkedlist.h"

template <class T>
class HashTable
{
	protected:
		// “桶”的個數，表示哈希表的大小
		int numBuckets;

		// 哈希表為鏈表構成的數組
		Array< DCLinkedList<T> > buckets;

		// 哈希函數及指向當前數據項的指針、當前的哈希值
		unsigned long (*hf)(T key);  // 除以哈希表大小的工作在內部完成
		T *current;
		int hashval;

		// 表中元素個數
		int size;

	public:
		// 參數為哈希表大小及哈希函數的構造函數
		HashTable(int nbuckets, unsigned long hashf(T key));

		// 處理表的方法
		void Insert(const T& key);
		bool Find(T& key);			// 檢索時只要設置結構中與關鍵字有關的成員，該函數會返回哈希表中對應的完整項
		void DeleteAt(void);		// 刪除當前成員
		void Delete(const T& key);
		void ClearList(void);
		void Update(const T& key);  // 對已經在哈希表中的元素進行更新
};

template <class T>
HashTable<T>::HashTable(int nbuckets, unsigned long hashf(T key)):
			numBuckets(nbuckets), buckets(nbuckets), hf(hashf), current(NULL), hashval(0) 
{}

// 如果數據已存在，則更新它，否則將其插入
template <class T>
void HashTable<T>::Insert(const T& key)
{
	// hashval 為哈希值（桶索引）
	hashval = int(hf(key) % numBuckets);

	// lst 為 buckets[hashval] 的別名，可避免下標尋址
	DCLinkedList<T>& lst = buckets[hashval];

	for (lst.Reset(); !lst.EndOfList(); lst.Next())
	{
		// 若找到匹配值，修改其數據后返回（/* 如果關鍵字相同即認為是同一條目（認為兩者相等）*/）
		if (lst.Data() == key)
		{
			lst.Data() = key;  // 將數據區也設為相等
			current = &lst.Data();
			return;
		}
	}
	// 若沒有找到，則將數據項加入表中
	lst.InsertRear(key);
	current = &lst.Data();
	size++;
}

template <class T>
bool HashTable<T>::Find(T& key)
{
	// 計算鍵值的哈希值并將 lst 指向它對應的 DCLinkedList
	hashval = int(hf(key) % numBuckets);
	DCLinkedList<T>& lst = buckets[hashval];

	// 在鍵表中掃描結點并尋找與 key 匹配的記錄
	for (lst.Reset(); !lst.EndOfList(); lst.Next())
	{
		// 若找到匹配值，則取其數據值，將 current 指向該記錄
		if (lst.Data() == key)
		{
			key = lst.Data();
			current = &lst.Data();
			return true;
		}
	}
	return false;
}

template <class T>
void HashTable<T>::Delete(const T& key)
{
	hashval = int(hf(key) % numBuckets);
	DCLinkedList<T>& lst = buckets[hashval];

	for (lst.Reset(); !lst.EndOfList(); lst.Next())
	{
		if (lst.Data() == key)  // 如果關鍵字匹配，刪除結點
		{
			lst.DeleteAt();
			current = &lst.Data();
			size--;
			return;
		}
	}
}

template <class T>
void HashTable<T>::DeleteAt(void)
{
	DCLinkedList<T>& lst = buckets[hashval];
	if (current != NULL && !lst.EndOfList())
	{
		lst.DeleteAt();
		current = &lst.Data();
		size--;
	}
}

template <class T>
void HashTable<T>::ClearList(void)
{     
	for (int i = 0; i < numBuckets; i++)
		buckets[i].ClearList();
	size = 0;
	current = NULL;
}

template <class T>
void HashTable<T>::Update(const T& key)
{     
	DCLinkedList<T>& lst = buckets[hashval];
	if (current != NULL && !lst.EndOfList() && *current == key)
		*current = key;
	else
		Insert(key);
}

#endif	// HASH_TABLE_CLASS