/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.10 $
 *********************************************************************/

#ifndef _HASHTABLE_H
#define _HASHTABLE_H

#include "Map.h"
#include "LinkedList.h"
#include "Pair.h"
#include "Iterator.h"
#include <string>

namespace util
{
	/**
	 * Calculate a hash code for a type. If a new type is added, a
	 * hashCode function for it must be written. There are predefined
	 * functions for strings and elementary types.
	 **/
	template <class key> unsigned long hashCode(const key& obj);
	/**
	 * Calculate a hash code for a string. This will map string literals
	 * to cardinal numbers.
	 **/
	template <> unsigned long hashCode(const std::string& obj);

	/**
	 * Hashtable is an implementation of an associative array. It stores
	 * key-value pairs and allows look-ups using key values of any type.
	 **/
	template <class key, class value>	class Hashtable : public Map<key, value>, public Iterator<Pair<key,value> >
	{
	public:
		/**
		 * Create a new hash table.
		 * @param size the initial size of the table. The table will safely
		 *        hold any number of entries, but if the actual number of
		 *        stored entries is much larger than the initial size,
		 *        performance will be reduced.
		 **/
		Hashtable(unsigned int size=128);

		/**
		 * Copy a hash table.
		 **/
		Hashtable(const Hashtable& other);

		/**
		 * Copy a hash table.
		 **/
		Hashtable& operator= (const Hashtable& other);		
		/**
		 * Release the resources allocated by a Hashtable.
		 **/
		virtual ~Hashtable();
		
		/**
		 * Get a pointer to a stored object.
		 * @param obj the key object that references the wanted object
		 * @return a pointer to the value or NULL if it was not found
		 **/
		virtual value* get(const key& obj);

		/**
		 * Put a new entry into the table. If a value is already mapped to
		 * the key, the old value is replaced.
		 *
		 * @param obj the reference key
		 * @param val the object to be stored
		 **/
		virtual void put(const key& obj, const value& val);

		/**
		 * Remove the data referenced by <i>obj</i>. The memory reserved
		 * by the reference key and the actual object is released.
		 * @param obj the reference key
		 **/
		virtual void remove(const key& obj);

		/**
		 * Remove the given value from this hash table. The memory
		 * reserved by the reference key and the actual object is
		 * released. If the object is a pointer, it must be deleted by the
		 * user.
		 *
		 * @param obj the object to be removed
		 **/
		void removeValue(const value& obj);

		/**
		 * Check whether this hash table contains the given reference key.
		 *
		 * @return true if <i>obj</i> is found in the table, false otherwise
		 **/
		bool containsKey(const key& obj);
		
		/**
		 * Check whether this hash table contains the given value.
		 *
		 * @return true if <i>obj</i> is found in the table, false otherwise
		 **/
		bool containsValue(const value& obj);

		/**
		 * Clear the table. All allocated resources will be released.
		 **/
		void clear(void);

		/**
		 * Reset the internal iterator of this Hashtable.
		 **/
		void reset(void) { _uiArrayIndex = _uiNodeIndex = 0; }
		/**
		 * Get the next stored item. The items are not returned in
		 * insertion order.
		 **/
		Pair<key,value>* next(void);
		/**
		 * Check if we still have some items to fetch.
		 **/
		bool hasNext(void) const;

		/**
		 * Get the current number of key-value pairs in the hash table.
		 **/
		int getItems() const { return _iItems; }

	private:
		unsigned int _uiSize;
		unsigned int _uiArrayIndex, _uiNodeIndex;
		int _iItems;
		LinkedList<Pair<key, value> >** _ppData;
		void copy(LinkedList<Pair<key,value> >** from,
							LinkedList<Pair<key,value> >** to,
							unsigned int size);
	};

	template <class key, class value> Hashtable<key,value>::Hashtable(unsigned int elements) :
		_uiSize(elements), _uiArrayIndex(0), _uiNodeIndex(0), _iItems(0)
	{
		_ppData = new LinkedList<Pair<key, value> >*[_uiSize];

		for (unsigned int i=0;i<_uiSize;i++)
			_ppData[i] = NULL;
	}

	template <class key, class value> Hashtable<key,value>::Hashtable(const Hashtable& other) :
		_uiSize(other._uiSize), _uiArrayIndex(other._uiArrayIndex), _uiNodeIndex(other._uiNodeIndex), _iItems(other._iItems)
	{
		_ppData = new LinkedList<Pair<key, value> >*[_uiSize];

		copy(other._ppData,_ppData,_uiSize);
	}

	template <class key, class value> Hashtable<key,value>& Hashtable<key,value>::operator= (const Hashtable& other)
	{
		_uiSize = other._uiSize;
		_uiArrayIndex = other._uiArrayIndex;
		_uiNodeIndex = other._uiNodeIndex;
		_iItems = other._iItems;
		
		LinkedList<Pair<key, value> >** tmp = new LinkedList<Pair<key, value> >*[_uiSize];
		copy(other._ppData,tmp,_uiSize);

		clear();
		delete[] _ppData;
		_ppData = tmp;
		return *this;
	}

	template <class key, class value> void Hashtable<key,value>::copy(LinkedList<Pair<key,value> >** from,
																																		LinkedList<Pair<key,value> >** to,
																																		unsigned int size)
	{
		for (unsigned int i=0;i<size;i++)
			{
				LinkedList<Pair<key,value> >* next = from[i], *last = NULL;
				if (!next)
					to[i] = NULL;
				else
					{
						do
							{
								LinkedList<Pair<key,value> >* newNode =
									new LinkedList<Pair<key,value> >(Pair<key,value>(next->data().first(),next->data().second()));
								if (!last)
									to[i] = newNode;
								else
									last->setNext(newNode);
								last = newNode;
								next = next->getNext();
							} while (next);
					}
			}
	}

	template <class key, class value> Hashtable<key,value>::~Hashtable()
	{
		clear();
		delete[] _ppData;
	}
	
	template <class key, class value> void Hashtable<key,value>::clear(void)
	{
		for (unsigned int i=0;i<_uiSize;i++)
			{
				delete _ppData[i];
				_ppData[i] = NULL;
			}
		_iItems = 0;
	}

	template <class key, class value> void Hashtable<key,value>::put(const key& obj, const value& val)
	{
		//First find the list index
		unsigned int index = hashCode(obj) % _uiSize;
		LinkedList<Pair<key,value> >* node = _ppData[index];
		//If it is not occupied, just create a new linked list and attach it
		if (!node)
			{
				Pair<key,value> newPair(obj,val);
				_ppData[index] = new LinkedList<Pair<key,value> >(newPair);
				_iItems++;
			}
		//If it is occupied, go through the linked list and try to find a
		//match for the key.
		else
			{
				LinkedList<Pair<key,value> >* last = NULL;
				while (node)
					{
						if (node->data().first() == obj)
							break;
						last = node;
						node = node->getNext();
					}
				//If a match was not found, add to the end of the list
				if (!node)
					{
						Pair<key,value> newPair(obj,val);
						last->setNext(new LinkedList<Pair<key,value> >(newPair));
						_iItems++;
					}
				//Else just replace the old value
				else
					node->data().second() = val;
			}
	}

	template <class key, class value> void Hashtable<key,value>::remove(const key& obj)
	{
		//First find the list index
		unsigned int index = hashCode(obj) % _uiSize;
		LinkedList<Pair<key,value> >* node = _ppData[index];

		//If the node is occupied, go through the linked list and try to find a
		//match for the key.
		if (node)
			{
				LinkedList<Pair<key,value> >* previous = NULL;
				while (node)
					{
						if (node->data().first() == obj)
							break;
						previous = node;
						node = node->getNext();
					}

				//If a matching node was found, delete the data.
				if (node)
					{
						//If this is the first node, then move the start pointer
						if (!previous)
							_ppData[index] = node->getNext();
						else
							previous->setNext(node->getNext());
						node->setNext(NULL);
						delete node;
						_iItems--;
					}
			}
	}

	template <class key, class value> void Hashtable<key,value>::removeValue(const value& obj)
	{
		//Loop through the array of linked lists
		for (unsigned int i=0;i<_uiSize;i++)
			{
				LinkedList<Pair<key,value> >* node = _ppData[i], *previous = NULL;
				//Loop through the linked list
				while (node && node->getData().second() != obj)
					{
						previous = node;
						node = node->getNext();
					}

				if (node) //Match was found
					{
						//If this is the first node, then move the start pointer
						if (!previous)
							_ppData[i] = node->getNext();
						else
							previous->setNext(node->getNext());
						node->setNext(NULL);
						delete node;
						_iItems--;
					}
			}
	}

	template <class key, class value> bool Hashtable<key,value>::containsKey(const key& obj)
	{
		for (unsigned int i=0;i<_uiSize;i++)
			{
				LinkedList<Pair<key,value> >* node = _ppData[i];
				while (node && node->getData().first() != obj)
					node = node->getNext();
				if (node) return true;
			}
		return false;
	}

	template <class key, class value> bool Hashtable<key,value>::containsValue(const value& obj)
	{
		for (unsigned int i=0;i<_uiSize;i++)
			{
				LinkedList<Pair<key,value> >* node = _ppData[i];
				while (node && node->getData().second() != obj)
					node = node->getNext();
				if (node) return true;
			}
		return false;
	}

	template <class key, class value> value* Hashtable<key,value>::get(const key& obj)
	{
		unsigned int index = hashCode(obj) % _uiSize;
		LinkedList<Pair<key,value> >* node = _ppData[index];

		while (node)
			{
				if (node->data().first() == obj)
					return &node->data().second();
				node = node->getNext();
			}
		return NULL;
	}

	template <class key, class value> Pair<key,value>* Hashtable<key,value>::next(void)
	{
		if (_uiArrayIndex >= _uiSize)
			return NULL;
		
		LinkedList<Pair<key,value> >* node = _ppData[_uiArrayIndex];
		unsigned int index = 0;
		while (node && index < _uiNodeIndex)
			{
				node = node->getNext();
				index++;
			}

		_uiNodeIndex++;
		
		if (node)
			return &node->data();

		_uiNodeIndex = 1;
		_uiArrayIndex++;
		
		while (_uiArrayIndex < _uiSize && !_ppData[_uiArrayIndex]) _uiArrayIndex++;

		if (_uiArrayIndex < _uiSize)
			return &_ppData[_uiArrayIndex]->data();
		return NULL;
	}

	template <class key, class value> bool Hashtable<key,value>::hasNext(void) const
	{
		if (_uiArrayIndex >= _uiSize)
			return false;
		
		LinkedList<Pair<key,value> >* node = _ppData[_uiArrayIndex];
		unsigned int index = 0;
		while (node && index < _uiNodeIndex)
			{
				node = node->getNext();
				index++;
			}
		if (node) return true;

		unsigned int i;
		for (i=_uiArrayIndex+1;i < _uiSize && !_ppData[i]; i++);

		return (i < _uiSize);
	}


	//******************* HASHING FUNCTIONS **********************

	template <class key> unsigned long hashCode(const key& obj)
	{
		return (unsigned long)obj;
	}
}

#endif