53 template<
typename T> T
As()
const;
56 template <
typename ...ELEM_TYPE>
59 void Append(
const TYPE& elm);
115 template <
typename KEYTYPE>
IndexT FindIndex(
typename std::enable_if<true, const KEYTYPE&>::type elm)
const;
129 template <
typename KEYTYPE>
IndexT BinarySearchIndex(
typename std::enable_if<true, const KEYTYPE&>::type elm)
const;
163template<
class TYPE,
int STACK_SIZE>
166 capacity(STACK_SIZE),
168 elements(smallVector)
176template<
class TYPE,
int STACK_SIZE>
206template<
class TYPE,
int STACK_SIZE>
209 capacity(initialSize),
227 for (i = 0; i < this->
capacity; i++)
242template<
class TYPE,
int STACK_SIZE>
245 capacity((
SizeT)list.size()),
246 count((
SizeT)list.size())
259 for (i = 0; i < this->
count; i++)
261 this->
elements[i] = list.begin()[i];
274template<
class TYPE,
int STACK_SIZE>
279 elements(smallVector)
287template<
class TYPE,
int STACK_SIZE>
290 this->capacity = rhs.capacity;
291 this->count = rhs.count;
292 this->grow = rhs.grow;
294 if (this->capacity <= STACK_SIZE)
296 for (
IndexT i = 0; i < rhs.count; ++i)
298 this->smallVector[i] = rhs.smallVector[i];
301 this->elements = this->smallVector;
304 this->elements = rhs.elements;
308 rhs.elements =
nullptr;
314template<
class TYPE,
int STACK_SIZE>
void
317 #if NEBULA_BOUNDSCHECKS
318 if (this->elements != this->smallVector)
322 this->grow = src.
grow;
323 this->capacity = src.
count;
324 this->count = src.
count;
325 if (this->capacity > 0)
327 if (this->capacity > STACK_SIZE)
328 this->elements =
new TYPE[this->capacity];
330 this->elements = smallVector;
333 for (i = 0; i < this->count; i++)
335 this->elements[i] = src.
elements[i];
343template<
class TYPE,
int STACK_SIZE>
void
351 if (this->elements != this->smallVector)
352 delete[] this->elements;
354 this->elements = this->smallVector;
361template<
class TYPE,
int STACK_SIZE>
void
370template<
class TYPE,
int STACK_SIZE>
379template<
class TYPE,
int STACK_SIZE>
void
384 this->capacity = _capacity;
386 if (this->capacity > 0)
388 if (this->capacity > STACK_SIZE)
389 this->elements =
new TYPE[this->capacity];
391 this->elements = smallVector;
395 this->elements = smallVector;
402template<
class TYPE,
int STACK_SIZE>
void
407 if ((this->capacity > 0) && (rhs.
count <= this->capacity))
412 for (i = 0; i < rhs.
count; i++)
414 this->elements[i] = rhs.
elements[i];
418 for (; i < this->count; i++)
420 this->Destroy(&(this->elements[i]));
422 this->grow = rhs.
grow;
423 this->count = rhs.
count;
437template<
class TYPE,
int STACK_SIZE>
440 if (this->elements && this->capacity > STACK_SIZE)
441 delete[] this->elements;
443 this->capacity = rhs.capacity;
444 this->count = rhs.count;
445 this->grow = rhs.grow;
447 if (this->capacity <= STACK_SIZE)
449 for (
IndexT i = 0; i < rhs.count; ++i)
451 this->smallVector[i] = rhs.smallVector[i];
454 this->elements = this->smallVector;
457 this->elements = rhs.elements;
461 rhs.elements =
nullptr;
467template<
class TYPE,
int STACK_SIZE>
void
470 if (newCapacity > STACK_SIZE)
472 TYPE* newArray =
new TYPE[newCapacity];
477 for (i = 0; i < this->count; i++)
479 newArray[i] = this->elements[i];
483 if (this->elements != this->smallVector)
484 delete[] this->elements;
486 this->elements = newArray;
488 this->capacity = newCapacity;
495template<
class TYPE,
int STACK_SIZE>
void
498 #if NEBULA_BOUNDSCHECKS
503 if (0 == this->capacity)
505 growToSize = this->grow;
510 SizeT growBy = this->capacity >> 1;
513 growBy = MinGrowSize;
515 else if (growBy > MaxGrowSize)
517 growBy = MaxGrowSize;
519 growToSize = this->capacity + growBy;
521 this->GrowTo(growToSize);
529template<
class TYPE,
int STACK_SIZE>
void
532 #if NEBULA_BOUNDSCHECKS
538 if (fromIndex == toIndex)
544 SizeT num = this->count - fromIndex;
547 SizeT neededSize = toIndex + num;
548 while (neededSize > this->capacity)
553 if (fromIndex > toIndex)
557 for (i = 0; i < num; i++)
559 this->elements[toIndex + i] = this->elements[fromIndex + i];
563 for (i = (fromIndex + i) - 1; i < this->count; i++)
565 this->Destroy(&(this->elements[i]));
572 for (i = num - 1; i >= 0; --i)
574 this->elements[toIndex + i] = this->elements[fromIndex + i];
578 for (i =
int(fromIndex); i < int(toIndex); i++)
580 this->Destroy(&(this->elements[i]));
585 this->count = toIndex + num;
591template<
class TYPE,
int STACK_SIZE>
void
595 if (this->count == this->capacity)
599 #if NEBULA_BOUNDSCHECKS
602 this->elements[this->count++] = elm;
608template<
class TYPE,
int STACK_SIZE>
inline void
612 if (this->count == this->capacity)
616#if NEBULA_BOUNDSCHECKS
619 this->elements[this->count++] = std::forward<TYPE>(elm);
625template<
class TYPE,
int STACK_SIZE>
void
628 SizeT neededCapacity = this->count + rhs.
count;
629 if (neededCapacity > this->capacity)
631 this->GrowTo(neededCapacity);
636 for (i = 0; i < rhs.
count; i++)
638 this->elements[this->count + i] = std::forward<TYPE>(rhs.
elements[i]);
640 this->count += rhs.
count;
646template<
class TYPE,
int STACK_SIZE>
void
649 SizeT neededCapacity = this->count + count;
650 if (neededCapacity > this->capacity)
652 this->GrowTo(neededCapacity);
657 for (i = 0; i < count; i++)
659 this->elements[this->count + i] = std::forward<TYPE>(arr[i]);
661 this->count += count;
674template<
class TYPE,
int STACK_SIZE>
void
677 #if NEBULA_BOUNDSCHECKS
680 SizeT neededCapacity = this->count + num;
681 if (neededCapacity > this->capacity)
683 this->GrowTo(neededCapacity);
690template<
class TYPE,
int STACK_SIZE>
const SizeT
699template<
class TYPE,
int STACK_SIZE>
const SizeT
702 return this->count *
sizeof(TYPE);
708template<
class TYPE,
int STACK_SIZE>
const SizeT
711 return this->capacity;
719template<
class TYPE,
int STACK_SIZE> TYPE&
722 #if NEBULA_BOUNDSCHECKS
723 n_assert(this->elements && (index < this->count));
725 return this->elements[index];
733template<
class TYPE,
int STACK_SIZE>
bool
736 if (rhs.
Size() == this->Size())
739 SizeT num = this->Size();
740 for (i = 0; i < num; i++)
742 if (!(this->elements[i] == rhs.
elements[i]))
760template<
class TYPE,
int STACK_SIZE>
bool
763 return !(*
this == rhs);
769template<
class TYPE,
int STACK_SIZE> TYPE&
772 #if NEBULA_BOUNDSCHECKS
773 n_assert(this->elements && (this->count > 0));
775 return this->elements[0];
781template<
class TYPE,
int STACK_SIZE> TYPE&
784 #if NEBULA_BOUNDSCHECKS
785 n_assert(this->elements && (this->count > 0));
787 return this->elements[this->count - 1];
793template<
class TYPE,
int STACK_SIZE>
bool
796 return (this->count == 0);
802template<
class TYPE,
int STACK_SIZE>
void
805 #if NEBULA_BOUNDSCHECKS
806 n_assert(this->elements && (index < this->count));
808 if (index == (this->count - 1))
815 this->Move(index + 1, index);
823template<
class TYPE,
int STACK_SIZE>
void
826 #if NEBULA_BOUNDSCHECKS
827 n_assert(this->elements && (index < this->count));
831 IndexT lastElementIndex = this->count - 1;
832 if (index < lastElementIndex)
834 if constexpr (!std::is_trivially_move_assignable<TYPE>::value)
835 this->elements[index] = std::move(this->elements[lastElementIndex]);
837 this->elements[index] = this->elements[lastElementIndex];
848 #if NEBULA_BOUNDSCHECKS
849 n_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->count)));
851 this->EraseIndex(
IndexT(iter - this->elements));
862 #if NEBULA_BOUNDSCHECKS
863 n_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->count)));
865 this->EraseIndexSwap(
IndexT(iter - this->elements));
872template<
class TYPE,
int STACK_SIZE>
void
876 this->Destroy(&(this->elements[this->count - 1]));
883template<
class TYPE,
int STACK_SIZE>
void
892template<
class TYPE,
int STACK_SIZE>
void
895 #if NEBULA_BOUNDSCHECKS
898 if (index == this->count)
905 this->Move(index, index + 1);
906 this->elements[index] = elm;
915template<
class TYPE,
int STACK_SIZE>
void
919 for (i = 0; i < this->count; i++)
921 this->Destroy(&(this->elements[i]));
931template<
class TYPE,
int STACK_SIZE>
void
941template<
class TYPE,
int STACK_SIZE>
void
954 return this->elements;
963 return this->elements + this->count;
978 for (index = 0; index < this->count; index++)
980 if (this->elements[index] == elm)
982 return &(this->elements[index]);
996template<
class TYPE,
int STACK_SIZE>
IndexT
1000 for (index = 0; index < this->count; index++)
1002 if (this->elements[index] == elm)
1013template<
class TYPE,
int STACK_SIZE>
1014template<
typename ...ELEM_TYPE>
1018 this->Reserve(
sizeof...(elements) + 1);
1019 this->Append(first);
1020 this->Append(std::forward<const ELEM_TYPE&>(elements)...);
1038template<
class TYPE,
int STACK_SIZE>
1039template<
typename KEYTYPE>
inline IndexT
1043 for (index = 0; index < this->count; index++)
1045 if (this->elements[index] == elm)
1063template<
class TYPE,
int STACK_SIZE>
void
1066 if ((first + num) > this->count)
1068 this->GrowTo(first + num);
1071 for (i = first; i < (first + num); i++)
1073 this->elements[i] = elm;
1090 for (i = 0; i < num; i++)
1092 if (0 == this->Find(rhs[i]))
1104template<
class TYPE,
int STACK_SIZE>
void
1107 std::sort(this->Begin(), this->End());
1113template<
class TYPE,
int STACK_SIZE>
void
1116 std::sort(this->Begin(), this->End(), func);
1124template<
class TYPE,
int STACK_SIZE>
IndexT
1127 SizeT num = this->Size();
1136 if (0 != (
half = num/2))
1138 mid = lo + ((num & 1) ?
half : (
half - 1));
1139 if (elm < this->elements[mid])
1144 else if (elm > this->elements[mid])
1156 if (elm != this->elements[lo])
1183template<
class TYPE,
int STACK_SIZE>
1184template<
typename KEYTYPE>
inline IndexT
1187 SizeT num = this->Size();
1196 if (0 != (
half = num / 2))
1198 mid = lo + ((num & 1) ?
half : (
half - 1));
1199 if (this->elements[mid] > elm)
1204 else if (this->elements[mid] < elm)
1216 if (this->elements[lo] != elm)
1238template<
class TYPE,
int STACK_SIZE>
1241 return this->elements == this->smallVector;
1250 return this->elements;
1259 return this->elements + this->count;
1267template<
class TYPE,
int STACK_SIZE>
bool
1270 if (this->count > 1)
1273 for (i = 0; i < this->count - 1; i++)
1275 if (this->elements[i] > this->elements[i + 1])
1290template<
class TYPE,
int STACK_SIZE>
IndexT
1293 IndexT i = startIndex + 1;
1294 for (; i < this->count; i++)
1296 if (this->elements[i] != elm)
1298 this->Insert(i, elm);
1305 return (this->Size() - 1);
1313template<
class TYPE,
int STACK_SIZE>
IndexT
1316 SizeT num = this->Size();
1321 return this->Size() - 1;
1331 if (0 != (
half = num/2))
1333 mid = lo + ((num & 1) ?
half : (
half - 1));
1334 if (elm < this->elements[mid])
1339 else if (elm > this->elements[mid])
1348 return this->InsertAtEndOfIdenticalRange(mid, elm);
1353 if (elm < this->elements[lo])
1355 this->Insert(lo, elm);
1358 else if (elm > this->elements[lo])
1360 this->Insert(lo + 1, elm);
1367 return this->InsertAtEndOfIdenticalRange(lo, elm);
1372 #if NEBULA_BOUNDSCHECKS
1375 this->Insert(lo, elm);
1379 if (elm < this->elements[lo])
1381 this->Insert(lo, elm);
1384 else if (elm > this->elements[lo])
1386 this->Insert(lo + 1, elm);
1395 n_error(
"Array::InsertSorted: Can't happen!");
Nebula's small vector optimized array.
Definition arraystack.h:22
TYPE * Iterator
define iterator
Definition arraystack.h:25
bool IsSorted() const
test if the array is sorted, this is a slow operation!
Definition arraystack.h:1268
static const SizeT MinGrowSize
Definition arraystack.h:151
void Destroy(TYPE *elm)
destroy an element (call destructor without freeing memory)
Definition arraystack.h:362
SizeT capacity
Definition arraystack.h:154
void Fill(IndexT first, SizeT num, const TYPE &elm)
fill array range with element
Definition arraystack.h:1064
TYPE & operator[](IndexT index) const
[] operator
Definition arraystack.h:720
Iterator Find(const TYPE &elm) const
find identical element in array, return iterator
Definition arraystack.h:975
void Realloc(SizeT capacity, SizeT grow)
clear contents and preallocate with new attributes
Definition arraystack.h:380
void Free()
free memory and reset size
Definition arraystack.h:942
void EraseFront()
erase first element
Definition arraystack.h:884
SizeT grow
Definition arraystack.h:153
void GrowTo(SizeT newCapacity)
grow array to target size
Definition arraystack.h:468
void operator=(const ArrayStack< TYPE, STACK_SIZE > &rhs)
assignment operator
Definition arraystack.h:403
static const SizeT MaxGrowSize
Definition arraystack.h:152
void Append(const TYPE &first, const ELEM_TYPE &... elements)
Append multiple elements to the end of the array.
Definition arraystack.h:1016
IndexT InsertSorted(const TYPE &elm)
insert element into sorted array, return index where element was included
Definition arraystack.h:1314
Iterator EraseSwap(Iterator iter)
erase element at iterator, fill gap by swapping in last element, destroys sorting!
Definition arraystack.h:860
ArrayStack()
constructor with default parameters
Definition arraystack.h:164
void Copy(const ArrayStack< TYPE, STACK_SIZE > &src)
copy content
Definition arraystack.h:315
IndexT BinarySearchIndex(const TYPE &elm) const
do a binary search, requires a sorted array
Definition arraystack.h:1125
void SortWithFunc(bool(*func)(const TYPE &lhs, const TYPE &rhs))
sort with custom function
void AppendArray(const ArrayStack< TYPE, STACK_SIZE > &rhs)
append the contents of an array to this array
Definition arraystack.h:626
Iterator begin() const
for range-based iteration
Definition arraystack.h:1248
void EraseIndex(IndexT index)
erase element at index, keep sorting intact
Definition arraystack.h:803
SizeT count
Definition arraystack.h:155
bool operator!=(const ArrayStack< TYPE, STACK_SIZE > &rhs) const
inequality operator
Definition arraystack.h:761
bool IsEmpty() const
return true if array empty
Definition arraystack.h:794
TYPE * elements
Definition arraystack.h:157
ArrayStack< TYPE, STACK_SIZE > Difference(const ArrayStack< TYPE, STACK_SIZE > &rhs)
returns new array with elements which are not in rhs (slow!)
Definition arraystack.h:1085
void Reserve(SizeT num)
increase capacity to fit N more elements into the array
Definition arraystack.h:675
IndexT InsertAtEndOfIdenticalRange(IndexT startIndex, const TYPE &elm)
insert element at the first non-identical position, return index of inclusion position
Definition arraystack.h:1291
void EraseBack()
erase last element
Definition arraystack.h:873
const bool IsStackUsed() const
returns true if the stack is used
Definition arraystack.h:1239
TYPE & Front() const
return reference to first element
Definition arraystack.h:770
const SizeT Capacity() const
get overall allocated size of array in number of elements
Definition arraystack.h:709
const SizeT ByteSize() const
return the byte size of the array.
Definition arraystack.h:700
void Grow()
grow array
Definition arraystack.h:496
T As() const
convert to "anything"
void Delete()
delete content
Definition arraystack.h:344
Iterator end() const
Definition arraystack.h:1257
bool operator==(const ArrayStack< TYPE, STACK_SIZE > &rhs) const
equality operator
Definition arraystack.h:734
Iterator Begin() const
return iterator to beginning of array
Definition arraystack.h:952
void Move(IndexT fromIndex, IndexT toIndex)
move elements, grows array if needed
Definition arraystack.h:530
void EraseIndexSwap(IndexT index)
erase element at index, fill gap by swapping in last element, destroys sorting!
Definition arraystack.h:824
TYPE & Back() const
return reference to last element
Definition arraystack.h:782
~ArrayStack()
destructor
Definition arraystack.h:371
const SizeT Size() const
get number of elements in array
Definition arraystack.h:691
TYPE smallVector[STACK_SIZE]
Definition arraystack.h:156
void Insert(IndexT index, const TYPE &elm)
insert element before element at index
Definition arraystack.h:893
IndexT FindIndex(const TYPE &elm) const
find identical element in array, return index, InvalidIndex if not found
Definition arraystack.h:997
Iterator End() const
return iterator to end of array
Definition arraystack.h:961
void Reset()
reset array (does NOT call destructors)
Definition arraystack.h:932
void Sort()
sort the array
Definition arraystack.h:1105
Iterator Erase(Iterator iter)
erase element pointed to by iterator, keep sorting intact
Definition arraystack.h:846
void Clear()
clear array (calls destructors)
Definition arraystack.h:916
void __cdecl n_error(const char *msg,...)
This function is called when a serious situation is encountered which requires abortion of the applic...
Definition debug.cc:138
#define n_assert(exp)
Definition debug.h:50
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
static const int InvalidIndex
Definition types.h:54
int SizeT
Definition types.h:49
int IndexT
Definition types.h:48