This is an old version of the documentation. View the latest version here.
Control Surface  1.0.0
MIDI Control Surface library for Arduino
LinkedList.hpp
Go to the documentation of this file.
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 
15 
22 template <class Node>
24  public:
26  template <class INode>
28  public:
30 
31  bool operator!=(const node_iterator_base &rhs) const {
32  return node != rhs.node;
33  }
34 
35  INode &operator*() const {
36  // TODO: check node != nullptr
37  return *node;
38  }
39 
40  protected:
41  INode *node;
42  };
43 
45  template <class INode>
46  class node_iterator : public node_iterator_base<INode> {
47  public:
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 
60  // TODO: check node != nullptr
61  this->node = this->node->next;
62  return *this;
63  }
64 
67  // TODO: check node != nullptr
68  this->node = this->node->previous;
69  return *this;
70  }
71  };
72 
74  template <class INode>
75  class reverse_node_iterator : public node_iterator_base<INode> {
76  public:
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 
89  // TODO: check node != nullptr
90  this->node = this->node->previous;
91  return *this;
92  }
93 
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 
113  void append(Node *node) {
114  if (first == nullptr)
115  first = node;
116  node->previous = last;
117  if (node->previous != nullptr)
118  node->previous->next = node;
119  last = node;
120  node->next = nullptr;
121  }
122 
129  void append(Node &node) { append(&node); }
130 
140  void insertBefore(Node *toBeInserted, Node *before) {
141  if (before == first)
142  first = toBeInserted;
143  else
144  before->previous->next = toBeInserted;
145  toBeInserted->previous = before->previous;
146  toBeInserted->next = before;
147  before->previous = toBeInserted;
148  }
149 
151  void insertBefore(Node &toBeInserted, Node &before) {
152  insertBefore(&toBeInserted, &before);
153  }
154 
165  template <class Compare>
166  void insertSorted(Node *node, Compare cmp) {
167  iterator it = this->begin();
168  iterator end = this->end();
169  while (it != end) {
170  if (cmp(*node, *it)) {
171  insertBefore(*node, *it);
172  return;
173  }
174  ++it;
175  }
176  append(node);
177  }
178 
186  void insertSorted(Node *node) {
187  insertSorted(node, [](Node &lhs, Node &rhs) { return lhs < rhs; });
188  }
189 
196  void remove(Node *node) {
197  if (node->previous != nullptr)
198  node->previous->next = node->next;
199  if (node == last)
200  last = node->previous;
201  if (node->next != nullptr)
202  node->next->previous = node->previous;
203  if (node == first)
204  first = node->next;
205  node->previous = nullptr;
206  node->next = nullptr;
207  }
208 
215  void remove(Node &node) { remove(&node); }
216 
228  void moveDown(Node *node) {
229  Node *nodeB = node->previous;
230  if (nodeB == nullptr) // Can't move first node further down
231  return;
232  Node *nodeA = nodeB->previous;
233  Node *nodeD = node->next;
234 
235  if (nodeA != nullptr)
236  nodeA->next = node;
237  else
238  first = node;
239  nodeB->next = nodeD;
240  nodeB->previous = node;
241  node->next = nodeB;
242  node->previous = nodeA;
243  if (nodeD != nullptr)
244  nodeD->previous = nodeB;
245  else
246  last = nodeB;
247  }
248 
264  bool couldContain(Node *node) {
265  return node && (node == first || node->next != nullptr ||
266  node->previous != nullptr);
267  }
268 
269  iterator begin() { return {first}; }
270  iterator end() { return {nullptr}; }
271 
272  const_iterator begin() const { return {first}; }
273  const_iterator end() const { return {nullptr}; }
274 
275  reverse_iterator rbegin() { return {last}; }
276  reverse_iterator rend() { return {nullptr}; }
277 
278  const_reverse_iterator rbegin() const { return {last}; }
279  const_reverse_iterator rend() const { return {nullptr}; }
280 
282  Node *getFirst() const { return first; }
284  Node *getLast() const { return last; }
285 
286  private:
287  Node *first = nullptr;
288  Node *last = nullptr;
289 };
290 
297 template <class Node>
299  protected:
300  friend class DoublyLinkedList<Node>;
301  Node *next = nullptr;
302  Node *previous = nullptr;
303  virtual ~DoublyLinkable() = default;
304 };
305 
306 /// @}
DoublyLinkedList::last
Node * last
Definition: LinkedList.hpp:288
DoublyLinkedList::reverse_node_iterator::difference_type
void difference_type
Definition: LinkedList.hpp:80
DoublyLinkedList::reverse_node_iterator
Reverse bidirectional doubly linked list iterator.
Definition: LinkedList.hpp:75
DoublyLinkedList::node_iterator::pointer
INode * pointer
Definition: LinkedList.hpp:53
DoublyLinkedList::rend
const_reverse_iterator rend() const
Definition: LinkedList.hpp:279
DoublyLinkable::~DoublyLinkable
virtual ~DoublyLinkable()=default
DoublyLinkedList::rbegin
const_reverse_iterator rbegin() const
Definition: LinkedList.hpp:278
DoublyLinkedList::reverse_node_iterator::operator--
reverse_node_iterator & operator--()
Prefix decrement operator.
Definition: LinkedList.hpp:95
DoublyLinkedList::insertSorted
void insertSorted(Node *node, Compare cmp)
Insert a new node at the correct location into a sorted list.
Definition: LinkedList.hpp:166
DoublyLinkedList< DisplayInterface >::const_reverse_iterator
reverse_node_iterator< const DisplayInterface > const_reverse_iterator
Definition: LinkedList.hpp:105
DoublyLinkedList::append
void append(Node *node)
Append a node to a linked list.
Definition: LinkedList.hpp:113
DoublyLinkable::next
Node * next
Definition: LinkedList.hpp:301
DoublyLinkedList::node_iterator_base::operator!=
bool operator!=(const node_iterator_base &rhs) const
Definition: LinkedList.hpp:31
DoublyLinkedList::node_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: LinkedList.hpp:55
DoublyLinkedList::first
Node * first
Definition: LinkedList.hpp:287
DoublyLinkedList< DisplayInterface >::const_iterator
node_iterator< const DisplayInterface > const_iterator
Definition: LinkedList.hpp:103
DoublyLinkedList::end
const_iterator end() const
Definition: LinkedList.hpp:273
DoublyLinkedList::insertBefore
void insertBefore(Node *toBeInserted, Node *before)
Insert a node before another node.
Definition: LinkedList.hpp:140
DoublyLinkedList::node_iterator::operator--
node_iterator & operator--()
Prefix decrement operator.
Definition: LinkedList.hpp:66
DoublyLinkedList::node_iterator_base::operator*
INode & operator*() const
Definition: LinkedList.hpp:35
DoublyLinkable::previous
Node * previous
Definition: LinkedList.hpp:302
DoublyLinkedList::remove
void remove(Node *node)
Remove a node from the linked list.
Definition: LinkedList.hpp:196
DoublyLinkedList< DisplayInterface >::iterator
node_iterator< DisplayInterface > iterator
Definition: LinkedList.hpp:102
DoublyLinkedList::append
void append(Node &node)
Append a node to a linked list.
Definition: LinkedList.hpp:129
DoublyLinkedList::node_iterator::node_iterator
node_iterator(INode *node)
Definition: LinkedList.hpp:48
DoublyLinkedList< DisplayInterface >::reverse_iterator
reverse_node_iterator< DisplayInterface > reverse_iterator
Definition: LinkedList.hpp:104
DoublyLinkedList::begin
iterator begin()
Definition: LinkedList.hpp:269
DoublyLinkedList::node_iterator_base::node
INode * node
Definition: LinkedList.hpp:41
DoublyLinkedList::couldContain
bool couldContain(Node *node)
Check if the linked list could contain the given node.
Definition: LinkedList.hpp:264
DoublyLinkedList::node_iterator_base
Base class for doubly linked list iterators.
Definition: LinkedList.hpp:27
DoublyLinkedList::node_iterator::operator++
node_iterator & operator++()
Prefix increment operator.
Definition: LinkedList.hpp:59
DoublyLinkedList::node_iterator
Forward bidirectional doubly linked list iterator.
Definition: LinkedList.hpp:46
DoublyLinkedList::node_iterator::value_type
INode value_type
Definition: LinkedList.hpp:52
DoublyLinkedList::insertBefore
void insertBefore(Node &toBeInserted, Node &before)
Definition: LinkedList.hpp:151
DoublyLinkedList::rbegin
reverse_iterator rbegin()
Definition: LinkedList.hpp:275
DoublyLinkedList::getLast
Node * getLast() const
Get a pointer to the last node.
Definition: LinkedList.hpp:284
DoublyLinkedList::reverse_node_iterator::reverse_node_iterator
reverse_node_iterator(INode *node)
Definition: LinkedList.hpp:77
DoublyLinkedList::reverse_node_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: LinkedList.hpp:84
DoublyLinkedList::node_iterator::difference_type
void difference_type
Definition: LinkedList.hpp:51
DoublyLinkedList::insertSorted
void insertSorted(Node *node)
Insert a new node at the correct location into a sorted list, using operator<.
Definition: LinkedList.hpp:186
DoublyLinkedList::begin
const_iterator begin() const
Definition: LinkedList.hpp:272
DoublyLinkedList
A class for doubly linked lists.
Definition: LinkedList.hpp:23
DoublyLinkedList::rend
reverse_iterator rend()
Definition: LinkedList.hpp:276
DoublyLinkable
A class that can be inherited from to allow inserting into a DoublyLinkedList.
Definition: LinkedList.hpp:298
DoublyLinkedList::node_iterator::reference
INode & reference
Definition: LinkedList.hpp:54
DoublyLinkedList::reverse_node_iterator::operator++
reverse_node_iterator & operator++()
Prefix increment operator.
Definition: LinkedList.hpp:88
Debug.hpp
DoublyLinkedList::end
iterator end()
Definition: LinkedList.hpp:270
DoublyLinkedList::remove
void remove(Node &node)
Remove a node from the linked list.
Definition: LinkedList.hpp:215
DoublyLinkedList::moveDown
void moveDown(Node *node)
Move down the given node in the linked list.
Definition: LinkedList.hpp:228
MinMaxFix.hpp
DoublyLinkedList::node_iterator_base::node_iterator_base
node_iterator_base(INode *node)
Definition: LinkedList.hpp:29
DoublyLinkedList::reverse_node_iterator::pointer
INode * pointer
Definition: LinkedList.hpp:82
DoublyLinkedList::reverse_node_iterator::value_type
INode value_type
Definition: LinkedList.hpp:81
DoublyLinkedList::getFirst
Node * getFirst() const
Get a pointer to the first node.
Definition: LinkedList.hpp:282
DoublyLinkedList::reverse_node_iterator::reference
INode & reference
Definition: LinkedList.hpp:83