#ifndef Array_H
#define Array_H

#include "Betriebssystem.h"
#include <stdexcept>
#include "Text.h"

namespace Framework
{
    template< class TYP >
    //! Ein Eintrag in einer Linked List
    struct ArrayEintrag
    {
        TYP var;
        bool set = false;
        ArrayEintrag< TYP >* next = 0;

        //! Setzt den Eintrag auf die Werte des anderen Eintrages
        ArrayEintrag& operator=( ArrayEintrag& r )
        {
            var = r.var;
            set = r.set;
            next = r.next;
            return *this;
        }
        //! Gibt den aktuell gespeicherten Wert zurück
        operator TYP()
        {
            if( !set )
            {
                Text err = "Index out of Range Exception File: ";
                err += __FILE__;
                err += " Line: ";
                err += __LINE__;
                throw std::out_of_range( (char*)err );
            }
            return var;
        }
        //! inkrementiert durch die Linked List durch
        ArrayEintrag< TYP >& operator++() //! prefix
        {
            if( !next )
            {
                ArrayEintrag<TYP> tmp;
                tmp.set = 0;
                tmp.next = 0;
                *this = tmp;
                return *this;
            }
            *this = *next;
            return *next;
        }
        //! inkrementiert durch die Linked List durch
        ArrayEintrag< TYP >& operator++( int ) //! postfix
        {
            if( !next )
            {
                ArrayEintrag<TYP> tmp;
                tmp.set = 0;
                tmp.next = 0;
                *this = tmp;
                return *this;
            }
            *this = *next;
            return *next;
        }
    };

    template< class TYP >
    class Iterator
    {
    private:
        ArrayEintrag< TYP >* current;

    public:
        Iterator( ArrayEintrag< TYP >* start )
        {
            current = start;
            while( current && !current->set )
            {
                current = current->next;
            }
        }

        Iterator( const Iterator& it )
        {
            current = it.current;
        }

        Iterator< TYP >& operator=( Iterator< TYP >& r )
        {
            current = r.current;
            return *this;
        }

        bool hasNext()
        {
            ArrayEintrag< TYP >* next = current->next;
            while( next && !next->set )
            {
                next = next->next;
            }
            return next != 0;
        }

        Iterator< TYP > next()
        {
            if( !current )
            {
                Text err = "Index out of Range Exception File: ";
                err += __FILE__;
                err += " Line: ";
                err += __LINE__;
                throw std::out_of_range( (char*)err );
            }
            return Iterator( current->next );
        }

        operator bool()
        {
            return current != 0;
        }

        operator TYP()
        {
            if( !current || !current->set )
            {
                Text err = "Index out of Range Exception File: ";
                err += __FILE__;
                err += " Line: ";
                err += __LINE__;
                throw std::out_of_range( (char*)err );
            }
            return current->var;
        }

        Iterator< TYP >& operator++() //! prefix
        {
            do
            {
                if( current )
                    current = current->next;
            } while( current && !current->set );
            return *this;
        }

        Iterator< TYP > operator++( int ) //! postfix
        {
            Iterator< TYP > temp( *this );
            do
            {
                if( current )
                    current = current->next;
            } while( current && !current->set );
            return temp;
        }

        TYP operator->()
        {
            if( !current || !current->set )
            {
                Text err = "Index out of Range Exception File: ";
                err += __FILE__;
                err += " Line: ";
                err += __LINE__;
                throw std::out_of_range( (char*)err );
            }
            return current->var;
        }

        TYP val()
        {
            if( !current || !current->set )
            {
                Text err = "Index out of Range Exception File: ";
                err += __FILE__;
                err += " Line: ";
                err += __LINE__;
                throw std::out_of_range( (char*)err );
            }
            return current->var;
        }
    };
#define _ val()

    template< class TYP >
    //! Eine Linked List von Klassen, die kein Reference Counting berteiben
    class Array
    {
    private:
        ArrayEintrag< TYP >* entries;
        int ref;

    public:
        //! Erstellt eine neue Linked List
        Array() noexcept
        {
            entries = new ArrayEintrag< TYP >();
            entries->set = 0;
            entries->next = 0;
            ref = 1;
        }

        //! Kopiert eine Linked list
        Array( const Array& arr )
        {
            entries = new ArrayEintrag< TYP >();
            entries->set = 0;
            entries->next = 0;
            int anz = arr.getEintragAnzahl();
            for( int i = 0; i < anz; i++ )
                add( arr.get( i ) );
            ref = 1;
        }

        //! Leert und löscht die Linked List 
        ~Array()
        {
            leeren();
            delete entries;
        }

        //! Hängt ein Element ans Ende der Liste an
        //! \param t Das neue Element
        void add( TYP t )
        {
            for( ArrayEintrag< TYP >* e = entries; 1; e = e->next )
            {
                if( !e->set && !e->next )
                {
                    e->var = t;
                    e->set = 1;
                    break;
                }
                if( !e->next )
                {
                    e->next = new ArrayEintrag< TYP >();
                    e->next->set = 0;
                    e->next->next = 0;
                }
            }
        }

        //! Fügt ein Element bei einer bestimmten Position in die Liste ein
        //! \param t das neue Element
        //! \param i Die Position, wo das Element eingefügt wird (danach der Index des neuen Elementes)
        void add( TYP t, int i )
        {
            if( i < 0 )
                return;
            ArrayEintrag< TYP >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                {
                    ArrayEintrag< TYP >* ne = new ArrayEintrag< TYP >();
                    ne->set = 0;
                    ne->next = 0;
                    e->next = ne;
                }
                e = e->next;
            }
            ArrayEintrag< TYP >* ne = new ArrayEintrag< TYP >();
            ne->var = e->var;
            ne->set = e->set;
            ne->next = e->next;
            e->next = ne;
            e->var = t;
            e->set = 1;
        }

        //! Setzt den Wert des i-ten Eintrags
        //! \param t der Neue Wert
        //! \param i Der Index des Eintrages der gesetzt werden soll
        void set( TYP t, int i )
        {
            if( i < 0 )
                return;
            ArrayEintrag< TYP >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                {
                    ArrayEintrag< TYP >* ne = new ArrayEintrag< TYP >();
                    ne->set = 0;
                    ne->next = 0;
                    e->next = ne;
                }
                e = e->next;
            }
            e->var = t;
            e->set = 1;
        }

        //! Verändert die Position des i-ten Elementes in der Liste
        //! \param i Der Index des Elementes, welches verschoben werden soll
        //! \param p Die Zielposition des Elementes (danach der neue Index des Elementes)
        void setPosition( int i, int p )
        {
            if( i < 0 || p < 0 || i == p )
                return;
            ArrayEintrag< TYP >* e = entries;
            ArrayEintrag< TYP >* ve = 0;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                    return;
                ve = e;
                e = e->next;
            }
            ArrayEintrag< TYP >* e2 = entries == e ? e->next : entries;
            ArrayEintrag< TYP >* ve2 = 0;
            for( int a = 0; a < p; ++a )
            {
                if( !e2 )
                    return;
                ve2 = e2;
                if( e2->next == e )
                    e2 = e->next;
                else
                    e2 = e2->next;
            }
            if( !e )
                return;
            if( !ve2 )
                entries = e;
            else
                ve2->next = e;
            if( ve )
                ve->next = e->next;
            else
                entries = e->next;
            e->next = e2;
        }

        //! Löscht ein Bestimmtes Element
        //! \param i Der Index des Elementes das gelöscht werden soll
        void remove( int i )
        {
            if( i < 0 )
                return;
            ArrayEintrag< TYP >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                    return;
                e = e->next;
            }
            if( !e )
                return;
            if( e->next )
            {
                e->var = e->next->var;
                e->set = e->next->set;
            }
            else
                e->set = 0;
            ArrayEintrag< TYP >* del = e->next;
            if( e->next )
                e->next = e->next->next;
            else
                e->next = 0;
            if( del )
            {
                del->set = 0;
                del->next = 0;
                delete del;
            }
        }

        //! Vertauscht zwei Elemente in der Liste
        //! \param vi Der Index des ersten Elementes
        //! \param ni Der Index des zweiten Elementes
        void tausch( int vi, int ni )
        {
            if( vi < 0 || ni < 0 )
                return;
            TYP tmp = get( ni );
            set( get( vi ), ni );
            set( tmp, vi );
        }

        //! Löscht alle Elemente der Liste
        void leeren()
        {
            ArrayEintrag< TYP >* e2 = 0;
            for( ArrayEintrag< TYP >* e = entries; e; e = e->next )
            {
                delete e2;
                e2 = e;
            }
            delete e2;
            entries = new ArrayEintrag< TYP >();
            entries->set = 0;
            entries->next = 0;
        }

        //! Gibt einen Iterator zurück.
        //! Mit ++ kann durch die Liste iteriert werden
        Iterator< TYP > getIterator() const
        {
            return Iterator< TYP >( entries );
        }

        //! Gibt zurück, wie viele Elemente in der Liste sind
        int getEintragAnzahl() const
        {
            int i = 0;
            for( auto it = getIterator(); it; it++ )
                ++i;
            return i;
        }

        //! Gibt den Wert des i-ten Elementes zurück
        //! \param i Der index des gesuchten Elementes
        //! throws:
        //!  std::out_of_range wenn i < 0 oder i >= getEintragAnzahl()
        TYP get( int i ) const
        {
            if( i < 0 )
            {
                Text err = "Index out of Range Exception File: ";
                err += __FILE__;
                err += " Line: ";
                err += __LINE__;
                err += " Index: ";
                err += i;
                throw std::out_of_range( (char*)err );
            }
            ArrayEintrag< TYP >* e = entries;
            for( int a = 0; a < i && e; ++a )
                e = e->next;
            if( e && e->set )
                return e->var;
            Text err = "Index out of Range Exception File: ";
            err += __FILE__;
            err += " Line: ";
            err += __LINE__;
            err += " Index: ";
            err += i;
            throw std::out_of_range( (char*)err );
        }

        //! Überprüft, ob ein Element in der Liste enthalten ist
        //! \param i Der Index des gesuchten Elementes
        //! \return (true), wenn der Index vorhanden ist. (false) sonnst
        bool hat( int i ) const
        {
            if( i < 0 )
                return 0;
            ArrayEintrag< TYP >* e = entries;
            for( int a = 0; a < i && e; ++a )
                e = e->next;
            if( e && e->set )
                return 1;
            return 0;
        }

        //! Gibt den Index eines Wertes zurück
        //! \param t Der Wert, nach dem gesucht werden soll
        int getWertIndex( TYP t ) const
        {
            int ret = 0;
            for( ArrayEintrag< TYP >* e = entries; e; e = e->next )
            {
                if( e->set && e->var == t )
                    return ret;
                ++ret;
            }
            return -1;
        }

        //! Erhöht den Reference Counting Zähler.
        //! \return this.
        Array< TYP >* getThis()
        {
            ++ref;
            return this;
        }

        //! Verringert den Reference Counting Zähler. Wenn der Zähler 0 erreicht, wird das Zeichnung automatisch gelöscht.
        //! \return 0.
        Array< TYP >* release()
        {
            --ref;
            if( !ref )
                delete this;
            return 0;
        }

        Array& operator=( const Array& arr )
        {
            leeren();
            int anz = arr.getEintragAnzahl();
            for( int i = 0; i < anz; i++ )
                add( arr.get( i ) );
            return *this;
        }
    };

    template< class TYP >
    //! Eine Linked List von Zeigern auf Zeichnunge, die Reference Counting berteiben
    class RCArray
    {
    private:
        ArrayEintrag< TYP* >* entries;
        int ref;

    public:
        //! Erstellt eine neue Linked List
        RCArray() noexcept
        {
            entries = new ArrayEintrag< TYP* >();
            entries->set = 0;
            entries->next = 0;
            ref = 1;
        }

        //! Kopiert eine Linked list
        RCArray( const RCArray& arr )
        {
            entries = new ArrayEintrag< TYP* >();
            entries->set = 0;
            entries->next = 0;
            int anz = arr.getEintragAnzahl();
            for( int i = 0; i < anz; i++ )
                add( arr.get( i ) );
            ref = 1;
        }

        //! Leert und löscht die Linked List 
        ~RCArray()
        {
            leeren();
            delete entries;
        }

        //! Hängt ein Element ans Ende der Liste an
        //! \param t Das neue Element
        void add( TYP* t )
        {
            for( ArrayEintrag< TYP* >* e = entries; 1; e = e->next )
            {
                if( !e->set && !e->next )
                {
                    e->var = t;
                    e->set = 1;
                    break;
                }
                if( !e->next )
                {
                    e->next = new ArrayEintrag< TYP* >();
                    if( e->next->set && e->next->var )
                        e->next->var->release();
                    e->next->set = 0;
                    e->next->next = 0;
                }
            }
        }

        //! Fügt ein Element bei einer bestimmten Position in die Liste ein
        //! \param t das neue Element
        //! \param i Die Position, wo das Element eingefügt wird (danach der Index des neuen Elementes)
        void add( TYP* t, int i )
        {
            if( i < 0 )
            {
                if( t )
                    t->release();
                return;
            }
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                {
                    ArrayEintrag< TYP* >* ne = new ArrayEintrag< TYP* >();
                    ne->set = 0;
                    ne->next = 0;
                    e->next = ne;
                }
                e = e->next;
            }
            ArrayEintrag< TYP* >* ne = new ArrayEintrag< TYP* >();
            ne->var = e->var;
            ne->set = e->set;
            ne->next = e->next;
            e->next = ne;
            e->var = t;
            e->set = 1;
        }

        //! Setzt den Wert des i-ten Eintrags
        //! \param t der Neue Wert
        //! \param i Der Index des Eintrages der gesetzt werden soll
        void set( TYP* t, int i )
        {
            if( i < 0 )
            {
                if( t )
                    t->release();
                return;
            }
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                {
                    ArrayEintrag< TYP* >* ne = new ArrayEintrag< TYP* >();
                    ne->set = 0;
                    ne->next = 0;
                    e->next = ne;
                }
                e = e->next;
            }
            if( e->set && e->var )
                e->var->release();
            e->var = t;
            e->set = 1;
        }

        //! Verändert die Position des i-ten Elementes in der Liste
        //! \param i Der Index des Elementes, welches verschoben werden soll
        //! \param p Die Zielposition des Elementes (danach der neue Index des Elementes)
        void setPosition( int i, int p )
        {
            if( i < 0 || p < 0 || i == p )
                return;
            ArrayEintrag< TYP* >* ve = 0;
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                    return;
                ve = e;
                e = e->next;
            }
            ArrayEintrag< TYP* >* e2 = entries == e ? e->next : entries;
            ArrayEintrag< TYP* >* ve2 = 0;
            for( int a = 0; a < p; ++a )
            {
                if( !e2 )
                    return;
                ve2 = e2;
                if( e2->next == e )
                    e2 = e->next;
                else
                    e2 = e2->next;
            }
            if( !e )
                return;
            if( !ve2 )
                entries = e;
            else
                ve2->next = e;
            if( ve )
                ve->next = e->next;
            else
                entries = e->next;
            e->next = e2;
        }

        //! Löscht ein Bestimmtes Element
        //! \param i Der Index des Elementes das gelöscht werden soll
        void remove( int i )
        {
            if( i < 0 )
                return;
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i; ++a )
            {
                if( !e->next )
                    return;
                e = e->next;
            }
            if( !e )
                return;
            if( e->next )
            {
                if( e->set && e->var )
                    e->var->release();
                e->var = e->next->var;
                e->set = e->next->set;
            }
            else
            {
                if( e->set && e->var )
                    e->var->release();
                e->set = 0;
            }
            ArrayEintrag< TYP* >* del = e->next;
            if( e->next )
                e->next = e->next->next;
            else
                e->next = 0;
            if( del )
            {
                del->set = 0;
                del->next = 0;
                delete del;
            }
        }

        //! Vertauscht zwei Elemente in der Liste
        //! \param vi Der Index des ersten Elementes
        //! \param ni Der Index des zweiten Elementes
        void tausch( int vi, int ni )
        {
            if( vi < 0 || ni < 0 )
                return;
            TYP* tmp = get( ni );
            set( get( vi ), ni );
            set( tmp, vi );
        }

        //! Löscht alle Elemente der Liste
        void leeren()
        {
            ArrayEintrag< TYP* >* e2 = 0;
            for( ArrayEintrag< TYP* >* e = entries; e; e = e->next )
            {
                if( e2 && e2->var && e2->set )
                    e2->var->release();
                delete e2;
                e2 = e;
            }
            if( e2 && e2->var && e2->set )
                e2->var->release();
            delete e2;
            entries = new ArrayEintrag< TYP* >();
            entries->set = 0;
            entries->next = 0;
        }

        //! Gibt einen Iterator zurück.
        //! Mit ++ kann durch die Liste iteriert werden
        Iterator< TYP* > getIterator() const
        {
            return Iterator< TYP* >( entries );
        }

        //! Gibt zurück, wie viele Elemente in der Liste sind
        int getEintragAnzahl() const
        {
            int i = 0;
            for( auto it = getIterator(); it; it++ )
                ++i;
            return i;
        }

        int getLastIndex() const
        {
            int index = 0;
            ArrayEintrag< TYP* >* e = entries;
            for( ; e; ++index )
                e = e->next;
            return index - 1;
        }

        //! Gibt den Wert des i-ten Elementes zurück mit erhöhtem Reference Counter
        //! \param i Der index des gesuchten Elementes, (0) wenn der Index nicht existiert
        TYP* get( int i ) const
        {
            if( i < 0 )
                return (TYP*)0;
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i && e; ++a )
                e = e->next;
            if( e && e->set && e->var )
                return (TYP*)e->var->getThis();
            return (TYP*)0;
        }

        //! Gibt den Wert des i-ten Elementes zurück ohne erhöhten Reference Counter
        //! \param i Der index des gesuchten Elementes, (0) wenn der Index nicht existiert
        TYP* z( int i ) const //! gibt den index - ten T zurück
        {
            if( i < 0 )
                return (TYP*)0;
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i && e; ++a )
                e = e->next;
            if( e && e->set && e->var )
                return (TYP*)e->var;
            return (TYP*)0;
        }

        //! Überprüft, ob ein Element in der Liste enthalten ist
        //! \param i Der Index des gesuchten Elementes
        //! \return (true), wenn der Index vorhanden ist. (false) sonnst
        bool hat( int i ) const
        {
            if( i < 0 )
                return 0;
            ArrayEintrag< TYP* >* e = entries;
            for( int a = 0; a < i && e; ++a )
                e = e->next;
            if( e && e->set )
                return 1;
            return 0;
        }

        //! Erhöht den Reference Counting Zähler.
        //! \return this.
        RCArray< TYP >* getThis()
        {
            ++ref;
            return this;
        }

        //! Verringert den Reference Counting Zähler. Wenn der Zähler 0 erreicht, wird das Zeichnung automatisch gelöscht.
        //! \return 0.
        RCArray< TYP >* release()
        {
            --ref;
            if( !ref )
                delete this;
            return 0;
        }

        RCArray& operator=( const RCArray& arr )
        {
            leeren();
            int anz = arr.getEintragAnzahl();
            for( int i = 0; i < anz; i++ )
                add( arr.get( i ) );
            return *this;
        }
    };
}

#endif