1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5#include "Prerequisites/BsPrerequisitesUtil.h"
6
7namespace bs
8{
9 /** @addtogroup General
10 * @{
11 */
12
13 /** Dynamically sized array, similar to std::vector. */
14 template <class Type>
15 class DynArray final
16 {
17 public:
18 typedef Type ValueType;
19 typedef Type* Iterator;
20 typedef const Type* ConstIterator;
21 typedef std::reverse_iterator<Type*> ReverseIterator;
22 typedef std::reverse_iterator<const Type*> ConstReverseIterator;
23 typedef ptrdiff_t DifferenceType;
24
25 DynArray() = default;
26 DynArray(UINT32 size, const ValueType& value = ValueType())
27 {
28 append(size, value);
29 }
30
31 DynArray(Iterator first, Iterator last)
32 {
33 append(first, last);
34 }
35
36 DynArray(std::initializer_list<ValueType> list)
37 {
38 append(list);
39 }
40
41 DynArray(const DynArray<ValueType>& other)
42 {
43 if (!other.empty())
44 *this = other;
45 }
46
47 DynArray(DynArray<ValueType>&& other)
48 {
49 if (!other.empty())
50 *this = std::move(other);
51 }
52
53 ~DynArray()
54 {
55 for (auto& entry : *this)
56 entry.~Type();
57
58 bs_free(mElements);
59 }
60
61 DynArray<ValueType>& operator= (const DynArray<ValueType>& other)
62 {
63 if (this == &other)
64 return *this;
65
66 UINT32 mySize = size();
67 const UINT32 otherSize = other.size();
68
69 // Use assignment copy if we have more elements than the other array, and destroy any excess elements
70 if(mySize > otherSize)
71 {
72 Iterator newEnd;
73 if(otherSize > 0)
74 newEnd = std::copy(other.begin(), other.end(), begin());
75 else
76 newEnd = begin();
77
78 for(;newEnd != end(); ++newEnd)
79 (*newEnd).~Type();
80
81 }
82 // Otherwise we need to partially copy (up to our size), and do uninitialized copy for rest. And an optional
83 // grow if our capacity isn't enough (in which case we do uninitialized copy for all).
84 else
85 {
86 if (otherSize > mCapacity)
87 {
88 clear();
89 mySize = 0;
90
91 realloc(otherSize);
92 }
93 else if (mySize > 0)
94 std::copy(other.begin(), other.begin() + mySize, begin());
95
96 std::uninitialized_copy(other.begin() + mySize, other.end(), begin() + mySize);
97 }
98
99 mSize = otherSize;
100 return *this;
101 }
102
103 DynArray<ValueType>& operator= (DynArray<ValueType>&& other)
104 {
105 if(this == &other)
106 return *this;
107
108 // Just steal the buffer
109 for (auto& entry : *this)
110 entry.~Type();
111
112 bs_free(mElements);
113
114 mElements = std::exchange(other.mElements, nullptr);
115 mSize = std::exchange(other.mSize, 0);
116 mCapacity = std::exchange(other.mCapacity, 0);
117
118 return *this;
119 }
120
121 DynArray<ValueType>& operator= (std::initializer_list<ValueType> list)
122 {
123 UINT32 mySize = size();
124 const UINT32 otherSize = (UINT32)list.size();
125
126 // Use assignment copy if we have more elements than the list, and destroy any excess elements
127 if(mySize > otherSize)
128 {
129 Iterator newEnd;
130 if(otherSize > 0)
131 newEnd = std::copy(list.begin(), list.end(), begin());
132 else
133 newEnd = begin();
134
135 for(;newEnd != end(); ++newEnd)
136 (*newEnd).~Type();
137
138 }
139 // Otherwise we need to partially copy (up to our size), and do uninitialized copy for rest. And an optional
140 // grow if our capacity isn't enough (in which case we do uninitialized copy for all).
141 else
142 {
143 if (otherSize > mCapacity)
144 {
145 clear();
146 mySize = 0;
147
148 realloc(otherSize);
149 }
150 else if (mySize > 0)
151 std::copy(list.begin(), list.begin() + mySize, begin());
152
153 std::uninitialized_copy(list.begin() + mySize, list.end(), begin() + mySize);
154 }
155
156 mSize = otherSize;
157 return *this;
158 }
159
160 bool operator== (const DynArray<ValueType>& other) const
161 {
162 if (this->size() != other.size()) return false;
163 return std::equal(this->begin(), this->end(), other.begin());
164 }
165
166 bool operator!= (const DynArray<ValueType>& other) const
167 {
168 return !(*this == other);
169 }
170
171 bool operator< (const DynArray<ValueType>& other) const
172 {
173 return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
174 }
175
176 bool operator> (const DynArray<ValueType>& other) const
177 {
178 return other < *this;
179 }
180
181 bool operator<= (const DynArray<ValueType>& other) const
182 {
183 return !(other < *this);
184 }
185
186 bool operator>= (const DynArray<ValueType>& other) const
187 {
188 return !(*this < other);
189 }
190
191 Type& operator[] (UINT32 index)
192 {
193 assert(index < mSize && "Array index out-of-range.");
194
195 return mElements[index];
196 }
197
198 const Type& operator[] (UINT32 index) const
199 {
200 assert(index < mSize && "Array index out-of-range.");
201
202 return mElements[index];
203 }
204
205 bool empty() const { return mSize == 0; }
206
207 Iterator begin() { return mElements; }
208 Iterator end() { return mElements + mSize; }
209
210 ConstIterator begin() const { return mElements; }
211 ConstIterator end() const { return mElements + mSize; }
212
213 ConstIterator cbegin() const { return mElements; }
214 ConstIterator cend() const { return mElements + mSize; }
215
216 ReverseIterator rbegin() { return ReverseIterator(end()); }
217 ReverseIterator rend() { return ReverseIterator(begin()); }
218
219 ConstReverseIterator rbegin() const { return ReverseIterator(end()); }
220 ConstReverseIterator rend() const { return ReverseIterator(begin()); }
221
222 ConstReverseIterator crbegin() const { return ReverseIterator(end()); }
223 ConstReverseIterator crend() const { return ReverseIterator(begin()); }
224
225 UINT32 size() const { return mSize; }
226 UINT32 capacity() const { return mCapacity; }
227
228 Type* data() { return mElements; }
229 const Type* data() const { return mElements; }
230
231 Type& front()
232 {
233 assert(!empty());
234 return *mElements[0];
235 }
236
237 Type& back()
238 {
239 assert(!empty());
240 return *mElements[mSize - 1];
241 }
242
243 const Type& front() const
244 {
245 assert(!empty());
246 return mElements[0];
247 }
248
249 const Type& back() const
250 {
251 assert(!empty());
252 return mElements[mSize - 1];
253 }
254
255 void add(const Type& element)
256 {
257 if (size() == capacity())
258 realloc(std::max(1U, capacity() * 2));
259
260 new (&mElements[mSize++]) Type(element);
261 }
262
263 void add(Type&& element)
264 {
265 if (size() == capacity())
266 realloc(std::max(1U, capacity() * 2));
267
268 new (&mElements[mSize++]) Type(std::move(element));
269 }
270
271 void pop()
272 {
273 assert(mSize > 0 && "Popping an empty array.");
274 --mSize;
275 mElements[mSize].~Type();
276 }
277
278 void remove(UINT32 index)
279 {
280 erase(begin() + index);
281 }
282
283 bool contains(const Type& element)
284 {
285 for (UINT32 i = 0; i < mSize; i++)
286 {
287 if (mElements[i] == element)
288 return true;
289 }
290
291 return false;
292 }
293
294 void removeValue(const Type& element)
295 {
296 for (UINT32 i = 0; i < mSize; i++)
297 {
298 if (mElements[i] == element)
299 {
300 remove(i);
301 break;
302 }
303 }
304 }
305
306 void clear()
307 {
308 for (UINT32 i = 0; i < mSize; ++i)
309 mElements[i].~Type();
310
311 mSize = 0;
312 }
313
314 void resize(UINT32 size, const Type& value = Type())
315 {
316 if (size > capacity())
317 realloc(size);
318
319 if (size > mSize)
320 {
321 for (UINT32 i = mSize; i < size; i++)
322 new (&mElements[i]) Type(value);
323 }
324 else
325 {
326 for (UINT32 i = size; i < mSize; i++)
327 mElements[i].~Type();
328 }
329
330 mSize = size;
331 }
332
333 void reserve(UINT32 size)
334 {
335 if (size > capacity())
336 realloc(size);
337 }
338
339 void shrink()
340 {
341 realloc(mSize);
342 }
343
344 void append(ConstIterator start, ConstIterator end)
345 {
346 const UINT32 count = (UINT32)std::distance(start, end);
347
348 if ((size() + count) > capacity())
349 realloc(size() + count);
350
351 std::uninitialized_copy(start, end, this->end());
352 mSize += count;
353 }
354
355 void append(UINT32 count, const Type& element)
356 {
357 if ((size() + count) > capacity())
358 realloc(size() + count);
359
360 std::uninitialized_fill_n(end(), count, element);
361 mSize += count;
362 }
363
364 void append(std::initializer_list<Type> list)
365 {
366 append(list.begin(), list.end());
367 }
368
369 void swap(DynArray<ValueType>& other)
370 {
371 const UINT32 tmpSize = size();
372 const UINT32 tmpCapacity = capacity();
373 Type* tmp = data();
374
375 mSize = other.size();
376 mCapacity = other.capacity();
377 mElements = other.data();
378
379 other.mSize = tmpSize;
380 other.mCapacity = tmpCapacity;
381 other.mElements = tmp;
382 }
383
384 bool swapAndErase(Iterator iter)
385 {
386 assert(!empty());
387
388 auto iterLast = end() - 1;
389
390 bool swapped = false;
391 if (iter != iterLast)
392 {
393 std::swap(*iter, *iterLast);
394 swapped = true;
395 }
396
397 pop();
398 return swapped;
399 }
400
401 template <typename ...Args>
402 void emplaceBack(Args&& ...args)
403 {
404 if (size() == capacity())
405 realloc(std::max(1U, capacity() * 2));
406
407 new (&mElements[mSize++]) Type(std::forward<Args>(args) ...);
408 }
409
410 template <typename ...Args>
411 Iterator emplace(ConstIterator it, Args&&... args)
412 {
413 Iterator iterc = const_cast<Iterator>(it);
414 DifferenceType offset = iterc - begin();
415
416 if (size() == capacity())
417 realloc(std::max(1U, capacity() * 2));
418
419 new (&mElements[mSize++]) Type(std::forward<Args>(args) ...);
420 std::rotate(begin() + offset, end() - 1, end());
421
422 return begin() + offset;
423 }
424
425 Iterator insert(ConstIterator it, const ValueType& element)
426 {
427 Iterator iterc = const_cast<Iterator>(it);
428 DifferenceType offset = iterc - begin();
429
430 if (size() == capacity())
431 realloc(std::max(1U, capacity() * 2));
432
433 new (&mElements[mSize++]) Type(element);
434 std::rotate(begin() + offset, end() - 1, end());
435
436 return begin() + offset;
437 }
438
439 Iterator insert(ConstIterator it, ValueType&& element)
440 {
441 Iterator iterc = const_cast<Iterator>(it);
442 DifferenceType offset = iterc - begin();
443
444 if (size() == capacity())
445 realloc(std::max(1U, capacity() * 2));
446
447 new (&mElements[mSize++]) Type(std::move(element));
448 std::rotate(begin() + offset, end() - 1, end());
449
450 return begin() + offset;
451 }
452
453 Iterator insert(ConstIterator it, UINT32 n, const ValueType& element)
454 {
455 Iterator iterc = const_cast<Iterator>(it);
456 DifferenceType offset = iterc - begin();
457 Iterator iter = &mElements[offset];
458
459 if (!n)
460 return iter;
461
462 if (size() + n > capacity())
463 realloc((size() + n) * 2);
464
465 UINT32 c = n;
466 while (c--)
467 new (&mElements[mSize++]) Type(element);
468
469 std::rotate(begin() + offset, end() - n, end());
470
471 return begin() + offset;
472 }
473
474 template <typename InputIt>
475 typename std::enable_if<!std::is_integral<InputIt>::value, void>::type insert(ConstIterator it,
476 InputIt first, InputIt last)
477 {
478 Iterator iterc = const_cast<Iterator>(it);
479 DifferenceType offset = iterc - begin();
480 UINT32 n = (UINT32)(last - first);
481
482 if (size() + n > capacity())
483 realloc((size() + n) * 2);
484
485 while (first != last)
486 new (&mElements[mSize++]) Type(*first++);
487
488 std::rotate(begin() + offset, end() - n, end());
489 }
490
491 Iterator insert(ConstIterator it, std::initializer_list<ValueType> list)
492 {
493 Iterator iterc = const_cast<Iterator>(it);
494 DifferenceType offset = iterc - begin();
495 Iterator iter = &mElements[offset];
496 UINT32 n = (UINT32)list.size();
497
498 if (!n)
499 return iter;
500
501 if (size() + n > capacity())
502 realloc((size() + n) * 2);
503
504 for (auto& entry : list)
505 new (&mElements[mSize++]) Type(entry);
506
507 std::rotate(begin() + offset, end() - n, end());
508
509 return iter;
510 }
511
512 Iterator erase(ConstIterator first, ConstIterator last)
513 {
514 assert(first >= begin() && "Iterator to insert is out of bounds.");
515 assert(last < end() && "Inserting at past-the-end iterator.");
516
517 Iterator iter = const_cast<Iterator>(first);
518
519 if (first == last)
520 return iter;
521
522 Iterator iterLast = const_cast<Iterator>(last);
523 std::move(iterLast, end(), iter);
524
525 for (Iterator it = iter; it < iterLast; ++it)
526 pop();
527
528 return iter;
529 }
530
531 Iterator erase(ConstIterator it)
532 {
533 assert(it >= begin() && "Iterator to erase is out of bounds.");
534 assert(it < end() && "Erasing at past-the-end iterator.");
535
536 Iterator toErase = const_cast<Iterator>(it);
537 std::move(toErase + 1, end(), toErase);
538 pop();
539
540 return toErase;
541 }
542
543 private:
544 void realloc(UINT32 capacity)
545 {
546 Type* buffer = bs_allocN<Type>(capacity);
547
548 if (mElements)
549 {
550 std::uninitialized_copy(
551 std::make_move_iterator(begin()),
552 std::make_move_iterator(end()),
553 buffer);
554
555 for(auto& entry : *this)
556 entry.~Type();
557
558 bs_free(mElements);
559 }
560
561 mElements = buffer;
562 mCapacity = capacity;
563 }
564
565 Type* mElements = nullptr;
566 UINT32 mSize = 0;
567 UINT32 mCapacity = 0;
568 };
569
570 /** @} */
571}
572