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