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));
        }
    };
} // namespace Framework