KSG-Framework/Array.h

#ifndef Array_H
#define Array_H

#include <functional>
#include <stdexcept>

#include "Errors.h"
#include "ReferenceCounter.h"
#include "Text.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;
            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;
            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;
        }

        //! returns the index of the first element that matches zT or -1 if not found
        int indexOf(TYP* zT) const
        {
            int i = 0;
            for (TYP* t : *this)
            {
				if (t == zT)
					return i;
				++i;
			}
			return -1;
        }

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

#endif