/*
Name          : HashTable.h
Author        : Tomáš Kohlschütter
Date          : 21.11.06 22:52
Description   : hash tabulka
*/

#pragma once
//#include <string.h>
//#include <stdlib.h>
//#include <malloc.h>
//#include <stdio.h>
//#include <ctype.h>

// pole prvocisel, podle kterych se bude urcovat velikost hash tabulky
// prevzato z knihovny STLPort
static const unsigned long primeList[] = {
	7ul,          23ul,
	53ul,         97ul,         193ul,       389ul,       769ul,
	1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
	49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
	1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
	50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul };

/*
 * Alokator/dealokator pameti pomoci operatoru new/delete
 */
struct newAllocator
{
	static inline void *__CRTDECL allocate(size_t size) { return ::operator new(size); }
	static inline void __CRTDECL deallocate(void* pUserData) { ::operator delete(pUserData); }
};

/*
 * Alokator/dealokator pameti pomoci funkci malloc/free
 */
struct mallocAllocator
{
	static inline void *__CRTDECL allocate(size_t size) { return ::malloc(size); }
	static inline void __CRTDECL deallocate(void* pUserData) { ::free(pUserData); }
};

template<class T1, class T2>
struct pair
{
	T1 first;
	T2 second;
	
	//pair(const T1& _first, const T2& _second) : first(_first), second(_second) { }
	pair(T1 _first, T2 _second) : first(_first), second(_second) { }	
};

/*
 * univerzalni hash tabulka, kterou lze pouzit pro ruzne typy objektu
 * objekt typu KEY musi zvladat porovnani pomoci operatoru == a pretypovani na size_t
 * pretypovanim na size_t se rozumi vypocet hashe
 */
template<class KEY, class VALUE, class ALLOC = newAllocator>
class HashTable
{
public:

	// konstruktor - inicializuje promenne a alokuje pamet pro hash tabulku
	HashTable() : count(0), size(0)/*, collisionCount(0)*/
	{
		table = (Bucket**)ALLOC::allocate(sizeof(Bucket*) * primeList[size]);
		memset(table, 0, primeList[size] * sizeof(Bucket*));
	}

	// destruktor - uvolni pamet alokovanou pro hash tabulku
	~HashTable()
	{
		memset(table, 0, primeList[size] * sizeof(Bucket*));
		ALLOC::deallocate(table);
	}

	/*
	 * Vlozi novou polozku do hash tabulky
	 */
	void insert(const pair<KEY, VALUE>& type)
	{
		// vyhleda, zda-li neexistuje v tabulce duplicita vkladane polozky
		Bucket* temp = table[hash(type.first)];
		while(temp != 0)
		{
			if(temp->type.first == type.first)
				return;

			temp = temp->next;
		}

		// TODO: Zvetsit tabulku az kdyz jsou zaplnene vsechny buckety??
		if(primeList[size] == count) resize(); // zvetsi hash tabulku, pokud je jiz zaplnena

		unsigned int index = hash(type.first);

		/*if(table[index] != NULL) collisionCount++;*/
		temp = (Bucket*)ALLOC::allocate(sizeof(Bucket));

		temp->type = type;
		temp->next = table[index];

		table[index] = temp;
		count++;
	}

	/*
	 * Smaze polozku z tabulky
	 */
	void erase(const KEY& key)
	{
		unsigned int index = hash(key);
		Bucket* item = table[index];

		if(!item)
			return;

		if(item->type.first == key)
		{
			table[index] = item->next;
			ALLOC::deallocate(item);

			count--;
		}
		else
		{
			while(item->next != 0)
			{
				if(item->next->type.first == key)
				{
					Bucket* next = item->next->next;
					ALLOC::deallocate(item->next);

					item->next = next;
					count--;
					break;
				}
				item = item->next;
			}
		}
	}

	/*
	 * Nalezne polozku v tabulce
	 */
	const VALUE* find(const KEY& key) const
	{
		Bucket* item = table[hash(key)];
		while(item != 0)
		{
			if(item->type.first == key)
				break;

			item = item->next;
		}
		return item ? &item->type.second : NULL;
	}

	inline bool empty() const
	{
		return count == 0;
	}

	/*
	 * Vraci pocet objektu v tabulce
	 */
	inline unsigned int getCount() const
	{
		return count;
	}

private:

	struct Bucket
	{
		pair<KEY, VALUE> type;
		Bucket* next;
	};

	Bucket **table;         // tabulka bucketu
	unsigned int count;     // pocet platnych objektu v tabulce
	unsigned short size;    // index prvocisla, ktere urcuje aktualni velikost pole
	/*unsigned int collisionCount;*/

	/*
	 * Vychozi hashovaci funkce
	 */
	inline unsigned int hash(const KEY& key) const
	{
		return (size_t)key % primeList[size];
	}

	/*
	 * Zmeni velikost hash tabulky na hodnotu dalsiho prvocisla
	 */
	inline void resize()
	{
		/*collisionCount = 0;*/
		unsigned long oldSize = primeList[size];

		// alokujeme novou tabulku o velikosti dalsiho prvocisla
		Bucket** newTable = (Bucket**)ALLOC::allocate(sizeof(Bucket*) * primeList[++size]);
		memset(newTable, 0, primeList[size] * sizeof(Bucket*));

		// prekopirujeme obsah puvodni tabulky do nove
		for(unsigned long i = 0; i < oldSize; i++)
		{
			Bucket* item = table[i];
			while(item != 0)
			{
				unsigned int index = hash(item->type.first);
				Bucket* next = item->next;

				item->next = newTable[index];
				newTable[index] = item;

				item = next;
			}
		}

		ALLOC::deallocate(table);
		table = newTable;
	}
};