core/data/List.h

#ifndef CORE_LIST_H
#define CORE_LIST_H

#include "utils/ArrayString.h"

namespace Core {
    template<typename T>
    class List final {
        int length;
        int capacity;
        T* data;

    public:
        List() : length(0), capacity(0), data(nullptr) {
        }

        List(const List& other) = delete;

        List(List&& other) : List() {
            swap(other);
        }

        ~List() {
            clear();
            delete[] reinterpret_cast<char*>(data);
        }

        List& operator=(const List& other) = delete;

        List& operator=(List&& other) {
            swap(other);
            return *this;
        }

        // returns true on error
        check_return bool copyFrom(const List& other) {
            List copy;
            copy.data = allocate(other.capacity);
            if(copy.data == nullptr) {
                return true;
            }
            copy.capacity = other.capacity;
            for(int i = 0; i < other.length; i++) {
                copy.unsafeAdd(other[i]);
            }
            swap(copy);
            return false;
        }

        T* begin() {
            return data;
        }

        T* end() {
            return data + length;
        }

        const T* begin() const {
            return data;
        }

        const T* end() const {
            return data + length;
        }

        // returns true on error
        check_return bool reserve(int n) {
            if(n <= capacity) {
                return false;
            }
            List copy;
            copy.data = allocate(n);
            if(copy.data == nullptr) {
                return true;
            }
            copy.capacity = n;
            for(int i = 0; i < length; i++) {
                copy.unsafeAdd(Core::move(data[i]));
            }
            swap(copy);
            return false;
        }

        // returns true on error
        check_return bool shrink() {
            if(length == capacity) {
                return false;
            }
            List copy;
            copy.data = allocate(length);
            if(copy.data == nullptr) {
                return true;
            }
            copy.capacity = length;
            for(int i = 0; i < length; i++) {
                copy.unsafeAdd(Core::move(data[i]));
            }
            swap(copy);
            return false;
        }

        // returns true on error
        check_return bool resize(int n, const T& t) {
            if(length < n) {
                if(reserve(n)) {
                    return true;
                }
                for(int i = length; i < n; i++) {
                    unsafeAdd(t);
                }
            } else if(length > n) {
                for(int i = n; i < length; i++) {
                    data[i].~T();
                }
                length = n;
            }
            return false;
        }

        // returns true on error
        check_return bool resize(int n) {
            if(length < n) {
                if(reserve(n)) {
                    return true;
                }
                for(int i = length; i < n; i++) {
                    unsafeAdd(T());
                }
            } else if(length > n) {
                for(int i = n; i < length; i++) {
                    data[i].~T();
                }
                length = n;
            }
            return false;
        }

        // returns a nullptr on error
        template<typename... Args>
        check_return T* add(Args&&... args) {
            if(ensureCapacity()) {
                return nullptr;
            }
            return unsafeAdd(Core::forward<Args>(args)...);
        }

        T& operator[](int index) {
            return data[index];
        }

        const T& operator[](int index) const {
            return data[index];
        }

        int getLength() const {
            return length;
        }

        int getCapacity() const {
            return capacity;
        }

        void clear() {
            for(int i = 0; i < length; i++) {
                data[i].~T();
            }
            length = 0;
        }

        // returns true on error
        check_return bool removeBySwap(int index) {
            if(index < 0 || index >= length) {
                return true;
            }
            length--;
            if(index != length) {
                data[index] = Core::move(data[length]);
            }
            data[length].~T();
            return false;
        }

        // returns true on error
        check_return bool remove(int index) {
            if(index < 0 || index >= length) {
                return true;
            }
            length--;
            for(int i = index; i < length; i++) {
                data[i] = Core::move(data[i + 1]);
            }
            data[length].~T();
            return false;
        }

        // returns true on error
        check_return bool removeLast() {
            return removeBySwap(length - 1);
        }

        // returns true on error
        template<int L>
        check_return bool toString(ArrayString<L>& s) const {
            if(s.append("[")) {
                return true;
            }
            for(int i = 0; i < length - 1; i++) {
                if(s.append(data[i]) || s.append(", ")) {
                    return true;
                }
            }
            if(length > 0 && s.append(data[length - 1])) {
                return true;
            }
            return s.append("]");
        }

    private:
        struct alignas(T) Aligned {
            char data[sizeof(T)];
        };

        static T* allocate(int n) {
            if(n <= 0) {
                return nullptr;
            }
            return reinterpret_cast<T*>(new Aligned[static_cast<size_t>(n)]);
        }

        void swap(List& other) {
            Core::swap(length, other.length);
            Core::swap(capacity, other.capacity);
            Core::swap(data, other.data);
        }

        // returns true on error
        check_return bool ensureCapacity() {
            if(length >= capacity) {
                return reserve(capacity + Core::Math::max(4, capacity / 4));
            }
            return false;
        }

        // does not check for capacity
        template<typename... Args>
        T* unsafeAdd(Args&&... args) {
            return new(data + length++) T(Core::forward<Args>(args)...);
        }
    };
}

#endif