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 fbxarray.h
13#ifndef _FBXSDK_CORE_BASE_ARRAY_H_
14#define _FBXSDK_CORE_BASE_ARRAY_H_
15
16#include <fbxsdk/fbxsdk_def.h>
17
18#include <fbxsdk/fbxsdk_nsbegin.h>
19
20/** Class for array of basic elements such as pointers and basic types. This class will not
21* call constructor and destructor for elements, thus it is not suitable for object references.
22* Memory allocations are always done in a single contiguous memory region. */
23template <class T> class FbxArray
24{
25public:
26 //! Element compare function pointer definition
27 typedef int (*CompareFunc)(const void*, const void*);
28
29 //! Constructor.
30 FbxArray() : mSize(0), mCapacity(0), mArray(NULL){}
31
32 //! Reserve constructor.
33 FbxArray(const int pCapacity) : mSize(0), mCapacity(0), mArray(NULL){ if( pCapacity > 0 ) Reserve(pCapacity); }
34
35 //! Copy constructor.
36 FbxArray(const FbxArray& pArray) : mSize(0), mCapacity(0), mArray(NULL){ *this = pArray; }
37
38 /** Destructor.
39 * \remark The destructor for each element will not be called. */
40 ~FbxArray(){ Clear(); }
41
42 /** Insert an element at the given position, growing the array if capacity is not sufficient.
43 * \param pIndex Position where to insert the element. Must be a positive value.
44 * \param pElement Element to insert in the array.
45 * \param pCompact If \c true and capacity is exceeded, grow capacity by one, otherwise double capacity (default).
46 * \return -1 if insert failed, otherwise the position of the inserted element in the array.
47 * \remark If the given index is greater than Size(), the element is appended at the end. Use compact mode only if you need to save memory. */
48 inline int InsertAt(const int pIndex, const T& pElement, bool pCompact=false)
49 {
50 FBX_ASSERT_RETURN_VALUE(pIndex >= 0, -1);
51 int lIndex = FbxMin(pIndex, mSize);
52 if( mSize >= mCapacity )
53 {
54 T lElement = pElement; //Copy element because we might move memory
55 int lNewCapacity = FbxMax(pCompact ? mCapacity + 1 : mCapacity * 2, 1); //We always double capacity when not compacting
56 T* lArray = Allocate(lNewCapacity);
57 FBX_ASSERT_RETURN_VALUE(lArray, -1);
58 mArray = lArray;
59 mCapacity = lNewCapacity;
60 return InsertAt(pIndex, lElement); //Insert copied element because reference might be moved
61 }
62
63 if( lIndex < mSize ) //Move elements to leave a space open to insert the new element
64 {
65 //If pElement is inside memmove range, copy element and insert copy instead
66 if( (&pElement >= &mArray[lIndex]) && (&pElement < &mArray[mSize]) )
67 {
68 T lElement = pElement;
69 return InsertAt(pIndex, lElement);
70 }
71 memmove(&mArray[lIndex + 1], &mArray[lIndex], (mSize - lIndex) * sizeof(T));
72 }
73
74 memcpy(&mArray[lIndex], &pElement, sizeof(T));
75 mSize++;
76
77 return lIndex;
78 }
79
80 /** Append an element at the end of the array, doubling the array if capacity is not sufficient.
81 * \param pElement Element to append to the array.
82 * \return -1 if add failed, otherwise the position of the added element in the array. */
83 inline int Add(const T& pElement)
84 {
85 return InsertAt(mSize, pElement);
86 }
87
88 /** Append an element at the end of array, if not already present, doubling the array if capacity is not sufficient.
89 * \param pElement Element to append to the array.
90 * \return -1 if add failed, otherwise the position of the added element in the array. */
91 inline int AddUnique(const T& pElement)
92 {
93 int lIndex = Find(pElement);
94 return ( lIndex == -1 ) ? Add(pElement) : lIndex;
95 }
96
97 /** Append an element at the end of the array, growing the array by one element if capacity is not sufficient.
98 * \param pElement Element to append to the array.
99 * \return -1 if add failed, otherwise the position of the added element in the array. */
100 inline int AddCompact(const T& pElement)
101 {
102 return InsertAt(mSize, pElement, true);
103 }
104
105 /** Retrieve the number of element contained in the array. To increase the capacity without increasing the size, please use Reserve().
106 * \return The number of element in the array.
107 * \remark The size of the array cannot exceed its capacity. */
108 inline int Size() const { return mSize; }
109
110 /** Retrieve the current allocated memory capacity of the array.
111 * \return The capacity of the array in number of element.
112 * \remark The capacity will always be greater or equal to its size. */
113 inline int Capacity() const { return mCapacity; }
114
115 /** Retrieve a reference of the element at given index position in the array.
116 * \param pIndex Position of element in the array.
117 * \return A reference to the element at the specified position in the array.
118 * \remark No error will be thrown if the index is out of bounds. */
119 inline T& operator[](const int pIndex) const
120 {
121 #ifdef _DEBUG
122 FBX_ASSERT_MSG(pIndex >= 0, "Index is out of range!");
123 if( pIndex >= mSize )
124 {
125 if( pIndex < mCapacity )
126 {
127 FBX_ASSERT_NOW("Index is out of range, but not outside of capacity! Call SetAt() to use reserved memory.");
128 }
129 else FBX_ASSERT_NOW("Index is out of range!");
130 }
131 #endif
132 return (T&)mArray[pIndex];
133 }
134
135 /** Retrieve a copy of the element at given index position in the array.
136 * \param pIndex Position of element in the array.
137 * \return The value of the element at the specified position in the array.
138 * \remark No error will be thrown if the index is out of bounds. */
139 inline T GetAt(const int pIndex) const
140 {
141 return operator[](pIndex);
142 }
143
144 /** Retrieve a copy of the first element.
145 * \return Copy of the first element.
146 * \remark The array should have at least one element and no error will be thrown if the array is empty. */
147 inline T GetFirst() const
148 {
149 return GetAt(0);
150 }
151
152 /** Retrieve a copy of the last element.
153 * \return Copy of the last element.
154 * \remark The array should have at least one element and no error will be thrown if the array is empty. */
155 inline T GetLast() const
156 {
157 return GetAt(mSize-1);
158 }
159
160 /** Find first matching element, from first to last.
161 * \param pElement The element to be compared to each of the elements.
162 * \param pStartIndex The position to start searching from.
163 * \return Position of first matching element or -1 if there is no matching element. */
164 inline int Find(const T& pElement, const int pStartIndex=0) const
165 {
166 FBX_ASSERT_RETURN_VALUE(pStartIndex >= 0, -1);
167 for( int i = pStartIndex; i < mSize; ++i )
168 {
169 if( operator[](i) == pElement ) return i;
170 }
171 return -1;
172 }
173
174 /** Find first matching element, from last to first.
175 * \param pElement The element to be compared to each of the elements.
176 * \param pStartIndex The position to start searching from.
177 * \return Position of first matching element or -1 if there is no matching element. */
178 inline int FindReverse(const T& pElement, const int pStartIndex=FBXSDK_INT_MAX) const
179 {
180 for( int i = FbxMin(pStartIndex, mSize-1); i >= 0; --i )
181 {
182 if( operator[](i) == pElement ) return i;
183 }
184 return -1;
185 }
186
187 /** Request for allocation of additional memory without inserting new elements. After the memory has been reserved, please use SetAt() to initialize elements.
188 * \param pCapacity The number of additional element memory allocation requested.
189 * \return \c true if the memory allocation succeeded or if the capacity is unchanged, \c false otherwise.
190 * \remark If the requested capacity is less than or equal to the current capacity, this call has no effect. In either case, Size() is unchanged. */
191 inline bool Reserve(const int pCapacity)
192 {
193 FBX_ASSERT_RETURN_VALUE(pCapacity > 0, false);
194 if( pCapacity > mCapacity )
195 {
196 T* lArray = Allocate(pCapacity);
197 FBX_ASSERT_RETURN_VALUE(lArray, false);
198 mArray = lArray;
199 mCapacity = pCapacity;
200
201 //Initialize new memory to zero
202 memset(&mArray[mSize], 0, (mCapacity - mSize) * sizeof(T));
203 }
204 return true;
205 }
206
207 /** Set the element at given position in the array.
208 * \param pIndex Position of element in the array.
209 * \param pElement The new element.
210 * \remark If the index is outside range, and outside capacity, this call has no effect. However, if index is
211 * within capacity range, element count is increased such that Size() will become pIndex + 1. */
212 inline void SetAt(const int pIndex, const T& pElement)
213 {
214 FBX_ASSERT_RETURN(pIndex < mCapacity);
215 if( pIndex >= mSize ) mSize = pIndex + 1;
216 if( mArray ) memcpy(&mArray[pIndex], &pElement, sizeof(T));
217 }
218
219 /** Set the value of the first element.
220 * \param pElement The new value of the last element.
221 * \remark The array should have at least one element and no error will be thrown if the array is empty. */
222 inline void SetFirst(const T& pElement)
223 {
224 SetAt(0, pElement);
225 }
226
227 /** Set the value of the last element.
228 * \param pElement The new value of the last element.
229 * \remark The array should have at least one element and no error will be thrown if the array is empty. */
230 inline void SetLast(const T& pElement)
231 {
232 SetAt(mSize-1, pElement);
233 }
234
235 /** Remove an element at the given position in the array.
236 * \param pIndex Position of the element to remove.
237 * \return Removed element.
238 * \remark No error will be thrown if the index is out of bounds. */
239 inline T RemoveAt(const int pIndex)
240 {
241 T lElement = GetAt(pIndex);
242 if( pIndex + 1 < mSize )
243 {
244 memmove(&mArray[pIndex], &mArray[pIndex + 1], (mSize - pIndex - 1) * sizeof(T));
245 }
246 mSize--;
247 return lElement;
248 }
249
250 /** Remove the first element in the array.
251 * \return Removed element.
252 * \remark The array should have at least one element and no error will be thrown if the array is empty. */
253 inline T RemoveFirst()
254 {
255 return RemoveAt(0);
256 }
257
258 /** Remove the last element in the array.
259 * \return Removed element.
260 * \remark The array should have at least one element and no error will be thrown if the array is empty. */
261 inline T RemoveLast()
262 {
263 return RemoveAt(mSize-1);
264 }
265
266 /** Remove first matching element in the array.
267 * \param pElement Element to be removed.
268 * \return \c true if a matching element is found and removed, \c false otherwise. */
269 inline bool RemoveIt(const T& pElement)
270 {
271 int Index = Find(pElement);
272 if( Index >= 0 )
273 {
274 RemoveAt(Index);
275 return true;
276 }
277 return false;
278 }
279
280 /** Remove a range of elements at the given position in the array.
281 * \param pIndex Begin position of the elements to remove.
282 * \param pCount The count of elements to remove.
283 * \return \c true if successful, otherwise \c false. */
284 inline void RemoveRange(const int pIndex, const int pCount)
285 {
286 if( pIndex + pCount < mSize )
287 {
288 memmove(&mArray[pIndex], &mArray[pIndex + pCount], (mSize - pIndex - pCount) * sizeof(T));
289 }
290 mSize -= pCount;
291 }
292
293 /** Inserts or erases elements at the end such that Size() becomes pSize, increasing capacity if needed. Please use SetAt() to initialize any new elements.
294 * \param pSize The new count of elements to set the array to. Must be greater or equal to zero.
295 * \return \c true if the memory (re)allocation succeeded, \c false otherwise.
296 * \remark If the requested element count is less than or equal to the current count, elements are freed from memory. Otherwise, the array grows and elements are unchanged. */
297 inline bool Resize(const int pSize)
298 {
299 if( pSize == mSize && mSize == mCapacity ) return true;
300
301 if( pSize == 0 )
302 {
303 Clear();
304 return true;
305 }
306
307 FBX_ASSERT_RETURN_VALUE(pSize > 0, false);
308 if( pSize != mCapacity )
309 {
310 T* lArray = Allocate(pSize);
311 FBX_ASSERT_RETURN_VALUE(lArray, false);
312 mArray = lArray;
313 }
314
315 if( pSize > mCapacity ) //Initialize new memory to zero
316 {
317 memset(&mArray[mSize], 0, (pSize - mSize) * sizeof(T));
318 }
319
320 mSize = pSize;
321 mCapacity = pSize;
322 return true;
323 }
324
325 /** Increase size of array by the specified size.
326 * \param pSize The size to add to the array size.
327 * \return \c true if operation succeeded, \c false otherwise. */
328 inline bool Grow(const int pSize)
329 {
330 return Resize(mSize + pSize);
331 }
332
333 /** Reduce size of array by the specified size.
334 * \param pSize The size to remove from the array size.
335 * \return \c true if operation succeeded, \c false otherwise. */
336 inline bool Shrink(const int pSize)
337 {
338 return Resize(mSize - pSize);
339 }
340
341 /** Compact the array so that its capacity is the same as its size.
342 * \return \c true if operation succeeded, \c false otherwise. */
343 inline bool Compact()
344 {
345 return Resize(mSize);
346 }
347
348 /** Reset the number of element to zero and free the memory allocated.
349 * \remark This only free the memory allocated by the array, and doesn't call the destructor of each element. */
350 inline void Clear()
351 {
352 if( mArray != NULL )
353 {
354 mSize = 0;
355 mCapacity = 0;
356 FbxFree(mArray);
357 mArray = NULL;
358 }
359 }
360
361 /** Sort the array using the specified compare function pointer
362 * \param pCompareFunc The compare function to use to sort elements. */
363 inline void Sort(CompareFunc pCompareFunc)
364 {
365 qsort(mArray, mSize, sizeof(T), pCompareFunc);
366 }
367
368 //! Get pointer to internal array of elements.
369 inline T* GetArray() const { return mArray ? (T*)mArray : NULL; }
370
371 //! Cast operator.
372 inline operator T* (){ return mArray ? (T*)mArray : NULL; }
373
374 /** Append another array at the end of this array.
375 * \param pOther The other array to append to this array. */
376 inline void AddArray(const FbxArray<T>& pOther)
377 {
378 if( Grow(pOther.mSize) )
379 {
380 memcpy(&mArray[mSize - pOther.mSize], pOther.mArray, pOther.mSize * sizeof(T));
381 }
382 }
383
384 /** Append the elements of another array at the end of this array if they are not present.
385 * \param pOther Another array. */
386 inline void AddArrayNoDuplicate(const FbxArray<T>& pOther)
387 {
388 for( int i = 0, c = pOther.mSize; i < c; ++i )
389 {
390 AddUnique(pOther[i]);
391 }
392 }
393
394 /** Remove the elements of another array from this array is they are present.
395 * \param pOther Another array. */
396 inline void RemoveArray(const FbxArray<T>& pOther)
397 {
398 for( int i = 0, c = pOther.mSize; i < c; ++i )
399 {
400 RemoveIt(pOther[i]);
401 }
402 }
403
404 /** Operator to copy elements of an array.
405 * \return this array containing a copy of pOther elements. */
406 inline FbxArray<T>& operator=(const FbxArray<T>& pOther)
407 {
408 if( this != &pOther )
409 {
410 if( Resize(pOther.mSize) )
411 {
412 memcpy(mArray, pOther.mArray, pOther.mSize * sizeof(T));
413 }
414 }
415 return *this;
416 }
417
418 /** Operator to compare elements of an array.
419 * \return \c true if the two arrays are equal, otherwise \c false. */
420 inline bool operator==(const FbxArray<T>& pOther) const
421 {
422 if( this == &pOther ) return true;
423 if( mSize != pOther.mSize ) return false;
424 return memcmp(mArray, pOther.mArray, sizeof(T) * mSize) == 0;
425 }
426
427/*****************************************************************************************************************************
428** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
429*****************************************************************************************************************************/
430#ifndef DOXYGEN_SHOULD_SKIP_THIS
431 inline int GetCount() const { return mSize; }
432
433private:
434 inline T* Allocate(const int pCapacity)
435 {
436 return (T*)FbxRealloc(mArray, pCapacity * sizeof(T));
437 }
438
439 int mSize;
440 int mCapacity;
441 T* mArray;
442
443#if defined(FBXSDK_COMPILER_MSC)
444 //Previously class FbxArray is for pointers. Somehow, it's used to store other types. Here's a compile-time checking for known incompatible classes.
445 //If it happens you find new incompatible ones, declare them with macro FBXSDK_INCOMPATIBLE_WITH_ARRAY. Also see file fbxstring.h.
446 FBX_ASSERT_STATIC(FBXSDK_IS_SIMPLE_TYPE(T) || __is_enum(T) || (__has_trivial_constructor(T)&&__has_trivial_destructor(T)) || !FBXSDK_IS_INCOMPATIBLE_WITH_ARRAY(T));
447#endif
448
449#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
450};
451
452//! Call FbxFree on each element of the array, and then clear it.
453template <class T> inline void FbxArrayFree(FbxArray<T>& pArray)
454{
455 for( int i = 0, c = pArray.Size(); i < c; ++i )
456 {
457 FbxFree(pArray[i]);
458 }
459 pArray.Clear();
460}
461
462//! Call FbxDelete on each element of the array, and then clear it.
463template <class T> inline void FbxArrayDelete(FbxArray<T>& pArray)
464{
465 for( int i = 0, c = pArray.Size(); i < c; ++i )
466 {
467 FbxDelete(pArray[i]);
468 }
469 pArray.Clear();
470}
471
472//! Call Destroy on each element of the array, and then clear it.
473template <class T> inline void FbxArrayDestroy(FbxArray<T>& pArray)
474{
475 for( int i = 0, c = pArray.Size(); i < c; ++i )
476 {
477 (pArray[i])->Destroy();
478 }
479 pArray.Clear();
480}
481
482//! Make sure to break build if someone try to make FbxArray<FbxArray<T>>, which is not supported.
483template <class T> FBXSDK_INCOMPATIBLE_WITH_ARRAY_TEMPLATE(FbxArray<T>);
484
485#include <fbxsdk/fbxsdk_nsend.h>
486
487#endif /* _FBXSDK_CORE_BASE_ARRAY_H_ */
488