1/**************************************************************************/
2/* list.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef LIST_H
32#define LIST_H
33
34#include "core/error/error_macros.h"
35#include "core/os/memory.h"
36#include "core/templates/sort_array.h"
37
38/**
39 * Generic Templatized Linked List Implementation.
40 * The implementation differs from the STL one because
41 * a compatible preallocated linked list can be written
42 * using the same API, or features such as erasing an element
43 * from the iterator.
44 */
45
46template <class T, class A = DefaultAllocator>
47class List {
48 struct _Data;
49
50public:
51 class Element {
52 private:
53 friend class List<T, A>;
54
55 T value;
56 Element *next_ptr = nullptr;
57 Element *prev_ptr = nullptr;
58 _Data *data = nullptr;
59
60 public:
61 /**
62 * Get NEXT Element iterator, for constant lists.
63 */
64 _FORCE_INLINE_ const Element *next() const {
65 return next_ptr;
66 }
67 /**
68 * Get NEXT Element iterator,
69 */
70 _FORCE_INLINE_ Element *next() {
71 return next_ptr;
72 }
73
74 /**
75 * Get PREV Element iterator, for constant lists.
76 */
77 _FORCE_INLINE_ const Element *prev() const {
78 return prev_ptr;
79 }
80 /**
81 * Get PREV Element iterator,
82 */
83 _FORCE_INLINE_ Element *prev() {
84 return prev_ptr;
85 }
86
87 /**
88 * * operator, for using as *iterator, when iterators are defined on stack.
89 */
90 _FORCE_INLINE_ const T &operator*() const {
91 return value;
92 }
93 /**
94 * operator->, for using as iterator->, when iterators are defined on stack, for constant lists.
95 */
96 _FORCE_INLINE_ const T *operator->() const {
97 return &value;
98 }
99 /**
100 * * operator, for using as *iterator, when iterators are defined on stack,
101 */
102 _FORCE_INLINE_ T &operator*() {
103 return value;
104 }
105 /**
106 * operator->, for using as iterator->, when iterators are defined on stack, for constant lists.
107 */
108 _FORCE_INLINE_ T *operator->() {
109 return &value;
110 }
111
112 /**
113 * get the value stored in this element.
114 */
115 _FORCE_INLINE_ T &get() {
116 return value;
117 }
118 /**
119 * get the value stored in this element, for constant lists
120 */
121 _FORCE_INLINE_ const T &get() const {
122 return value;
123 }
124 /**
125 * set the value stored in this element.
126 */
127 _FORCE_INLINE_ void set(const T &p_value) {
128 value = (T &)p_value;
129 }
130
131 void erase() {
132 data->erase(this);
133 }
134
135 _FORCE_INLINE_ Element() {}
136 };
137
138 typedef T ValueType;
139
140 struct Iterator {
141 _FORCE_INLINE_ T &operator*() const {
142 return E->get();
143 }
144 _FORCE_INLINE_ T *operator->() const { return &E->get(); }
145 _FORCE_INLINE_ Iterator &operator++() {
146 E = E->next();
147 return *this;
148 }
149 _FORCE_INLINE_ Iterator &operator--() {
150 E = E->prev();
151 return *this;
152 }
153
154 _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
155 _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
156
157 Iterator(Element *p_E) { E = p_E; }
158 Iterator() {}
159 Iterator(const Iterator &p_it) { E = p_it.E; }
160
161 private:
162 Element *E = nullptr;
163 };
164
165 struct ConstIterator {
166 _FORCE_INLINE_ const T &operator*() const {
167 return E->get();
168 }
169 _FORCE_INLINE_ const T *operator->() const { return &E->get(); }
170 _FORCE_INLINE_ ConstIterator &operator++() {
171 E = E->next();
172 return *this;
173 }
174 _FORCE_INLINE_ ConstIterator &operator--() {
175 E = E->prev();
176 return *this;
177 }
178
179 _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
180 _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
181
182 _FORCE_INLINE_ ConstIterator(const Element *p_E) { E = p_E; }
183 _FORCE_INLINE_ ConstIterator() {}
184 _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
185
186 private:
187 const Element *E = nullptr;
188 };
189
190 _FORCE_INLINE_ Iterator begin() {
191 return Iterator(front());
192 }
193 _FORCE_INLINE_ Iterator end() {
194 return Iterator(nullptr);
195 }
196
197#if 0
198 //to use when replacing find()
199 _FORCE_INLINE_ Iterator find(const K &p_key) {
200 return Iterator(find(p_key));
201 }
202#endif
203 _FORCE_INLINE_ ConstIterator begin() const {
204 return ConstIterator(front());
205 }
206 _FORCE_INLINE_ ConstIterator end() const {
207 return ConstIterator(nullptr);
208 }
209#if 0
210 //to use when replacing find()
211 _FORCE_INLINE_ ConstIterator find(const K &p_key) const {
212 return ConstIterator(find(p_key));
213 }
214#endif
215private:
216 struct _Data {
217 Element *first = nullptr;
218 Element *last = nullptr;
219 int size_cache = 0;
220
221 bool erase(const Element *p_I) {
222 ERR_FAIL_NULL_V(p_I, false);
223 ERR_FAIL_COND_V(p_I->data != this, false);
224
225 if (first == p_I) {
226 first = p_I->next_ptr;
227 }
228
229 if (last == p_I) {
230 last = p_I->prev_ptr;
231 }
232
233 if (p_I->prev_ptr) {
234 p_I->prev_ptr->next_ptr = p_I->next_ptr;
235 }
236
237 if (p_I->next_ptr) {
238 p_I->next_ptr->prev_ptr = p_I->prev_ptr;
239 }
240
241 memdelete_allocator<Element, A>(const_cast<Element *>(p_I));
242 size_cache--;
243
244 return true;
245 }
246 };
247
248 _Data *_data = nullptr;
249
250public:
251 /**
252 * return a const iterator to the beginning of the list.
253 */
254 _FORCE_INLINE_ const Element *front() const {
255 return _data ? _data->first : nullptr;
256 }
257
258 /**
259 * return an iterator to the beginning of the list.
260 */
261 _FORCE_INLINE_ Element *front() {
262 return _data ? _data->first : nullptr;
263 }
264
265 /**
266 * return a const iterator to the last member of the list.
267 */
268 _FORCE_INLINE_ const Element *back() const {
269 return _data ? _data->last : nullptr;
270 }
271
272 /**
273 * return an iterator to the last member of the list.
274 */
275 _FORCE_INLINE_ Element *back() {
276 return _data ? _data->last : nullptr;
277 }
278
279 /**
280 * store a new element at the end of the list
281 */
282 Element *push_back(const T &value) {
283 if (!_data) {
284 _data = memnew_allocator(_Data, A);
285 _data->first = nullptr;
286 _data->last = nullptr;
287 _data->size_cache = 0;
288 }
289
290 Element *n = memnew_allocator(Element, A);
291 n->value = (T &)value;
292
293 n->prev_ptr = _data->last;
294 n->next_ptr = nullptr;
295 n->data = _data;
296
297 if (_data->last) {
298 _data->last->next_ptr = n;
299 }
300
301 _data->last = n;
302
303 if (!_data->first) {
304 _data->first = n;
305 }
306
307 _data->size_cache++;
308
309 return n;
310 }
311
312 void pop_back() {
313 if (_data && _data->last) {
314 erase(_data->last);
315 }
316 }
317
318 /**
319 * store a new element at the beginning of the list
320 */
321 Element *push_front(const T &value) {
322 if (!_data) {
323 _data = memnew_allocator(_Data, A);
324 _data->first = nullptr;
325 _data->last = nullptr;
326 _data->size_cache = 0;
327 }
328
329 Element *n = memnew_allocator(Element, A);
330 n->value = (T &)value;
331 n->prev_ptr = nullptr;
332 n->next_ptr = _data->first;
333 n->data = _data;
334
335 if (_data->first) {
336 _data->first->prev_ptr = n;
337 }
338
339 _data->first = n;
340
341 if (!_data->last) {
342 _data->last = n;
343 }
344
345 _data->size_cache++;
346
347 return n;
348 }
349
350 void pop_front() {
351 if (_data && _data->first) {
352 erase(_data->first);
353 }
354 }
355
356 Element *insert_after(Element *p_element, const T &p_value) {
357 CRASH_COND(p_element && (!_data || p_element->data != _data));
358
359 if (!p_element) {
360 return push_back(p_value);
361 }
362
363 Element *n = memnew_allocator(Element, A);
364 n->value = (T &)p_value;
365 n->prev_ptr = p_element;
366 n->next_ptr = p_element->next_ptr;
367 n->data = _data;
368
369 if (!p_element->next_ptr) {
370 _data->last = n;
371 } else {
372 p_element->next_ptr->prev_ptr = n;
373 }
374
375 p_element->next_ptr = n;
376
377 _data->size_cache++;
378
379 return n;
380 }
381
382 Element *insert_before(Element *p_element, const T &p_value) {
383 CRASH_COND(p_element && (!_data || p_element->data != _data));
384
385 if (!p_element) {
386 return push_back(p_value);
387 }
388
389 Element *n = memnew_allocator(Element, A);
390 n->value = (T &)p_value;
391 n->prev_ptr = p_element->prev_ptr;
392 n->next_ptr = p_element;
393 n->data = _data;
394
395 if (!p_element->prev_ptr) {
396 _data->first = n;
397 } else {
398 p_element->prev_ptr->next_ptr = n;
399 }
400
401 p_element->prev_ptr = n;
402
403 _data->size_cache++;
404
405 return n;
406 }
407
408 /**
409 * find an element in the list,
410 */
411 template <class T_v>
412 Element *find(const T_v &p_val) {
413 Element *it = front();
414 while (it) {
415 if (it->value == p_val) {
416 return it;
417 }
418 it = it->next();
419 }
420
421 return nullptr;
422 }
423
424 /**
425 * erase an element in the list, by iterator pointing to it. Return true if it was found/erased.
426 */
427 bool erase(const Element *p_I) {
428 if (_data && p_I) {
429 bool ret = _data->erase(p_I);
430
431 if (_data->size_cache == 0) {
432 memdelete_allocator<_Data, A>(_data);
433 _data = nullptr;
434 }
435
436 return ret;
437 }
438
439 return false;
440 }
441
442 /**
443 * erase the first element in the list, that contains value
444 */
445 bool erase(const T &value) {
446 Element *I = find(value);
447 return erase(I);
448 }
449
450 /**
451 * return whether the list is empty
452 */
453 _FORCE_INLINE_ bool is_empty() const {
454 return (!_data || !_data->size_cache);
455 }
456
457 /**
458 * clear the list
459 */
460 void clear() {
461 while (front()) {
462 erase(front());
463 }
464 }
465
466 _FORCE_INLINE_ int size() const {
467 return _data ? _data->size_cache : 0;
468 }
469
470 void swap(Element *p_A, Element *p_B) {
471 ERR_FAIL_COND(!p_A || !p_B);
472 ERR_FAIL_COND(p_A->data != _data);
473 ERR_FAIL_COND(p_B->data != _data);
474
475 if (p_A == p_B) {
476 return;
477 }
478 Element *A_prev = p_A->prev_ptr;
479 Element *A_next = p_A->next_ptr;
480 Element *B_prev = p_B->prev_ptr;
481 Element *B_next = p_B->next_ptr;
482
483 if (A_prev) {
484 A_prev->next_ptr = p_B;
485 } else {
486 _data->first = p_B;
487 }
488 if (B_prev) {
489 B_prev->next_ptr = p_A;
490 } else {
491 _data->first = p_A;
492 }
493 if (A_next) {
494 A_next->prev_ptr = p_B;
495 } else {
496 _data->last = p_B;
497 }
498 if (B_next) {
499 B_next->prev_ptr = p_A;
500 } else {
501 _data->last = p_A;
502 }
503 p_A->prev_ptr = A_next == p_B ? p_B : B_prev;
504 p_A->next_ptr = B_next == p_A ? p_B : B_next;
505 p_B->prev_ptr = B_next == p_A ? p_A : A_prev;
506 p_B->next_ptr = A_next == p_B ? p_A : A_next;
507 }
508 /**
509 * copy the list
510 */
511 void operator=(const List &p_list) {
512 clear();
513 const Element *it = p_list.front();
514 while (it) {
515 push_back(it->get());
516 it = it->next();
517 }
518 }
519
520 T &operator[](int p_index) {
521 CRASH_BAD_INDEX(p_index, size());
522
523 Element *I = front();
524 int c = 0;
525 while (c < p_index) {
526 I = I->next();
527 c++;
528 }
529
530 return I->get();
531 }
532
533 const T &operator[](int p_index) const {
534 CRASH_BAD_INDEX(p_index, size());
535
536 const Element *I = front();
537 int c = 0;
538 while (c < p_index) {
539 I = I->next();
540 c++;
541 }
542
543 return I->get();
544 }
545
546 void move_to_back(Element *p_I) {
547 ERR_FAIL_COND(p_I->data != _data);
548 if (!p_I->next_ptr) {
549 return;
550 }
551
552 if (_data->first == p_I) {
553 _data->first = p_I->next_ptr;
554 }
555
556 if (_data->last == p_I) {
557 _data->last = p_I->prev_ptr;
558 }
559
560 if (p_I->prev_ptr) {
561 p_I->prev_ptr->next_ptr = p_I->next_ptr;
562 }
563
564 p_I->next_ptr->prev_ptr = p_I->prev_ptr;
565
566 _data->last->next_ptr = p_I;
567 p_I->prev_ptr = _data->last;
568 p_I->next_ptr = nullptr;
569 _data->last = p_I;
570 }
571
572 void reverse() {
573 int s = size() / 2;
574 Element *F = front();
575 Element *B = back();
576 for (int i = 0; i < s; i++) {
577 SWAP(F->value, B->value);
578 F = F->next();
579 B = B->prev();
580 }
581 }
582
583 void move_to_front(Element *p_I) {
584 ERR_FAIL_COND(p_I->data != _data);
585 if (!p_I->prev_ptr) {
586 return;
587 }
588
589 if (_data->first == p_I) {
590 _data->first = p_I->next_ptr;
591 }
592
593 if (_data->last == p_I) {
594 _data->last = p_I->prev_ptr;
595 }
596
597 p_I->prev_ptr->next_ptr = p_I->next_ptr;
598
599 if (p_I->next_ptr) {
600 p_I->next_ptr->prev_ptr = p_I->prev_ptr;
601 }
602
603 _data->first->prev_ptr = p_I;
604 p_I->next_ptr = _data->first;
605 p_I->prev_ptr = nullptr;
606 _data->first = p_I;
607 }
608
609 void move_before(Element *value, Element *where) {
610 if (value->prev_ptr) {
611 value->prev_ptr->next_ptr = value->next_ptr;
612 } else {
613 _data->first = value->next_ptr;
614 }
615 if (value->next_ptr) {
616 value->next_ptr->prev_ptr = value->prev_ptr;
617 } else {
618 _data->last = value->prev_ptr;
619 }
620
621 value->next_ptr = where;
622 if (!where) {
623 value->prev_ptr = _data->last;
624 _data->last = value;
625 return;
626 }
627
628 value->prev_ptr = where->prev_ptr;
629
630 if (where->prev_ptr) {
631 where->prev_ptr->next_ptr = value;
632 } else {
633 _data->first = value;
634 }
635
636 where->prev_ptr = value;
637 }
638
639 /**
640 * simple insertion sort
641 */
642
643 void sort() {
644 sort_custom<Comparator<T>>();
645 }
646
647 template <class C>
648 void sort_custom_inplace() {
649 if (size() < 2) {
650 return;
651 }
652
653 Element *from = front();
654 Element *current = from;
655 Element *to = from;
656
657 while (current) {
658 Element *next = current->next_ptr;
659
660 if (from != current) {
661 current->prev_ptr = nullptr;
662 current->next_ptr = from;
663
664 Element *find = from;
665 C less;
666 while (find && less(find->value, current->value)) {
667 current->prev_ptr = find;
668 current->next_ptr = find->next_ptr;
669 find = find->next_ptr;
670 }
671
672 if (current->prev_ptr) {
673 current->prev_ptr->next_ptr = current;
674 } else {
675 from = current;
676 }
677
678 if (current->next_ptr) {
679 current->next_ptr->prev_ptr = current;
680 } else {
681 to = current;
682 }
683 } else {
684 current->prev_ptr = nullptr;
685 current->next_ptr = nullptr;
686 }
687
688 current = next;
689 }
690 _data->first = from;
691 _data->last = to;
692 }
693
694 template <class C>
695 struct AuxiliaryComparator {
696 C compare;
697 _FORCE_INLINE_ bool operator()(const Element *a, const Element *b) const {
698 return compare(a->value, b->value);
699 }
700 };
701
702 template <class C>
703 void sort_custom() {
704 //this version uses auxiliary memory for speed.
705 //if you don't want to use auxiliary memory, use the in_place version
706
707 int s = size();
708 if (s < 2) {
709 return;
710 }
711
712 Element **aux_buffer = memnew_arr(Element *, s);
713
714 int idx = 0;
715 for (Element *E = front(); E; E = E->next_ptr) {
716 aux_buffer[idx] = E;
717 idx++;
718 }
719
720 SortArray<Element *, AuxiliaryComparator<C>> sort;
721 sort.sort(aux_buffer, s);
722
723 _data->first = aux_buffer[0];
724 aux_buffer[0]->prev_ptr = nullptr;
725 aux_buffer[0]->next_ptr = aux_buffer[1];
726
727 _data->last = aux_buffer[s - 1];
728 aux_buffer[s - 1]->prev_ptr = aux_buffer[s - 2];
729 aux_buffer[s - 1]->next_ptr = nullptr;
730
731 for (int i = 1; i < s - 1; i++) {
732 aux_buffer[i]->prev_ptr = aux_buffer[i - 1];
733 aux_buffer[i]->next_ptr = aux_buffer[i + 1];
734 }
735
736 memdelete_arr(aux_buffer);
737 }
738
739 const void *id() const {
740 return (void *)_data;
741 }
742
743 /**
744 * copy constructor for the list
745 */
746 List(const List &p_list) {
747 const Element *it = p_list.front();
748 while (it) {
749 push_back(it->get());
750 it = it->next();
751 }
752 }
753
754 List() {}
755
756 ~List() {
757 clear();
758 if (_data) {
759 ERR_FAIL_COND(_data->size_cache);
760 memdelete_allocator<_Data, A>(_data);
761 }
762 }
763};
764
765#endif // LIST_H
766