1/****************************************************************************************
2
3 Copyright (C) 2015 Autodesk, Inc.
4 All rights reserved.
5
6 Use of this software is subject to the terms of the Autodesk license agreement
7 provided at the time of installation or download, or which otherwise accompanies
8 this software in either electronic or hard copy form.
9
10****************************************************************************************/
11
12//! \file fbxdynamicarray.h
13#ifndef _FBXSDK_CORE_BASE_DYNAMICARRAY_H_
14#define _FBXSDK_CORE_BASE_DYNAMICARRAY_H_
15
16#include <fbxsdk/fbxsdk_def.h>
17
18#include <fbxsdk/core/base/fbxcontainerallocators.h>
19
20#include <fbxsdk/fbxsdk_nsbegin.h>
21
22/** Template class for dynamic array holding objects.
23 * \nosubgrouping
24 * \see FbxStaticArray
25 */
26template <typename Type, typename Allocator=FbxBaseAllocator> class FbxDynamicArray
27{
28public:
29 //! Default constructor.
30 FbxDynamicArray() :
31 mArray(NULL),
32 mCapacity(0),
33 mSize(0),
34 mAllocator(sizeof(Type))
35 {
36 }
37
38 /** Constructor.
39 * \param pInitialSize initial capacity of this array */
40 FbxDynamicArray(const size_t pInitialSize) :
41 mArray(NULL),
42 mCapacity(0),
43 mSize(0),
44 mAllocator(sizeof(Type))
45 {
46 Reserve(pInitialSize);
47 }
48
49 /** Copy constructor.
50 * \remarks The copy constructor of \c Type will be
51 * invoked in order to copy the value of elements to the
52 * new array.
53 */
54 FbxDynamicArray(const FbxDynamicArray& pArray) :
55 mArray(NULL),
56 mCapacity(0),
57 mSize(0),
58 mAllocator(sizeof(Type))
59 {
60 Reserve(pArray.mCapacity);
61 CopyArray(mArray, pArray.mArray, pArray.mSize);
62 mSize = pArray.mSize;
63 }
64
65 //! Destructor.
66 ~FbxDynamicArray()
67 {
68 for( size_t i = 0; i < mSize; ++i )
69 {
70 mArray[i].~Type();
71 }
72 mAllocator.FreeMemory(mArray);
73 }
74
75 //! Gets the current capacity of the array.
76 size_t Capacity() const
77 {
78 return mCapacity;
79 }
80
81 //! Gets the size of the array.
82 size_t Size() const
83 {
84 return mSize;
85 }
86
87 /** Assures that sufficient memory is allocated to hold n objects in the array, and increases the capacity if necessary.
88 * \param pCount Number of objects to reserve */
89 void Reserve(const size_t pCount)
90 {
91 if( pCount > mCapacity )
92 {
93 //We don't use mAllocator.PreAllocate, because we want our array to be continuous in memory.
94 Type* lNewArray = (Type*)mAllocator.AllocateRecords(pCount);
95 MoveArray(lNewArray, mArray, mSize);
96 mAllocator.FreeMemory(mArray);
97 mArray = lNewArray;
98 mCapacity = pCount;
99 }
100 }
101
102 /** Appends n objects at the end of the array.
103 * \param pItem object to append
104 * \param pNCopies number of copies to append */
105 void PushBack(const Type& pItem, const size_t pNCopies = 1)
106 {
107 if( mSize + pNCopies > mCapacity )
108 {
109 size_t lNewSize = mCapacity + mCapacity / 2; //grow by 50%
110 if( mSize + pNCopies > lNewSize )
111 {
112 lNewSize = mSize + pNCopies;
113 }
114 Reserve(lNewSize);
115 }
116 FBX_ASSERT(mSize + pNCopies <= mCapacity);
117 Fill(mArray + mSize, pItem, pNCopies);
118 mSize += pNCopies;
119 }
120
121 /** Inserts n objects at the specified position.
122 * \param pIndex position index
123 * \param pItem object to insert
124 * \param pNCopies number of copies to append */
125 void Insert(const size_t pIndex, const Type& pItem, const size_t pNCopies=1)
126 {
127 FBX_ASSERT(pIndex >= 0);
128 FBX_ASSERT(pIndex <= mSize);
129 Type lValue = pItem; // in case pItem is in array
130 if( pNCopies == 0 )
131 {
132 }
133 else if( pIndex >= mSize )
134 {
135 PushBack(pItem, pNCopies);
136 }
137 else if( mSize + pNCopies > mCapacity )
138 {
139 size_t lNewSize = mCapacity + mCapacity / 2; //not enough room, grow by 50%
140 if( mSize + pNCopies > lNewSize )
141 {
142 lNewSize = mSize + pNCopies;
143 }
144
145 Type* lNewArray = (Type*)mAllocator.AllocateRecords(lNewSize);
146 MoveArray(lNewArray, mArray, pIndex); // copy prefix
147 Fill(lNewArray + pIndex, pItem, pNCopies); // copy values
148 MoveArray(lNewArray + pIndex + pNCopies, mArray + pIndex, mSize - pIndex); // copy suffix
149 mAllocator.FreeMemory(mArray);
150 mArray = lNewArray;
151 mSize += pNCopies;
152 mCapacity = lNewSize;
153 }
154 else
155 {
156 // copy suffix backwards
157 MoveArrayBackwards(mArray + pIndex + pNCopies, mArray + pIndex, mSize - pIndex);
158 Fill(mArray + pIndex, pItem, pNCopies); // copy values
159 mSize += pNCopies;
160 }
161 }
162
163 /** Removes n objects at the end.
164 * \param pNElements number of objects to remove */
165 void PopBack(size_t pNElements=1)
166 {
167 FBX_ASSERT(pNElements <= mSize);
168 for( size_t i = mSize - pNElements; i < mSize; ++i )
169 {
170 mArray[i].~Type();
171 }
172 mSize -= pNElements;
173 }
174
175 /** Removes n objects at the specified position.
176 * \param pIndex position index
177 * \param pNElements number of objects to remove */
178 void Remove(const size_t pIndex, size_t pNElements=1)
179 {
180 FBX_ASSERT(pIndex >= 0);
181 FBX_ASSERT(pIndex <= mSize);
182 FBX_ASSERT(pIndex + pNElements <= mSize);
183 if( pIndex + pNElements >= mSize )
184 {
185 PopBack(pNElements);
186 }
187 else
188 {
189 for( size_t i = pIndex; i < pIndex + pNElements; ++i )
190 {
191 mArray[i].~Type();
192 }
193 MoveOverlappingArray(&mArray[pIndex], &mArray[pIndex + pNElements], mSize - pIndex - pNElements);
194 mSize -= pNElements;
195 }
196 }
197
198 /** Gets nth object in the array.
199 * \param pIndex position index */
200 Type& operator[](const size_t pIndex)
201 {
202 return mArray[pIndex];
203 }
204
205 /** Gets nth object in the array.
206 * \param pIndex position index */
207 const Type& operator[](const size_t pIndex) const
208 {
209 return mArray[pIndex];
210 }
211
212 /** Retrieve the first item in the array.
213 * \return The first item in the array. */
214 Type& First()
215 {
216 return operator[](0);
217 }
218
219 /** Retrieve the first item in the array.
220 * \return The first item in the array. */
221 const Type& First() const
222 {
223 return operator[](0);
224 }
225
226 /** Retrieve the last item in the array.
227 * \return The last item in the array. */
228 Type& Last()
229 {
230 return operator[](mSize-1);
231 }
232
233 /** Retrieve the last item in the array.
234 * \return The last item in the array. */
235 const Type& Last() const
236 {
237 return operator[](mSize-1);
238 }
239
240 /** Find first matching element, from first to last.
241 * \param pItem The item to try to find in the array.
242 * \param pStartIndex The index to start searching from.
243 * \return Index of the first matching item, otherwise returns -1 (equivalent of SIZE_MAX for size_t). */
244 size_t Find(const Type& pItem, const size_t pStartIndex=0) const
245 {
246 for( size_t i = pStartIndex; i < mSize; ++i )
247 {
248 if( operator[](i) == pItem ) return i;
249 }
250 return -1;
251 }
252
253 /** Assignment operator.
254 * \remarks The copy constructor of \c Type will be invoked in order to copy the value of elements to the new array. */
255 FbxDynamicArray& operator=(const FbxDynamicArray& pArray)
256 {
257 Reserve(pArray.mCapacity);
258 CopyArray(mArray, pArray.mArray, pArray.mSize);
259 mSize = pArray.mSize;
260 return *this;
261 }
262
263/*****************************************************************************************************************************
264** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
265*****************************************************************************************************************************/
266#ifndef DOXYGEN_SHOULD_SKIP_THIS
267private:
268 static void CopyArray(Type* pDest, const Type* pSrc, size_t pCount)
269 {
270 for( int i = 0; i < int(pCount); i++ )
271 {
272 new(&(pDest[i])) Type(pSrc[i]); //in-place new won't allocate memory, so it is safe
273 }
274 }
275
276 static void MoveArray(Type* pDest, const Type* pSrc, size_t pCount)
277 {
278 for( int i = 0; i < int(pCount); i++ )
279 {
280 new(&(pDest[i])) Type(pSrc[i]); //in-place new won't allocate memory, so it is safe
281 }
282
283 for( int i = 0; i < int(pCount); i++ )
284 {
285 pSrc[i].~Type();
286 }
287 }
288
289 static void MoveOverlappingArray(Type* pDest, const Type* pSrc, size_t pCount)
290 {
291 for( int i = 0; i < int(pCount); i++ )
292 {
293 new(&(pDest[i])) Type(pSrc[i]); //in-place new won't allocate memory, so it is safe
294 pSrc[i].~Type();
295 }
296 }
297
298 static void MoveArrayBackwards(Type* pDest, const Type* pSrc, size_t pCount)
299 {
300 for( int i = 0; i < int(pCount); ++i )
301 {
302 new(&(pDest[pCount-1-i])) Type(pSrc[pCount-1-i]); //in-place new won't allocate memory, so it is safe
303 pSrc[pCount-1-i].~Type();
304 }
305 }
306
307 static void Fill(Type* pDest, const Type& pItem, size_t pCount)
308 {
309 for( int i = 0; i < int(pCount); i++ )
310 {
311 new(&(pDest[i])) Type(pItem); //in-place new won't allocate memory, so it is safe
312 }
313 }
314
315 Type* mArray;
316 size_t mCapacity;
317 size_t mSize;
318 Allocator mAllocator;
319#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
320};
321
322#include <fbxsdk/fbxsdk_nsend.h>
323
324#endif /* _FBXSDK_CORE_BASE_DYNAMICARRAY_H_ */
325