1/**************************************************************************/
2/* vector.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 VECTOR_H
32#define VECTOR_H
33
34/**
35 * @class Vector
36 * Vector container. Regular Vector Container. Use with care and for smaller arrays when possible. Use Vector for large arrays.
37 */
38
39#include "core/error/error_macros.h"
40#include "core/os/memory.h"
41#include "core/templates/cowdata.h"
42#include "core/templates/search_array.h"
43#include "core/templates/sort_array.h"
44
45#include <climits>
46#include <initializer_list>
47
48template <class T>
49class VectorWriteProxy {
50public:
51 _FORCE_INLINE_ T &operator[](int p_index) {
52 CRASH_BAD_INDEX(p_index, ((Vector<T> *)(this))->_cowdata.size());
53
54 return ((Vector<T> *)(this))->_cowdata.ptrw()[p_index];
55 }
56};
57
58template <class T>
59class Vector {
60 friend class VectorWriteProxy<T>;
61
62public:
63 VectorWriteProxy<T> write;
64
65private:
66 CowData<T> _cowdata;
67
68public:
69 bool push_back(T p_elem);
70 _FORCE_INLINE_ bool append(const T &p_elem) { return push_back(p_elem); } //alias
71 void fill(T p_elem);
72
73 void remove_at(int p_index) { _cowdata.remove_at(p_index); }
74 _FORCE_INLINE_ bool erase(const T &p_val) {
75 int idx = find(p_val);
76 if (idx >= 0) {
77 remove_at(idx);
78 return true;
79 }
80 return false;
81 }
82
83 void reverse();
84
85 _FORCE_INLINE_ T *ptrw() { return _cowdata.ptrw(); }
86 _FORCE_INLINE_ const T *ptr() const { return _cowdata.ptr(); }
87 _FORCE_INLINE_ void clear() { resize(0); }
88 _FORCE_INLINE_ bool is_empty() const { return _cowdata.is_empty(); }
89
90 _FORCE_INLINE_ T get(int p_index) { return _cowdata.get(p_index); }
91 _FORCE_INLINE_ const T &get(int p_index) const { return _cowdata.get(p_index); }
92 _FORCE_INLINE_ void set(int p_index, const T &p_elem) { _cowdata.set(p_index, p_elem); }
93 _FORCE_INLINE_ int size() const { return _cowdata.size(); }
94 Error resize(int p_size) { return _cowdata.resize(p_size); }
95 Error resize_zeroed(int p_size) { return _cowdata.template resize<true>(p_size); }
96 _FORCE_INLINE_ const T &operator[](int p_index) const { return _cowdata.get(p_index); }
97 Error insert(int p_pos, T p_val) { return _cowdata.insert(p_pos, p_val); }
98 int find(const T &p_val, int p_from = 0) const { return _cowdata.find(p_val, p_from); }
99 int rfind(const T &p_val, int p_from = -1) const { return _cowdata.rfind(p_val, p_from); }
100 int count(const T &p_val) const { return _cowdata.count(p_val); }
101
102 void append_array(Vector<T> p_other);
103
104 _FORCE_INLINE_ bool has(const T &p_val) const { return find(p_val) != -1; }
105
106 void sort() {
107 sort_custom<_DefaultComparator<T>>();
108 }
109
110 template <class Comparator, bool Validate = SORT_ARRAY_VALIDATE_ENABLED, class... Args>
111 void sort_custom(Args &&...args) {
112 int len = _cowdata.size();
113 if (len == 0) {
114 return;
115 }
116
117 T *data = ptrw();
118 SortArray<T, Comparator, Validate> sorter{ args... };
119 sorter.sort(data, len);
120 }
121
122 int bsearch(const T &p_value, bool p_before) {
123 return bsearch_custom<_DefaultComparator<T>>(p_value, p_before);
124 }
125
126 template <class Comparator, class Value, class... Args>
127 int bsearch_custom(const Value &p_value, bool p_before, Args &&...args) {
128 SearchArray<T, Comparator> search{ args... };
129 return search.bisect(ptrw(), size(), p_value, p_before);
130 }
131
132 Vector<T> duplicate() {
133 return *this;
134 }
135
136 void ordered_insert(const T &p_val) {
137 int i;
138 for (i = 0; i < _cowdata.size(); i++) {
139 if (p_val < operator[](i)) {
140 break;
141 }
142 }
143 insert(i, p_val);
144 }
145
146 inline void operator=(const Vector &p_from) {
147 _cowdata._ref(p_from._cowdata);
148 }
149
150 Vector<uint8_t> to_byte_array() const {
151 Vector<uint8_t> ret;
152 if (is_empty()) {
153 return ret;
154 }
155 ret.resize(size() * sizeof(T));
156 memcpy(ret.ptrw(), ptr(), sizeof(T) * size());
157 return ret;
158 }
159
160 Vector<T> slice(int p_begin, int p_end = INT_MAX) const {
161 Vector<T> result;
162
163 const int s = size();
164
165 int begin = CLAMP(p_begin, -s, s);
166 if (begin < 0) {
167 begin += s;
168 }
169 int end = CLAMP(p_end, -s, s);
170 if (end < 0) {
171 end += s;
172 }
173
174 ERR_FAIL_COND_V(begin > end, result);
175
176 int result_size = end - begin;
177 result.resize(result_size);
178
179 const T *const r = ptr();
180 T *const w = result.ptrw();
181 for (int i = 0; i < result_size; ++i) {
182 w[i] = r[begin + i];
183 }
184
185 return result;
186 }
187
188 bool operator==(const Vector<T> &p_arr) const {
189 int s = size();
190 if (s != p_arr.size()) {
191 return false;
192 }
193 for (int i = 0; i < s; i++) {
194 if (operator[](i) != p_arr[i]) {
195 return false;
196 }
197 }
198 return true;
199 }
200
201 bool operator!=(const Vector<T> &p_arr) const {
202 int s = size();
203 if (s != p_arr.size()) {
204 return true;
205 }
206 for (int i = 0; i < s; i++) {
207 if (operator[](i) != p_arr[i]) {
208 return true;
209 }
210 }
211 return false;
212 }
213
214 struct Iterator {
215 _FORCE_INLINE_ T &operator*() const {
216 return *elem_ptr;
217 }
218 _FORCE_INLINE_ T *operator->() const { return elem_ptr; }
219 _FORCE_INLINE_ Iterator &operator++() {
220 elem_ptr++;
221 return *this;
222 }
223 _FORCE_INLINE_ Iterator &operator--() {
224 elem_ptr--;
225 return *this;
226 }
227
228 _FORCE_INLINE_ bool operator==(const Iterator &b) const { return elem_ptr == b.elem_ptr; }
229 _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return elem_ptr != b.elem_ptr; }
230
231 Iterator(T *p_ptr) { elem_ptr = p_ptr; }
232 Iterator() {}
233 Iterator(const Iterator &p_it) { elem_ptr = p_it.elem_ptr; }
234
235 private:
236 T *elem_ptr = nullptr;
237 };
238
239 struct ConstIterator {
240 _FORCE_INLINE_ const T &operator*() const {
241 return *elem_ptr;
242 }
243 _FORCE_INLINE_ const T *operator->() const { return elem_ptr; }
244 _FORCE_INLINE_ ConstIterator &operator++() {
245 elem_ptr++;
246 return *this;
247 }
248 _FORCE_INLINE_ ConstIterator &operator--() {
249 elem_ptr--;
250 return *this;
251 }
252
253 _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return elem_ptr == b.elem_ptr; }
254 _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return elem_ptr != b.elem_ptr; }
255
256 ConstIterator(const T *p_ptr) { elem_ptr = p_ptr; }
257 ConstIterator() {}
258 ConstIterator(const ConstIterator &p_it) { elem_ptr = p_it.elem_ptr; }
259
260 private:
261 const T *elem_ptr = nullptr;
262 };
263
264 _FORCE_INLINE_ Iterator begin() {
265 return Iterator(ptrw());
266 }
267 _FORCE_INLINE_ Iterator end() {
268 return Iterator(ptrw() + size());
269 }
270
271 _FORCE_INLINE_ ConstIterator begin() const {
272 return ConstIterator(ptr());
273 }
274 _FORCE_INLINE_ ConstIterator end() const {
275 return ConstIterator(ptr() + size());
276 }
277
278 _FORCE_INLINE_ Vector() {}
279 _FORCE_INLINE_ Vector(std::initializer_list<T> p_init) {
280 Error err = _cowdata.resize(p_init.size());
281 ERR_FAIL_COND(err);
282
283 int i = 0;
284 for (const T &element : p_init) {
285 _cowdata.set(i++, element);
286 }
287 }
288 _FORCE_INLINE_ Vector(const Vector &p_from) { _cowdata._ref(p_from._cowdata); }
289
290 _FORCE_INLINE_ ~Vector() {}
291};
292
293template <class T>
294void Vector<T>::reverse() {
295 for (int i = 0; i < size() / 2; i++) {
296 T *p = ptrw();
297 SWAP(p[i], p[size() - i - 1]);
298 }
299}
300
301template <class T>
302void Vector<T>::append_array(Vector<T> p_other) {
303 const int ds = p_other.size();
304 if (ds == 0) {
305 return;
306 }
307 const int bs = size();
308 resize(bs + ds);
309 for (int i = 0; i < ds; ++i) {
310 ptrw()[bs + i] = p_other[i];
311 }
312}
313
314template <class T>
315bool Vector<T>::push_back(T p_elem) {
316 Error err = resize(size() + 1);
317 ERR_FAIL_COND_V(err, true);
318 set(size() - 1, p_elem);
319
320 return false;
321}
322
323template <class T>
324void Vector<T>::fill(T p_elem) {
325 T *p = ptrw();
326 for (int i = 0; i < size(); i++) {
327 p[i] = p_elem;
328 }
329}
330
331#endif // VECTOR_H
332