XTemplate.h

Go to the documentation of this file.

//! @file XTemplate.h
//! @brief a simple array class for handling data which does not require to be construct / destroy
//! 
//////////////////////////////////////////////////////////////////////
 
#if !defined(CXTEMPLATE_INCLUDE_H)
#define CXTEMPLATE_INCLUDE_H
 
#ifdef _MSC_VER
#pragma once
#endif // _MSC_VER
 
#include "XObject.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
//////////////////////////////////////////
// CXArray predefined typedef
 
template <class TYPE, class ARG_TYPE> class CXArray;
typedef CXArray<unsigned int, unsigned int> CXUIntArray;
typedef CXArray<int, int> CXIntArray;
typedef CXArray<float, float> CXFloatArray;
typedef CXArray<double, double> CXDoubleArray;
typedef CXArray<void *, void*> CXPtrArray;
typedef CXArray<CXString, const CXString&> CXStringArray;
 
//! @class CXArray
//! @brief CXArray is an array of simple data information which does not requires to call a constructor / destructor.
//! @details If you intend to manage array of more complex data, please look at CElementArray.
//! @param TYPE specified the data type stored in the array.
template<class TYPE, class ARG_TYPE = const TYPE&>
class CXArray : public CXObject
{
public:
    //! @enum GrowMode
    //! GrowMode control the way the array inflate while adding data.
    typedef enum GrowMode
    {
        GROW_DEFAULT = 0, //!< A default grow mode which increase the array size by 1024 bytes each times its needed. using it with SetSize(0) will free the buffer
        GROW_KEEP_MODE = -1, //!< Keep the default grow size (SetAtGrow, SetSize)
        GROW_DOUBLE_SIZE = -2, //!< Double size the array for fast element growing (required when the final element number is not known, and is probably big)
    } GrowMode;
 
    // Construction
    CXArray(bool enableMemcpy = true);
    CXArray(const CXArray<TYPE, ARG_TYPE>& copyFrom);
 
    // Attributes
    int GetSizeOfElement() const; // Size of the stored element
    int GetSize() const;
    void SetSize(int newCount, int newGrowCount = GROW_KEEP_MODE); //!< The buffer always grows unless FreeExtra / RemoveAll(false) is called
    void PreAllocate(int size, int newGrowCount = GROW_KEEP_MODE); //!< Preallocate size elements. GetSize() return 0 after the call.
 
    // Operations
    // Clean up
    void FreeExtra(); //!< Remove extra data allocated when adding data 
    void RemoveAll(bool keepBuffer = false); //!< Remove all data and set size to 0
 
    // Access to the element data (may return NULL)
    const TYPE* GetData() const; //!< Get raw array const data access
    TYPE* GetData(); //!< Get raw array data access for modifying data directly.
 
    // Potentially growing the array
    void SetAtGrow(int index, ARG_TYPE newElement, int nGrowBy = GROW_KEEP_MODE);
    int Add(ARG_TYPE newElement, int nGrowBy = GROW_KEEP_MODE);
    int AddArray(const CXArray<TYPE, ARG_TYPE>& src); //!< Add an array to another array. There might be duplicated items.
    void Copy(const CXArray<TYPE, ARG_TYPE>& src);
    void Copy(const CXArray<TYPE, ARG_TYPE> *src);
 
    const TYPE& operator[](int index) const;
    TYPE& operator[](int index);
 
    void InsertAt(int index, ARG_TYPE newElement, int insertCount = 1);
    void RemoveAt(int index, int removedCount = 1);
    bool Remove(ARG_TYPE newElement, bool firstonly = true); //!< Remove newElement and return true if found. If firstonly = true, the return return once the first newElement has been removed
 
protected:
    // Note this is safer to use int instead of unsigned int, even if index if always >=0
    // One good reason is the for loop case, in case of unsigned int:
    // unsigned int size = array.GetLength()
    // for (i=size-1; i>=0; i--) // Loop never end
    TYPE *buffer;       // the array of data
    int elementCount;       // number of elements
    int maxElementCount;    // max allocated elements
    int growElementCount;       // number of element to grow the array
    bool enableMemcpy; // The data can be copied with a simple memcpy, the operator = should always been called. This is mainly for using ie std::simple_string which requires deep copy, as object contains pointer to themself in debug mode.
 
private:
    const CXArray<TYPE, ARG_TYPE>& operator=(const CXArray<TYPE, ARG_TYPE>& Rhs) {return *this;}; // Use Copy instead, to avoid unvoluntary copy
 
public:
    virtual ~CXArray();
 
#ifndef MOOTOOLS_NO_ARCHIVE_SUPPORT
    void Serialize(CXArchive&);
#endif
 
#ifdef _DEBUG
    void Dump() const;
#endif
};
 
/////////////////////////////////////////////////////////////////////////////
// CXArray<TYPE, ARG_TYPE> inline functions
template<class TYPE, class ARG_TYPE>
inline int CXArray<TYPE, ARG_TYPE>::GetSizeOfElement() const
{
    return sizeof(TYPE);
}
 
template<class TYPE, class ARG_TYPE>
inline int CXArray<TYPE, ARG_TYPE>::GetSize() const
{
    return elementCount;
}
 
template<class TYPE, class ARG_TYPE>
inline void CXArray<TYPE, ARG_TYPE>::RemoveAll(bool keepBuffer)
{
    // keepBuffer = false deallocate the buffer. This is done using GROW_DEFAULT mode.
    // SetSize changes growElementCount. Restore the previous value after the call in order to keep the way the caller want the array to grow
    int prevGrowElementCount = growElementCount;
    SetSize(0, keepBuffer ? GROW_KEEP_MODE : GROW_DEFAULT);
    growElementCount = prevGrowElementCount;
}
 
template<class TYPE, class ARG_TYPE>
inline const TYPE* CXArray<TYPE, ARG_TYPE>::GetData() const
{
    return (const TYPE*)buffer;
}
 
template<class TYPE, class ARG_TYPE>
inline TYPE* CXArray<TYPE, ARG_TYPE>::GetData()
{
    return (TYPE*)buffer;
}
 
template<class TYPE, class ARG_TYPE>
inline int CXArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement, int nGrowBy)
{
    int index = elementCount;
    SetAtGrow(index, newElement, nGrowBy);
    return index;
}
 
template<class TYPE, class ARG_TYPE>
inline const TYPE& CXArray<TYPE, ARG_TYPE>::operator[](int index) const
{           
    XASSERT(index >= 0 && index < elementCount);
    if(index >= 0 && index < elementCount)
        return buffer[index];
 
    XThrowException(CXInvalidArgException);     
}
 
template<class TYPE, class ARG_TYPE>
inline TYPE& CXArray<TYPE, ARG_TYPE>::operator[](int index)
{   
    XASSERT(index >= 0 && index < elementCount);
    if(index >= 0 && index < elementCount)
        return buffer[index]; 
 
    XThrowException(CXInvalidArgException);     
}
 
/////////////////////////////////////////////////////////////////////////////
// CXArray<TYPE, ARG_TYPE>
 
template<class TYPE>
inline void XArrayCopy(TYPE* pDst, const TYPE* pSrc, int elementCount)
{
    XENSURE(elementCount == 0 || (pDst != NULL && pSrc != NULL));
 
    // default is element-copy using assignment
    while (elementCount--)
        *pDst++ = *pSrc++;
}
 
#ifdef _DEBUG
template<class TYPE>
void XArrayDump(const TYPE* pElements, int elementCount)
{
    XENSURE(elementCount == 0 || pElements != NULL);
}
#endif
 
/////////////////////////////////////////////////////////////////////////////
// CXArray<TYPE, ARG_TYPE> out-of-line functions
 
template<class TYPE, class ARG_TYPE>
CXArray<TYPE, ARG_TYPE>::CXArray(bool refenableMemcpy)
{
    buffer = NULL;
    elementCount = maxElementCount = 0;
    growElementCount = GROW_DEFAULT;
    this->enableMemcpy = refenableMemcpy;
}
 
template<class TYPE, class ARG_TYPE>
CXArray<TYPE, ARG_TYPE>::CXArray(const CXArray<TYPE, ARG_TYPE>& copyFrom)
{
    buffer = NULL;
    elementCount = maxElementCount = 0;
    growElementCount = copyFrom.growElementCount;
    this->enableMemcpy = copyFrom.enableMemcpy;
    this->Copy(copyFrom);
}
 
template<class TYPE, class ARG_TYPE>
CXArray<TYPE, ARG_TYPE>::~CXArray()
{
    XASSERT(this);
 
    if (buffer != NULL)
    {
#ifndef MOOTOOLS_FOR_UNREAL
        try
        {
#endif
            for (int i = 0; i < elementCount; i++ )
                (buffer + i)->~TYPE();
 
            xDeallocateArray((unsigned char *)buffer);
#ifndef MOOTOOLS_FOR_UNREAL
        }
        catch(...)
        {
            XTRACE(_T("Array: exception in destructor occured.\n"));
        }
#endif
    }
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::PreAllocate(int size, int newGrowCount)
{
    if (size == maxElementCount && elementCount == 0) // Already preallocated with the same size
        return;
 
    RemoveAll();
    SetSize(size, newGrowCount);
    maxElementCount = size;
    elementCount = 0;
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::SetSize(int newCount, int newGrowCount)
{
    XASSERT(this);
    XASSERT(newCount >= 0);
 
    if(newCount < 0 )
        XThrowException(CXInvalidArgException);
 
    if (newGrowCount != GROW_KEEP_MODE)
        growElementCount = newGrowCount;  // set new size
 
    if (newCount == 0)
    {
        // Destroy all
        if (buffer != NULL)
        {
            for (int i = 0; i < elementCount; i++ )
                (buffer + i)->~TYPE();
 
            if (newGrowCount == GROW_DEFAULT)
            {
                xDeallocateArray((unsigned char *)buffer);
                buffer = NULL;
            }
        }
 
        elementCount = 0;
        if (newGrowCount == GROW_DEFAULT)
            maxElementCount = 0;
    }
    else if (buffer == NULL)
    {
        // Allocate elements using grow amount if needed
#ifdef SIZE_T_MAX
        XASSERT(newCount <= SIZE_T_MAX/sizeof(TYPE));    // no overflow
#endif
        int allocCount = __max(newCount, growElementCount);
        buffer = (TYPE*) xAllocateArray(unsigned char, (size_t)allocCount * sizeof(TYPE));
        memset((void*)buffer, 0, (size_t)allocCount * sizeof(TYPE));
 
        for (int i = 0; i < newCount; i++ )
            xConstruct(TYPE, (void*)(buffer+i));
 
        elementCount = newCount;
        maxElementCount = allocCount;
    }
    else if (newCount <= maxElementCount)
    {
        // it fits
        if (newCount > elementCount)
        {
            // construct new elements
            memset((void*)(buffer + elementCount), 0, (size_t)(newCount-elementCount) * sizeof(TYPE));
            for (int i = 0; i < newCount-elementCount; i++ )
                xConstruct(TYPE, (void*)(buffer+elementCount+i));
        }
        else if (elementCount > newCount)
        {
            // destroy old elements
            for (int i = 0; i < elementCount-newCount; i++ )
                (buffer + newCount + i)->~TYPE();
        }
 
        elementCount = newCount;
    }
    else
    {
        // otherwise, grow array
        newGrowCount = growElementCount;
        if (newGrowCount == GROW_DOUBLE_SIZE)
            newGrowCount = maxElementCount;
        else if (newGrowCount == GROW_DEFAULT)
        {
            newGrowCount = elementCount / 8;
            newGrowCount = (newGrowCount < 4) ? 4 : ((newGrowCount > 1024) ? 1024 : newGrowCount);
        }
         // else newGrowCount > 0
 
        int newMaxCount;
        if (newCount < maxElementCount + newGrowCount)
            newMaxCount = maxElementCount + newGrowCount; 
        else
            newMaxCount = newCount;  // still ok
 
        XASSERT(newMaxCount >= maxElementCount);  // no wrap around
 
        if(newMaxCount  < maxElementCount)
            XThrowException(CXInvalidArgException);
 
#ifdef SIZE_T_MAX
        XASSERT(newMaxCount <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
#endif
        TYPE* newBuffer = (TYPE*) xAllocateArray(unsigned char, (size_t)newMaxCount * sizeof(TYPE));
 
        if (enableMemcpy)
        {
            // copy new data from old
            xmemcpy_s(newBuffer, (size_t)newMaxCount * sizeof(TYPE), buffer, (size_t)elementCount * sizeof(TYPE));
        }
        else
        {
            // The data need to be construct and assigned using the = operator
            int i;
 
            for (i = 0; i < elementCount; i++)
                xConstruct(TYPE, (void*)(newBuffer + i));
 
            for (i = 0; i < elementCount; i++)
                newBuffer[i] = buffer[i];
 
            for (i = 0; i < elementCount; i++)
                (buffer + i)->~TYPE();
        }
 
        // construct remaining elements
        XASSERT(newCount > elementCount);
        memset((void*)(newBuffer + elementCount), 0, (size_t)(newCount-elementCount) * sizeof(TYPE));
 
        for (int i = 0; i < newCount-elementCount; i++ )
            xConstruct(TYPE, (void*)(newBuffer+elementCount+i));
 
        // destroy array (note: no destructors called)
        xDeallocateArray((unsigned char *)buffer);
 
        buffer = newBuffer;
        elementCount = newCount;
        maxElementCount = newMaxCount;
    }
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::Copy(const CXArray<TYPE, ARG_TYPE>* src)
{
    if (!src)
    {
        RemoveAll();
        return;
    }
 
    this->Copy(*src);
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::Copy(const CXArray<TYPE, ARG_TYPE>& src)
{
    XASSERT(this);
 
    if (this != &src)
    {
        enableMemcpy = src.enableMemcpy;
 
        SetSize(src.elementCount);
        XArrayCopy<TYPE>(buffer, src.buffer, src.elementCount);
    }
}
 
template<class TYPE, class ARG_TYPE>
int CXArray<TYPE, ARG_TYPE>::AddArray(const CXArray<TYPE, ARG_TYPE>& src)
{
    XASSERT(this);
 
    int baseindex = GetSize();
    int i, srcsize = src.GetSize();
    SetSize(baseindex + srcsize);
    for (i = 0; i < srcsize; i++)
        buffer[baseindex+i] = src[i];
 
    return baseindex + srcsize;
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::FreeExtra()
{
    XASSERT(this);
 
    if (elementCount != maxElementCount)
    {
        // shrink to desired size
#ifdef SIZE_T_MAX
        XASSERT(elementCount <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
#endif
        TYPE* newBuffer = NULL;
        if (elementCount != 0)
        {
            newBuffer = (TYPE*) xAllocateArray(unsigned char, elementCount * sizeof(TYPE));
 
            if (enableMemcpy)
            {
                // copy new data from old
                xmemcpy_s(newBuffer, elementCount * sizeof(TYPE), buffer, elementCount * sizeof(TYPE));
            }
            else
            {
                // The data need to be construct and assigned using the = operator
                int i;
 
                for (i = 0; i < elementCount; i++)
                    xConstruct(TYPE, (void*)(newBuffer + i));
 
                for (i = 0; i < elementCount; i++)
                    newBuffer[i] = buffer[i];
 
                for (i = 0; i < elementCount; i++)
                    (buffer + i)->~TYPE();
            }
 
            // destroy array (note: no destructors called)
            xDeallocateArray((unsigned char *)buffer);
        }
 
        buffer = newBuffer;
        maxElementCount = elementCount;
    }
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::SetAtGrow(int index, ARG_TYPE newElement, int nGrowBy)
{
    XASSERT(this);
    XASSERT(index >= 0);
 
    if(index < 0)
        XThrowException(CXInvalidArgException);
 
    if (index >= elementCount)
        SetSize(index+1, nGrowBy);
    buffer[index] = newElement;
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::InsertAt(int index, ARG_TYPE newElement, int insertedCount)
{
    XASSERT(this);
    XASSERT(index >= 0);    // will expand to meet need
    XASSERT(insertedCount > 0);     // zero or negative size not allowed
 
    if(index < 0 || insertedCount <= 0)
        XThrowException(CXInvalidArgException);
 
    if (index >= elementCount)
    {
        // adding after the end of the array
        SetSize(index + insertedCount);   // grow so index is valid
    }
    else
    {
        // inserting in the middle of the array
        int prevBufCount = elementCount;
        SetSize(elementCount + insertedCount);  // grow it to new size
                
        // shift old data up to fill gap
        if (enableMemcpy)
        {
            // destroy the data that have been created in SetSize before copying over it
            for (int i = 0; i < insertedCount; i++)
                (buffer + prevBufCount + i)->~TYPE();
 
            xmemmove_s(buffer + index + insertedCount, (prevBufCount - index) * sizeof(TYPE), buffer + index, (prevBufCount - index) * sizeof(TYPE));
 
            // No init the new data
            memset((void*)(buffer + index), 0, (size_t)insertedCount * sizeof(TYPE));
            for (int i = 0; i < insertedCount; i++)
                xConstruct(TYPE, (void*)(buffer + index + i));
        }
        else
        {
            // The data need to be assigned using the = operator
            int copyCount = (prevBufCount - index);
            while (copyCount > 0)
            {
                buffer[index+insertedCount+copyCount-1] = buffer[index+copyCount-1];
                copyCount--;
            }
        }
    }
 
    // insert new value in the gap
    XASSERT(index + insertedCount <= elementCount);
    while (insertedCount--)
        buffer[index++] = newElement;
}
 
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::RemoveAt(int index, int removedCount)
{
    XASSERT(this);
    XASSERT(index >= 0);
    XASSERT(removedCount >= 0);
    int upperIndex = index + removedCount;
    XASSERT(upperIndex <= elementCount && upperIndex >= index && upperIndex >= removedCount);
 
    if (index < 0 || removedCount < 0 || (upperIndex > elementCount) || (upperIndex < index) || (upperIndex < removedCount))
        XThrowException(CXInvalidArgException);
 
    // just remove a range
    int moveCount = elementCount - (upperIndex);
    for (int i = 0; i < removedCount; i++ )
        (buffer + index + i)->~TYPE();
 
    if (moveCount)
    {
        if (enableMemcpy)
            xmemmove_s(buffer + index, (size_t)moveCount * sizeof(TYPE), buffer + upperIndex, (size_t)moveCount * sizeof(TYPE));
        else
        {
            // The data need to be assigned using the = operator
            int i = 0;
            while (moveCount-- > 0)
            {
                buffer[index+i] = buffer[upperIndex+i];
                i++;
            }
        }
    }
 
    elementCount -= removedCount;
}
 
template<class TYPE, class ARG_TYPE>
bool CXArray<TYPE, ARG_TYPE>::Remove(ARG_TYPE element, bool firstonly)
{
    bool result = false;
    int i, size = GetSize();
    for (i = 0; i < size; i++)
    {
        if (buffer[i] == element)
        {
            RemoveAt(i);
            if (firstonly)
                return true;
 
            i--; size--;
            result = true;
        }
    }
 
    return result;
}
 
////////////////////////////////////////////////////////////
// Specialization : CXStringArray serialization
 
#ifndef MOOTOOLS_NO_ARCHIVE_SUPPORT
template<> DLL_TOOLSFUNCTION void CXStringArray::Serialize(CXArchive& ar);
#endif
 
#ifdef _DEBUG
template<class TYPE, class ARG_TYPE>
void CXArray<TYPE, ARG_TYPE>::Dump() const
{
    CXObject::Dump();
 
    XTRACE(_T("with %d elements\n"));
    XArrayDump<TYPE>(buffer, elementCount);
}
#endif //_DEBUG
 
END_MOOTOOLS_NAMESPACE
 
#endif // !defined(CXTEMPLATE_INCLUDE_H)