third_party/PowerVR_SDK/Tools/PVRTArray.h

/*!****************************************************************************

 @file         PVRTArray.h
 @copyright    Copyright (c) Imagination Technologies Limited.
 @brief        Expanding array template class. Allows appending and direct
               access. Mixing access methods should be approached with caution.

******************************************************************************/
#ifndef __PVRTARRAY_H__
#define __PVRTARRAY_H__

#include "PVRTGlobal.h"
#include "PVRTError.h"

/******************************************************************************
**  Classes
******************************************************************************/

/*!***************************************************************************
 @class       CPVRTArray
 @brief       Expanding array template class.
*****************************************************************************/
template<typename T>
class CPVRTArray
{
public:
	/*!***************************************************************************
	@brief     Blank constructor. Makes a default sized array.
	*****************************************************************************/
	CPVRTArray() : m_uiSize(0), m_uiCapacity(GetDefaultSize())
	{
		m_pArray = new T[m_uiCapacity];
	}

	/*!***************************************************************************
	@brief  	Constructor taking initial size of array in elements.
	@param[in]	uiSize	intial size of array
	*****************************************************************************/
	CPVRTArray(const unsigned int uiSize) : m_uiSize(0), m_uiCapacity(uiSize)
	{
		_ASSERT(uiSize != 0);
		m_pArray = new T[uiSize];
	}

	/*!***************************************************************************
	@brief      Copy constructor.
	@param[in]	original	the other dynamic array
	*****************************************************************************/
	CPVRTArray(const CPVRTArray& original) : m_uiSize(original.m_uiSize),
											  m_uiCapacity(original.m_uiCapacity)
	{
		m_pArray = new T[m_uiCapacity];
		for(unsigned int i=0;i<m_uiSize;i++)
		{
			m_pArray[i]=original.m_pArray[i];
		}
	}

	/*!***************************************************************************
	@brief      constructor from ordinary array.
	@param[in]	pArray		an ordinary array
	@param[in]	uiSize		number of elements passed
	*****************************************************************************/
	CPVRTArray(const T* const pArray, const unsigned int uiSize) : m_uiSize(uiSize),
														  m_uiCapacity(uiSize)
	{
		_ASSERT(uiSize != 0);
		m_pArray = new T[uiSize];
		for(unsigned int i=0;i<m_uiSize;i++)
		{
			m_pArray[i]=pArray[i];
		}
	}

	/*!***************************************************************************
	@brief      constructor from a capacity and initial value.
	@param[in]	uiSize		initial capacity
	@param[in]	val			value to populate with
	*****************************************************************************/
	CPVRTArray(const unsigned int uiSize, const T& val)	: m_uiSize(uiSize),
														m_uiCapacity(uiSize)
	{
		_ASSERT(uiSize != 0);
		m_pArray = new T[uiSize];
		for(unsigned int uiIndex = 0; uiIndex < m_uiSize; ++uiIndex)
		{
			m_pArray[uiIndex] = val;
		}
	}

	/*!***************************************************************************
	@brief      Destructor.
	*****************************************************************************/
	virtual ~CPVRTArray()
	{
		if(m_pArray)
			delete [] m_pArray;
	}

	/*!***************************************************************************
	@brief      Inserts an element into the array, expanding it
				if necessary.
	@param[in]	pos		The position to insert the new element at
	@param[in]	addT	The element to insert
	@return 	The index of the new item or -1 on failure.
	*****************************************************************************/
	int Insert(const unsigned int pos, const T& addT)
	{
		unsigned int uiIndex = pos;

		if(pos >= m_uiSize) // Are we adding to the end
			uiIndex = Append(addT);
		else
		{
			unsigned int uiNewCapacity = 0;
			T* pArray = m_pArray;

			if(m_uiSize > m_uiCapacity)
			{
				uiNewCapacity = m_uiCapacity + 10;	// Expand the array by 10.

				pArray = new T[uiNewCapacity];		// New Array

				if(!pArray)
					return -1;						// Failed to allocate memory!

				// Copy the first half to the new array
				for(unsigned int i = 0; i < pos; ++i)
				{
					pArray[i] = m_pArray[i];
				}
			}

			// Copy last half to the new array
			for(unsigned int i = m_uiSize; i > pos; --i)
			{
				pArray[i] = m_pArray[i - 1];
			}

			// Insert our new element
			pArray[pos] = addT;
			uiIndex = pos;

			// Increase our size
			++m_uiSize;

			// Switch pointers and free memory if needed
			if(pArray != m_pArray)
			{
				m_uiCapacity = uiNewCapacity;
				delete[] m_pArray;
				m_pArray = pArray;
			}
		}

		return uiIndex;
	}

	/*!***************************************************************************
	@brief      Appends an element to the end of the array, expanding it
				if necessary.
	@param[in]	addT	The element to append
	@return 	The index of the new item.
	*****************************************************************************/
	unsigned int Append(const T& addT)
	{
		unsigned int uiIndex = Append();
		m_pArray[uiIndex] = addT;
		return uiIndex;
	}

	/*!***************************************************************************
	@brief      Creates space for a new item, but doesn't add. Instead
				returns the index of the new item.
	@return 	The index of the new item.
	*****************************************************************************/
	unsigned int Append()
	{
		unsigned int uiIndex = m_uiSize;
		SetCapacity(m_uiSize+1);
		m_uiSize++;

		return uiIndex;
	}

	/*!***************************************************************************
	@brief      Clears the array.
	*****************************************************************************/
	void Clear()
	{
		m_uiSize = 0U;
	}

	/*!***************************************************************************
	@brief      Changes the array to the new size
	@param[in]	uiSize		New size of array
	*****************************************************************************/
	EPVRTError Resize(const unsigned int uiSize)
	{
		EPVRTError err = SetCapacity(uiSize);

		if(err != PVR_SUCCESS)
			return err;

		m_uiSize = uiSize;
		return PVR_SUCCESS;
	}

	/*!***************************************************************************
	@brief      Expands array to new capacity
	@param[in]	uiSize		New capacity of array
	*****************************************************************************/
	EPVRTError SetCapacity(const unsigned int uiSize)
	{
		if(uiSize <= m_uiCapacity)
			return PVR_SUCCESS;	// nothing to be done

		unsigned int uiNewCapacity;
		if(uiSize < m_uiCapacity*2)
		{
			uiNewCapacity = m_uiCapacity*2;			// Ignore the new size. Expand to twice the previous size.
		}
		else
		{
			uiNewCapacity = uiSize;
		}

		T* pNewArray = new T[uiNewCapacity];		// New Array
		if(!pNewArray)
			return PVR_FAIL;						// Failed to allocate memory!

		// Copy source data to new array
		for(unsigned int i = 0; i < m_uiSize; ++i)
		{
			pNewArray[i] = m_pArray[i];
		}

		// Switch pointers and free memory
		m_uiCapacity	= uiNewCapacity;
		T* pOldArray	= m_pArray;
		m_pArray		= pNewArray;
		delete [] pOldArray;
		return PVR_SUCCESS;
	}

	/*!***************************************************************************
	@fn     	Copy
	@brief      A copy function. Will attempt to copy from other CPVRTArrays
				if this is possible.
	@param[in]	other	The CPVRTArray needing copied
	*****************************************************************************/
	template<typename T2>
	void Copy(const CPVRTArray<T2>& other)
	{
		T* pNewArray = new T[other.GetCapacity()];
		if(pNewArray)
		{
			// Copy data
			for(unsigned int i = 0; i < other.GetSize(); i++)
			{
				pNewArray[i] = other[i];
			}

			// Free current array
			if(m_pArray)
				delete [] m_pArray;

			// Swap pointers
			m_pArray		= pNewArray;

			m_uiCapacity	= other.GetCapacity();
			m_uiSize		= other.GetSize();
		}
	}

	/*!***************************************************************************
	@brief      assignment operator.
	@param[in]	other	The CPVRTArray needing copied
	*****************************************************************************/
	CPVRTArray& operator=(const CPVRTArray<T>& other)
	{
		if(&other != this)
			Copy(other);

		return *this;
	}

	/*!***************************************************************************
	@brief      appends an existing CPVRTArray on to this one.
	@param[in]	other		the array to append.
	*****************************************************************************/
	CPVRTArray& operator+=(const CPVRTArray<T>& other)
	{
		if(&other != this)
		{
			for(unsigned int uiIndex = 0; uiIndex < other.GetSize(); ++uiIndex)
			{
				Append(other[uiIndex]);
			}
		}

		return *this;
	}

	/*!***************************************************************************
	@brief      Indexed access into array. Note that this has no error
				checking whatsoever
	@param[in]	uiIndex	index of element in array
	@return 	the element indexed
	*****************************************************************************/
	T& operator[](const unsigned int uiIndex)
	{
		_ASSERT(uiIndex < m_uiCapacity);
		return m_pArray[uiIndex];
	}

	/*!***************************************************************************
	@brief      Indexed access into array. Note that this has no error checking whatsoever
	@param[in]	uiIndex	    index of element in array
	@return 	The element indexed
	*****************************************************************************/
	const T& operator[](const unsigned int uiIndex) const
	{
		_ASSERT(uiIndex < m_uiCapacity);
		return m_pArray[uiIndex];
	}

	/*!***************************************************************************
	@return 	Size of array
	@brief      Gives current size of array/number of elements
	*****************************************************************************/
	unsigned int GetSize() const
	{
		return m_uiSize;
	}

	/*!***************************************************************************
	@brief      Gives the default size of array/number of elements
	@return 	Default size of array
	*****************************************************************************/
	static unsigned int GetDefaultSize()
	{
		return 16U;
	}

	/*!***************************************************************************
	@brief      Gives current allocated size of array/number of elements
	@return 	Capacity of array
	*****************************************************************************/
	unsigned int GetCapacity() const
	{
		return m_uiCapacity;
	}

	/*!***************************************************************************
	@brief      Indicates whether the given object resides inside the array. 
	@param[in]	object		The object to check in the array
	@return 	true if object is contained in this array.
	*****************************************************************************/
	bool Contains(const T& object) const
	{
		for(unsigned int uiIndex = 0; uiIndex < m_uiSize; ++uiIndex)
		{
			if(m_pArray[uiIndex] == object)
				return true;
		}
		return false;
	}

	/*!***************************************************************************
	@brief     	Attempts to find the object in the array and returns a
				pointer if it is found, or NULL if not found. The time
				taken is O(N).
	@param[in]	object		The object to check in the array
	@return 	Pointer to the found object or NULL.
	*****************************************************************************/
	T* Find(const T& object) const
	{
		for(unsigned int uiIndex = 0; uiIndex < m_uiSize; ++uiIndex)
		{
			if(m_pArray[uiIndex] == object)
				return &m_pArray[uiIndex];
		}
		return NULL;
	}

	/*!***************************************************************************
	@brief      Simple bubble-sort of the array. Pred should be an object that
				defines a bool operator().
	@param[in]	predicate		The object which defines "bool operator()"
	*****************************************************************************/
	template<class Pred>
	void Sort(Pred predicate)
	{
		bool bSwap;
		for(unsigned int i=0; i < m_uiSize; ++i)
		{
			bSwap = false;
			for(unsigned int j=0; j < m_uiSize-1; ++j)
			{
				if(predicate(m_pArray[j], m_pArray[j+1]))
				{
					PVRTswap(m_pArray[j], m_pArray[j+1]);
					bSwap = true;
				}
			}

			if(!bSwap)
				return;
		}
	}

	/*!***************************************************************************
	@brief      Removes an element from the array.
	@param[in]	uiIndex		The index to remove
	@return 	success or failure
	*****************************************************************************/
	virtual EPVRTError Remove(unsigned int uiIndex)
	{
		_ASSERT(uiIndex < m_uiSize);
		if(m_uiSize == 0)
			return PVR_FAIL;

		if(uiIndex == m_uiSize-1)
		{
			return RemoveLast();
		}
        
        m_uiSize--;
        // Copy the data. memmove will only work for built-in types.
        for(unsigned int uiNewIdx = uiIndex; uiNewIdx < m_uiSize; ++uiNewIdx)
        {
            m_pArray[uiNewIdx] = m_pArray[uiNewIdx+1];
        }
		
		return PVR_SUCCESS;
	}

	/*!***************************************************************************
	@brief    	Removes the last element. Simply decrements the size value
	@return 	success or failure
	*****************************************************************************/
	virtual EPVRTError RemoveLast()
	{
		if(m_uiSize > 0)
		{
			m_uiSize--;
			return PVR_SUCCESS;
		}	
		else
		{
			return PVR_FAIL;
		}
	}

protected:
	unsigned int 	m_uiSize;		/*!< Current size of contents of array */
	unsigned int	m_uiCapacity;	/*!< Currently allocated size of array */
	T				*m_pArray;		/*!< The actual array itself */
};

// note "this" is required for ISO standard, C++ and gcc complains otherwise
// http://lists.apple.com/archives/Xcode-users//2005/Dec/msg00644.html

/*!***************************************************************************
 @class       CPVRTArrayManagedPointers
 @brief       Maintains an array of managed pointers.
*****************************************************************************/
template<typename T>
class CPVRTArrayManagedPointers : public CPVRTArray<T*>
{
public:
	/*!***************************************************************************
	@brief     Destructor.
	*****************************************************************************/
    virtual ~CPVRTArrayManagedPointers()
	{
		if(this->m_pArray)
		{
			for(unsigned int i=0;i<this->m_uiSize;i++)
			{
				delete(this->m_pArray[i]);
			}
		}
	}

	/*!***************************************************************************
	@brief      Removes an element from the array.
	@param[in]	uiIndex		The index to remove.
	@return 	success or failure
	*****************************************************************************/
	virtual EPVRTError Remove(unsigned int uiIndex)
	{
		_ASSERT(uiIndex < this->m_uiSize);
		if(this->m_uiSize == 0)
			return PVR_FAIL;

		if(uiIndex == this->m_uiSize-1)
		{
			return this->RemoveLast();
		}

		unsigned int uiSize = (this->m_uiSize - (uiIndex+1)) * sizeof(T*);
	
		delete this->m_pArray[uiIndex];
		memmove(this->m_pArray + uiIndex, this->m_pArray + (uiIndex+1), uiSize);

		this->m_uiSize--;
		return PVR_SUCCESS;
	}

	/*!***************************************************************************
	@brief      Removes the last element. Simply decrements the size value
	@return 	success or failure
	*****************************************************************************/
	virtual EPVRTError RemoveLast()
	{
		if(this->m_uiSize > 0 && this->m_pArray)
		{
			delete this->m_pArray[this->m_uiSize-1];
			this->m_uiSize--;
			return PVR_SUCCESS;
		}
		else
		{
			return PVR_FAIL;
		}
	}
};

#endif // __PVRTARRAY_H__

/*****************************************************************************
End of file (PVRTArray.h)
*****************************************************************************/