LCOV - code coverage report
Current view: top level - src/Helpers - LinkedList.hpp (source / functions) Hit Total Coverage
Test: 19d2efc7037c2e176feca44750a12594c76f466f Lines: 96 96 100.0 %
Date: 2019-11-24 14:50:27 Functions: 150 213 70.4 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14-5-g4ff2ed6