LinkedList.hpp

Go to the documentation of this file.

/* ✔ */
 
#pragma once
 
#include <AH/Debug/Debug.hpp>
#include <AH/Math/MinMaxFix.hpp>
#include <stdlib.h>
 
#include <AH/STL/iterator>
 
 
template <class Node>
class DoublyLinkedList {
  public:
    template <class INode>
    class node_iterator_base {
      public:
        node_iterator_base(INode *node) : node(node) {}
 
        bool operator!=(const node_iterator_base &rhs) const {
            return node != rhs.node;
        }
 
        bool operator==(const node_iterator_base &rhs) const {
            return !(*this != rhs);
        }
 
        INode &operator*() const {
            // TODO: check node != nullptr
            return *node;
        }
 
        INode *operator->() const {
            // TODO: check node != nullptr
            return node;
        }
 
      protected:
        INode *node;
    };
 
    template <class INode>
    class node_iterator : public node_iterator_base<INode> {
      public:
        node_iterator(INode *node) : node_iterator_base<INode>(node) {}
 
        using difference_type = long;
        using value_type = INode;
        using pointer = INode *;
        using reference = INode &;
        using iterator_category = std::bidirectional_iterator_tag;
 
        node_iterator &operator++() {
            // TODO: check node != nullptr
            this->node = this->node->next;
            return *this;
        }
 
        node_iterator &operator--() {
            // TODO: check node != nullptr
            this->node = this->node->previous;
            return *this;
        }
    };
 
    template <class INode>
    class reverse_node_iterator : public node_iterator_base<INode> {
      public:
        reverse_node_iterator(INode *node) : node_iterator_base<INode>(node) {}
 
        using difference_type = long;
        using value_type = INode;
        using pointer = INode *;
        using reference = INode &;
        using iterator_category = std::bidirectional_iterator_tag;
 
        reverse_node_iterator &operator++() {
            // TODO: check node != nullptr
            this->node = this->node->previous;
            return *this;
        }
 
        reverse_node_iterator &operator--() {
            // TODO: check node != nullptr
            this->node = this->node->next;
            return *this;
        }
    };
 
    using iterator = node_iterator<Node>;
    using const_iterator = node_iterator<const Node>;
    using reverse_iterator = reverse_node_iterator<Node>;
    using const_reverse_iterator = reverse_node_iterator<const Node>;
 
    void append(Node *node) {
        if (first == nullptr)
            first = node;
        node->previous = last;
        if (node->previous != nullptr)
            node->previous->next = node;
        last = node;
        node->next = nullptr;
    }
 
    void append(Node &node) { append(&node); }
 
    void insertBefore(Node *toBeInserted, Node *before) {
        if (before == first)
            first = toBeInserted;
        else
            before->previous->next = toBeInserted;
        toBeInserted->previous = before->previous;
        toBeInserted->next = before;
        before->previous = toBeInserted;
    }
 
    void insertBefore(Node &toBeInserted, Node &before) {
        insertBefore(&toBeInserted, &before);
    }
 
    template <class Compare>
    void insertSorted(Node *node, Compare cmp) {
        iterator it = this->begin();
        iterator end = this->end();
        while (it != end) {
            if (cmp(*node, *it)) {
                insertBefore(*node, *it);
                return;
            }
            ++it;
        }
        append(node);
    }
 
    void insertSorted(Node *node) {
        insertSorted(node, [](Node &lhs, Node &rhs) { return lhs < rhs; });
    }
 
    void remove(Node *node) {
        if (node->previous != nullptr)
            node->previous->next = node->next;
        if (node == last)
            last = node->previous;
        if (node->next != nullptr)
            node->next->previous = node->previous;
        if (node == first)
            first = node->next;
        node->previous = nullptr;
        node->next = nullptr;
    }
 
    void remove(Node &node) { remove(&node); }
 
    void moveDown(Node *node) {
        Node *nodeB = node->previous;
        if (nodeB == nullptr) // Can't move first node further down
            return;
        Node *nodeA = nodeB->previous;
        Node *nodeD = node->next;
 
        if (nodeA != nullptr)
            nodeA->next = node;
        else
            first = node;
        nodeB->next = nodeD;
        nodeB->previous = node;
        node->next = nodeB;
        node->previous = nodeA;
        if (nodeD != nullptr)
            nodeD->previous = nodeB;
        else
            last = nodeB;
    }
 
    void moveDown(Node &node) { moveDown(&node); }
 
    bool couldContain(const Node *node) const {
        return node && (node == first || node->next != nullptr ||
                        node->previous != nullptr);
    }
 
    bool couldContain(const Node &node) const { return couldContain(&node); }
 
    iterator begin() { return {first}; }
    iterator end() { return {nullptr}; }
 
    const_iterator begin() const { return {first}; }
    const_iterator end() const { return {nullptr}; }
 
    reverse_iterator rbegin() { return {last}; }
    reverse_iterator rend() { return {nullptr}; }
 
    const_reverse_iterator rbegin() const { return {last}; }
    const_reverse_iterator rend() const { return {nullptr}; }
 
    Node *getFirst() const { return first; }
    Node *getLast() const { return last; }
 
  private:
    Node *first = nullptr;
    Node *last = nullptr;
};
 
template <class Node>
class DoublyLinkable {
  protected:
    friend class DoublyLinkedList<Node>;
    Node *next = nullptr;
    Node *previous = nullptr;
    virtual ~DoublyLinkable() = default;
 
    DoublyLinkable() = default;
    DoublyLinkable(const DoublyLinkable &) {
        // Don't copy the pointers
    }
    DoublyLinkable &operator=(const DoublyLinkable &) {
        // Don't copy the pointers
        return *this;
    }
    DoublyLinkable(DoublyLinkable &&) {
        // Don't swap the pointers
    }
    DoublyLinkable &operator=(DoublyLinkable &&) {
        // Don't swap the pointers
        return *this;
    }
};