Kylin/DataStructure/DoublyLinkedList.h

#ifndef DUALLINKEDLIST_H
#define DUALLINKEDLIST_H

#include "Exception.h"
#include "List.h"
#include <initializer_list>

namespace Kylin {
template <typename T>
class DoublyLinkedList : public List<T> {
protected:
    struct Node : public Object {
        Node *prev = nullptr;
        Node *next = nullptr;
        T value;
    };
    struct : public Object {
        Node *prev = nullptr;
        Node *next = nullptr;
        uint8_t reserved[sizeof(T)];
    } mutable m_header;

public:
    struct Iterator {
        Iterator(Node *pos = nullptr) : m_pos(pos) {}
        bool operator!=(const Iterator &other) { return m_pos != other.m_pos; }
        T *operator->() const { return &m_pos->value; }
        T &operator*() const { return m_pos->value; }
        Iterator &operator++() {
            m_pos = m_pos->next;
            return *this;
        }
        Iterator operator++(int) {
            auto old = *this;
            m_pos = m_pos->next;
            return old;
        }

        Node *m_pos;
    };

    static constexpr size_t npos = static_cast<size_t>(-1);

    DoublyLinkedList() { m_last = reinterpret_cast<Node *>(&m_header); }

    DoublyLinkedList(std::initializer_list<T> init) {
        m_last = reinterpret_cast<Node *>(&m_header);
        for (auto &value : init) append(value);
    }

    DoublyLinkedList(const DoublyLinkedList &other) {
        auto sourceNode = other.m_header.next;
        auto targetNode = reinterpret_cast<Node *>(&m_header);
        while (sourceNode != nullptr) {
            auto newNode = create();
            if (newNode == nullptr) THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create node ...");
            newNode->value = sourceNode->value;
            targetNode->next = newNode;
            newNode->prev = targetNode;
            targetNode = newNode;
            sourceNode = sourceNode->next;
            m_size++;
            targetNode->next = nullptr;
            m_last = targetNode;
        }
    }

    DoublyLinkedList(DoublyLinkedList &&other) {
        m_size = other.m_size;
        m_header = other.m_header;
        m_last = other.m_last;

        other.m_size = 0;
        other.m_header.next = nullptr;
        other.m_last = reinterpret_cast<Node *>(&other.m_header);
    }

    void swap(DoublyLinkedList &other) {
        if (this == &other) return;
        auto tempSize = other.m_size;
        auto tempHeader = other.m_header;
        auto tempLast = other.m_last;

        other.m_header = m_header;
        other.m_size = m_size;
        other.m_last = m_last;

        m_header = tempHeader;
        m_size = tempSize;
        m_last = tempLast;
    }

    /**
     * @brief O(n)
     */
    void append(const T &value) override {
        auto node = create();
        if (node == nullptr) THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create node ...");
        node->value = value;

        m_last->next = node;

        node->prev = m_last;
        m_last = node;
        m_size++;
    }

    /**
     * @brief O(n)
     */
    virtual void insert(size_t index, const T &value) {
        if (index >= m_size) return append(value);
        auto node = create();
        if (node == nullptr) THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create node...");
        node->value = value;
        auto prev = position(index);
        auto next = prev->next;
        prev->next = node;
        node->next = next;

        if (prev != reinterpret_cast<Node *>(&m_header)) node->prev = prev;
        if (next != nullptr) next->prev = node;
        m_size++;
    }

    T &last() override {
        if (m_size <= 0) THROW_EXCEPTION(InvalidOperationException, "There is no element in the container.");
        return m_last->value;
    }

    /**
     * @brief O(n)
     */
    void removeAt(size_t index) override {
        if (index >= m_size) THROW_EXCEPTION(IndexOutOfBoundsException, "The index is out if range.");
        auto prev = position(index);
        auto toDel = prev->next;
        auto next = toDel->next;
        prev->next = next;
        if (next != nullptr) next->prev = prev;
        if (index == m_size - 1) {
            m_last = prev;
        }
        m_size--;
        destroy(toDel);
    }

    /**
     * @brief O(n)
     */
    virtual void clear() {
        while (m_header.next != nullptr) {
            auto toDel = m_header.next;
            m_header.next = toDel->next;
            if (m_header.next != nullptr) m_header.next->prev = nullptr;
            m_size--;
            destroy(toDel);
        }
    }

    size_t size() const noexcept override { return m_size; }

    size_t indexOf(const T &value, size_t from = 0) const override {
        auto node = position(from)->next;
        for (size_t i = from; i < m_size; i++) {
            if (node->value == value) return i;
            node = node->next;
        }
        return npos;
    }

    Iterator begin() { return Iterator(m_header.next); }

    Iterator begin() const { return Iterator(m_header.next); }

    virtual Iterator end() { return Iterator(); }

    virtual Iterator end() const { return Iterator(); }

    T &operator[](size_t index) override {
        if (index >= size()) THROW_EXCEPTION(IndexOutOfBoundsException, "The index is out of range.");
        return position(index)->next->value;
    }

protected:
    Node *create() { return new Node(); }

    void destroy(Node *p) { delete p; }

    /**
     * @brief position to index-1 ,O(n)
     */
    virtual Node *position(size_t index) const {
        auto ret = reinterpret_cast<Node *>(&m_header);
        for (size_t i = 0; i < index; i++) {
            ret = ret->next;
        }
        return ret;
    }

protected:
    size_t m_size = 0;
    Node *m_last = nullptr;
};
} // namespace Kylin

#endif // DUALLINKEDLIST_H