1// tArray.h 
2// 
3// A simple array implementation that can grow its memory as needed. Adding elements or to an array or adding two 
4// arrays together are the sorts if things that may cause an internal grow of the memory. 
5// 
6// Copyright (c) 2004-2005, 2017, 2020 Tristan Grimmer. 
7// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
8// granted, provided that the above copyright notice and this permission notice appear in all copies. 
9// 
10// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
11// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
12// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
13// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
14// PERFORMANCE OF THIS SOFTWARE. 
15 
16#pragma once 
17#include "Foundation/tStandard.h" 
18#include "Foundation/tFundamentals.h" 
19 
20 
21template<typename T> class tArray 
22{ 
23public: 
24 tArray() /* Initially empty array with growCount of 256.*/ { } 
25 tArray(int capacity, int growCount = 256) /* Capacity and growcount must be >= 0. */ : GrowCount(growCount) { Clear(capacity); } 
26 tArray(const tArray& src) { *this = src; } 
27 
28 virtual ~tArray() { delete[] Elements; } 
29 
30 // Frees the current content. Allows you to optionally set the new initial capacity. If growCount == -1, the 
31 // growCount remains unchanged. 
32 void Clear(int capacity = 0, int growCount = -1); 
33 int GetNumAppendedElements() const { return NumAppendedElements; } 
34 T* GetElements() const { return Elements; } 
35 
36 // Returns the number of elements that may be stored in the array before a costly grow operation. 
37 int GetCapacity() const { return Capacity; } 
38 
39 // Grows the max size (capacity) of the array by the specified number of items. 
40 bool GrowCapacity(int numElementsGrow); 
41 
42 // The append calls will grow the array if necessary. If growCount is 0 and there's no more room, false is returned. 
43 bool Append(const T&); 
44 
45 // The truncate call will return the last appended element and will reduce NumAppendedElements by 1 
46 T& Truncate() { tAssert(NumAppendedElements); return Elements[--NumAppendedElements]; } 
47 
48 // For this append call if the GrowCount is 0 and there is not enough current room, false is returned and the array 
49 // is left unmodified. If growing is necessary, it will succeed even if the space needed exceeds a single grow. 
50 // It does this in one shot, but grows by a multiple of the GrowCount. 
51 bool Append(const T*, int numElements); 
52 
53 operator T*() { return Elements; } 
54 operator T*() const { return Elements; } 
55 operator const T*() { return Elements; } 
56 operator const T*() const { return Elements; } 
57 T& operator[](int index) { tAssert((index < Capacity) && (index >= 0)); return Elements[index]; } 
58 const T operator[](int index) const { tAssert((index < Capacity) && (index >= 0)); return Elements[index]; } 
59 bool operator==(const tArray&) const; // Empty arrays are considered equal. 
60 bool operator!=(const tArray& rhs) const { return !(*this == rhs); } 
61 const tArray& operator+(const tArray& src) { Append(src.GetElements(), src.GetNumElements()); } 
62 const tArray& operator=(const tArray&); 
63 
64private: 
65 T* Elements = nullptr; 
66 int NumAppendedElements = 0; 
67 
68 int Capacity = 0; 
69 int GrowCount = 256; 
70}; 
71 
72 
73// Implementation below this line. 
74 
75 
76template<typename T> inline void tArray<T>::Clear(int capacity, int growCount) 
77{ 
78 tAssert((capacity >= 0) && (growCount >= -1)) 
79 delete[] Elements; 
80 Elements = nullptr; 
81 Capacity = capacity; 
82 NumAppendedElements = 0; 
83 
84 if (Capacity > 0) 
85 Elements = new T[Capacity]; 
86 
87 if (growCount > -1) 
88 GrowCount = growCount; 
89} 
90 
91 
92template<typename T> inline bool tArray<T>::GrowCapacity(int numElementsGrow) 
93{ 
94 if (numElementsGrow <= 0) 
95 return false; 
96 
97 int newCap = Capacity + numElementsGrow; 
98 T* newItems = new T[newCap]; 
99 for (int e = 0; e < Capacity; e++) 
100 newItems[e] = Elements[e]; 
101 
102 delete[] Elements; 
103 Elements = newItems; 
104 Capacity = newCap; 
105 return true; 
106} 
107 
108 
109template<typename T> inline bool tArray<T>::Append(const T& item) 
110{ 
111 if (NumAppendedElements >= Capacity) 
112 GrowCapacity(GrowCount); 
113 
114 if (NumAppendedElements >= Capacity) 
115 return false; 
116 
117 tAssert(NumAppendedElements < Capacity); 
118 Elements[NumAppendedElements++] = item; 
119 return true; 
120} 
121 
122 
123template<typename T> inline bool tArray<T>::Append(const T* elements, int numElementToAppend) 
124{ 
125 tAssert(elements && (numElementToAppend > 0)); 
126 int numAvail = Capacity - NumAppendedElements; 
127 if ((GrowCount <= 0) && (numElementToAppend > numAvail)) 
128 return false; 
129 
130 // First we append all elements that do not require the array to grow. We could do this in no more than two memcpys 
131 // if we want a performance boost. 
132 int count = (numElementToAppend < numAvail) ? numElementToAppend : numAvail; 
133 int index = 0; 
134 for (; index < count; index++) 
135 Elements[NumAppendedElements + index] = elements[index]; 
136 
137 NumAppendedElements += count; 
138 numElementToAppend -= count; 
139 if (numElementToAppend <= 0) 
140 return true; 
141 
142 // There are some left so we need to grow the array. We grow once in multiples of GrowCount. 
143 // At this point, GrowCount should be guaranteed to be > 0 since we early exited. 
144 tAssert(GrowCount > 0); 
145 tMath::tDivt quotRem = tMath::tDiv(numElementToAppend, GrowCount); 
146 int numGrows = quotRem.Quotient; 
147 if (quotRem.Remainder > 0) 
148 numGrows++; 
149 
150 GrowCapacity(GrowCount * numGrows); 
151 
152 // And now we just have a tight loop to copy them in. 
153 for (int i = 0; i < numElementToAppend; i++) 
154 Elements[NumAppendedElements + i] = elements[index++]; 
155 
156 NumAppendedElements += numElementToAppend; 
157 return true; 
158} 
159 
160 
161template<typename T> inline const tArray<T>& tArray<T>::operator=(const tArray<T>& src) 
162{ 
163 if (&src == this) 
164 return *this; 
165 
166 Clear(0, src.GrowCount); 
167 NumAppendedElements = src.NumAppendedElements; 
168 Capacity = src.Capacity; 
169 if (Capacity > 0) 
170 Elements = new T[Capacity]; 
171 
172 for (int e = 0; e < Capacity; e++) 
173 Elements[e] = src.Elements[e]; 
174 
175 return *this; 
176} 
177 
178 
179template<typename T> inline bool tArray<T>::operator==(const tArray& rhs) const 
180{ 
181 if (Capacity != rhs.Capacity) 
182 return false; 
183 
184 if (NumAppendedElements != rhs.NumAppendedElements) 
185 return false; 
186 
187 for (int e = 0; e < Capacity; e++) 
188 if (Elements[e] != rhs.Elements[e]) 
189 return false; 
190 
191 return true; 
192} 
193