KSG-Framework/Array.h

#ifndef Array_H
#define Array_H

#include <stdexcept>
#include <functional>

#include "Errors.h"
#include "Text.h"
#include "ReferenceCounter.h"

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

		ArrayEintrag()
			: var(),
			set(0),
			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(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;
		}
#ifdef WIN32
#pragma warning( once : 26495 )
	};
#else
};
#endif


	template< class TYP >
	class Iterator
	{
	private:
		ArrayEintrag< TYP >* current;
		std::function<ArrayEintrag<TYP>* (ArrayEintrag<TYP>* removed)> onRemove;

	public:
		Iterator(ArrayEintrag< TYP >* start, std::function<ArrayEintrag<TYP>* (ArrayEintrag<TYP>* removed)> onRemove)
		{
			this->onRemove = onRemove;
			current = start;
			while (current && !current->set)
			{
				current = current->next;
			}
		}

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

		~Iterator()
		{
			current = 0;
		}

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

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

		TYP operator*()
		{
			return current->var;
		}

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

		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(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(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(err);
			}
			return current->var;
		}

		void set(TYP val)
		{
			if (current)
			{
				current->var = val;
				current->set = true;
			}
			else
			{
				Text err = "Index out of Range Exception File: ";
				err += __FILE__;
				err += " Line: ";
				err += __LINE__;
				throw std::out_of_range(err);
			}
		}

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

		void remove()
		{
			current = onRemove(current);
		}
	};
#define _ val()

	template< class TYP >
	//! Eine Linked List von Klassen, die kein Reference Counting berteiben
	class Array : public virtual ReferenceCounter
	{
	private:
		ArrayEintrag< TYP >* entries;
		ArrayEintrag< TYP >* last;
		int count;
		std::function<ArrayEintrag<TYP>* (ArrayEintrag<TYP>* removed)> onRemove;

	public:
		//! Erstellt eine neue Linked List
		Array() noexcept
			: ReferenceCounter()
		{
			entries = new ArrayEintrag< TYP >();
			entries->set = 0;
			entries->next = 0;
			last = entries;
			count = 0;
			onRemove = [this](ArrayEintrag<TYP>* entry)
			{
				if (!entry)
					return (ArrayEintrag<TYP>*)0;
				if (entry->next)
				{
					entry->var = entry->next->var;
					entry->set = entry->next->set;
				}
				else
					entry->set = 0;
				ArrayEintrag< TYP >* del = entry->next;
				if (entry->next)
					entry->next = entry->next->next;
				else
					entry->next = 0;
				if (del)
				{
					del->set = 0;
					del->next = 0;
					if (last == del)
						last = entry;
					delete del;
				}
				count--;
				return entry->set ? entry : 0;
			};
		}

		//! Kopiert eine Linked list
		//! 
		Array(const Array& arr)
			: Array()
		{
			int anz = arr.getEintragAnzahl();
			for (int i = 0; i < anz; i++)
				add(arr.get(i));
		}

		//! 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)
		{
			if (!last->set)
			{
				last->var = t;
				last->set = 1;
				count++;
				return;
			}
			last->next = new ArrayEintrag< TYP >();
			last = last->next;
			last->set = 1;
			last->var = t;
			count++;
		}

		//! 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 || i > count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			if (i == count)
			{
				add(t);
				return;
			}
			ArrayEintrag< TYP >* e = entries;
			for (int a = 0; a < i; ++a)
				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;
			count++;
		}

		//! 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 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP >* e = entries;
			for (int a = 0; a < i; ++a)
				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 == p)
				return;
			if (i < 0 || p < 0 || i >= count || p >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP >* e = entries;
			ArrayEintrag< TYP >* ve = 0;
			for (int a = 0; a < i; ++a)
			{
				ve = e;
				e = e->next;
			}
			ArrayEintrag< TYP >* e2 = entries == e ? e->next : entries;
			ArrayEintrag< TYP >* ve2 = 0;
			for (int a = 0; a < p; ++a)
			{
				ve2 = e2;
				if (e2->next == e)
					e2 = e->next;
				else
					e2 = e2->next;
			}
			if (e == last)
				last = e2;
			else if (e2 == last)
				last = e;
			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 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP >* e = entries;
			for (int a = 0; a < i; ++a)
				e = e->next;
			onRemove(e);
		}

		//! Löscht ein Bestimmtes Element
		//! \param i Der Index des Elementes das gelöscht werden soll
		void removeValue(TYP value)
		{
			ArrayEintrag< TYP >* e = entries;
			while (e->var != value)
			{
				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;
				if (last == del)
					last = e;
				delete del;
			}
			count--;
		}

		//! 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)
		{
			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;
			last = entries;
			count = 0;
		}

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

		Iterator< TYP > end() const
		{
			return Iterator< TYP >(0, onRemove);
		}

		//! Gibt zurück, wie viele Elemente in der Liste sind
		int getEintragAnzahl() const
		{
			return count;
		}

		//! Gibt den Wert des i-ten Elementes zurück
		//! \param i Der index des gesuchten Elementes
		//! throws:
		//! \param std:out_of_range wenn i < 0 oder i >= getEintragAnzahl()
		TYP get(int i) const
		{
			if (i < 0 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP >* e = entries;
			for (int a = 0; a < i && e; ++a)
				e = e->next;
			return e->var;
		}

		//! Ü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
		{
			return i >= 0 && i < count;
		}

		//! 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;
		}

		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 : public virtual ReferenceCounter
	{
	private:
		ArrayEintrag< TYP* >* entries;
		ArrayEintrag< TYP* >* last;
		int count;
		std::function<ArrayEintrag<TYP*>* (ArrayEintrag<TYP*>* removed)> onRemove;

	public:
		//! Erstellt eine neue Linked List
		RCArray() noexcept
			: ReferenceCounter()
		{
			entries = new ArrayEintrag< TYP* >();
			entries->var = 0;
			entries->set = 0;
			entries->next = 0;
			last = entries;
			count = 0;
			onRemove = [this](ArrayEintrag<TYP*>* entry)
			{
				if (!entry)
					return (ArrayEintrag< TYP* >*)0;
				if (entry->next)
				{
					if (entry->set && entry->var)
						entry->var->release();
					entry->var = entry->next->var;
					entry->set = entry->next->set;
				}
				else
				{
					if (entry->set && entry->var)
						entry->var->release();
					entry->set = 0;
				}
				ArrayEintrag< TYP* >* del = entry->next;
				if (entry->next)
					entry->next = entry->next->next;
				else
					entry->next = 0;
				if (del)
				{
					del->var = 0;
					del->set = 0;
					del->next = 0;
					if (last == del)
						last = entry;
					delete del;
				}
				count--;
				return entry->set ? entry : 0;
			};
		}

		//! Kopiert eine Linked list
		RCArray(const RCArray& arr)
			: RCArray()
		{
			int anz = arr.getEintragAnzahl();
			for (int i = 0; i < anz; i++)
				add(arr.get(i));
		}

		//! 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)
		{
			count++;
			if (!last->set)
			{
				last->var = t;
				last->set = 1;
				return;
			}
			last->next = new ArrayEintrag< TYP* >();
			last = last->next;
			last->var = t;
			last->set = 1;
		}

		//! 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 || i > count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			if (i == count)
			{
				add(t);
				return;
			}
			ArrayEintrag< TYP* >* e = entries;
			for (int a = 0; a < i; ++a)
				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;
			if (last->next)
				last = last->next;
			count++;
		}

		//! 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 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP* >* e = entries;
			for (int a = 0; a < i; ++a)
				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 == p)
				return;
			if (i < 0 || p < 0 || i >= count || p >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP* >* ve = 0;
			ArrayEintrag< TYP* >* e = entries;
			for (int a = 0; a < i; ++a)
			{
				ve = e;
				e = e->next;
			}
			ArrayEintrag< TYP* >* e2 = entries == e ? e->next : entries;
			ArrayEintrag< TYP* >* ve2 = 0;
			for (int a = 0; a < p; ++a)
			{
				ve2 = e2;
				if (e2->next == e)
					e2 = e->next;
				else
					e2 = e2->next;
			}
			if (last == e)
				last = e2;
			else if (last == e2)
				last = e;
			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 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP* >* e = entries;
			for (int a = 0; a < i; ++a)
				e = e->next;
			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;
				if (last == del)
					last = e;
				delete del;
			}
			count--;
		}

		//! 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()
		{
			for (ArrayEintrag< TYP* >* e = entries; e; )
			{
				if (e && e->var && e->set)
					e->var->release();
				auto tmp = e->next;
				delete e;
				e = tmp;
			}
			entries = new ArrayEintrag< TYP* >();
			entries->set = 0;
			entries->next = 0;
			last = entries;
			count = 0;
		}

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

		Iterator< TYP* > end() const
		{
			return Iterator< TYP* >(0, onRemove);
		}

		//! Gibt zurück, wie viele Elemente in der Liste sind
		int getEintragAnzahl() const
		{
			return count;
		}

		int getLastIndex() const
		{
			return count - 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 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			ArrayEintrag< TYP* >* e = entries;
			for (int a = 0; a < i && e; ++a)
				e = e->next;
			if (e && e->set && e->var)
				return dynamic_cast<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 || i >= count)
				throwOutOfRange(__FILE__, __LINE__, i, count);
			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
		{
			return i >= 0 && i < count;
		}

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

#endif