enum STATE
{
	EXIST,
	EMPTY,
	DELETE
};
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	STATE _state = EMPTY;//狀態
};

//查找部分	
 template<class K, class V, class HashFunc = DefaultHashFunc<K>>
 class HashTable
 {
 public:
		HashTable()
		{
			_table.resize(10);
		}

		HashData<const K, V>* Find(const K& key)//用K找V
		{
			//線性探測
      //當數據類型不確定，無法用一種同一的方法進行計算時(如字符串無法%)，寫成仿函數
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)//直到空才停止查找
			{
				if (_table[hashi]._state == EXIST
					&& _table[hashi]._kv.first == key)
				{
					return (HashData<const K, V>*) & _table[hashi];
					//HashData<const K, V>* 和 HashData<K, V>* 是兩個不同類型，用不同的模板參數去實例化(const K與K)
					//需要強制類型轉換一下
					//指針可以直接強轉
				}
				++hashi;
				hashi %= _table.size();
			}
			return nullptr;
		}

		//按需編譯
		bool Erase(const K& key)
		{
			HashData<const K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}
	private:
		vector<HashData<K, V>> _table;
		size_t _n = 0;//存儲有效數據個數
		//空間中數據不是連續存儲的，結構上是數組，邏輯上是哈希表
	};
}

//仿函數部分
template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
	//模版的特化
	template<>
	struct DefaultHashFunc<string>
	{
		size_t operator()(const string& str)
		{
			size_t hash = 0;
      
			//BKDR
			for (auto ch : str)
			{
				//降低重複概率
				hash *= 131;
        //溢出不重要,插入是溢出被截斷；
        //查找時按相同規律，也會溢出截斷，不影響
				hash += ch;
			}
			return hash;
		}
	};

bool Insert(const pair<K, V>& kv)
{
	//擴容
	if ((double)_n / _table.size() >= 0.7)
	{
		size_t newSize = _table.size() * 2;
		//_table.resize(newSize); 直接resize映射關係變了，位置出現錯誤
		HashTable<K, V> newHT;
    //直接創建HashTable，比創建	vector<HashData<K, V>> 要好，能直接複用哈希表的Insert
		newHT._table.resize(newSize);
		//遍歷舊錶數據插入新表中
		for (size_t i = 0; i < _table.size(); ++i)
		{
			if (_table[i]._state == EXIST)
			{
				newHT.Insert(_table[i]._kv);
			}
		}

		_table.swap(newHT._table);
	}

	//線性探測
	HashFunc hf;仿函數
	size_t hashi = hf(kv.first) % _table.size();//值%大小 = hashi
	while (_table[hashi]._state == EXIST)
	{
		++hashi;
		hashi %= _table.size();
	}

	_table[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	++_n;

	return true;
}

struct HashNode
{
	HashNode(const pair<K,V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}
	pair<K, V> _kv;
	HashNode<K, V>* _next;//節點中有指向下一個節點的指針
};

template<class K,class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
	typedef HashNode<K, V> Node;
  public:
  private:
	vector<Node*> _table;//指針數組 -- 
	size_t _n = 0;//記錄存儲有效數據
};

bool Insert(const pair<K, V>& kv)
	{
		HashFunc hf;
		if (Find(kv.first))
		{
			return false;
		}

		//負載因子到1擴容
		if (_n == _table.size())
		{
			size_t newSize = _table.size() * 2;
			vector<Node*> newTable;
			newTable.resize(newSize,nullptr);
			//遍歷舊錶，把節點拿過來——如果直接調insert，又會newNode出新節點，舊節點無法銷燬
			for (size_t i = 0; i < _table.size(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					//頭插到新表
					size_t hashi = hf(cur->_kv.first) % newSize;
					cur->_next = newTable[hashi];
					newTable[hashi] = cur;
					cur = next;//往後，直到一個桶為空
				}
				_table[i] = nullptr;
			}
			_table.swap(newTable);
		}
    
    //插入數據 - 頭插
		size_t hashi = hf(kv.first) % _table.size();
		Node* newnode = new Node(kv);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		_n++;

		return true;
	}

Node* Find(const K& key)
{
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	Node* cur = _table[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;//返回節點
		}
		cur = cur->_next;
	}
	return nullptr;//沒找到
}

#pragma once
#include<vector>
#include<string>
#include<iostream>
using namespace std;

//兩個仿函數 - 解決哈希函數問題(有些數據比如char不能直接取模)
//都能用 放全局 ——細節在類中
template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//模版的特化
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		//return str[0];
		size_t hash = 0;
		
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
namespace hash_bucket
{
	//泛型編程: 不是針對某種具體類型，而是針對廣泛的類型(兩種以上) —— 模板
	template<class T>
	struct HashNode
	{
		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
		T _data;//不確定是key 還是 key-value的
		HashNode<T>* _next;
	};


	//前置聲明
	template<class K, class T, class KeyOfT, class HashFunc>
	class HashTable;

	//template<class T>
	template<class K, class T,class Ptr,class Ref, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
	struct HTIterator
	{
		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
		typedef HashNode<T> Node;
		typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc> Self;//
		Node* _node;//只有node沒有_table，找不到下一個位置，需要把哈希表也傳過去
		const HashTable<K, T, KeyOfT, HashFunc>* _pht;//創建哈希表的指針

		//普通迭代器它是拷貝構造
		//const迭代器是構造
		HTIterator(const iterator& it)
			:_node(it._node)
			, _pht(it._pht)//傳參時this就是HashTable的指針，更方便
		{}

		HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)//傳參時this就是HashTable的指針，更方便
		{}
		HTIterator(Node * node, const HashTable<K, T, KeyOfT, HashFunc>*pht)
			:_node(node)
			, _pht(pht)//傳參時this就是HashTable的指針，更方便
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				//當前桶未結束
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;//得到key
				HashFunc hf;//得到key "數"
				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
				//從下一個位置查找不為空的桶
				++hashi;
				while (hashi < _pht->_table.size())
				{
					if (_pht->_table[hashi])
					{	
						_node = _pht->_table[hashi];//找到下一個桶
						return *this;
					}
					else
					{
						++hashi;
					}
				}
				//所有桶都走完了
				_node = nullptr;//空充當最後一個位置
			}
			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}
	};

	//set -> hash_bucket::HashTable<K, K> _t;
	//map -> hash_bucket::HashTable<K,pair<K,V>> _t;
	//第一個模板參數K有什麼用？
	//在Find/Erase時，參數是K類型，如果沒有K，對於map，Find需要傳pair ×
	template<class K,class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{	
		typedef HashNode<T> Node;//第二個模板參數確定是key 還是 key-value

		//友元聲明
		template<class K, class T, class Ptr,class Ref,class KeyOfT, class HashFunc>
		friend struct HTIterator;
	public:
		typedef HTIterator<K, T,T*,T&, KeyOfT, HashFunc> iterator;
		typedef HTIterator<K, T,const T*,const T&, KeyOfT, HashFunc> const_iterator;

		iterator begin()
		{
			//找第一個桶
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return iterator(cur, this);
				}
			}

			return iterator(nullptr, this);
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin()const
		{
			//找第一個桶
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return const_iterator(cur, this);
				}
			}

			return const_iterator(nullptr, this);
		}

		const_iterator end()const
		{
			return const_iterator(nullptr, this);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}

		HashTable()
		{
			_table.resize(10, nullptr);
		}
    
		pair<iterator,bool> Insert(const T& data)
		{
			HashFunc hf;

			KeyOfT kot;

			iterator it = Find(kot(data));
			if (it != end())
			{
				return make_pair(it, false);
			}

			//負載因子到1擴容
			if (_n == _table.size())
			{
				size_t newSize = _table.size() * 2;
        
				vector<Node*> newTable;
				newTable.resize(newSize,nullptr);

				//遍歷舊錶，把節點拿過來——如果直接調insert，又會newNode出新節點，舊節點無法銷燬
				for (size_t i = 0; i < _table.size(); ++i)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						//頭插到新表
						size_t hashi = hf(kot(cur->_data)) % newSize;
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;//往後，直到一個桶為空
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

			size_t hashi = hf(kot(data)) % _table.size();
			//頭插
			Node* newnode = new Node(data);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;

			return make_pair(iterator(newnode,this),true);
		}

		iterator Find(const K& key)
		{
			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				cur = cur->_next;
			}
			return iterator(nullptr,this);
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					//頭刪
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;

					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			--_n;
			return false;
		}

		void Print()
		{
			KeyOfT kot;
			for (size_t i = 0; i < _table.size(); ++i)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur != nullptr)
				{
					cout << kot(cur->_data) << ":" << kot(cur->_data) <<"->";
					cur = cur->_next;
				}
				cout << "NULL" << endl;
			}
			cout << endl;
		}
	private:
		//編譯器默認析構：對內置類型不做處理，對自定義類型調默認析構 —— 
		// 存節點的“指針”是內置類型，不做處理，需要自己寫析構函數
		//包括拷貝構造都需要自己寫
		vector<Node*> _table;//指針數組
		size_t _n = 0;//記錄存儲有效數據
	};
}

template<class K>
class undered_set
{
  //內部類，獲取 “鍵” Key
	struct SetKeyOfT
	{
		K operator()(const K& key)
		{
			return key;
		}
	};

public:
  //迭代器封裝 - 要保證set中值不允許在迭代器被修改
	typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

	const_iterator begin()const
	{
		return _ht.begin();
	}
	const_iterator end()const
	{
		return _ht.end();
	}
	返回值為了兼容
	pair<iterator, bool> insert(const K& key)
	{
	//	return _ht.Insert(key); //不嚴格,兩種不同類型轉換
		pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
		return pair <const_iterator, bool>(ret.first,ret.second);
	}
private:
	hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
  //底層機制以 HashTable 完成
};

template<class K, class V>
class undered_map
{
  //內部類，獲取 “鍵” Key
	struct MapKeyOfT
	{
		K operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
  //對於map而言：value是允許被修改的，但 key不可以
	typedef typename hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT>::iterator iterator;
	typedef typename hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT>::const_iterator const_iterator;
  //所有操作幾乎都有 HashTable對應版本，傳遞調用就行
	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}

	const_iterator begin()const
	{
		return _ht.begin();
	}
	const_iterator end()const
	{
		return _ht.end();
	}
//允許通過[key]去查找/添加/修改value
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
		return ret.first->second;
	}
  //插入要注意：不允洗鍵值重複
  //insert返回值是為了方便[]操作
	pair<iterator,bool> insert(const pair<K, V>& kv)
	{
		return _ht.Insert(kv);
	}
private:
	hash_bucket::HashTable<K, pair<const K,V>,MapKeyOfT> _ht;
};

template<class K>
class undered_set
{
private:
	struct SetKeyOfT
	{
		K operator()(const K& key)
		{
			return key;
		}
	};

public:
	typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

	const_iterator begin()const
	{
		return _ht.begin();
	}
	const_iterator end()const
	{
		return _ht.end();
	}

	pair<iterator, bool> insert(const K& key)
	{
	//	return _ht.Insert(key); //不嚴格,兩種不同類型轉換
		pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
		return pair <const_iterator, bool>(ret.first,ret.second);
	}
private:
	hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};

//模板特化有兩種
template <typename T> struct A {}; // 通用
template <> struct A<int> {}; // 對int的全特化