Line data    Source code

       1             : /* ✔ */
       2             : 
       3             : #pragma once
       4             : 
       5             : #include <AH/Debug/Debug.hpp>
       6             : #include <AH/Math/MinMaxFix.hpp>
       7             : #include <stdlib.h>
       8             : 
       9             : #include <AH/STL/iterator>
      10             : 
      11             : /// @addtogroup AH_Containers
      12             : /// @{
      13             : 
      14             : /**
      15             :  * @brief   A class for doubly linked lists.
      16             :  * 
      17             :  * @tparam  Node
      18             :  *          The type of the nodes of the list.
      19             :  */
      20             : template <class Node>
      21             : class DoublyLinkedList {
      22             :   public:
      23             :     /// Base class for doubly linked list iterators
      24             :     template <class INode>
      25             :     class node_iterator_base {
      26             :       public:
      27         272 :         node_iterator_base(INode *node) : node(node) {}
      28             : 
      29         337 :         bool operator!=(const node_iterator_base &rhs) const {
      30         337 :             return node != rhs.node;
      31             :         }
      32             : 
      33             :         bool operator==(const node_iterator_base &rhs) const {
      34             :             return !(*this != rhs);
      35             :         }
      36             : 
      37         314 :         INode &operator*() const {
      38             :             // TODO: check node != nullptr
      39         314 :             return *node;
      40             :         }
      41             : 
      42             :         INode *operator->() const {
      43             :             // TODO: check node != nullptr
      44             :             return node;
      45             :         }
      46             : 
      47             :       protected:
      48             :         INode *node;
      49             :     };
      50             : 
      51             :     /// Forward bidirectional doubly linked list iterator
      52             :     template <class INode>
      53             :     class node_iterator : public node_iterator_base<INode> {
      54             :       public:
      55         268 :         node_iterator(INode *node) : node_iterator_base<INode>(node) {}
      56             : 
      57             :         using difference_type = long;
      58             :         using value_type = INode;
      59             :         using pointer = INode *;
      60             :         using reference = INode &;
      61             :         using iterator_category = std::bidirectional_iterator_tag;
      62             : 
      63             :         /// Prefix increment operator
      64         191 :         node_iterator &operator++() {
      65             :             // TODO: check node != nullptr
      66         191 :             this->node = this->node->next;
      67         191 :             return *this;
      68             :         }
      69             : 
      70             :         /// Prefix decrement operator
      71             :         node_iterator &operator--() {
      72             :             // TODO: check node != nullptr
      73             :             this->node = this->node->previous;
      74             :             return *this;
      75             :         }
      76             :     };
      77             : 
      78             :     /// Reverse bidirectional doubly linked list iterator
      79             :     template <class INode>
      80             :     class reverse_node_iterator : public node_iterator_base<INode> {
      81             :       public:
      82           4 :         reverse_node_iterator(INode *node) : node_iterator_base<INode>(node) {}
      83             : 
      84             :         using difference_type = long;
      85             :         using value_type = INode;
      86             :         using pointer = INode *;
      87             :         using reference = INode &;
      88             :         using iterator_category = std::bidirectional_iterator_tag;
      89             : 
      90             :         /// Prefix increment operator
      91          10 :         reverse_node_iterator &operator++() {
      92             :             // TODO: check node != nullptr
      93          10 :             this->node = this->node->previous;
      94          10 :             return *this;
      95             :         }
      96             : 
      97             :         /// Prefix decrement operator
      98             :         reverse_node_iterator &operator--() {
      99             :             // TODO: check node != nullptr
     100             :             this->node = this->node->next;
     101             :             return *this;
     102             :         }
     103             :     };
     104             : 
     105             :     using iterator = node_iterator<Node>;
     106             :     using const_iterator = node_iterator<const Node>;
     107             :     using reverse_iterator = reverse_node_iterator<Node>;
     108             :     using const_reverse_iterator = reverse_node_iterator<const Node>;
     109             : 
     110             :     /**
     111             :      * @brief   Append a node to a linked list.
     112             :      * 
     113             :      * @param   node
     114             :      *          A pointer to the node to be appended.
     115             :      */
     116         200 :     void append(Node *node) {
     117         200 :         if (first == nullptr)
     118          65 :             first = node;
     119         200 :         node->previous = last;
     120         200 :         if (node->previous != nullptr)
     121         135 :             node->previous->next = node;
     122         200 :         last = node;
     123         200 :         node->next = nullptr;
     124         200 :     }
     125             : 
     126             :     /**
     127             :      * @brief   Append a node to a linked list.
     128             :      * 
     129             :      * @param   node
     130             :      *          A reference to the node to be appended.
     131             :      */
     132         140 :     void append(Node &node) { append(&node); }
     133             : 
     134             :     /**
     135             :      * @brief   Insert a node before another node.
     136             :      * 
     137             :      * @param   toBeInserted
     138             :      *          The new node to be inserted.
     139             :      * @param   before
     140             :      *          The node to insert the new node before. It must be in the list
     141             :      *          already.
     142             :      */
     143          27 :     void insertBefore(Node *toBeInserted, Node *before) {
     144          27 :         if (before == first)
     145           7 :             first = toBeInserted;
     146             :         else
     147          20 :             before->previous->next = toBeInserted;
     148          27 :         toBeInserted->previous = before->previous;
     149          27 :         toBeInserted->next = before;
     150          27 :         before->previous = toBeInserted;
     151          27 :     }
     152             : 
     153             :     /// @see    insertBefore(Node *, Node *)
     154          27 :     void insertBefore(Node &toBeInserted, Node &before) {
     155          27 :         insertBefore(&toBeInserted, &before);
     156          27 :     }
     157             : 
     158             :     /**
     159             :      * @brief   Insert a new node at the correct location into a sorted list.
     160             :      * 
     161             :      * @param   node 
     162             :      *          The new node to be inserted.
     163             :      * @param   cmp
     164             :      *          The function to order the nodes.
     165             :      * @tparam  Compare
     166             :      *          A functor that compares two Nodes and returns a boolean.
     167             :      */
     168             :     template <class Compare>
     169          35 :     void insertSorted(Node *node, Compare cmp) {
     170          35 :         iterator it = this->begin();
     171          35 :         iterator end = this->end();
     172         139 :         while (it != end) {
     173         129 :             if (cmp(*node, *it)) {
     174          25 :                 insertBefore(*node, *it);
     175          25 :                 return;
     176             :             }
     177         104 :             ++it;
     178             :         }
     179          10 :         append(node);
     180             :     }
     181             : 
     182             :     /**
     183             :      * @brief   Insert a new node at the correct location into a sorted list, 
     184             :      *          using `operator<`.
     185             :      * 
     186             :      * @param   node 
     187             :      *          The new node to be inserted.
     188             :      */
     189          22 :     void insertSorted(Node *node) {
     190          96 :         insertSorted(node, [](Node &lhs, Node &rhs) { return lhs < rhs; });
     191          22 :     }
     192             : 
     193             :     /**
     194             :      * @brief   Remove a node from the linked list.
     195             :      * 
     196             :      * @param   node
     197             :      *          A pointer to the node to be removed.
     198             :      */
     199         118 :     void remove(Node *node) {
     200         118 :         if (node->previous != nullptr)
     201          43 :             node->previous->next = node->next;
     202         118 :         if (node == last)
     203          84 :             last = node->previous;
     204         118 :         if (node->next != nullptr)
     205          34 :             node->next->previous = node->previous;
     206         118 :         if (node == first)
     207          75 :             first = node->next;
     208         118 :         node->previous = nullptr;
     209         118 :         node->next = nullptr;
     210         118 :     }
     211             : 
     212             :     /**
     213             :      * @brief   Remove a node from the linked list.
     214             :      * 
     215             :      * @param   node
     216             :      *          A reference to the node to be removed.
     217             :      */
     218         112 :     void remove(Node &node) { remove(&node); }
     219             : 
     220             :     /**
     221             :      * @brief   Move down the given node in the linked list.
     222             :      * 
     223             :      * For example: moving down node `C`:
     224             :      * ```
     225             :      * Before:  ... → A → B → C → D → ...
     226             :      * After:   ... → A → C → B → D → ...
     227             :      * ```
     228             :      * @param   node
     229             :      *          A pointer to the node to be moved down.
     230             :      */
     231           5 :     void moveDown(Node *node) {
     232           5 :         Node *nodeB = node->previous;
     233           5 :         if (nodeB == nullptr) // Can't move first node further down
     234           2 :             return;
     235           3 :         Node *nodeA = nodeB->previous;
     236           3 :         Node *nodeD = node->next;
     237             : 
     238           3 :         if (nodeA != nullptr)
     239           2 :             nodeA->next = node;
     240             :         else
     241           1 :             first = node;
     242           3 :         nodeB->next = nodeD;
     243           3 :         nodeB->previous = node;
     244           3 :         node->next = nodeB;
     245           3 :         node->previous = nodeA;
     246           3 :         if (nodeD != nullptr)
     247           2 :             nodeD->previous = nodeB;
     248             :         else
     249           1 :             last = nodeB;
     250             :     }
     251             : 
     252             :     /**
     253             :      * @brief   Move down the given node in the linked list.
     254             :      * 
     255             :      * For example: moving down node `C`:
     256             :      * ```
     257             :      * Before:  ... → A → B → C → D → ...
     258             :      * After:   ... → A → C → B → D → ...
     259             :      * ```
     260             :      * @param   node
     261             :      *          A reference to the node to be moved down.
     262             :      */
     263             :     void moveDown(Node &node) { moveDown(&node); }
     264             : 
     265             :     /** 
     266             :      * @brief   Check if the linked list could contain the given node.
     267             :      * 
     268             :      * @retval  true
     269             :      *          The given node is part of some linked list or it is the first
     270             :      *          node of the given linked list.  
     271             :      *          It could be that the node is part of a different linked list
     272             :      *          if it was ever added to a different list.
     273             :      *          However, **if this function returns true and the node was never
     274             :      *          added to another linked list, it means that this linked list 
     275             :      *          contains the given node**.
     276             :      * @retval  false
     277             :      *          The given node is not part of any linked list, or it is the 
     278             :      *          only element of a different linked list.
     279             :      */
     280         209 :     bool couldContain(const Node *node) const {
     281         310 :         return node && (node == first || node->next != nullptr ||
     282         310 :                         node->previous != nullptr);
     283             :     }
     284             : 
     285             :     /// @copydoc DoublyLinkedList::couldContain(const Node *) const
     286         194 :     bool couldContain(const Node &node) const { return couldContain(&node); }
     287             : 
     288         133 :     iterator begin() { return {first}; }
     289         133 :     iterator end() { return {nullptr}; }
     290             : 
     291           1 :     const_iterator begin() const { return {first}; }
     292           1 :     const_iterator end() const { return {nullptr}; }
     293             : 
     294           1 :     reverse_iterator rbegin() { return {last}; }
     295           1 :     reverse_iterator rend() { return {nullptr}; }
     296             : 
     297           1 :     const_reverse_iterator rbegin() const { return {last}; }
     298           1 :     const_reverse_iterator rend() const { return {nullptr}; }
     299             : 
     300             :     /// Get a pointer to the first node.
     301          14 :     Node *getFirst() const { return first; }
     302             :     /// Get a pointer to the last node.
     303          12 :     Node *getLast() const { return last; }
     304             : 
     305             :   private:
     306             :     Node *first = nullptr;
     307             :     Node *last = nullptr;
     308             : };
     309             : 
     310             : /**
     311             :  * @brief   A class that can be inherited from to allow inserting into a 
     312             :  *          DoublyLinkedList.
     313             :  * @tparam  Node
     314             :  *          The type of the nodes of the list.
     315             :  */
     316             : template <class Node>
     317             : class DoublyLinkable {
     318             :   protected:
     319             :     friend class DoublyLinkedList<Node>;
     320             :     Node *next = nullptr;
     321             :     Node *previous = nullptr;
     322         208 :     virtual ~DoublyLinkable() = default;
     323             : 
     324         208 :     DoublyLinkable() = default;
     325             :     DoublyLinkable(const DoublyLinkable &) {
     326             :         // Don't copy the pointers
     327             :     }
     328             :     DoublyLinkable &operator=(const DoublyLinkable &) {
     329             :         // Don't copy the pointers
     330             :         return *this;
     331             :     }
     332             :     DoublyLinkable(DoublyLinkable &&) {
     333             :         // Don't swap the pointers
     334             :     }
     335             :     DoublyLinkable &operator=(DoublyLinkable &&) {
     336             :         // Don't swap the pointers
     337             :         return *this;
     338             :     }
     339             : };
     340             : 
     341             : /// @}