Control Surface master
MIDI Control Surface library for Arduino
LinkedList.hpp
Go to the documentation of this file.
1/* ✔ */
2
3#pragma once
4
6
7AH_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
17
24template <class Node>
26 public:
28 template <class INode>
30 public:
32
33 bool operator!=(const node_iterator_base &rhs) const {
34 return node != rhs.node;
35 }
36
37 bool operator==(const node_iterator_base &rhs) const {
38 return !(*this != rhs);
39 }
40
41 INode &operator*() const {
42 // TODO: check node != nullptr
43 return *node;
44 }
45
46 INode *operator->() const {
47 // TODO: check node != nullptr
48 return node;
49 }
50
51 protected:
52 INode *node;
53 };
54
56 template <class INode>
57 class node_iterator : public node_iterator_base<INode> {
58 public:
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
69 // TODO: check node != nullptr
70 this->node = this->node->next;
71 return *this;
72 }
73
76 // TODO: check node != nullptr
77 this->node = this->node->previous;
78 return *this;
79 }
80 };
81
83 template <class INode>
85 public:
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
96 // TODO: check node != nullptr
97 this->node = this->node->previous;
98 return *this;
99 }
100
103 // TODO: check node != nullptr
104 this->node = this->node->next;
105 return *this;
106 }
107 };
108
113
120 void append(Node *node) {
121 if (first == nullptr)
122 first = node;
123 node->previous = last;
124 if (node->previous != nullptr)
125 node->previous->next = node;
126 last = node;
127 node->next = nullptr;
128 }
129
136 void append(Node &node) { append(&node); }
137
147 void insertBefore(Node *toBeInserted, Node *before) {
148 if (before == first)
149 first = toBeInserted;
150 else
151 before->previous->next = toBeInserted;
152 toBeInserted->previous = before->previous;
153 toBeInserted->next = before;
154 before->previous = toBeInserted;
155 }
156
158 void insertBefore(Node &toBeInserted, Node &before) {
159 insertBefore(&toBeInserted, &before);
160 }
161
172 template <class Compare>
173 void insertSorted(Node *node, Compare cmp) {
174 iterator it = this->begin();
175 iterator end = this->end();
176 while (it != end) {
177 if (cmp(*node, *it)) {
178 insertBefore(*node, *it);
179 return;
180 }
181 ++it;
182 }
183 append(node);
184 }
185
193 void insertSorted(Node *node) {
194 insertSorted(node, [](Node &lhs, Node &rhs) { return lhs < rhs; });
195 }
196
203 void remove(Node *node) {
204 if (node->previous != nullptr)
205 node->previous->next = node->next;
206 if (node == last)
207 last = node->previous;
208 if (node->next != nullptr)
209 node->next->previous = node->previous;
210 if (node == first)
211 first = node->next;
212 node->previous = nullptr;
213 node->next = nullptr;
214 }
215
222 void remove(Node &node) { remove(&node); }
223
235 void moveDown(Node *node) {
236 Node *nodeB = node->previous;
237 if (nodeB == nullptr) // Can't move first node further down
238 return;
239 Node *nodeA = nodeB->previous;
240 Node *nodeD = node->next;
241
242 if (nodeA != nullptr)
243 nodeA->next = node;
244 else
245 first = node;
246 nodeB->next = nodeD;
247 nodeB->previous = node;
248 node->next = nodeB;
249 node->previous = nodeA;
250 if (nodeD != nullptr)
251 nodeD->previous = nodeB;
252 else
253 last = nodeB;
254 }
255
267 void moveDown(Node &node) { moveDown(&node); }
268
284 bool couldContain(const Node *node) const {
285 return node && (node == first || node->next != nullptr ||
286 node->previous != nullptr);
287 }
288
290 bool couldContain(const Node &node) const { return couldContain(&node); }
291
292 iterator begin() { return {first}; }
293 iterator end() { return {nullptr}; }
294
295 const_iterator begin() const { return {first}; }
296 const_iterator end() const { return {nullptr}; }
297
299 reverse_iterator rend() { return {nullptr}; }
300
301 const_reverse_iterator rbegin() const { return {last}; }
302 const_reverse_iterator rend() const { return {nullptr}; }
303
305 Node *getFirst() const { return first; }
307 Node *getLast() const { return last; }
308
309 private:
310 Node *first = nullptr;
311 Node *last = nullptr;
312};
313
320template <class Node>
322 protected:
323 friend class DoublyLinkedList<Node>;
324 Node *next = nullptr;
325 Node *previous = nullptr;
326 virtual ~DoublyLinkable() = default;
327
328 DoublyLinkable() = default;
330 // Don't copy the pointers
331 }
333 // Don't copy the pointers
334 return *this;
335 }
337 // Don't swap the pointers
338 }
340 // Don't swap the pointers
341 return *this;
342 }
343};
344
346
#define AH_DIAGNOSTIC_POP()
Definition: Warnings.hpp:36
#define AH_DIAGNOSTIC_WERROR()
Definition: Warnings.hpp:35
A class that can be inherited from to allow inserting into a DoublyLinkedList.
Definition: LinkedList.hpp:321
DoublyLinkable & operator=(const DoublyLinkable &)
Definition: LinkedList.hpp:332
virtual ~DoublyLinkable()=default
DoublyLinkable()=default
DoublyLinkable & operator=(DoublyLinkable &&)
Definition: LinkedList.hpp:339
DoublyLinkable(const DoublyLinkable &)
Definition: LinkedList.hpp:329
DoublyLinkable(DoublyLinkable &&)
Definition: LinkedList.hpp:336
Base class for doubly linked list iterators.
Definition: LinkedList.hpp:29
bool operator==(const node_iterator_base &rhs) const
Definition: LinkedList.hpp:37
bool operator!=(const node_iterator_base &rhs) const
Definition: LinkedList.hpp:33
Forward bidirectional doubly linked list iterator.
Definition: LinkedList.hpp:57
std::bidirectional_iterator_tag iterator_category
Definition: LinkedList.hpp:65
node_iterator & operator--()
Prefix decrement operator.
Definition: LinkedList.hpp:75
node_iterator & operator++()
Prefix increment operator.
Definition: LinkedList.hpp:68
Reverse bidirectional doubly linked list iterator.
Definition: LinkedList.hpp:84
reverse_node_iterator & operator++()
Prefix increment operator.
Definition: LinkedList.hpp:95
std::bidirectional_iterator_tag iterator_category
Definition: LinkedList.hpp:92
reverse_node_iterator & operator--()
Prefix decrement operator.
Definition: LinkedList.hpp:102
A class for doubly linked lists.
Definition: LinkedList.hpp:25
const_reverse_iterator rend() const
Definition: LinkedList.hpp:302
const_iterator begin() const
Definition: LinkedList.hpp:295
void append(Node *node)
Append a node to a linked list.
Definition: LinkedList.hpp:120
bool couldContain(const Node *node) const
Check if the linked list could contain the given node.
Definition: LinkedList.hpp:284
void remove(Node *node)
Remove a node from the linked list.
Definition: LinkedList.hpp:203
bool couldContain(const Node &node) const
Check if the linked list could contain the given node.
Definition: LinkedList.hpp:290
Node * getLast() const
Get a pointer to the last node.
Definition: LinkedList.hpp:307
void moveDown(Node &node)
Move down the given node in the linked list.
Definition: LinkedList.hpp:267
reverse_iterator rend()
Definition: LinkedList.hpp:299
Node * getFirst() const
Get a pointer to the first node.
Definition: LinkedList.hpp:305
void append(Node &node)
Append a node to a linked list.
Definition: LinkedList.hpp:136
void moveDown(Node *node)
Move down the given node in the linked list.
Definition: LinkedList.hpp:235
void remove(Node &node)
Remove a node from the linked list.
Definition: LinkedList.hpp:222
void insertSorted(Node *node)
Insert a new node at the correct location into a sorted list, using operator<.
Definition: LinkedList.hpp:193
iterator end()
Definition: LinkedList.hpp:293
const_iterator end() const
Definition: LinkedList.hpp:296
reverse_iterator rbegin()
Definition: LinkedList.hpp:298
void insertBefore(Node *toBeInserted, Node *before)
Insert a node before another node.
Definition: LinkedList.hpp:147
iterator begin()
Definition: LinkedList.hpp:292
void insertSorted(Node *node, Compare cmp)
Insert a new node at the correct location into a sorted list.
Definition: LinkedList.hpp:173
void insertBefore(Node &toBeInserted, Node &before)
Definition: LinkedList.hpp:158
const_reverse_iterator rbegin() const
Definition: LinkedList.hpp:301