Nebula
Loading...
Searching...
No Matches
fixedarray.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
12#include "core/types.h"
13#include "util/array.h"
14
15
16//------------------------------------------------------------------------------
17namespace Util
18{
19template<class TYPE, bool StackAlloc = false> class FixedArray
20{
21public:
23 typedef TYPE* Iterator;
24
28 FixedArray(const SizeT s);
30 FixedArray(const SizeT s, const TYPE& initialValue);
42 FixedArray(std::initializer_list<TYPE> list);
44 FixedArray(std::nullptr_t);
52 TYPE& operator[](IndexT index) const;
57
59 void SetSize(SizeT s);
61 const SizeT Size() const;
63 const SizeT ByteSize() const;
65 void Resize(SizeT newSize);
67 bool IsEmpty() const;
69 void Clear();
71 void Fill(const TYPE& val);
73 void Fill(IndexT first, SizeT num, const TYPE& val);
75 Iterator Begin() const;
77 Iterator End() const;
79 Iterator Find(const TYPE& val) const;
81 IndexT FindIndex(const TYPE& val) const;
83 void Sort();
85 IndexT BinarySearchIndex(const TYPE& val) const;
88
90 Iterator begin() const;
91 Iterator end() const;
92 size_t size() const;
93 void resize(size_t size);
94private:
95
96 template<class T, bool S>
97 friend class FixedArray;
98
100 void Delete();
102 void Alloc(SizeT s);
105
107 TYPE* elements;
108};
109
110
111//------------------------------------------------------------------------------
114template<class TYPE, bool StackAlloc>
116 count(0),
117 elements(nullptr)
118{
119 // empty
120}
121
122//------------------------------------------------------------------------------
125template<class TYPE, bool StackAlloc> void
127{
128 if (this->elements)
129 {
130 if constexpr (StackAlloc)
131 {
132 ArrayFreeStack(this->count, this->elements);
133 }
134 else
135 {
136 ArrayFree(this->count, this->elements);
137 }
138
139 this->elements = nullptr;
140
141 }
142 this->count = 0;
143}
144
145//------------------------------------------------------------------------------
148template<class TYPE, bool StackAlloc> void
150{
151 #if NEBULA_BOUNDSCHECKS
152 n_assert(0 == this->elements);
153 #endif
154 if (s > 0)
155 {
156 if constexpr (StackAlloc)
157 {
158 this->elements = ArrayAllocStack<TYPE>(s);
159 }
160 else
161 {
162 this->elements = ArrayAlloc<TYPE>(s);
163 }
164 }
165 this->count = s;
166}
167
168//------------------------------------------------------------------------------
172template<class TYPE, bool StackAlloc> void
174{
175 if (this->elements != rhs.elements && rhs.count > 0)
176 {
177 this->Alloc(rhs.count);
178 if constexpr (!std::is_trivially_copyable<TYPE>::value)
179 {
180 IndexT i;
181 for (i = 0; i < this->count; i++)
182 {
183 this->elements[i] = rhs.elements[i];
184 }
185 }
186 else
187 memcpy(this->elements, rhs.elements, this->count * sizeof(TYPE));
188 }
189}
190
191//------------------------------------------------------------------------------
194template<class TYPE, bool StackAlloc>
196 count(0),
197 elements(nullptr)
198{
199 this->Alloc(s);
200}
201
202//------------------------------------------------------------------------------
205template<class TYPE, bool StackAlloc>
206FixedArray<TYPE, StackAlloc>::FixedArray(const SizeT s, const TYPE& initialValue) :
207 count(0),
208 elements(nullptr)
209{
210 this->Alloc(s);
211 this->Fill(initialValue);
212}
213
214//------------------------------------------------------------------------------
217template<class TYPE, bool StackAlloc>
219 count(0),
220 elements(nullptr)
221{
222 if (this->elements != rhs.elements && rhs.count > 0)
223 {
224 this->Alloc(rhs.count);
225 if constexpr (!std::is_trivially_copyable<TYPE>::value)
226 {
227 IndexT i;
228 for (i = 0; i < this->count; i++)
229 {
230 this->elements[i] = rhs.elements[i];
231 }
232 }
233 else
234 memcpy(this->elements, rhs.elements, this->count * sizeof(TYPE));
235 }
236}
237
238//------------------------------------------------------------------------------
241template<class TYPE, bool StackAlloc>
243 count(0),
244 elements(nullptr)
245{
246 if (this->elements != rhs.elements && rhs.count > 0)
247 {
248 this->Alloc(rhs.count);
249 if constexpr (!std::is_trivially_copyable<TYPE>::value)
250 {
251 IndexT i;
252 for (i = 0; i < this->count; i++)
253 {
254 this->elements[i] = rhs.elements[i];
255 }
256 }
257 else
258 memcpy(this->elements, rhs.elements, this->count * sizeof(TYPE));
259 }
260}
261
262//------------------------------------------------------------------------------
265template<class TYPE, bool StackAlloc>
267 count(rhs.Size()),
268 elements(nullptr)
269{
270 if (this->count > 0)
271 {
272 this->Alloc(this->count);
273 if constexpr (!std::is_trivially_copyable<TYPE>::value)
274 {
275 IndexT i;
276 for (i = 0; i < this->count; i++)
277 {
278 this->elements[i] = rhs.Begin()[i];
279 }
280 }
281 else
282 memcpy(this->elements, rhs.Begin(), this->count * sizeof(TYPE));
283 }
284}
285
286//------------------------------------------------------------------------------
289template<class TYPE, bool StackAlloc>
291 : elements(nullptr)
292 , count(0)
293{
294 // If array lives on the stack, then we need to allocate
295 if (rhs.count > 0)
296 {
297 if (rhs.stackElements.data() == rhs.elements || StackAlloc)
298 {
299 this->Alloc(rhs.count);
300 if constexpr (!std::is_trivially_copyable<TYPE>::value)
301 {
302 IndexT i;
303 for (i = 0; i < this->count; i++)
304 {
305 this->elements[i] = rhs.Begin()[i];
306 }
307 }
308 else
309 memcpy(this->elements, rhs.Begin(), this->count * sizeof(TYPE));
310 }
311 else
312 {
313 this->elements = rhs.elements;
314 rhs.elements = nullptr;
315 this->count = rhs.count;
316 rhs.capacity = 0;
317 rhs.count = 0;
318 }
319 }
320}
321
322//------------------------------------------------------------------------------
325template<class TYPE, bool StackAlloc>
327 count(rhs.count),
328 elements(rhs.elements)
329{
330 if constexpr (StackAlloc)
331 {
332 this->Alloc(rhs.count);
333 if constexpr (!std::is_trivially_copyable<TYPE>::value)
334 {
335 IndexT i;
336 for (i = 0; i < this->count; i++)
337 {
338 this->elements[i] = rhs.Begin()[i];
339 }
340 }
341 else
342 memcpy(this->elements, rhs.Begin(), this->count * sizeof(TYPE));
343 }
344 else
345 {
346 rhs.count = 0;
347 rhs.elements = nullptr;
348 }
349}
350
351//------------------------------------------------------------------------------
354template<class TYPE, bool StackAlloc>
355FixedArray<TYPE, StackAlloc>::FixedArray(std::initializer_list<TYPE> list) :
356 count(0),
357 elements(nullptr)
358{
359 this->Alloc((SizeT)list.size());
360 if constexpr (!std::is_trivially_copyable<TYPE>::value)
361 {
362 IndexT i;
363 for (i = 0; i < this->count; i++)
364 {
365 this->elements[i] = list.begin()[i];
366 }
367 }
368 else
369 memcpy(this->elements, list.begin(), this->count * sizeof(TYPE));
370}
371
372//------------------------------------------------------------------------------
375template<class TYPE, bool StackAlloc>
377 count(0),
378 elements(nullptr)
379{
380}
381
382//------------------------------------------------------------------------------
385template<class TYPE, bool StackAlloc>
387{
388 this->Delete();
389}
390
391//------------------------------------------------------------------------------
394template<class TYPE, bool StackAlloc> void
396{
397 if (this != &rhs)
398 {
399 this->Delete();
400 this->Copy(rhs);
401 }
402}
403
404//------------------------------------------------------------------------------
407template<class TYPE, bool StackAlloc> void
409{
410 if (this != &rhs)
411 {
412 this->Delete();
413 this->elements = rhs.elements;
414 this->count = rhs.count;
415 rhs.elements = nullptr;
416 rhs.count = 0;
417 }
418}
419
420//------------------------------------------------------------------------------
423template<class TYPE, bool StackAlloc> TYPE&
425{
426 #if NEBULA_BOUNDSCHECKS
427 n_assert(this->elements && (index < this->count));
428 #endif
429 return this->elements[index];
430}
431
432//------------------------------------------------------------------------------
435template<class TYPE, bool StackAlloc> bool
437{
438 if (this->count != rhs.count)
439 {
440 return false;
441 }
442 else
443 {
444 #if NEBULA_BOUNDSCHECKS
445 n_assert(this->elements && rhs.elements);
446 #endif
447 IndexT i;
448 SizeT num = this->count;
449 for (i = 0; i < num; i++)
450 {
451 if (this->elements[i] != rhs.elements[i])
452 {
453 return false;
454 }
455 }
456 return true;
457 }
458}
459
460//------------------------------------------------------------------------------
463template<class TYPE, bool StackAlloc> bool
465{
466 return !(*this == rhs);
467}
468
469//------------------------------------------------------------------------------
472template<class TYPE, bool StackAlloc> void
474{
475 this->Delete();
476 this->Alloc(s);
477}
478
479//------------------------------------------------------------------------------
482template<class TYPE, bool StackAlloc> void
484{
485 // allocate new array and copy over old elements
486 if (newSize == this->count)
487 return;
488
489 TYPE* newElements = 0;
490 if (newSize > 0)
491 {
492 if constexpr (StackAlloc)
493 {
494 newElements = ArrayAllocStack<TYPE>(newSize);
495 }
496 else
497 {
498 newElements = ArrayAlloc<TYPE>(newSize);
499 }
500 SizeT numCopy = this->count;
501 if (numCopy > 0)
502 {
503 if (numCopy > newSize)
504 numCopy = newSize;
505 if constexpr (!std::is_trivially_move_assignable<TYPE>::value && std::is_move_assignable<TYPE>::value)
506 {
507 IndexT i;
508 for (i = 0; i < numCopy; i++)
509 {
510 newElements[i] = std::move(this->elements[i]);
511 }
512 }
513 else
514 {
515 Memory::MoveElements(this->elements, newElements, numCopy);
516 }
517 }
518 }
519
520 // delete old elements
521 this->Delete();
522
523 // set content to new elements
524 this->elements = newElements;
525 this->count = newSize;
526}
527
528//------------------------------------------------------------------------------
531template<class TYPE, bool StackAlloc> const SizeT
533{
534 return this->count;
535}
536
537//------------------------------------------------------------------------------
540template<class TYPE, bool StackAlloc> const SizeT
542{
543 return this->count * sizeof(TYPE);
544}
545
546//------------------------------------------------------------------------------
549template<class TYPE, bool StackAlloc> bool
551{
552 return 0 == this->count;
553}
554
555//------------------------------------------------------------------------------
558template<class TYPE, bool StackAlloc> void
560{
561 this->Delete();
562}
563
564//------------------------------------------------------------------------------
567template<class TYPE, bool StackAlloc> void
569{
570 IndexT i;
571 for (i = 0; i < this->count; i++)
572 {
573 this->elements[i] = val;
574 }
575}
576
577//------------------------------------------------------------------------------
580template<class TYPE, bool StackAlloc> void
582{
583 #if NEBULA_BOUNDSCHECKS
584 n_assert((first + num) <= this->count);
585 n_assert(0 != this->elements);
586 #endif
587 IndexT i;
588 for (i = first; i < (first + num); i++)
589 {
590 this->elements[i] = val;
591 }
592}
593
594//------------------------------------------------------------------------------
597template<class TYPE, bool StackAlloc> typename FixedArray<TYPE, StackAlloc>::Iterator
599{
600 return this->elements;
601}
602
603//------------------------------------------------------------------------------
606template<class TYPE, bool StackAlloc> typename FixedArray<TYPE, StackAlloc>::Iterator
608{
609 return this->elements + this->count;
610}
611
612//------------------------------------------------------------------------------
615template<class TYPE, bool StackAlloc> typename FixedArray<TYPE, StackAlloc>::Iterator
617{
618 IndexT i;
619 for (i = 0; i < this->count; i++)
620 {
621 if (elm == this->elements[i])
622 {
623 return &(this->elements[i]);
624 }
625 }
626 return 0;
627}
628
629//------------------------------------------------------------------------------
632template<class TYPE, bool StackAlloc> IndexT
634{
635 IndexT i;
636 for (i = 0; i < this->count; i++)
637 {
638 if (elm == this->elements[i])
639 {
640 return i;
641 }
642 }
643 return InvalidIndex;
644}
645
646//------------------------------------------------------------------------------
649template<class TYPE, bool StackAlloc> void
651{
652 std::sort(this->Begin(), this->End());
653}
654
655//------------------------------------------------------------------------------
659template<class TYPE, bool StackAlloc> IndexT
661{
662 SizeT num = this->Size();
663 if (num > 0)
664 {
665 IndexT half;
666 IndexT lo = 0;
667 IndexT hi = num - 1;
668 IndexT mid;
669 while (lo <= hi)
670 {
671 if (0 != (half = num/2))
672 {
673 mid = lo + ((num & 1) ? half : (half - 1));
674 if (elm < this->elements[mid])
675 {
676 hi = mid - 1;
677 num = num & 1 ? half : half - 1;
678 }
679 else if (elm > this->elements[mid])
680 {
681 lo = mid + 1;
682 num = half;
683 }
684 else
685 {
686 return mid;
687 }
688 }
689 else if (num)
690 {
691 if (elm != this->elements[lo])
692 {
693 return InvalidIndex;
694 }
695 else
696 {
697 return lo;
698 }
699 }
700 else
701 {
702 break;
703 }
704 }
705 }
706 return InvalidIndex;
707}
708
709//------------------------------------------------------------------------------
712template<class TYPE, bool StackAlloc> Array<TYPE>
714{
715 Array<TYPE> result;
716 result.Reserve(this->count);
717 IndexT i;
718 for (i = 0; i < this->count; i++)
719 {
720 result.Append(this->elements[i]);
721 }
722 return result;
723}
724
725//------------------------------------------------------------------------------
728template<class TYPE, bool StackAlloc> typename FixedArray<TYPE, StackAlloc>::Iterator
730{
731 return this->elements;
732}
733
734//------------------------------------------------------------------------------
737template<class TYPE, bool StackAlloc> typename FixedArray<TYPE, StackAlloc>::Iterator
739{
740 return this->elements + this->count;
741}
742
743//------------------------------------------------------------------------------
746template<class TYPE, bool StackAlloc> void
748{
749 if (s > this->capacity)
750 {
751 this->GrowTo(s);
752 }
753 this->count = s;
754}
755
756//------------------------------------------------------------------------------
759template<class TYPE, bool StackAlloc> size_t
761{
762 return this->count;
763}
764
765} // namespace Util
766//------------------------------------------------------------------------------
Definition half.h:20
Nebula's dynamic array class.
Definition array.h:60
void Reserve(SizeT num)
increase capacity to fit N more elements into the array.
Definition array.h:862
void Append(const TYPE &first, const ELEM_TYPE &... elements)
Append multiple elements to the end of the array.
Definition array.h:1334
Iterator Begin() const
return iterator to beginning of array
Definition array.h:1245
Implements a fixed size one-dimensional array.
Definition fixedarray.h:20
void Delete()
delete content
Definition fixedarray.h:126
void operator=(const FixedArray< TYPE, StackAlloc > &rhs)
assignment operator
Definition fixedarray.h:395
Iterator End() const
get iterator past last element
Definition fixedarray.h:607
IndexT BinarySearchIndex(const TYPE &val) const
do a binary search, requires a sorted array
Definition fixedarray.h:660
FixedArray(FixedArray< TYPE, StackAlloc > &&rhs)
move constructor
Definition fixedarray.h:326
TYPE & operator[](IndexT index) const
write [] operator
Definition fixedarray.h:424
Iterator Find(const TYPE &val) const
find identical element in unsorted array (slow)
Definition fixedarray.h:616
Array< TYPE > AsArray() const
return content as Array (slow!)
Definition fixedarray.h:713
void Fill(const TYPE &val)
fill the entire array with a value
Definition fixedarray.h:568
bool operator==(const FixedArray< TYPE, StackAlloc > &rhs) const
equality operator
Definition fixedarray.h:436
Iterator end() const
Definition fixedarray.h:738
FixedArray(const FixedArray< TYPE, false > &rhs)
copy constructor
Definition fixedarray.h:242
Iterator Begin() const
get iterator to first element
Definition fixedarray.h:598
FixedArray(const SizeT s)
constructor with size
Definition fixedarray.h:195
const SizeT ByteSize() const
get total byte size
Definition fixedarray.h:541
size_t size() const
Definition fixedarray.h:760
TYPE * Iterator
define element iterator
Definition fixedarray.h:23
const SizeT Size() const
get number of elements
Definition fixedarray.h:532
void resize(size_t size)
Definition fixedarray.h:747
FixedArray(const FixedArray< TYPE, true > &rhs)
copy constructor
Definition fixedarray.h:218
IndexT FindIndex(const TYPE &val) const
find index of identical element in unsorted array (slow)
Definition fixedarray.h:633
void operator=(FixedArray< TYPE, StackAlloc > &&rhs) noexcept
move assignment operator
Definition fixedarray.h:408
bool operator!=(const FixedArray< TYPE, StackAlloc > &rhs) const
inequality operator
Definition fixedarray.h:464
void Clear()
clear the array, free elements
Definition fixedarray.h:559
FixedArray()
default constructor
Definition fixedarray.h:115
FixedArray(std::initializer_list< TYPE > list)
constructor from initializer list
Definition fixedarray.h:355
bool IsEmpty() const
return true if array if empty (has no elements)
Definition fixedarray.h:550
void Fill(IndexT first, SizeT num, const TYPE &val)
fill array range with element
Definition fixedarray.h:581
FixedArray(const Array< TYPE > &rhs)
construct from array
Definition fixedarray.h:266
void Resize(SizeT newSize)
resize array without deleting existing content
Definition fixedarray.h:483
void SetSize(SizeT s)
set number of elements (clears existing content)
Definition fixedarray.h:473
~FixedArray()
destructor
Definition fixedarray.h:386
TYPE * elements
Definition fixedarray.h:107
void Copy(const FixedArray< TYPE, StackAlloc > &src)
copy content
Definition fixedarray.h:173
friend class FixedArray
Definition fixedarray.h:97
void Alloc(SizeT s)
allocate array for given size
Definition fixedarray.h:149
FixedArray(const SizeT s, const TYPE &initialValue)
constructor with size and initial value
Definition fixedarray.h:206
FixedArray(std::nullptr_t)
construct an empty fixed array
Definition fixedarray.h:376
SizeT count
Definition fixedarray.h:106
FixedArray(Array< TYPE > &&rhs)
move from array
Definition fixedarray.h:290
Iterator begin() const
for range-based iteration (C++11)
Definition fixedarray.h:729
void Sort()
sort the array
Definition fixedarray.h:650
#define n_assert(exp)
Definition debug.h:50
void ArrayFreeStack(size_t size, TYPE *buffer)
Definition memory.h:111
TYPE * ArrayAllocStack(size_t size)
Definition memory.h:75
void ArrayFree(size_t size, TYPE *buffer)
Definition memory.h:94
TYPE * ArrayAlloc(size_t size)
Definition memory.h:57
__forceinline void MoveElements(const T *from, T *to, size_t numElements)
Move a chunk of memory, can handle overlapping regions.
Definition posixmemory.h:192
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
#define StackAlloc(size)
Definition posixmemory.h:30
static const int InvalidIndex
Definition types.h:54
int SizeT
Definition types.h:49
int IndexT
Definition types.h:48