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