/*
 * hashtable.cpp
 *
 *  Created on: 16.01.2013
 *      Author: trifon
 */

#include "dictionary.h"
#include <cstring>

template <class T>
class LinkedList;

int const MAX = 103;
int const JUMP = 101;

class StringKey {
private:
	char const* s;
public:
	StringKey(char const* _s = NULL) : s(_s) {}
	operator char const*() const { return s; }

	bool operator==(StringKey const& sk) const
	{
		if (s == NULL && sk.s == NULL)
			return true;
		if (s == NULL || sk.s == NULL)
			return false;
		return strcmp(s, sk.s) == 0;
	}

	bool operator!=(StringKey const& sk) const
	{
		return !operator==(sk);
	}

	int hashCode() const
	{
		if (s == NULL)
			return -1;
		char const* p = s;
		int hash = 0;
		while (*p)
		{
			hash = (hash + *p) % MAX;
			p++;
		}
		return hash;
	}
};

template <typename K = StringKey, typename V = int>
class OpenHashTable : public Dictionary<K, V>
{
	struct Pair {
		K key;
		V value;
	};

private:
	Pair table[MAX];
public:
	int nextIndex(int index) const {
		return (index * JUMP) % MAX;
	}

	V* search(K const& key) const {
		int index = key.hashCode();
		int count = 0;
		if (index < 0)
			return NULL;
		while (count < MAX &&
			   table[index].key &&
			   table[index].key != key)
		{
			index = nextIndex(index);
			count++;
		} // count == MAX ||
		  // table[index].key == NULL ||
		  // table[index].key == key
		if (table[index].key == key)
			return (V*)&table[index].value;
		return NULL;
	}

	bool add(K const& key, V const& value) {
		int index = key.hashCode();
		if (index < 0)
			return false;
		int count = 0;
		while (count < MAX && table[index].key
				&& table[index].key != key)
		{
			index = nextIndex(index);
			count++;
		} // count == MAX ||
		  // table[index].key == NULL ||
		  // table[index].key == key
		if (count == MAX || table[index].key == key)
			return false;
		table[index].key = key;
		table[index].value = value;
		return true;
	}

	bool remove(K const& key) {
		int index = key.hashCode();
		if (index < 0)
			return false;
		int count = 0;
		int foundIndex = -1, lastIndex = -1;
		while (count < MAX && table[index].key)
		{
			if (table[index].key == key)
				foundIndex = index;
			lastIndex = index;
			index = nextIndex(index);
			count++;
		} // count == MAX || table[index].key == NULL

		if (foundIndex == -1)
			return false;
		// foundIndex е валиден
		// също lastIndex е валиден
		if (lastIndex == foundIndex)
			// изтриваме последният елемент, лесен случай
			table[foundIndex].key = NULL;
		else
		{
			// изтриваме елемент, различен от последния
			table[foundIndex] = table[lastIndex];
			table[lastIndex].key = NULL;
		}
		return true;
	}

	LinkedList<K> keys() const {
		LinkedList<K> k;
		for(int i = 0; i < MAX; i++)
			if (table[i].key)
				k.toEnd(table[i].key);
		return k;
	}

	LinkedList<V> values() const {
		LinkedList<V> v;
		for(int i = 0; i < MAX; i++)
			if (table[i].key)
				v.toEnd(table[i].value);
		return v;
	}

};

template <typename K = StringKey, typename V = int>
class LinkedHashTable : public Dictionary<K, V>
{
private:
	struct Pair {
			K key;
			V value;
		};

	typedef LinkedListIterator<Pair> I;
	LinkedList<Pair> table[MAX];

public:
	int nextIndex(int index) const {
		return (index * JUMP) % MAX;
	}

	V* search(K const& key) const {
		int index = key.hashCode();
		if (index < 0)
			return NULL;
		I it = table[index].iteratorBegin();
		while (it && (*it).key != key)
			++it;
		if (!it)
			return NULL;
		return &(*it).value;
	}

	bool add(K const& key, V const& value) {
		if (search(key) != NULL)
			return false;
		int index = key.hashCode();
		Pair p = { key, value };
		table[index].toEnd(p);
		return true;
	}

	bool remove(K const& key) {
		int index = key.hashCode();
		if (index < 0)
			return false;
		LinkedList<Pair>& l = table[index];
		Pair tmp;
		I it = l.iteratorBegin();
		if (!it)
			return false;
		if ((*it).key == key) {
			l.deleteAt(tmp, it);
			return true;
		}
		I itp = it++;
		while (it && (*it).key != key)
			itp = it++;
		if (!it)
			return false;
		l.deleteAfter(tmp, itp);
		return true;
	}

	LinkedList<K> keys() const {
		LinkedList<K> k;
		for(int i = 0; i < MAX; i++)
			for(I it = table[i].iteratorBegin(); it; ++it)
				k.toEnd((*it).key);
		return k;
	}

	LinkedList<V> values() const {
		LinkedList<V> v;
		for(int i = 0; i < MAX; i++)
			for(I it = table[i].iteratorBegin(); it; ++it)
				v.toEnd((*it).value);
		return v;
	}

	// задължителна заради LinkedList::print
	friend ostream& operator<<(ostream& os, Pair const& p) {
		return os << '(' << p.key << ',' << p.value << ')' << endl;
	}
};