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