summaryrefslogtreecommitdiff
path: root/core/templates/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'core/templates/list.h')
-rw-r--r--core/templates/list.h688
1 files changed, 688 insertions, 0 deletions
diff --git a/core/templates/list.h b/core/templates/list.h
new file mode 100644
index 0000000000..d745066e4c
--- /dev/null
+++ b/core/templates/list.h
@@ -0,0 +1,688 @@
+/*************************************************************************/
+/* list.h */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/*************************************************************************/
+
+#ifndef LIST_H
+#define LIST_H
+
+#include "core/error/error_macros.h"
+#include "core/os/memory.h"
+#include "core/templates/sort_array.h"
+
+/**
+ * Generic Templatized Linked List Implementation.
+ * The implementation differs from the STL one because
+ * a compatible preallocated linked list can be written
+ * using the same API, or features such as erasing an element
+ * from the iterator.
+ */
+
+template <class T, class A = DefaultAllocator>
+class List {
+ struct _Data;
+
+public:
+ class Element {
+ private:
+ friend class List<T, A>;
+
+ T value;
+ Element *next_ptr = nullptr;
+ Element *prev_ptr = nullptr;
+ _Data *data = nullptr;
+
+ public:
+ /**
+ * Get NEXT Element iterator, for constant lists.
+ */
+ _FORCE_INLINE_ const Element *next() const {
+ return next_ptr;
+ }
+ /**
+ * Get NEXT Element iterator,
+ */
+ _FORCE_INLINE_ Element *next() {
+ return next_ptr;
+ }
+
+ /**
+ * Get PREV Element iterator, for constant lists.
+ */
+ _FORCE_INLINE_ const Element *prev() const {
+ return prev_ptr;
+ }
+ /**
+ * Get PREV Element iterator,
+ */
+ _FORCE_INLINE_ Element *prev() {
+ return prev_ptr;
+ }
+
+ /**
+ * * operator, for using as *iterator, when iterators are defined on stack.
+ */
+ _FORCE_INLINE_ const T &operator*() const {
+ return value;
+ }
+ /**
+ * operator->, for using as iterator->, when iterators are defined on stack, for constant lists.
+ */
+ _FORCE_INLINE_ const T *operator->() const {
+ return &value;
+ }
+ /**
+ * * operator, for using as *iterator, when iterators are defined on stack,
+ */
+ _FORCE_INLINE_ T &operator*() {
+ return value;
+ }
+ /**
+ * operator->, for using as iterator->, when iterators are defined on stack, for constant lists.
+ */
+ _FORCE_INLINE_ T *operator->() {
+ return &value;
+ }
+
+ /**
+ * get the value stored in this element.
+ */
+ _FORCE_INLINE_ T &get() {
+ return value;
+ }
+ /**
+ * get the value stored in this element, for constant lists
+ */
+ _FORCE_INLINE_ const T &get() const {
+ return value;
+ }
+ /**
+ * set the value stored in this element.
+ */
+ _FORCE_INLINE_ void set(const T &p_value) {
+ value = (T &)p_value;
+ }
+
+ void erase() {
+ data->erase(this);
+ }
+
+ _FORCE_INLINE_ Element() {}
+ };
+
+private:
+ struct _Data {
+ Element *first;
+ Element *last;
+ int size_cache;
+
+ bool erase(const Element *p_I) {
+ ERR_FAIL_COND_V(!p_I, false);
+ ERR_FAIL_COND_V(p_I->data != this, false);
+
+ if (first == p_I) {
+ first = p_I->next_ptr;
+ }
+
+ if (last == p_I) {
+ last = p_I->prev_ptr;
+ }
+
+ if (p_I->prev_ptr) {
+ p_I->prev_ptr->next_ptr = p_I->next_ptr;
+ }
+
+ if (p_I->next_ptr) {
+ p_I->next_ptr->prev_ptr = p_I->prev_ptr;
+ }
+
+ memdelete_allocator<Element, A>(const_cast<Element *>(p_I));
+ size_cache--;
+
+ return true;
+ }
+ };
+
+ _Data *_data = nullptr;
+
+public:
+ /**
+ * return a const iterator to the beginning of the list.
+ */
+ _FORCE_INLINE_ const Element *front() const {
+ return _data ? _data->first : nullptr;
+ }
+
+ /**
+ * return an iterator to the beginning of the list.
+ */
+ _FORCE_INLINE_ Element *front() {
+ return _data ? _data->first : nullptr;
+ }
+
+ /**
+ * return a const iterator to the last member of the list.
+ */
+ _FORCE_INLINE_ const Element *back() const {
+ return _data ? _data->last : nullptr;
+ }
+
+ /**
+ * return an iterator to the last member of the list.
+ */
+ _FORCE_INLINE_ Element *back() {
+ return _data ? _data->last : nullptr;
+ }
+
+ /**
+ * store a new element at the end of the list
+ */
+ Element *push_back(const T &value) {
+ if (!_data) {
+ _data = memnew_allocator(_Data, A);
+ _data->first = nullptr;
+ _data->last = nullptr;
+ _data->size_cache = 0;
+ }
+
+ Element *n = memnew_allocator(Element, A);
+ n->value = (T &)value;
+
+ n->prev_ptr = _data->last;
+ n->next_ptr = nullptr;
+ n->data = _data;
+
+ if (_data->last) {
+ _data->last->next_ptr = n;
+ }
+
+ _data->last = n;
+
+ if (!_data->first) {
+ _data->first = n;
+ }
+
+ _data->size_cache++;
+
+ return n;
+ }
+
+ void pop_back() {
+ if (_data && _data->last) {
+ erase(_data->last);
+ }
+ }
+
+ /**
+ * store a new element at the beginning of the list
+ */
+ Element *push_front(const T &value) {
+ if (!_data) {
+ _data = memnew_allocator(_Data, A);
+ _data->first = nullptr;
+ _data->last = nullptr;
+ _data->size_cache = 0;
+ }
+
+ Element *n = memnew_allocator(Element, A);
+ n->value = (T &)value;
+ n->prev_ptr = nullptr;
+ n->next_ptr = _data->first;
+ n->data = _data;
+
+ if (_data->first) {
+ _data->first->prev_ptr = n;
+ }
+
+ _data->first = n;
+
+ if (!_data->last) {
+ _data->last = n;
+ }
+
+ _data->size_cache++;
+
+ return n;
+ }
+
+ void pop_front() {
+ if (_data && _data->first) {
+ erase(_data->first);
+ }
+ }
+
+ Element *insert_after(Element *p_element, const T &p_value) {
+ CRASH_COND(p_element && (!_data || p_element->data != _data));
+
+ if (!p_element) {
+ return push_back(p_value);
+ }
+
+ Element *n = memnew_allocator(Element, A);
+ n->value = (T &)p_value;
+ n->prev_ptr = p_element;
+ n->next_ptr = p_element->next_ptr;
+ n->data = _data;
+
+ if (!p_element->next_ptr) {
+ _data->last = n;
+ } else {
+ p_element->next_ptr->prev_ptr = n;
+ }
+
+ p_element->next_ptr = n;
+
+ _data->size_cache++;
+
+ return n;
+ }
+
+ Element *insert_before(Element *p_element, const T &p_value) {
+ CRASH_COND(p_element && (!_data || p_element->data != _data));
+
+ if (!p_element) {
+ return push_back(p_value);
+ }
+
+ Element *n = memnew_allocator(Element, A);
+ n->value = (T &)p_value;
+ n->prev_ptr = p_element->prev_ptr;
+ n->next_ptr = p_element;
+ n->data = _data;
+
+ if (!p_element->prev_ptr) {
+ _data->first = n;
+ } else {
+ p_element->prev_ptr->next_ptr = n;
+ }
+
+ p_element->prev_ptr = n;
+
+ _data->size_cache++;
+
+ return n;
+ }
+
+ /**
+ * find an element in the list,
+ */
+ template <class T_v>
+ Element *find(const T_v &p_val) {
+ Element *it = front();
+ while (it) {
+ if (it->value == p_val) {
+ return it;
+ }
+ it = it->next();
+ }
+
+ return nullptr;
+ }
+
+ /**
+ * erase an element in the list, by iterator pointing to it. Return true if it was found/erased.
+ */
+ bool erase(const Element *p_I) {
+ if (_data && p_I) {
+ bool ret = _data->erase(p_I);
+
+ if (_data->size_cache == 0) {
+ memdelete_allocator<_Data, A>(_data);
+ _data = nullptr;
+ }
+
+ return ret;
+ }
+
+ return false;
+ }
+
+ /**
+ * erase the first element in the list, that contains value
+ */
+ bool erase(const T &value) {
+ Element *I = find(value);
+ return erase(I);
+ }
+
+ /**
+ * return whether the list is empty
+ */
+ _FORCE_INLINE_ bool empty() const {
+ return (!_data || !_data->size_cache);
+ }
+
+ /**
+ * clear the list
+ */
+ void clear() {
+ while (front()) {
+ erase(front());
+ }
+ }
+
+ _FORCE_INLINE_ int size() const {
+ return _data ? _data->size_cache : 0;
+ }
+
+ void swap(Element *p_A, Element *p_B) {
+ ERR_FAIL_COND(!p_A || !p_B);
+ ERR_FAIL_COND(p_A->data != _data);
+ ERR_FAIL_COND(p_B->data != _data);
+
+ if (p_A == p_B) {
+ return;
+ }
+ Element *A_prev = p_A->prev_ptr;
+ Element *A_next = p_A->next_ptr;
+ Element *B_prev = p_B->prev_ptr;
+ Element *B_next = p_B->next_ptr;
+
+ if (A_prev) {
+ A_prev->next_ptr = p_B;
+ } else {
+ _data->first = p_B;
+ }
+ if (B_prev) {
+ B_prev->next_ptr = p_A;
+ } else {
+ _data->first = p_A;
+ }
+ if (A_next) {
+ A_next->prev_ptr = p_B;
+ } else {
+ _data->last = p_B;
+ }
+ if (B_next) {
+ B_next->prev_ptr = p_A;
+ } else {
+ _data->last = p_A;
+ }
+ p_A->prev_ptr = A_next == p_B ? p_B : B_prev;
+ p_A->next_ptr = B_next == p_A ? p_B : B_next;
+ p_B->prev_ptr = B_next == p_A ? p_A : A_prev;
+ p_B->next_ptr = A_next == p_B ? p_A : A_next;
+ }
+ /**
+ * copy the list
+ */
+ void operator=(const List &p_list) {
+ clear();
+ const Element *it = p_list.front();
+ while (it) {
+ push_back(it->get());
+ it = it->next();
+ }
+ }
+
+ T &operator[](int p_index) {
+ CRASH_BAD_INDEX(p_index, size());
+
+ Element *I = front();
+ int c = 0;
+ while (c < p_index) {
+ I = I->next();
+ c++;
+ }
+
+ return I->get();
+ }
+
+ const T &operator[](int p_index) const {
+ CRASH_BAD_INDEX(p_index, size());
+
+ const Element *I = front();
+ int c = 0;
+ while (c < p_index) {
+ I = I->next();
+ c++;
+ }
+
+ return I->get();
+ }
+
+ void move_to_back(Element *p_I) {
+ ERR_FAIL_COND(p_I->data != _data);
+ if (!p_I->next_ptr) {
+ return;
+ }
+
+ if (_data->first == p_I) {
+ _data->first = p_I->next_ptr;
+ }
+
+ if (_data->last == p_I) {
+ _data->last = p_I->prev_ptr;
+ }
+
+ if (p_I->prev_ptr) {
+ p_I->prev_ptr->next_ptr = p_I->next_ptr;
+ }
+
+ p_I->next_ptr->prev_ptr = p_I->prev_ptr;
+
+ _data->last->next_ptr = p_I;
+ p_I->prev_ptr = _data->last;
+ p_I->next_ptr = nullptr;
+ _data->last = p_I;
+ }
+
+ void invert() {
+ int s = size() / 2;
+ Element *F = front();
+ Element *B = back();
+ for (int i = 0; i < s; i++) {
+ SWAP(F->value, B->value);
+ F = F->next();
+ B = B->prev();
+ }
+ }
+
+ void move_to_front(Element *p_I) {
+ ERR_FAIL_COND(p_I->data != _data);
+ if (!p_I->prev_ptr) {
+ return;
+ }
+
+ if (_data->first == p_I) {
+ _data->first = p_I->next_ptr;
+ }
+
+ if (_data->last == p_I) {
+ _data->last = p_I->prev_ptr;
+ }
+
+ p_I->prev_ptr->next_ptr = p_I->next_ptr;
+
+ if (p_I->next_ptr) {
+ p_I->next_ptr->prev_ptr = p_I->prev_ptr;
+ }
+
+ _data->first->prev_ptr = p_I;
+ p_I->next_ptr = _data->first;
+ p_I->prev_ptr = nullptr;
+ _data->first = p_I;
+ }
+
+ void move_before(Element *value, Element *where) {
+ if (value->prev_ptr) {
+ value->prev_ptr->next_ptr = value->next_ptr;
+ } else {
+ _data->first = value->next_ptr;
+ }
+ if (value->next_ptr) {
+ value->next_ptr->prev_ptr = value->prev_ptr;
+ } else {
+ _data->last = value->prev_ptr;
+ }
+
+ value->next_ptr = where;
+ if (!where) {
+ value->prev_ptr = _data->last;
+ _data->last = value;
+ return;
+ }
+
+ value->prev_ptr = where->prev_ptr;
+
+ if (where->prev_ptr) {
+ where->prev_ptr->next_ptr = value;
+ } else {
+ _data->first = value;
+ }
+
+ where->prev_ptr = value;
+ }
+
+ /**
+ * simple insertion sort
+ */
+
+ void sort() {
+ sort_custom<Comparator<T>>();
+ }
+
+ template <class C>
+ void sort_custom_inplace() {
+ if (size() < 2) {
+ return;
+ }
+
+ Element *from = front();
+ Element *current = from;
+ Element *to = from;
+
+ while (current) {
+ Element *next = current->next_ptr;
+
+ if (from != current) {
+ current->prev_ptr = nullptr;
+ current->next_ptr = from;
+
+ Element *find = from;
+ C less;
+ while (find && less(find->value, current->value)) {
+ current->prev_ptr = find;
+ current->next_ptr = find->next_ptr;
+ find = find->next_ptr;
+ }
+
+ if (current->prev_ptr) {
+ current->prev_ptr->next_ptr = current;
+ } else {
+ from = current;
+ }
+
+ if (current->next_ptr) {
+ current->next_ptr->prev_ptr = current;
+ } else {
+ to = current;
+ }
+ } else {
+ current->prev_ptr = nullptr;
+ current->next_ptr = nullptr;
+ }
+
+ current = next;
+ }
+ _data->first = from;
+ _data->last = to;
+ }
+
+ template <class C>
+ struct AuxiliaryComparator {
+ C compare;
+ _FORCE_INLINE_ bool operator()(const Element *a, const Element *b) const {
+ return compare(a->value, b->value);
+ }
+ };
+
+ template <class C>
+ void sort_custom() {
+ //this version uses auxiliary memory for speed.
+ //if you don't want to use auxiliary memory, use the in_place version
+
+ int s = size();
+ if (s < 2) {
+ return;
+ }
+
+ Element **aux_buffer = memnew_arr(Element *, s);
+
+ int idx = 0;
+ for (Element *E = front(); E; E = E->next_ptr) {
+ aux_buffer[idx] = E;
+ idx++;
+ }
+
+ SortArray<Element *, AuxiliaryComparator<C>> sort;
+ sort.sort(aux_buffer, s);
+
+ _data->first = aux_buffer[0];
+ aux_buffer[0]->prev_ptr = nullptr;
+ aux_buffer[0]->next_ptr = aux_buffer[1];
+
+ _data->last = aux_buffer[s - 1];
+ aux_buffer[s - 1]->prev_ptr = aux_buffer[s - 2];
+ aux_buffer[s - 1]->next_ptr = nullptr;
+
+ for (int i = 1; i < s - 1; i++) {
+ aux_buffer[i]->prev_ptr = aux_buffer[i - 1];
+ aux_buffer[i]->next_ptr = aux_buffer[i + 1];
+ }
+
+ memdelete_arr(aux_buffer);
+ }
+
+ const void *id() const {
+ return (void *)_data;
+ }
+
+ /**
+ * copy constructor for the list
+ */
+ List(const List &p_list) {
+ const Element *it = p_list.front();
+ while (it) {
+ push_back(it->get());
+ it = it->next();
+ }
+ }
+
+ List() {}
+
+ ~List() {
+ clear();
+ if (_data) {
+ ERR_FAIL_COND(_data->size_cache);
+ memdelete_allocator<_Data, A>(_data);
+ }
+ }
+};
+
+#endif // LIST_H
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 03:17:06 +0000