#pragma once



enum State{EMPTY, EXIST, DELETE};


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

template<class K>
struct Elem
{
	Elem(const K& key = K(), State state = EMPTY)
	   : _key(key)
	   , _state(state)
	{}

	K _key;
	State _state;
};


// 约定：key是唯一
template<class K, bool isLine = true>
class HashTable
{
public:
	HashTable(size_t initCapacity = 13)
		: _table(initCapacity)
		, _size(0)
		, _total(0)
	{}

	bool Insert(const K& key)
	{
		_CheckCapacity();

		// 1. 通过哈希函数计算key在哈希表格中的位置
		size_t hashAddr = hashFunc(key);

		// 2. 检测hashAddr的位置是否为空
		size_t i = 0;
		while (EMPTY != _table[hashAddr]._state)
		{
			if (EXIST == _table[hashAddr]._state &&
				_table[hashAddr]._key == key)
			{
				return true;
			}

			// 发生哈希冲突: 从发生哈希冲突的位置开始找下一个空位置
			// 线性探测：逐个挨着依次往后查找
			if (isLine)
			{
				hashAddr++;
				if (hashAddr == _table.capacity())
					hashAddr = 0;
			}
			else
			{
				// 二次探测：H(i) = H0+i^2
				hashAddr = hashAddr + 2 * i + 1;
				hashAddr %= _table.capacity();
			}
		}

		// 3. 直接插入元素
		_table[hashAddr]._key = key;
		_table[hashAddr]._state = EXIST;
		_size++;
		_total++;
		return true;
	}

	int find(const K& key)
	{
		// 1. 通过哈希函数计算元素在表格中的位置
		size_t hashAddr = hashFunc(key);

		// 2. 找key
		while (EMPTY != _table[hashAddr]._state)
		{
			if (_table[hashAddr]._state == EXIST &&
				_table[hashAddr]._key == key)
			{
				return hashAddr;
			}

			// 发生哈希冲突: 从发生哈希冲突的位置开始找下一个空位置
			// 线性探测：逐个挨着依次往后查找
			if (isLine)
			{
				hashAddr++;
				if (hashAddr == _table.capacity())
					hashAddr = 0;
			}
			else
			{
				// 二次探测：H(i) = H0+i^2
				hashAddr = hashAddr + 2 * i + 1;
				hashAddr %= _table.capacity();
			}
		}

		return -1;
	}

	bool erase(const K& key)
	{
		int ret = find(key);
		if (-1 != ret)
		{
			_table[ret]._state = DELETE;
			_size--;
			return true;
		}

		return false;
	}

	size_t size()const
	{
		return _size;
	}

	void swap(HashTable<K>& ht)
	{
		_table.swap(ht._table);
		std::swap(_size, ht._size);
	}
private:
	void _CheckCapacity()
	{
		if (_total*10 / _table.capacity() >= 7)
		{
			HashTable<K> newHT(_table.capacity()*2);
			for (size_t i = 0; i < _table.capacity(); ++i)
			{
				if (EXIST == _table[i]._state)
					newHT.Insert(_table[i]._key);
			}

			this->swap(newHT);
		}
	}

	size_t hashFunc(const K& key)
	{
		return key % _table.capacity();
	}
private:
	vector<Elem<K>> _table;
	size_t _size;  // 哈希表中有效元素的个数
	size_t _total;
};


#include <string>

void TestHashTable()
{
	HashTable<int> ht(10);
	ht.Insert(28);
	ht.Insert(12);
	ht.Insert(34);
	ht.Insert(44);
	ht.Insert(24);
	ht.Insert(19);
	ht.Insert(29);
	cout << ht.size() << endl;

	ht.Insert(100);

	ht.erase(44);

	int ret = ht.find(24);
	if (-1 != ret)
	{
		cout << "24 is in hashtable" << endl;
	}
	else
	{
		cout << "24 is not in hashtable"  << endl;
	}


	HashTable<string> hts;
	hts.Insert("apple");
	hts.Insert("orange");
	hts.Insert("grape");
}