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 );
            }
            if( bucketIndex < bucketCount )
            {
                if( !iterator )
                    this->iterator = buckets[ bucketIndex ]->begin();
            }
            else
            {
                this->iterator = Iterator< MapEntry<K, V> >( 0 );
                this->bucketIndex = 0;
                this->buckets = 0;
                this->bucketCount = 0;
            }
            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( (char*)err );
            }
            if( iterator.hasNext() )
                return MapIterator( buckets, bucketCount, bucketIndex, iterator.next() );
            else
                return MapIterator( buckets, bucketCount, bucketIndex + 1, Iterator< MapEntry<K, V> >( 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( (char*)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 );
                    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( (char*)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( (char*)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( (char*)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 ) );
        }

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