tc3d_array.h

来自「自己写的一些基本的3d引擎的基础的代码」· C头文件 代码 · 共 654 行 · 第 1/2 页

				 * @return	none
				 */
				virtual TC3D_Void Adjust(TC3D_U32 size)
				{
					T *pOld = pData;
					TC3D_U32 cpyCount;

					// Do not adjust if same size
					if(size == tAlloc)
						return;

					// Allocate an array of the new size
					pData = tAllocator.Allocate(size);

					// Only copy what fits the array
					cpyCount = size < tSize ? size : tSize;

					// Copy all elements
					for(TC3D_U32 i = 0; i < cpyCount; i++)
						tAllocator.Construct(pData + i, pOld[i]);
		
					// Destruct old elements
					for(TC3D_U32 i = 0; i < tSize; i++)
						tAllocator.Destruct(pOld + i);

					// Free the old components
					if(pOld)
						tAllocator.Deallocate(pOld);
					tAlloc = size;

					if(size < tSize)
						tSize = size;
				}

				/**
				 * Push an element to the back of the array, this is
				 * very efficient because adding an additional element
				 * to the end introduces no overhead besides allocating
				 * additional memory if the current size of the array
				 * is not enough. If the array is empty, initial size
				 * is allocated and can be changed either by modifying
				 * THMUD_ARRAY_INITIAL_SIZE definition or creating an
				 * array with an initial size.
				 *
				 * @param	item	item to push
				 * @return	none
				 */
				virtual TC3D_Void Push_Back(const T &item)
				{
					// Allocate additional memory if needed
					if(!tAlloc)
						Adjust(CC3D_ARRAY_INIT_SIZE);

					if(tSize >= tAlloc)
						Adjust(tAlloc * 2);

                    tAllocator.Construct(pData + (tSize++), item);
					tSorted = DC3D_FALSE;
				}

				/**
				 * Push an element to the front of the array, this
				 * function is in general slower than Push_Back and
				 * should be avoided if possible. It is here merely
				 * for completeness and may be used in some conditions.
				 * Besides being slower, the allocation properties
				 * are identical to Push_Back.
				 * 
				 * @param	item	item to push
				 * @return	none
				 */
				virtual TC3D_Void Push_Front(const T &item)
				{
					// Allocate additional memory if needed
					if(!tAlloc)
						Adjust(CC3D_ARRAY_INIT_SIZE);

					if(tSize >= tAlloc)
						Adjust(tAlloc * 2);

					for(TC3D_U32 i = tSize; i > 0; i--)
						tAllocator.Construct(pData + i, pData[i - 1]);

					tAllocator.Construct(pData, item);
					tSize++;
					tSorted = DC3D_FALSE;
				}
				
				/**
				 * Pops an item from the back of the array
				 *
				 * @param	none
				 * @return	none
				 */
				virtual T Pop_Back()
				{
					T item = *(End() - 1);
					Erase(End() - 1, End());
					return item;
				}

				/**
				 * Pops an item from the front of the array
				 *
				 * @param	none
				 * @return	none
				 */
				virtual TC3D_Void Pop_Front()
				{
					T item = *Begin();
					Erase(Begin(), Begin() + 1);
					return item;
				}

				/**
				 * Insert an element to a specific place specified by
				 * an array iterator. This function is also slow because
				 * it will shift the array to make room for the newly added
				 * element. It also allocates memory if the array is not
				 * big enough
				 * 
				 * @param	it		iterator specifying the position to add
				 * @param	item	item to insert
				 * @return	none
				 */
				virtual TC3D_Void Insert(const CC3D_Iterator &it, const T &item)
				{
					if(!tSize)
					{
						Push_Back(item);
						return;
					}

					MC3D_DEBUG_ASSERT(it.pData <= (pData + tSize));

					if(tSize >= tAlloc)
						Adjust(tAlloc * 2);

					for(T *i = pData + tSize; i > it.pData; i--)
						tAllocator.Construct(i, *(i - 1));

					tAllocator.Construct(it.pData, item);
					tSize++;
					tSorted = DC3D_TRUE;
				}

				/** 
				 * Erase a range of elements pointed by the begin
				 * and end iterators. Once the elements have been
				 * erased and shifted, the array is adjusted to the
				 * proper size according to the allocation standards.
				 *
				 * @param	begin	begin point of deletion
				 * @param	end		end point of deletion
				 * @return	none
				 */
				virtual TC3D_Void Erase(const CC3D_Iterator &begin, const CC3D_Iterator &end)
				{
					if(begin.pData == end.pData)
						return;

					MC3D_DEBUG_ASSERT((end.pData - begin.pData) >= 0);
					MC3D_DEBUG_ASSERT((end.pData - begin.pData) <= (TC3D_S32)tSize);

					TC3D_U32 size = (TC3D_U32)(end.pData - begin.pData);
					T *pEnd = pData + tSize;
					
					// Shift in as many elements as possible
					TC3D_U32 shifted = 0;
					for(T *i = end.pData; i < pEnd; i++)
					{
						tAllocator.Destruct(i - size);
						tAllocator.Construct(i - size, *i);
						shifted++;
					}

					// Destroy the tailing elements after shifting
					for(T *i = pEnd - 1; i >= (pEnd - shifted); i--)
						tAllocator.Destruct(i);

					// Destroy elements if less shifting than deletion
					for(T *i = begin.pData + shifted; i < end.pData; i++)
						tAllocator.Destruct(i);

					tSize -= size;
					
					// Shrink the array accordingly
					TC3D_U32 shrinkSize = tAlloc;

					TC3D_U32 shrink = (TC3D_U32)(shrinkSize * 0.5f);
					while(tSize < shrink && shrinkSize > CC3D_ARRAY_INIT_SIZE)
					{
						shrinkSize = shrink;
						shrink = (TC3D_U32)(shrink * 0.5f);
					}
					if(shrinkSize < tAlloc)
						Adjust(shrinkSize > CC3D_ARRAY_INIT_SIZE ? shrinkSize : CC3D_ARRAY_INIT_SIZE);
				}

				/**
				 * Erases a single element with a given index
				 *
				 * @param	index	index value
				 * @return	none
				 */
				virtual TC3D_Void Erase(TC3D_U32 index) 
				{ 
					Erase(Begin() + index); 
				}

				/** 
				 * Erases a single element at the position pointed
				 * by the begin iterator. The elements after the
				 * point of deletion will be shifted properly.
				 *
				 * @param	begin	begin point of deletion
				 * @return	none
				 */
				virtual TC3D_Void Erase(const CC3D_Iterator &begin) 
				{ 
					Erase(begin, begin + 1); 
				}

				/** Get the size used of the array */
				inline virtual TC3D_U32 Size() const 
				{ 
					return tSize; 
				}

				/** Get the allocation size of the array */
				inline virtual TC3D_U32 Alloc() const 
				{ 
					return tAlloc; 
				}

				/** Get the constant pointer to the data elements */
				inline virtual const T *Pointer_Const() const 
				{ 
					return pData; 
				}

				/** Gets the pointer to the data elements */
				inline virtual T *Pointer() const
				{
					return pData;
				}

				/** Returns an iterator pointed at the beginning of the array */
				inline CC3D_Iterator Begin()
				{
					return CC3D_Iterator(pData, this);
				}
				
				/** Returns an iterator pointed at the end of the array */
				inline CC3D_Iterator End()
				{
					return CC3D_Iterator(pData + tSize, this);
				}

				/** Check if the array is empty */
				inline virtual TC3D_Bool Empty() const
				{
					return (tSize == 0);
				}

				/**
				 * Clear the array and deallocate all of its memory.
				 * This function can be used to clear out the entire
				 * array at once. Note that it does free all the memory
				 * so that adding components later will reallocate
				 * memory.
				 *
				 * @param	none
				 * @return	none
				 */
				virtual TC3D_Void Clear()
				{
					if(!tAlloc)
						return;

					// Destruct all contents
					for(TC3D_U32 i = 0; i < tSize; i++)
						tAllocator.Destruct(pData + i);

					// Deallocate array
					tAllocator.Deallocate(pData);

					// Reset size information
					pData = NULL;
					tSize = 0;
					tAlloc = 0;
					tSorted = DC3D_TRUE;
				}


				/** Array indexing */
				inline virtual T &operator [] (TC3D_U32 index) const
				{
					MC3D_DEBUG_ASSERT(index < tSize);

					return pData[index];
				}

				/** Array asignment */
				virtual TC3D_Array<T, TAlloc> &operator = (const TC3D_Array<T, TAlloc> &src)
				{
					if(this != &src)
					{
						// Clear, resize etc....
						Clear();
						Adjust(src.tAlloc);
						tSize = src.tSize;

						// Copyover all of the elements
						for(TC3D_U32 i = 0; i < src.tSize; i++)
                            tAllocator.Construct(pData + i, src.pData[i]);

						tSorted = src.tSorted;
					}
					return *this;
				}
		};
	};
};

#endif