KSG-Framework/Array.h

#pragma once

#include <functional>
#include <stdexcept>

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

namespace Framework
{
    template<class TYP>
    //! An entry in a linked list
    struct ArrayEntry
    {
        TYP var;
        bool set;
        ArrayEntry<TYP>* next;

        ArrayEntry()
            : var(),
              set(0),
              next(0)
        {}

        //! Sets the entry to the values of the other entry
        ArrayEntry& operator=(ArrayEntry& r)
        {
            var = r.var;
            set = r.set;
            next = r.next;
            return *this;
        }

        //! Returns the currently stored value
        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;
        }

        //! Increments through the linked list
        ArrayEntry<TYP>& operator++() //! prefix
        {
            if (!next)
            {
                ArrayEntry<TYP> tmp;
                tmp.set = 0;
                tmp.next = 0;
                *this = tmp;
                return *this;
            }
            *this = *next;
            return *next;
        }

        //! Increments through the linked list
        ArrayEntry<TYP>& operator++(int) //! postfix
        {
            if (!next)
            {
                ArrayEntry<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 ArrayIterator
        : public Iterator<TYP, ArrayIterator<TYP>>
    {
    private:
        ArrayEntry<TYP>* current;
        const std::function<ArrayEntry<TYP>*(ArrayEntry<TYP>* removed)>*
            onRemove;

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

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

        virtual ~ArrayIterator()
        {
            current = 0;
        }

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

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

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

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

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

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

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

        void set(TYP val) override
        {
            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!=(ArrayIterator<TYP>& r)
        {
            return current != r.current;
        }

        void remove() override
        {
            current = (*onRemove)(current);
        }
    };

#define _ val()

    template<class TYP>
    //! A linked list of classes that do not use reference counting
    class Array : public virtual ReferenceCounter
    {
    private:
        ArrayEntry<TYP>* entries;
        ArrayEntry<TYP>* last;
        int count;
        std::function<ArrayEntry<TYP>*(ArrayEntry<TYP>* removed)> onRemove;

    public:
        //! Creates a new linked list
        Array() noexcept
            : ReferenceCounter()
        {
            entries = new ArrayEntry<TYP>();
            entries->set = 0;
            entries->next = 0;
            last = entries;
            count = 0;
            onRemove = [this](ArrayEntry<TYP>* entry) {
                if (!entry) return (ArrayEntry<TYP>*)0;
                if (entry->next)
                {
                    entry->var = entry->next->var;
                    entry->set = entry->next->set;
                }
                else
                    entry->set = 0;
                ArrayEntry<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;
            };
        }

        //! Copies a linked list
        //!
        Array(const Array& arr)
            : Array()
        {
            int anz = arr.getEntryCount();
            for (int i = 0; i < anz; i++)
                add(arr.get(i));
        }

        //! Clears and deletes the linked list
        ~Array()
        {
            clear();
            delete entries;
        }

        //! Appends an element to the end of the list
        //! \param t The new element
        void add(TYP t)
        {
            if (!last->set)
            {
                last->var = t;
                last->set = 1;
                count++;
                return;
            }
            last->next = new ArrayEntry<TYP>();
            last = last->next;
            last->set = 1;
            last->var = t;
            count++;
        }

        //! Inserts an element at a specific position in the list
        //! \param t The new element
        //! \param i The position where the element is inserted (afterwards the
        //! index of the new element)
        void add(TYP t, int i)
        {
            if (i < 0 || i > count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            if (i == count)
            {
                add(t);
                return;
            }
            ArrayEntry<TYP>* e = entries;
            for (int a = 0; a < i; ++a)
                e = e->next;
            ArrayEntry<TYP>* ne = new ArrayEntry<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++;
        }

        //! Sets the value of the i-th entry
        //! \param t The new value
        //! \param i The index of the entry to be set
        void set(TYP t, int i)
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<TYP>* e = entries;
            for (int a = 0; a < i; ++a)
                e = e->next;
            e->var = t;
            e->set = 1;
        }

        //! Changes the position of the i-th element in the list
        //! \param i The index of the element to be moved
        //! \param p The target position of the element (afterwards the new
        //! index of the element)
        void setPosition(int i, int p)
        {
            if (i == p) return;
            if (i < 0 || p < 0 || i >= count || p >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            TYP t = get(i);
            remove(i);
            add(t, p);
        }

        //! Deletes a specific element
        //! \param i The index of the element to be deleted
        void remove(int i)
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<TYP>* e = entries;
            for (int a = 0; a < i; ++a)
                e = e->next;
            onRemove(e);
        }

        //! Deletes a specific element by value
        //! \param value The value of the element to be deleted
        void removeValue(TYP value)
        {
            ArrayEntry<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;
            ArrayEntry<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--;
        }

        //! Swaps two elements in the list
        //! \param vi The index of the first element
        //! \param ni The index of the second element
        void swap(int vi, int ni)
        {
            TYP tmp = get(ni);
            set(get(vi), ni);
            set(tmp, vi);
        }

        //! Deletes all elements of the list
        void clear()
        {
            ArrayEntry<TYP>* e2 = 0;
            for (ArrayEntry<TYP>* e = entries->next; e; e = e->next)
            {
                delete e2;
                e2 = e;
            }
            delete e2;
            entries->set = 0;
            entries->next = 0;
            last = entries;
            count = 0;
        }

        //! Returns an iterator.
        //! Use ++ to iterate through the list
        ArrayIterator<TYP> begin() const
        {
            return ArrayIterator<TYP>(entries, &onRemove);
        }

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

        //! Returns how many elements are in the list
        int getEntryCount() const
        {
            return count;
        }

        //! Returns the value of the i-th element
        //! \param i The index of the sought element
        //! throws:
        //! \param std:out_of_range if i < 0 or i >= getEntryCount()
        TYP get(int i) const
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<TYP>* e = entries;
            for (int a = 0; a < i && e; ++a)
                e = e->next;
            return e->var;
        }

        //! Checks whether an element exists in the list
        //! \param i The index of the sought element
        //! \return (true) if the index exists. (false) otherwise
        bool has(int i) const
        {
            return i >= 0 && i < count;
        }

        //! Returns the index of a value
        //! \param t The value to search for
        int getValueIndex(TYP t) const
        {
            int ret = 0;
            for (ArrayEntry<TYP>* e = entries; e; e = e->next)
            {
                if (e->set && e->var == t) return ret;
                ++ret;
            }
            return -1;
        }

        bool anyMatch(std::function<bool(const TYP element)> predicate) const
        {
            for (TYP t : *this)
            {
                if (predicate(t)) return 1;
            }
            return 0;
        }

        bool allMatch(std::function<bool(const TYP element)> predicate) const
        {
            for (TYP t : *this)
            {
                if (!predicate(t)) return 0;
            }
            return 1;
        }

        int findIndex(std::function<bool(const TYP element)> predicate) const
        {
            int index = 0;
            for (TYP t : *this)
            {
                if (predicate(t)) return index;
                index++;
            }
            return -1;
        }

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

        Stream<TYP> stream()
        {
            return Stream<TYP>(new IteratorSupplier<TYP>(
                new ArrayIterator<TYP>(entries, &onRemove)));
        }
    };

    template<class TYP>
    //! A linked list of pointers to objects that use reference counting
    class RCArray : public virtual ReferenceCounter
    {
    private:
        ArrayEntry<TYP*>* entries;
        ArrayEntry<TYP*>* last;
        int count;
        std::function<ArrayEntry<TYP*>*(ArrayEntry<TYP*>* removed)>
            onRemove;

    public:
        //! Creates a new linked list
        RCArray() noexcept
            : ReferenceCounter()
        {
            entries = new ArrayEntry<TYP*>();
            entries->var = 0;
            entries->set = 0;
            entries->next = 0;
            last = entries;
            count = 0;
            onRemove = [this](ArrayEntry<TYP*>* entry) {
                if (!entry) return (ArrayEntry<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;
                }
                ArrayEntry<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;
            };
        }

        //! Copies a linked list
        RCArray(const RCArray& arr)
            : RCArray()
        {
            int anz = arr.getEntryCount();
            for (int i = 0; i < anz; i++)
                add(arr.get(i));
        }

        //! Clears and deletes the linked list
        ~RCArray()
        {
            clear();
            delete entries;
        }

        //! Appends an element to the end of the list
        //! \param t The new element
        void add(TYP* t)
        {
            count++;
            if (!last->set)
            {
                last->var = t;
                last->set = 1;
                return;
            }
            last->next = new ArrayEntry<TYP*>();
            last = last->next;
            last->var = t;
            last->set = 1;
        }

        //! Inserts an element at a specific position in the list
        //! \param t The new element
        //! \param i The position where the element is inserted (afterwards the
        //! index of the new element)
        void add(TYP* t, int i)
        {
            if (i < 0 || i > count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            if (i == count)
            {
                add(t);
                return;
            }
            ArrayEntry<TYP*>* e = entries;
            for (int a = 0; a < i; ++a)
                e = e->next;
            ArrayEntry<TYP*>* ne = new ArrayEntry<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++;
        }

        //! Sets the value of the i-th entry
        //! \param t The new value
        //! \param i The index of the entry to be set
        void set(TYP* t, int i)
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<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;
        }

        //! Changes the position of the i-th element in the list
        //! \param i The index of the element to be moved
        //! \param p The target position of the element (afterwards the new
        //! index of the element)
        void setPosition(int i, int p)
        {
            if (i == p) return;
            if (i < 0 || p < 0 || i >= count || p >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            TYP* t = get(i);
            remove(i);
            add(t, p);
        }

        //! Deletes a specific element
        //! \param i The index of the element to be deleted
        void remove(int i)
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<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;
            }
            ArrayEntry<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--;
        }

        //! Swaps two elements in the list
        //! \param vi The index of the first element
        //! \param ni The index of the second element
        void swap(int vi, int ni)
        {
            if (vi < 0 || ni < 0) return;
            TYP* tmp = get(ni);
            set(get(vi), ni);
            set(tmp, vi);
        }

        //! Deletes all elements of the list
        void clear()
        {
            for (ArrayEntry<TYP*>* e = entries->next; e;)
            {
                if (e && e->var && e->set) e->var->release();
                auto tmp = e->next;
                delete e;
                e = tmp;
            }
            if (entries && entries->var && entries->set)
                entries->var->release();
            entries->set = 0;
            entries->next = 0;
            last = entries;
            count = 0;
        }

        //! Returns an iterator.
        //! Use ++ to iterate through the list
        ArrayIterator<TYP*> begin() const
        {
            return ArrayIterator<TYP*>(entries, &onRemove);
        }

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

        //! Returns how many elements are in the list
        int getEntryCount() const
        {
            return count;
        }

        int getLastIndex() const
        {
            return count - 1;
        }

        //! Returns the value of the i-th element with increased reference
        //! counter \param i The index of the sought element, (0) if the
        //! index does not exist
        TYP* get(int i) const
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<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;
        }

        //! Returns the value of the i-th element without increased reference
        //! counter \param i The index of the sought element, (0) if the
        //! index does not exist
        TYP* z(int i) const //! returns the index-th T
        {
            if (i < 0 || i >= count)
                throwOutOfRange(__FILE__, __LINE__, i, count);
            ArrayEntry<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;
        }

        //! Checks whether an element exists in the list
        //! \param i The index of the sought element
        //! \return (true) if the index exists. (false) otherwise
        bool has(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;
        }

        bool anyMatch(std::function<bool(const TYP* zElement)> predicate) const
        {
            for (TYP* t : *this)
            {
                if (predicate(t)) return 1;
            }
            return 0;
        }

        bool allMatch(std::function<bool(const TYP* zElement)> predicate) const
        {
            for (TYP* t : *this)
            {
                if (!predicate(t)) return 0;
            }
            return 1;
        }

        int findIndex(std::function<bool(const TYP* zElement)> predicate) const
        {
            int index = 0;
            for (TYP* t : *this)
            {
                if (predicate(t)) return index;
                index++;
            }
            return -1;
        }

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

        Stream<TYP*> stream()
        {
            return Stream<TYP*>(new IteratorSupplier<TYP*>(
                new ArrayIterator<TYP*>(entries, &onRemove)));
        }
    };
} // namespace Framework