core/data/LinkedList.h

#ifndef CORE_LINKED_LIST_H
#define CORE_LINKED_LIST_H

#include "utils/ArrayString.h"

namespace Core {
    template<typename T>
    struct LinkedList final {
        class Node {
            friend LinkedList;

            Node* next;
            Node* previous;

        public:
            T data;

            template<typename... Args>
            Node(Args&&... args)
                : next(nullptr), previous(nullptr),
                  data(Core::forward<Args>(args)...) {
            }
        };

        template<typename NT, typename R>
        struct IteratorBase final {
            NT* current;

        public:
            IteratorBase& operator++() {
                current = current->next;
                return *this;
            }

            bool operator!=(const IteratorBase& other) const {
                return current != other.current;
            }

            R& operator*() const {
                return current->data;
            }
        };

        using Iterator = IteratorBase<Node, T>;
        using ConstIterator = IteratorBase<const Node, const T>;

    private:
        Node* first;
        Node* last;
        int length;

    public:
        LinkedList() : first(nullptr), last(nullptr), length(0) {
        }

        LinkedList(const LinkedList& other) = delete;

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

        ~LinkedList() {
            clear();
        }

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

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

        // returns true on error
        check_return bool copyFrom(const LinkedList& other) {
            LinkedList copy;
            for(const T& t : other) {
                if(copy.add(t) == nullptr) {
                    return true;
                }
            }
            swap(copy);
            return false;
        }

        // returns a nullptr on error
        template<typename... Args>
        check_return Node* add(Args&&... args) {
            Node* n = new Node(Core::forward<Args>(args)...);
            if(n == nullptr) {
                return nullptr;
            }
            length++;
            if(first == nullptr) {
                first = n;
                last = n;
                return n;
            }
            last->next = n;
            n->previous = last;
            last = n;
            return n;
        }

        Iterator begin() {
            return {first};
        }

        Iterator end() {
            return {nullptr};
        }

        ConstIterator begin() const {
            return {first};
        }

        ConstIterator end() const {
            return {nullptr};
        }

        int getLength() const {
            return length;
        }

        void clear() {
            Node* n = first;
            while(n != nullptr) {
                Node* next = n->next;
                delete n;
                n = next;
            }
            length = 0;
            first = nullptr;
            last = nullptr;
        }

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

        void remove(Node*& n) {
            if(n == nullptr) {
                return;
            }
            if(n == first) {
                if(first->next != nullptr) {
                    first->next->previous = nullptr;
                }
                first = first->next;
            }
            if(n == last) {
                if(last->previous != nullptr) {
                    last->previous->next = nullptr;
                }
                last = last->previous;
            }
            if(n->previous != nullptr) {
                n->previous->next = n->next;
            }
            if(n->next != nullptr) {
                n->next->previous = n->previous;
            }
            length--;
            delete n;
            n = nullptr;
        }

        void removeFirst() {
            Node* n = first; // prevent first from becoming null
            remove(n);
        }

        void removeLast() {
            Node* n = last; // prevent last from becoming null
            remove(n);
        }

    private:
        void swap(LinkedList& other) {
            Core::swap(first, other.first);
            Core::swap(last, other.last);
            Core::swap(length, other.length);
        }
    };

}

#endif