#ifndef Array_H
#define Array_H

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

namespace Framework
{
    // Ein Eintrag in einer Linked List
	template< class TYP >
	struct ArrayEintrag
	{
		TYP var;
		bool set;
		ArrayEintrag< TYP > *next;
		
        // 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()
		{
			return var;
		}
        // inkrementiert durch die Linked List durch
		ArrayEintrag< TYP > &operator++( ) // prefix
		{
            if( !next )
            {
                *this = ArrayEintrag{ 0, 0, 0 };
                return *this;
            }
			*this = *next;
			return *next;
		}
        // inkrementiert durch die Linked List durch
		ArrayEintrag< TYP > &operator++( int ) // postfix
		{
            if( !next )
            {
                *this = ArrayEintrag{ 0, 0, 0 };
                return *this;
            }
			*this = *next;
			return *next;
		}
	};

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

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

		// Leert und löscht die Linked List 
		~Array()
		{
			leeren();
			delete einträge;
		}

		// Hängt ein Element ans Ende der Liste an
        //  t: Das neue Element
		void add( TYP t )
		{
			for( ArrayEintrag< TYP > *e = einträge; 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 = einträge;
			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 = einträge;
			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 = einträge;
			ArrayEintrag< TYP > *ve = 0;
			for( int a = 0; a < i; ++a )
			{
				if( !e->next )
					return;
				ve = e;
				e = e->next;
			}
			ArrayEintrag< TYP > *e2 = einträge == e ? e->next : einträge;
			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 )
				einträge = e;
			else
				ve2->next = e;
			if( ve )
				ve->next = e->next;
			else
				einträge = e->next;
			e->next = e2;
		}

        // Löscht ein Bestimmtes Element
        //  i: Der Index des Elementes das gelöscht werden soll
		void lösche( int i )
		{
			if( i < 0 )
				return;
			ArrayEintrag< TYP > *e = einträge;
			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 = einträge; e; e = e->next )
			{
				delete e2;
				e2 = e;
			}
			delete e2;
			einträge = new ArrayEintrag< TYP >();
			einträge->set = 0;
			einträge->next = 0;
		}

        // Gibt das Erste Element der Liste zurück.
        // Mit ++ kann durch die Liste iteriert werden
		ArrayEintrag< TYP > &getArray() 
		{
			return *einträge;
		}

		// Gibt zurück, wie viele Elemente in der Liste sind
		int getEintragAnzahl() const
		{
			int i = 0;
			for( ArrayEintrag< TYP > *e = einträge; e && ( e->set || e->next ); e = e->next )
				++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( err );
            }
			ArrayEintrag< TYP > *e = einträge;
			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( 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 = einträge;
			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 = einträge; 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;
		}
	};

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

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

        // Leert und löscht die Linked List 
		~RCArray()
		{
			leeren();
			delete einträge;
		}

        // Hängt ein Element ans Ende der Liste an
        //  t: Das neue Element
		void add( TYP* t )
		{
			for( ArrayEintrag< TYP* > *e = einträge; 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 = einträge;
			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 = einträge;
			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 = einträge;
			for( int a = 0; a < i; ++a )
			{
				if( !e->next )
					return;
				ve = e;
				e = e->next;
			}
			ArrayEintrag< TYP* > *e2 = einträge == e ? e->next : einträge;
			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 )
				einträge = e;
			else
				ve2->next = e;
			if( ve )
				ve->next = e->next;
			else
				einträge = e->next;
			e->next = e2;
		}

        // Löscht ein Bestimmtes Element
        //  i: Der Index des Elementes das gelöscht werden soll
		void lösche( int i )
		{
			if( i < 0 )
				return;
			ArrayEintrag< TYP* > *e = einträge;
			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 = einträge; 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;
			einträge = new ArrayEintrag< TYP* >();
			einträge->set = 0;
			einträge->next = 0;
		}

        // Gibt das Erste Element der Liste zurück.
        // Mit ++ kann durch die Liste iteriert werden
		ArrayEintrag< TYP* > &getArray()
		{
			return *einträge;
		}

        // Gibt zurück, wie viele Elemente in der Liste sind
		int getEintragAnzahl() const
		{
			int i = 0;
			for( ArrayEintrag< TYP* > *e = einträge; e && ( e->set || e->next ); e = e->next )
				++i;
			return i;
		}

        // 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 = einträge;
			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 = einträge;
			for( int a = 0; a < i && e; ++a )
				e = e->next;
			if( e && e->set && e->var )
				return (TYP*)e->var;
			return (TYP*)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;
		}
	};
}

#endif