KSG-Framework/HashMap.h

#pragma once

#include <functional>

#include "Array.h"

namespace Framework
{
	template<typename K, typename V>
	class MapEntry
	{
	private:
		K key;
		V value;

	public:
		MapEntry()
		{}

		MapEntry(K key, V value)
			: key(key),
			value(value)
		{}

		K getKey()
		{
			return key;
		}

		V getValue()
		{
			return value;
		}

		template<typename K2, typename V2>
		friend class HashMap;
	};

	template<typename K, typename V>
	class MapIterator
	{
	private:
		int bucketIndex;
		Iterator< MapEntry<K, V> > iterator;
		Array< MapEntry<K, V> >** buckets;
		int bucketCount;

	public:
		MapIterator(Array< MapEntry<K, V> >** buckets, int bucketCount, int bucketIndex, Iterator< MapEntry<K, V> > iterator)
			: iterator(iterator)
		{
			while (bucketIndex < bucketCount && (!buckets[bucketIndex] || buckets[bucketIndex]->getEintragAnzahl() == 0))
			{
				bucketIndex++;
				iterator = Iterator< MapEntry<K, V> >(0, 0);
			}
			if (bucketIndex < bucketCount)
			{
				if (!iterator)
					this->iterator = buckets[bucketIndex]->begin();
			}
			else
			{
				this->iterator = Iterator< MapEntry<K, V> >(0, 0);
				this->bucketIndex = 0;
				this->buckets = 0;
				this->bucketCount = 0;
				return;
			}
			this->buckets = buckets;
			this->bucketCount = bucketCount;
			this->bucketIndex = bucketIndex;
		}

		MapIterator(const MapIterator< K, V >& it)
			: iterator(it.iterator)
		{
			buckets = it.buckets;
			bucketCount = it.bucketCount;
			bucketIndex = it.bucketIndex;
		}

		MapIterator< K, V >& operator=(MapIterator< K, V > r)
		{
			iterator = r.iterator;
			buckets = r.buckets;
			bucketCount = r.bucketCount;
			bucketIndex = r.bucketIndex;
			return *this;
		}

		bool hasNext()
		{
			if (iterator && iterator.hasNext())
				return 1;
			int ind = bucketIndex + 1;
			while (ind < bucketCount && (!buckets[ind] || buckets[ind]->getEintragAnzahl() == 0))
				ind++;
			return ind < bucketCount;
		}

		MapIterator< K, V > next()
		{
			if (bucketIndex >= bucketCount)
			{
				Text err = "Index out of Range Exception File: ";
				err += __FILE__;
				err += " Line: ";
				err += __LINE__;
				throw std::out_of_range(err);
			}
			if (iterator.hasNext())
				return MapIterator(buckets, bucketCount, bucketIndex, iterator.next());
			else
				return MapIterator(buckets, bucketCount, bucketIndex + 1, Iterator< MapEntry<K, V> >(0, 0));
		}

		operator bool()
		{
			return bucketIndex < bucketCount;
		}

		operator MapEntry<K, V>()
		{
			if (bucketIndex >= bucketCount)
			{
				Text err = "Index out of Range Exception File: ";
				err += __FILE__;
				err += " Line: ";
				err += __LINE__;
				throw std::out_of_range(err);
			}
			return iterator.val();
		}

		MapIterator< K, V >& operator++() //! prefix
		{
			++iterator;
			if (!iterator)
			{
				bucketIndex++;
				while (bucketIndex < bucketCount && (!buckets[bucketIndex] || buckets[bucketIndex]->getEintragAnzahl() == 0))
					bucketIndex++;
				if (bucketIndex < bucketCount)
					this->iterator = buckets[bucketIndex]->begin();
				else
				{
					this->iterator = Iterator< MapEntry<K, V> >(0, 0);
					this->bucketIndex = 0;
					this->buckets = 0;
					this->bucketCount = 0;
				}
			}
			return *this;
		}

		MapIterator< K, V > operator++(int) //! postfix
		{
			MapIterator< K, V > temp(*this);
			++(*this);
			return temp;
		}

		MapEntry< K, V > operator*()
		{
			if (bucketIndex >= bucketCount)
			{
				Text err = "Index out of Range Exception File: ";
				err += __FILE__;
				err += " Line: ";
				err += __LINE__;
				throw std::out_of_range(err);
			}
			return iterator.val();
		}

		MapEntry< K, V > operator->()
		{
			if (bucketIndex >= bucketCount)
			{
				Text err = "Index out of Range Exception File: ";
				err += __FILE__;
				err += " Line: ";
				err += __LINE__;
				throw std::out_of_range(err);
			}
			return iterator.val();
		}

		void set(MapEntry<K, V> val)
		{
			if (bucketIndex < bucketCount)
				iterator.set(val);
			else
			{
				Text err = "Index out of Range Exception File: ";
				err += __FILE__;
				err += " Line: ";
				err += __LINE__;
				throw std::out_of_range(err);
			}
		}

		bool operator!=(MapIterator< K, V >& r)
		{
			return buckets != r.buckets || iterator != r.iterator;
		}
	};

	template<typename K, typename V>
	class HashMap : public virtual ReferenceCounter
	{
	private:
		Array< MapEntry<K, V> >** buckets;
		int bucketCount;
		std::function<int(K)> hash;
		int size;

	public:
		HashMap(int bucketCount, std::function<int(K)> hash)
			: ReferenceCounter(),
			buckets(new Array< MapEntry<K, V> >* [bucketCount]),
			bucketCount(bucketCount),
			hash(hash),
			size(0)
		{
			memset(buckets, 0, sizeof(Array< MapEntry<K, V> > *) * bucketCount);
		}

		~HashMap()
		{
			for (int i = 0; i < bucketCount; i++)
			{
				if (buckets[i])
					buckets[i]->release();
			}
			delete[] buckets;
		}

		void put(K key, V value)
		{
			int index = abs(hash(key)) % bucketCount;
			if (!buckets[index])
				buckets[index] = new Array< MapEntry<K, V>>();
			for (auto iterator = buckets[index]->begin(); iterator; iterator++)
			{
				if (iterator._.getKey() == key)
				{
					iterator.set(MapEntry<K, V>(key, value));
					return;
				}
			}
			buckets[index]->add(MapEntry<K, V>(key, value));
			size++;
		}

		void remove(K key)
		{
			int index = abs(hash(key)) % bucketCount;
			if (!buckets[index])
				return;
			int listIndex = 0;
			for (auto bucket : *buckets[index])
			{
				if (bucket.getKey() == key)
				{
					buckets[index]->remove(listIndex);
					size--;
					return;
				}
				listIndex++;
			}
		}

		V get(K key) const
		{
			int index = abs(hash(key)) % bucketCount;
			if (!buckets[index])
				throw "element not found";
			for (auto iterator : *buckets[index])
			{
				if (iterator.getKey() == key)
					return iterator.getValue();
			}
			throw "element not found";
		}

		V safeGet(K key, V fallback) const
		{
			int index = abs(hash(key)) % bucketCount;
			if (!buckets[index])
				return fallback;
			for (auto bucket : *buckets[index])
			{
				if (bucket.getKey() == key)
					return bucket.getValue();
			}
			return fallback;
		}

		bool has(K key) const
		{
			int index = abs(hash(key)) % bucketCount;
			if (!buckets[index])
				return 0;
			for (auto bucket : *buckets[index])
			{
				if (bucket.getKey() == key)
					return 1;
			}
			return 0;
		}

		int getSize() const
		{
			return size;
		}

		void leeren()
		{
			for (int i = 0; i < bucketCount; i++)
			{
				if (buckets[i])
					buckets[i]->leeren();
			}
		}

		MapIterator<K, V> begin()
		{
			return MapIterator<K, V>(buckets, bucketCount, 0, Iterator< MapEntry<K, V> >(0, 0));
		}

		MapIterator<K, V> end()
		{
			return MapIterator<K, V>(0, 0, 0, Iterator< MapEntry<K, V> >(0, 0));
		}
	};
}