Line data    Source code

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