Arduino Helpers master
Utility library for Arduino
LinkedList.hpp
Go to the documentation of this file.
1/* ✔ */
2
3#pragma once
4
5#include <AH/Debug/Debug.hpp>
7#include <stdlib.h>
8
9#include <AH/STL/iterator>
10
13
20template <class Node>
22 public:
24 template <class INode>
26 public:
28
29 bool operator!=(const node_iterator_base &rhs) const {
30 return node != rhs.node;
31 }
32
33 bool operator==(const node_iterator_base &rhs) const {
34 return !(*this != rhs);
35 }
36
37 INode &operator*() const {
38 // TODO: check node != nullptr
39 return *node;
40 }
41
42 INode *operator->() const {
43 // TODO: check node != nullptr
44 return node;
45 }
46
47 protected:
48 INode *node;
49 };
50
52 template <class INode>
53 class node_iterator : public node_iterator_base<INode> {
54 public:
56
57 using difference_type = long;
58 using value_type = INode;
59 using pointer = INode *;
60 using reference = INode &;
61 using iterator_category = std::bidirectional_iterator_tag;
62
65 // TODO: check node != nullptr
66 this->node = this->node->next;
67 return *this;
68 }
69
72 // TODO: check node != nullptr
73 this->node = this->node->previous;
74 return *this;
75 }
76 };
77
79 template <class INode>
81 public:
83
84 using difference_type = long;
85 using value_type = INode;
86 using pointer = INode *;
87 using reference = INode &;
88 using iterator_category = std::bidirectional_iterator_tag;
89
92 // TODO: check node != nullptr
93 this->node = this->node->previous;
94 return *this;
95 }
96
99 // TODO: check node != nullptr
100 this->node = this->node->next;
101 return *this;
102 }
103 };
104
109
116 void append(Node *node) {
117 if (first == nullptr)
118 first = node;
119 node->previous = last;
120 if (node->previous != nullptr)
121 node->previous->next = node;
122 last = node;
123 node->next = nullptr;
124 }
125
132 void append(Node &node) { append(&node); }
133
143 void insertBefore(Node *toBeInserted, Node *before) {
144 if (before == first)
145 first = toBeInserted;
146 else
147 before->previous->next = toBeInserted;
148 toBeInserted->previous = before->previous;
149 toBeInserted->next = before;
150 before->previous = toBeInserted;
151 }
152
154 void insertBefore(Node &toBeInserted, Node &before) {
155 insertBefore(&toBeInserted, &before);
156 }
157
168 template <class Compare>
169 void insertSorted(Node *node, Compare cmp) {
170 iterator it = this->begin();
171 iterator end = this->end();
172 while (it != end) {
173 if (cmp(*node, *it)) {
174 insertBefore(*node, *it);
175 return;
176 }
177 ++it;
178 }
179 append(node);
180 }
181
189 void insertSorted(Node *node) {
190 insertSorted(node, [](Node &lhs, Node &rhs) { return lhs < rhs; });
191 }
192
199 void remove(Node *node) {
200 if (node->previous != nullptr)
201 node->previous->next = node->next;
202 if (node == last)
203 last = node->previous;
204 if (node->next != nullptr)
205 node->next->previous = node->previous;
206 if (node == first)
207 first = node->next;
208 node->previous = nullptr;
209 node->next = nullptr;
210 }
211
218 void remove(Node &node) { remove(&node); }
219
231 void moveDown(Node *node) {
232 Node *nodeB = node->previous;
233 if (nodeB == nullptr) // Can't move first node further down
234 return;
235 Node *nodeA = nodeB->previous;
236 Node *nodeD = node->next;
237
238 if (nodeA != nullptr)
239 nodeA->next = node;
240 else
241 first = node;
242 nodeB->next = nodeD;
243 nodeB->previous = node;
244 node->next = nodeB;
245 node->previous = nodeA;
246 if (nodeD != nullptr)
247 nodeD->previous = nodeB;
248 else
249 last = nodeB;
250 }
251
263 void moveDown(Node &node) { moveDown(&node); }
264
280 bool couldContain(const Node *node) const {
281 return node && (node == first || node->next != nullptr ||
282 node->previous != nullptr);
283 }
284
286 bool couldContain(const Node &node) const { return couldContain(&node); }
287
288 iterator begin() { return {first}; }
289 iterator end() { return {nullptr}; }
290
291 const_iterator begin() const { return {first}; }
292 const_iterator end() const { return {nullptr}; }
293
295 reverse_iterator rend() { return {nullptr}; }
296
297 const_reverse_iterator rbegin() const { return {last}; }
298 const_reverse_iterator rend() const { return {nullptr}; }
299
301 Node *getFirst() const { return first; }
303 Node *getLast() const { return last; }
304
305 private:
306 Node *first = nullptr;
307 Node *last = nullptr;
308};
309
316template <class Node>
318 protected:
319 friend class DoublyLinkedList<Node>;
320 Node *next = nullptr;
321 Node *previous = nullptr;
322 virtual ~DoublyLinkable() = default;
323
324 DoublyLinkable() = default;
326 // Don't copy the pointers
327 }
329 // Don't copy the pointers
330 return *this;
331 }
333 // Don't swap the pointers
334 }
336 // Don't swap the pointers
337 return *this;
338 }
339};
340
A class that can be inherited from to allow inserting into a DoublyLinkedList.
Definition: LinkedList.hpp:317
DoublyLinkable & operator=(const DoublyLinkable &)
Definition: LinkedList.hpp:328
virtual ~DoublyLinkable()=default
DoublyLinkable()=default
DoublyLinkable & operator=(DoublyLinkable &&)
Definition: LinkedList.hpp:335
DoublyLinkable(const DoublyLinkable &)
Definition: LinkedList.hpp:325
DoublyLinkable(DoublyLinkable &&)
Definition: LinkedList.hpp:332
Base class for doubly linked list iterators.
Definition: LinkedList.hpp:25
bool operator==(const node_iterator_base &rhs) const
Definition: LinkedList.hpp:33
bool operator!=(const node_iterator_base &rhs) const
Definition: LinkedList.hpp:29
Forward bidirectional doubly linked list iterator.
Definition: LinkedList.hpp:53
std::bidirectional_iterator_tag iterator_category
Definition: LinkedList.hpp:61
node_iterator & operator--()
Prefix decrement operator.
Definition: LinkedList.hpp:71
node_iterator & operator++()
Prefix increment operator.
Definition: LinkedList.hpp:64
Reverse bidirectional doubly linked list iterator.
Definition: LinkedList.hpp:80
reverse_node_iterator & operator++()
Prefix increment operator.
Definition: LinkedList.hpp:91
std::bidirectional_iterator_tag iterator_category
Definition: LinkedList.hpp:88
reverse_node_iterator & operator--()
Prefix decrement operator.
Definition: LinkedList.hpp:98
A class for doubly linked lists.
Definition: LinkedList.hpp:21
const_reverse_iterator rend() const
Definition: LinkedList.hpp:298
const_iterator begin() const
Definition: LinkedList.hpp:291
void append(Node *node)
Append a node to a linked list.
Definition: LinkedList.hpp:116
bool couldContain(const Node *node) const
Check if the linked list could contain the given node.
Definition: LinkedList.hpp:280
void remove(Node *node)
Remove a node from the linked list.
Definition: LinkedList.hpp:199
bool couldContain(const Node &node) const
Check if the linked list could contain the given node.
Definition: LinkedList.hpp:286
Node * getLast() const
Get a pointer to the last node.
Definition: LinkedList.hpp:303
void moveDown(Node &node)
Move down the given node in the linked list.
Definition: LinkedList.hpp:263
reverse_iterator rend()
Definition: LinkedList.hpp:295
Node * getFirst() const
Get a pointer to the first node.
Definition: LinkedList.hpp:301
void append(Node &node)
Append a node to a linked list.
Definition: LinkedList.hpp:132
void moveDown(Node *node)
Move down the given node in the linked list.
Definition: LinkedList.hpp:231
void remove(Node &node)
Remove a node from the linked list.
Definition: LinkedList.hpp:218
void insertSorted(Node *node)
Insert a new node at the correct location into a sorted list, using operator<.
Definition: LinkedList.hpp:189
iterator end()
Definition: LinkedList.hpp:289
const_iterator end() const
Definition: LinkedList.hpp:292
reverse_iterator rbegin()
Definition: LinkedList.hpp:294
void insertBefore(Node *toBeInserted, Node *before)
Insert a node before another node.
Definition: LinkedList.hpp:143
iterator begin()
Definition: LinkedList.hpp:288
void insertSorted(Node *node, Compare cmp)
Insert a new node at the correct location into a sorted list.
Definition: LinkedList.hpp:169
void insertBefore(Node &toBeInserted, Node &before)
Definition: LinkedList.hpp:154
const_reverse_iterator rbegin() const
Definition: LinkedList.hpp:297