Nebula
Loading...
Searching...
No Matches
arraystack.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
16#include "core/types.h"
17
18//------------------------------------------------------------------------------
19namespace Util
20{
21template<class TYPE, int STACK_SIZE> class ArrayStack
22{
23public:
25 typedef TYPE* Iterator;
26
28 ArrayStack();
30 ArrayStack(SizeT initialCapacity, SizeT initialGrow);
32 ArrayStack(SizeT initialSize, SizeT initialGrow, const TYPE& initialValue);
38 ArrayStack(std::initializer_list<TYPE> list);
41
45 void operator=(ArrayStack<TYPE, STACK_SIZE>&& rhs) noexcept;
47 TYPE& operator[](IndexT index) const;
49 bool operator==(const ArrayStack<TYPE, STACK_SIZE>& rhs) const;
51 bool operator!=(const ArrayStack<TYPE, STACK_SIZE>& rhs) const;
53 template<typename T> T As() const;
54
56 template <typename ...ELEM_TYPE>
57 void Append(const TYPE& first, const ELEM_TYPE&... elements);
59 void Append(const TYPE& elm);
61 void Append(TYPE&& elm);
65 void AppendArray(const TYPE* arr, const SizeT count);
67 void Reserve(SizeT num);
69 const SizeT Size() const;
71 const SizeT ByteSize() const;
73 const SizeT Capacity() const;
75 TYPE& Front() const;
77 TYPE& Back() const;
79 bool IsEmpty() const;
81 void EraseIndex(IndexT index);
85 void EraseIndexSwap(IndexT index);
89 void EraseBack();
91 void EraseFront();
93 void Insert(IndexT index, const TYPE& elm);
95 IndexT InsertSorted(const TYPE& elm);
97 IndexT InsertAtEndOfIdenticalRange(IndexT startIndex, const TYPE& elm);
99 bool IsSorted() const;
101 void Clear();
103 void Reset();
105 void Free();
107 Iterator Begin() const;
109 Iterator End() const;
111 Iterator Find(const TYPE& elm) const;
113 IndexT FindIndex(const TYPE& elm) const;
115 template <typename KEYTYPE> IndexT FindIndex(typename std::enable_if<true, const KEYTYPE&>::type elm) const;
117 void Fill(IndexT first, SizeT num, const TYPE& elm);
123 void Sort();
125 void SortWithFunc(bool (*func)(const TYPE& lhs, const TYPE& rhs));
127 IndexT BinarySearchIndex(const TYPE& elm) const;
129 template <typename KEYTYPE> IndexT BinarySearchIndex(typename std::enable_if<true, const KEYTYPE&>::type elm) const;
130
132 const bool IsStackUsed() const;
133
135 Iterator begin() const;
136 Iterator end() const;
137private:
139 void Destroy(TYPE* elm);
141 void Copy(const ArrayStack<TYPE, STACK_SIZE>& src);
143 void Delete();
145 void Grow();
147 void GrowTo(SizeT newCapacity);
149 void Move(IndexT fromIndex, IndexT toIndex);
150
151 static const SizeT MinGrowSize = 16;
152 static const SizeT MaxGrowSize = 65536; // FIXME: big grow size needed for mesh tools
153 SizeT grow; // grow by this number of elements if array exhausted
154 SizeT capacity; // number of elements allocated
155 SizeT count; // number of elements in array
156 TYPE smallVector[STACK_SIZE];
157 TYPE* elements; // pointer to element array
158};
159
160//------------------------------------------------------------------------------
163template<class TYPE, int STACK_SIZE>
165 grow(MinGrowSize),
166 capacity(STACK_SIZE),
167 count(0),
168 elements(smallVector)
169{
170 // empty
171}
172
173//------------------------------------------------------------------------------
176template<class TYPE, int STACK_SIZE>
178 grow(_grow),
179 capacity(_capacity),
180 count(0)
181{
182 if (0 == this->grow)
183 {
184 this->grow = 16;
185 }
186 if (this->capacity > 0)
187 {
188 if (this->capacity > STACK_SIZE)
189 this->elements = new TYPE[this->capacity];
190 else
191 {
192 this->capacity = STACK_SIZE;
193 this->elements = smallVector;
194 }
195 }
196 else
197 {
198 this->capacity = STACK_SIZE;
199 this->elements = smallVector;
200 }
201}
202
203//------------------------------------------------------------------------------
206template<class TYPE, int STACK_SIZE>
207ArrayStack<TYPE, STACK_SIZE>::ArrayStack(SizeT initialSize, SizeT _grow, const TYPE& initialValue) :
208 grow(_grow),
209 capacity(initialSize),
210 count(initialSize)
211{
212 if (0 == this->grow)
213 {
214 this->grow = 16;
215 }
216 if (this->capacity > 0)
217 {
218 if (this->capacity > STACK_SIZE)
219 this->elements = new TYPE[this->capacity];
220 else
221 {
222 this->capacity = STACK_SIZE;
223 this->elements = smallVector;
224 }
225
226 IndexT i;
227 for (i = 0; i < this->capacity; i++)
228 {
229 this->elements[i] = initialValue;
230 }
231 }
232 else
233 {
234 this->capacity = STACK_SIZE;
235 this->elements = smallVector;
236 }
237}
238
239//------------------------------------------------------------------------------
242template<class TYPE, int STACK_SIZE>
243ArrayStack<TYPE, STACK_SIZE>::ArrayStack(std::initializer_list<TYPE> list) :
244 grow(16),
245 capacity((SizeT)list.size()),
246 count((SizeT)list.size())
247{
248 if (this->capacity > 0)
249 {
250 if (this->capacity > STACK_SIZE)
251 this->elements = new TYPE[this->capacity];
252 else
253 {
254 this->capacity = STACK_SIZE;
255 this->elements = smallVector;
256 }
257
258 IndexT i;
259 for (i = 0; i < this->count; i++)
260 {
261 this->elements[i] = list.begin()[i];
262 }
263 }
264 else
265 {
266 this->capacity = STACK_SIZE;
267 this->elements = smallVector;
268 }
269}
270
271//------------------------------------------------------------------------------
274template<class TYPE, int STACK_SIZE>
276 grow(0),
277 capacity(0),
278 count(0),
279 elements(smallVector)
280{
281 this->Copy(rhs);
282}
283
284//------------------------------------------------------------------------------
287template<class TYPE, int STACK_SIZE>
289{
290 this->capacity = rhs.capacity;
291 this->count = rhs.count;
292 this->grow = rhs.grow;
293
294 if (this->capacity <= STACK_SIZE)
295 {
296 for (IndexT i = 0; i < rhs.count; ++i)
297 {
298 this->smallVector[i] = rhs.smallVector[i];
299 }
300
301 this->elements = this->smallVector;
302 }
303 else
304 this->elements = rhs.elements;
305
306 rhs.count = 0;
307 rhs.capacity = 0;
308 rhs.elements = nullptr;
309}
310
311//------------------------------------------------------------------------------
314template<class TYPE, int STACK_SIZE> void
316{
317 #if NEBULA_BOUNDSCHECKS
318 if (this->elements != this->smallVector)
319 n_assert(0 == this->elements);
320 #endif
321
322 this->grow = src.grow;
323 this->capacity = src.count; // don't copy capacity, make this new copy smaller
324 this->count = src.count;
325 if (this->capacity > 0)
326 {
327 if (this->capacity > STACK_SIZE)
328 this->elements = new TYPE[this->capacity];
329 else
330 this->elements = smallVector;
331
332 IndexT i;
333 for (i = 0; i < this->count; i++)
334 {
335 this->elements[i] = src.elements[i];
336 }
337 }
338}
339
340//------------------------------------------------------------------------------
343template<class TYPE, int STACK_SIZE> void
345{
346 this->grow = 0;
347 this->capacity = 0;
348 this->count = 0;
349 if (this->elements)
350 {
351 if (this->elements != this->smallVector)
352 delete[] this->elements;
353
354 this->elements = this->smallVector;
355 }
356}
357
358//------------------------------------------------------------------------------
361template<class TYPE, int STACK_SIZE> void
363{
364 elm->~TYPE();
365}
366
367//------------------------------------------------------------------------------
370template<class TYPE, int STACK_SIZE>
372{
373 this->Delete();
374}
375
376//------------------------------------------------------------------------------
379template<class TYPE, int STACK_SIZE> void
381{
382 this->Delete();
383 this->grow = _grow;
384 this->capacity = _capacity;
385 this->count = 0;
386 if (this->capacity > 0)
387 {
388 if (this->capacity > STACK_SIZE)
389 this->elements = new TYPE[this->capacity];
390 else
391 this->elements = smallVector;
392 }
393 else
394 {
395 this->elements = smallVector;
396 }
397}
398
399//------------------------------------------------------------------------------
402template<class TYPE, int STACK_SIZE> void
404{
405 if (this != &rhs)
406 {
407 if ((this->capacity > 0) && (rhs.count <= this->capacity))
408 {
409 // source array fits into our capacity, copy in place
410 n_assert(0 != this->elements);
411 IndexT i;
412 for (i = 0; i < rhs.count; i++)
413 {
414 this->elements[i] = rhs.elements[i];
415 }
416
417 // properly destroy remaining original elements
418 for (; i < this->count; i++)
419 {
420 this->Destroy(&(this->elements[i]));
421 }
422 this->grow = rhs.grow;
423 this->count = rhs.count;
424 }
425 else
426 {
427 // source array doesn't fit into our capacity, need to reallocate
428 this->Delete();
429 this->Copy(rhs);
430 }
431 }
432}
433
434//------------------------------------------------------------------------------
437template<class TYPE, int STACK_SIZE>
439{
440 if (this->elements && this->capacity > STACK_SIZE)
441 delete[] this->elements;
442
443 this->capacity = rhs.capacity;
444 this->count = rhs.count;
445 this->grow = rhs.grow;
446
447 if (this->capacity <= STACK_SIZE)
448 {
449 for (IndexT i = 0; i < rhs.count; ++i)
450 {
451 this->smallVector[i] = rhs.smallVector[i];
452 }
453
454 this->elements = this->smallVector;
455 }
456 else
457 this->elements = rhs.elements;
458
459 rhs.count = 0;
460 rhs.capacity = 0;
461 rhs.elements = nullptr;
462}
463
464//------------------------------------------------------------------------------
467template<class TYPE, int STACK_SIZE> void
469{
470 if (newCapacity > STACK_SIZE)
471 {
472 TYPE* newArray = new TYPE[newCapacity];
473 if (this->elements)
474 {
475 // copy over contents
476 IndexT i;
477 for (i = 0; i < this->count; i++)
478 {
479 newArray[i] = this->elements[i];
480 }
481
482 // discard old array
483 if (this->elements != this->smallVector)
484 delete[] this->elements;
485 }
486 this->elements = newArray;
487 }
488 this->capacity = newCapacity;
489
490}
491
492//------------------------------------------------------------------------------
495template<class TYPE, int STACK_SIZE> void
497{
498 #if NEBULA_BOUNDSCHECKS
499 n_assert(this->grow > 0);
500 #endif
501
502 SizeT growToSize;
503 if (0 == this->capacity)
504 {
505 growToSize = this->grow;
506 }
507 else
508 {
509 // grow by half of the current capacity, but never more then MaxGrowSize
510 SizeT growBy = this->capacity >> 1;
511 if (growBy == 0)
512 {
513 growBy = MinGrowSize;
514 }
515 else if (growBy > MaxGrowSize)
516 {
517 growBy = MaxGrowSize;
518 }
519 growToSize = this->capacity + growBy;
520 }
521 this->GrowTo(growToSize);
522}
523
524//------------------------------------------------------------------------------
529template<class TYPE, int STACK_SIZE> void
531{
532 #if NEBULA_BOUNDSCHECKS
533 n_assert(this->elements);
534 n_assert(fromIndex < this->count);
535 #endif
536
537 // nothing to move?
538 if (fromIndex == toIndex)
539 {
540 return;
541 }
542
543 // compute number of elements to move
544 SizeT num = this->count - fromIndex;
545
546 // check if array needs to grow
547 SizeT neededSize = toIndex + num;
548 while (neededSize > this->capacity)
549 {
550 this->Grow();
551 }
552
553 if (fromIndex > toIndex)
554 {
555 // this is a backward move
556 IndexT i;
557 for (i = 0; i < num; i++)
558 {
559 this->elements[toIndex + i] = this->elements[fromIndex + i];
560 }
561
562 // destroy remaining elements
563 for (i = (fromIndex + i) - 1; i < this->count; i++)
564 {
565 this->Destroy(&(this->elements[i]));
566 }
567 }
568 else
569 {
570 // this is a forward move
571 IndexT i; // NOTE: this must remain signed for the following loop to work!!!
572 for (i = num - 1; i >= 0; --i)
573 {
574 this->elements[toIndex + i] = this->elements[fromIndex + i];
575 }
576
577 // destroy freed elements
578 for (i = int(fromIndex); i < int(toIndex); i++)
579 {
580 this->Destroy(&(this->elements[i]));
581 }
582 }
583
584 // adjust array size
585 this->count = toIndex + num;
586}
587
588//------------------------------------------------------------------------------
591template<class TYPE, int STACK_SIZE> void
593{
594 // grow allocated space if exhausted
595 if (this->count == this->capacity)
596 {
597 this->Grow();
598 }
599 #if NEBULA_BOUNDSCHECKS
600 n_assert(this->elements);
601 #endif
602 this->elements[this->count++] = elm;
603}
604
605//------------------------------------------------------------------------------
608template<class TYPE, int STACK_SIZE> inline void
610{
611 // grow allocated space if exhausted
612 if (this->count == this->capacity)
613 {
614 this->Grow();
615 }
616#if NEBULA_BOUNDSCHECKS
617 n_assert(this->elements);
618#endif
619 this->elements[this->count++] = std::forward<TYPE>(elm);
620}
621
622//------------------------------------------------------------------------------
625template<class TYPE, int STACK_SIZE> void
627{
628 SizeT neededCapacity = this->count + rhs.count;
629 if (neededCapacity > this->capacity)
630 {
631 this->GrowTo(neededCapacity);
632 }
633
634 // forward elements from array
635 IndexT i;
636 for (i = 0; i < rhs.count; i++)
637 {
638 this->elements[this->count + i] = std::forward<TYPE>(rhs.elements[i]);
639 }
640 this->count += rhs.count;
641}
642
643//------------------------------------------------------------------------------
646template<class TYPE, int STACK_SIZE> void
648{
649 SizeT neededCapacity = this->count + count;
650 if (neededCapacity > this->capacity)
651 {
652 this->GrowTo(neededCapacity);
653 }
654
655 // forward elements from array
656 IndexT i;
657 for (i = 0; i < count; i++)
658 {
659 this->elements[this->count + i] = std::forward<TYPE>(arr[i]);
660 }
661 this->count += count;
662}
663
664//------------------------------------------------------------------------------
674template<class TYPE, int STACK_SIZE> void
676{
677 #if NEBULA_BOUNDSCHECKS
678 n_assert(num > 0);
679 #endif
680 SizeT neededCapacity = this->count + num;
681 if (neededCapacity > this->capacity)
682 {
683 this->GrowTo(neededCapacity);
684 }
685}
686
687//------------------------------------------------------------------------------
690template<class TYPE, int STACK_SIZE> const SizeT
692{
693 return this->count;
694}
695
696//------------------------------------------------------------------------------
699template<class TYPE, int STACK_SIZE> const SizeT
701{
702 return this->count * sizeof(TYPE);
703}
704
705//------------------------------------------------------------------------------
708template<class TYPE, int STACK_SIZE> const SizeT
710{
711 return this->capacity;
712}
713
714//------------------------------------------------------------------------------
719template<class TYPE, int STACK_SIZE> TYPE&
721{
722 #if NEBULA_BOUNDSCHECKS
723 n_assert(this->elements && (index < this->count));
724 #endif
725 return this->elements[index];
726}
727
728//------------------------------------------------------------------------------
733template<class TYPE, int STACK_SIZE> bool
735{
736 if (rhs.Size() == this->Size())
737 {
738 IndexT i;
739 SizeT num = this->Size();
740 for (i = 0; i < num; i++)
741 {
742 if (!(this->elements[i] == rhs.elements[i]))
743 {
744 return false;
745 }
746 }
747 return true;
748 }
749 else
750 {
751 return false;
752 }
753}
754
755//------------------------------------------------------------------------------
760template<class TYPE, int STACK_SIZE> bool
762{
763 return !(*this == rhs);
764}
765
766//------------------------------------------------------------------------------
769template<class TYPE, int STACK_SIZE> TYPE&
771{
772 #if NEBULA_BOUNDSCHECKS
773 n_assert(this->elements && (this->count > 0));
774 #endif
775 return this->elements[0];
776}
777
778//------------------------------------------------------------------------------
781template<class TYPE, int STACK_SIZE> TYPE&
783{
784 #if NEBULA_BOUNDSCHECKS
785 n_assert(this->elements && (this->count > 0));
786 #endif
787 return this->elements[this->count - 1];
788}
789
790//------------------------------------------------------------------------------
793template<class TYPE, int STACK_SIZE> bool
795{
796 return (this->count == 0);
797}
798
799//------------------------------------------------------------------------------
802template<class TYPE, int STACK_SIZE> void
804{
805 #if NEBULA_BOUNDSCHECKS
806 n_assert(this->elements && (index < this->count));
807 #endif
808 if (index == (this->count - 1))
809 {
810 // special case: last element
811 this->EraseBack();
812 }
813 else
814 {
815 this->Move(index + 1, index);
816 }
817}
818
819//------------------------------------------------------------------------------
823template<class TYPE, int STACK_SIZE> void
825{
826 #if NEBULA_BOUNDSCHECKS
827 n_assert(this->elements && (index < this->count));
828 #endif
829
830 // swap with last element, and destroy last element
831 IndexT lastElementIndex = this->count - 1;
832 if (index < lastElementIndex)
833 {
834 if constexpr (!std::is_trivially_move_assignable<TYPE>::value)
835 this->elements[index] = std::move(this->elements[lastElementIndex]);
836 else
837 this->elements[index] = this->elements[lastElementIndex];
838 }
839 this->count--;
840}
841
842//------------------------------------------------------------------------------
845template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
847{
848 #if NEBULA_BOUNDSCHECKS
849 n_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->count)));
850 #endif
851 this->EraseIndex(IndexT(iter - this->elements));
852 return iter;
853}
854
855//------------------------------------------------------------------------------
859template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
861{
862 #if NEBULA_BOUNDSCHECKS
863 n_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->count)));
864 #endif
865 this->EraseIndexSwap(IndexT(iter - this->elements));
866 return iter;
867}
868
869//------------------------------------------------------------------------------
872template<class TYPE, int STACK_SIZE> void
874{
875 n_assert(this->count > 0);
876 this->Destroy(&(this->elements[this->count - 1]));
877 this->count--;
878}
879
880//------------------------------------------------------------------------------
883template<class TYPE, int STACK_SIZE> void
885{
886 this->Erase(0);
887}
888
889//------------------------------------------------------------------------------
892template<class TYPE, int STACK_SIZE> void
894{
895 #if NEBULA_BOUNDSCHECKS
896 n_assert(index <= this->count);
897 #endif
898 if (index == this->count)
899 {
900 // special case: append element to back
901 this->Append(elm);
902 }
903 else
904 {
905 this->Move(index, index + 1);
906 this->elements[index] = elm;
907 }
908}
909
910//------------------------------------------------------------------------------
915template<class TYPE, int STACK_SIZE> void
917{
918 IndexT i;
919 for (i = 0; i < this->count; i++)
920 {
921 this->Destroy(&(this->elements[i]));
922 }
923 this->count = 0;
924}
925
926//------------------------------------------------------------------------------
931template<class TYPE, int STACK_SIZE> void
933{
934 this->count = 0;
935}
936
937//------------------------------------------------------------------------------
941template<class TYPE, int STACK_SIZE> void
943{
944 this->Delete();
945 this->grow = 8;
946}
947
948//------------------------------------------------------------------------------
951template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
953{
954 return this->elements;
955}
956
957//------------------------------------------------------------------------------
960template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
962{
963 return this->elements + this->count;
964}
965
966//------------------------------------------------------------------------------
974template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
976{
977 IndexT index;
978 for (index = 0; index < this->count; index++)
979 {
980 if (this->elements[index] == elm)
981 {
982 return &(this->elements[index]);
983 }
984 }
985 return 0;
986}
987
988//------------------------------------------------------------------------------
996template<class TYPE, int STACK_SIZE> IndexT
998{
999 IndexT index;
1000 for (index = 0; index < this->count; index++)
1001 {
1002 if (this->elements[index] == elm)
1003 {
1004 return index;
1005 }
1006 }
1007 return InvalidIndex;
1008}
1009
1010//------------------------------------------------------------------------------
1013template<class TYPE, int STACK_SIZE>
1014template<typename ...ELEM_TYPE>
1015inline void
1016ArrayStack<TYPE, STACK_SIZE>::Append(const TYPE& first, const ELEM_TYPE&... elements)
1017{
1018 this->Reserve(sizeof...(elements) + 1);
1019 this->Append(first);
1020 this->Append(std::forward<const ELEM_TYPE&>(elements)...);
1021}
1022
1023//------------------------------------------------------------------------------
1038template<class TYPE, int STACK_SIZE>
1039template<typename KEYTYPE> inline IndexT
1040ArrayStack<TYPE, STACK_SIZE>::FindIndex(typename std::enable_if<true, const KEYTYPE&>::type elm) const
1041{
1042 IndexT index;
1043 for (index = 0; index < this->count; index++)
1044 {
1045 if (this->elements[index] == elm)
1046 {
1047 return index;
1048 }
1049 }
1050 return InvalidIndex;
1051}
1052
1053//------------------------------------------------------------------------------
1063template<class TYPE, int STACK_SIZE> void
1065{
1066 if ((first + num) > this->count)
1067 {
1068 this->GrowTo(first + num);
1069 }
1070 IndexT i;
1071 for (i = first; i < (first + num); i++)
1072 {
1073 this->elements[i] = elm;
1074 }
1075}
1076
1077//------------------------------------------------------------------------------
1084template<class TYPE, int STACK_SIZE> ArrayStack<TYPE, STACK_SIZE>
1086{
1088 IndexT i;
1089 SizeT num = rhs.Size();
1090 for (i = 0; i < num; i++)
1091 {
1092 if (0 == this->Find(rhs[i]))
1093 {
1094 diff.Append(rhs[i]);
1095 }
1096 }
1097 return diff;
1098}
1099
1100//------------------------------------------------------------------------------
1104template<class TYPE, int STACK_SIZE> void
1106{
1107 std::sort(this->Begin(), this->End());
1108}
1109
1110//------------------------------------------------------------------------------
1113template<class TYPE, int STACK_SIZE> void
1114Util::ArrayStack<TYPE, STACK_SIZE>::SortWithFunc(bool (*func)(const TYPE& lhs, const TYPE& rhs))
1115{
1116 std::sort(this->Begin(), this->End(), func);
1117}
1118
1119//------------------------------------------------------------------------------
1124template<class TYPE, int STACK_SIZE> IndexT
1126{
1127 SizeT num = this->Size();
1128 if (num > 0)
1129 {
1130 IndexT half;
1131 IndexT lo = 0;
1132 IndexT hi = num - 1;
1133 IndexT mid;
1134 while (lo <= hi)
1135 {
1136 if (0 != (half = num/2))
1137 {
1138 mid = lo + ((num & 1) ? half : (half - 1));
1139 if (elm < this->elements[mid])
1140 {
1141 hi = mid - 1;
1142 num = num & 1 ? half : half - 1;
1143 }
1144 else if (elm > this->elements[mid])
1145 {
1146 lo = mid + 1;
1147 num = half;
1148 }
1149 else
1150 {
1151 return mid;
1152 }
1153 }
1154 else if (0 != num)
1155 {
1156 if (elm != this->elements[lo])
1157 {
1158 return InvalidIndex;
1159 }
1160 else
1161 {
1162 return lo;
1163 }
1164 }
1165 else
1166 {
1167 break;
1168 }
1169 }
1170 }
1171 return InvalidIndex;
1172}
1173
1174//------------------------------------------------------------------------------
1183template<class TYPE, int STACK_SIZE>
1184template<typename KEYTYPE> inline IndexT
1185ArrayStack<TYPE, STACK_SIZE>::BinarySearchIndex(typename std::enable_if<true, const KEYTYPE&>::type elm) const
1186{
1187 SizeT num = this->Size();
1188 if (num > 0)
1189 {
1190 IndexT half;
1191 IndexT lo = 0;
1192 IndexT hi = num - 1;
1193 IndexT mid;
1194 while (lo <= hi)
1195 {
1196 if (0 != (half = num / 2))
1197 {
1198 mid = lo + ((num & 1) ? half : (half - 1));
1199 if (this->elements[mid] > elm)
1200 {
1201 hi = mid - 1;
1202 num = num & 1 ? half : half - 1;
1203 }
1204 else if (this->elements[mid] < elm)
1205 {
1206 lo = mid + 1;
1207 num = half;
1208 }
1209 else
1210 {
1211 return mid;
1212 }
1213 }
1214 else if (0 != num)
1215 {
1216 if (this->elements[lo] != elm)
1217 {
1218 return InvalidIndex;
1219 }
1220 else
1221 {
1222 return lo;
1223 }
1224 }
1225 else
1226 {
1227 break;
1228 }
1229 }
1230 }
1231 return InvalidIndex;
1232}
1233
1234
1235//------------------------------------------------------------------------------
1238template<class TYPE, int STACK_SIZE>
1240{
1241 return this->elements == this->smallVector;
1242}
1243
1244//------------------------------------------------------------------------------
1247template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
1249{
1250 return this->elements;
1251}
1252
1253//------------------------------------------------------------------------------
1256template<class TYPE, int STACK_SIZE> typename ArrayStack<TYPE, STACK_SIZE>::Iterator
1258{
1259 return this->elements + this->count;
1260}
1261
1262//------------------------------------------------------------------------------
1267template<class TYPE, int STACK_SIZE> bool
1269{
1270 if (this->count > 1)
1271 {
1272 IndexT i;
1273 for (i = 0; i < this->count - 1; i++)
1274 {
1275 if (this->elements[i] > this->elements[i + 1])
1276 {
1277 return false;
1278 }
1279 }
1280 }
1281 return true;
1282}
1283
1284//------------------------------------------------------------------------------
1290template<class TYPE, int STACK_SIZE> IndexT
1292{
1293 IndexT i = startIndex + 1;
1294 for (; i < this->count; i++)
1295 {
1296 if (this->elements[i] != elm)
1297 {
1298 this->Insert(i, elm);
1299 return i;
1300 }
1301 }
1302
1303 // fallthrough: new element needs to be appended to end
1304 this->Append(elm);
1305 return (this->Size() - 1);
1306}
1307
1308//------------------------------------------------------------------------------
1313template<class TYPE, int STACK_SIZE> IndexT
1315{
1316 SizeT num = this->Size();
1317 if (num == 0)
1318 {
1319 // array is currently empty
1320 this->Append(elm);
1321 return this->Size() - 1;
1322 }
1323 else
1324 {
1325 IndexT half;
1326 IndexT lo = 0;
1327 IndexT hi = num - 1;
1328 IndexT mid;
1329 while (lo <= hi)
1330 {
1331 if (0 != (half = num/2))
1332 {
1333 mid = lo + ((num & 1) ? half : (half - 1));
1334 if (elm < this->elements[mid])
1335 {
1336 hi = mid - 1;
1337 num = num & 1 ? half : half - 1;
1338 }
1339 else if (elm > this->elements[mid])
1340 {
1341 lo = mid + 1;
1342 num = half;
1343 }
1344 else
1345 {
1346 // element already exists at [mid], append the
1347 // new element to the end of the range
1348 return this->InsertAtEndOfIdenticalRange(mid, elm);
1349 }
1350 }
1351 else if (0 != num)
1352 {
1353 if (elm < this->elements[lo])
1354 {
1355 this->Insert(lo, elm);
1356 return lo;
1357 }
1358 else if (elm > this->elements[lo])
1359 {
1360 this->Insert(lo + 1, elm);
1361 return lo + 1;
1362 }
1363 else
1364 {
1365 // element already exists at [low], append
1366 // the new element to the end of the range
1367 return this->InsertAtEndOfIdenticalRange(lo, elm);
1368 }
1369 }
1370 else
1371 {
1372 #if NEBULA_BOUNDSCHECKS
1373 n_assert(0 == lo);
1374 #endif
1375 this->Insert(lo, elm);
1376 return lo;
1377 }
1378 }
1379 if (elm < this->elements[lo])
1380 {
1381 this->Insert(lo, elm);
1382 return lo;
1383 }
1384 else if (elm > this->elements[lo])
1385 {
1386 this->Insert(lo + 1, elm);
1387 return lo + 1;
1388 }
1389 else
1390 {
1391 // can't happen(?)
1392 }
1393 }
1394 // can't happen
1395 n_error("Array::InsertSorted: Can't happen!");
1396 return InvalidIndex;
1397}
1398
1399} // namespace Core
1400//------------------------------------------------------------------------------
Definition half.h:20
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