core/modules/List.cppm

export module Core.List;

export import Core.Utility;
export import Core.New;

import Core.AlignedData;
import Core.Math;
import Core.Meta;
import Core.ToString;
import Core.Assert;

export namespace Core {
    template<Moveable T>
    class List final {
        size_t length;
        size_t capacity;
        T* data;

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

        List(const List& other) noexcept :
            length(0), capacity(other.capacity),
            data(allocate(other.capacity)) {
            for(const T& t : other) {
                unsafeAdd(t);
            }
        }

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

        ~List() noexcept {
            clear();
            deleteWithSourceN<AlignedType<T>>(
                reinterpret_cast<AlignedType<T>*>(data));
        }

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

        T* begin() noexcept {
            return data;
        }

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

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

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

        void reserve(size_t n) noexcept {
            if(n > capacity) {
                setSize(n);
            }
        }

        void shrink() noexcept {
            if(length != capacity) {
                setSize(length);
            }
        }

        void resize(size_t n, const T& t) noexcept {
            if(length < n) {
                reserve(n);
                for(size_t i = n - length; i != 0; i--) {
                    unsafeAdd(t);
                }
            } else if(length > n) {
                for(size_t i = n; i < length; i++) {
                    data[i].~T();
                }
                length = n;
            }
        }

        void resize(size_t n) noexcept {
            if(length < n) {
                reserve(n);
                for(size_t i = n - length; i != 0; i--) {
                    unsafeAdd(T());
                }
            } else if(length > n) {
                for(size_t i = n; i < length; i++) {
                    data[i].~T();
                }
                length = n;
            }
        }

        template<typename... Args>
        T& put(Args&&... args) noexcept {
            ensureCapacity();
            return *unsafeAdd(Core::forward<Args>(args)...);
        }

        template<typename... Args>
        List& add(Args&&... args) noexcept {
            put(Core::forward<Args>(args)...);
            return *this;
        }

        template<typename... Args>
        T& putAt(size_t t, Args&&... args) noexcept {
            if(t >= length) {
                return put(Core::forward<Args>(args)...);
            }
            // put must not reallocate, to keep the moved element alive
            ensureCapacity();
            put(Core::move(data[length - 1]));
            for(size_t i = length - 2; i > t; i--) {
                data[i] = Core::move(data[i - 1]);
            }
            data[t] = Core::move(T(Core::forward<Args>(args)...));
            return data[t];
        }

        template<typename... Args>
        List& addAt(size_t index, Args&&... args) noexcept {
            putAt(index, Core::forward<Args>(args)...);
            return *this;
        }

        T& operator[](size_t index) noexcept {
            assert(index < length);
            return data[index];
        }

        const T& operator[](size_t index) const noexcept {
            assert(index < length);
            return data[index];
        }

        T& getLast() noexcept {
            assert(length > 0);
            return data[length - 1];
        }

        const T& getLast() const noexcept {
            assert(length > 0);
            return data[length - 1];
        }

        size_t getLength() const noexcept {
            return length;
        }

        size_t getCapacity() const noexcept {
            return capacity;
        }

        void clear() noexcept {
            for(T& t : *this) {
                t.~T();
            }
            length = 0;
        }

        void removeBySwap(size_t index) noexcept {
            assert(index < length);
            length--;
            if(index != length) {
                data[index] = Core::move(data[length]);
            }
            data[length].~T();
        }

        void remove(size_t index) noexcept {
            assert(index < length);
            length--;
            T* currentT = begin() + index;
            T* endT = end();
            while(currentT != endT) {
                T* nextT = currentT + 1;
                *currentT = Core::move(*nextT);
                currentT = nextT;
            }
            endT->~T();
        }

        void removeLast() noexcept {
            removeBySwap(length - 1);
        }

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

    private:
        static T* allocate(size_t n) noexcept {
            if(n <= 0) {
                return nullptr;
            }
            return reinterpret_cast<T*>(newWithSourceN<AlignedType<T>>(n));
        }

        void ensureCapacity() noexcept {
            if(length >= capacity) {
                reserve(capacity + Core::max(4lu, capacity / 4));
            }
        }

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

        void setSize(size_t n) noexcept {
            List copy;
            copy.data = allocate(n);
            copy.capacity = n;
            for(size_t i = 0; i < length; i++) {
                copy.unsafeAdd(Core::move(data[i]));
            }
            swap(copy);
        }
    };
}