#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
        //  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
        //  t: das neue Element
        //  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
        //  t: der Neue Wert
        //  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
        //  i: Der Index des Elementes, welches verschoben werden soll
        //  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
        //  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
        //  vi: Der Index des ersten Elementes
        //  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
        //  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
        //  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
        //  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
        //  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
        //  t: das neue Element
        //  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
        //  t: der Neue Wert
        //  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
        //  i: Der Index des Elementes, welches verschoben werden soll
        //  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
        //  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
        //  vi: Der Index des ersten Elementes
        //  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
        //  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
        //  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
        //  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