narray.h

奇迹世界公用文件源代码,研究网络游戏的朋友可以研究下

#ifndef N_ARRAY_H
#define N_ARRAY_H

//------------------------------------------------------------------------------
/**
    @brief A dynamic array template class, similar to the stl vector class 

    @author
    - RadonLabs GmbH 

    @since
    - 2005.6.14
    @remarks
    - 瘤肯 眠啊 
*/
//------------------------------------------------------------------------------

#include "../ProgramCommon/Macro.h"
#include "../ProgramCommon/Define.h"


//------------------------------------------------------------------------------
template<class TYPE> class nArray
{
public:
    typedef TYPE* iterator;

    /// behaviour flags
    enum
    {
        DoubleGrowSize = (1<<0),    // when set, grow size doubles each turn
    };

    /// constructor with default parameters
    nArray();
    /// constuctor with initial size and grow size
    nArray(int initialSize, int initialGrow);
    /// constructor with initial size, grow size and initial values
    nArray(int initialSize, int initialGrow, TYPE initialValue);
    /// copy constructor
    nArray(const nArray<TYPE>& rhs);
    /// destructor
    ~nArray();
    /// assignment operator
    nArray<TYPE>& operator=(const nArray<TYPE>& rhs);
    /// [] operator
    TYPE& operator[](int index) const;

    /// set behaviour flags
    void SetFlags(int f);
    /// get behaviour flags
    int GetFlags() const;
    /// clear contents and set a fixed size
    void SetFixedSize(int size);
    /// push element to back of array
    TYPE& PushBack(const TYPE& elm);
    /// append element to array (synonym for PushBack())
    void Append(const TYPE& elm);
    /// reserve 'num' elements at end of array and return pointer to first element
    iterator Reserve(int num);
    /// get number of elements in array
    int Size() const;
    /// get overall allocated size of array in number of elements
    int AllocSize() const;
    /// set element at index, grow array if necessary
    TYPE& Set(int index, const TYPE& elm);
    /// return reference to nth element in array
    TYPE& At(int index);
    /// return reference to first element
    TYPE& Front() const;
    /// return reference to last element
    TYPE& Back() const;
    /// return true if array empty
    bool Empty() const;
    /// erase element at index
    void Erase(int index);
    /// quick erase, does not call operator= or destructor
    void EraseQuick(int index);
    /// erase element pointed to by iterator
    iterator Erase(iterator iter);
    /// quick erase, does not call operator= or destructor
    iterator EraseQuick(iterator iter);
    /// insert element at index
    void Insert(int index, const TYPE& elm);
    /// clear array (calls destructors)
    void Clear();
    /// reset array (does NOT call destructors)
    void Reset();
    /// return iterator to beginning of array
    iterator Begin() const;
    /// return iterator to end of array
    iterator End() const;
    /// find identical element in array, return iterator
    iterator Find(const TYPE& elm) const;
    /// find identical element in array, return index
    int FindIndex(const TYPE& elm) const;
    /// find array range with element
    void Fill(int first, int num, const TYPE& elm);
    /// clear contents and preallocate with new attributes
    void Reallocate(int initialSize, int grow);

private:
    /// check if index is in valid range, and grow array if necessary
    void CheckIndex(int);
    /// destroy an element (call destructor without freeing memory)
    void Destroy(TYPE* elm);
    /// copy content
    void Copy(const nArray<TYPE>& src);
    /// delete content
    void Delete();
    /// grow array
    void Grow();
    /// grow array to target size
    void GrowTo(int newAllocSize);
    /// move elements, grows array if needed
    void Move(int fromIndex, int toIndex);
    /// unsafe quick move, does not call operator= or destructor
    void MoveQuick(int fromIndex, int toIndex);

    int growSize;           // grow by this number of elements if array exhausted
    int allocSize;          // number of elements allocated
    int numElements;        // number of elements in array
    int flags;
    TYPE* elements;         // pointer to element array
};

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
nArray<TYPE>::nArray() :
    growSize(16),
    allocSize(0),
    numElements(0),
    flags(0)
{
    this->elements = 0;
}

//------------------------------------------------------------------------------
/**
    Note: 'grow' can be zero to create a static preallocated array.
*/
template<class TYPE>
nArray<TYPE>::nArray(int initialSize, int grow) :
    growSize(grow),
    allocSize(initialSize),
    numElements(0),
    flags(0)
{
    ASSERT(initialSize >= 0);
    if (initialSize > 0)
    {
        this->elements = new TYPE[this->allocSize];
    }
    else
    {
        this->elements = 0;
    }
}

//------------------------------------------------------------------------------
/**
    Note: 'grow' can be zero to create a static preallocated array.
*/
template<class TYPE>
nArray<TYPE>::nArray(int initialSize, int grow, TYPE initialValue) :
    growSize(grow),
    allocSize(initialSize),
    numElements(initialSize),
    flags(0)
{
    ASSERT(initialSize >= 0);
    if (initialSize > 0)
    {
        this->elements = new TYPE[this->allocSize];
        int i;
        for (i = 0; i < initialSize; i++)
        {
            this->elements[i] = initialValue;
        }
    }
    else
    {
        this->elements = 0;
    }
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::Copy(const nArray<TYPE>& src)
{
    ASSERT(0 == this->elements);

    this->growSize    = src.growSize;
    this->allocSize   = src.allocSize;
    this->numElements = src.numElements;
    this->flags       = src.flags;
    if (this->allocSize > 0)
    {
        this->elements = new TYPE[this->allocSize];
        int i;
        for (i = 0; i < this->numElements; i++)
        {
            this->elements[i] = src.elements[i];
        }
    }
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::Delete()
{
    this->growSize = 0;
    this->allocSize = 0;
    this->numElements = 0;
    this->flags = 0;
    if (this->elements)
    {
        delete[] this->elements;
        this->elements = 0;
    }
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::Destroy(TYPE* elm)
{
    elm->~TYPE();
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
nArray<TYPE>::nArray(const nArray<TYPE>& rhs) :
    growSize(0),
    allocSize(0),
    numElements(0),
    elements(0),
    flags(0)
{
    this->Copy(rhs);
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
nArray<TYPE>::~nArray()
{
    this->Delete();
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::SetFlags(int f)
{
    this->flags = f;
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
int
nArray<TYPE>::GetFlags() const
{
    return this->flags;
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::Reallocate(int initialSize, int grow)
{
    this->Delete();
    this->growSize    = grow;
    this->allocSize   = initialSize;
    this->numElements = 0;
    if (initialSize > 0)
    {
        this->elements = new TYPE[initialSize];
    }
    else
    {
        this->elements = 0;
    }
}

//------------------------------------------------------------------------------
/**
    Set a new fixed size. This will throw away the current content, and
    create preallocate a new array which cannot grow. All elements in
    the array will be valid.
*/
template<class TYPE>
void
nArray<TYPE>::SetFixedSize(int size)
{
    this->Reallocate(size, 0);
    this->numElements = size;
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
nArray<TYPE>&
nArray<TYPE>::operator=(const nArray<TYPE>& rhs)
{
    this->Delete();
    this->Copy(rhs);
    return *this;
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::GrowTo(int newAllocSize)
{
    TYPE* newArray = new TYPE[newAllocSize];

    if (this->elements)
    {
        // copy over contents
        int i;
        for (i = 0; i < this->numElements; i++)
        {
            newArray[i] = this->elements[i];
        }

        // discard old array and update contents
        delete[] this->elements;
    }
    this->elements  = newArray;
    this->allocSize = newAllocSize;
}

//------------------------------------------------------------------------------
/**
*/
template<class TYPE>
void
nArray<TYPE>::Grow()
{
    ASSERT(this->growSize > 0);
    int growToSize;
    if ((DoubleGrowSize & this->flags) != 0)
    {
        // double growth behaviour
        if (0 == this->allocSize)
        {
            growToSize = growSize;
        }
        else
        {
            growToSize = 2 * this->allocSize;
        }
    }
    else
    {
        // classic linear growth behaviour
        growToSize = this->allocSize + this->growSize;
    }
    this->GrowTo(growToSize);
}

//------------------------------------------------------------------------------
/**
    30-Jan-03   floh    serious bugfixes!
*/
template<class TYPE>
void
nArray<TYPE>::Move(int fromIndex, int toIndex)
{
    ASSERT(this->elements);
    ASSERT(fromIndex < this->numElements);

    // nothing to move?
    if (fromIndex == toIndex)
    {
        return;
    }

    // compute number of elements to move
    int num = this->numElements - fromIndex;

    // check if array needs to grow
    int neededSize = toIndex + num;
    while (neededSize >= this->allocSize)
    {
        this->Grow();
    }

    if (fromIndex > toIndex)
    {
        // this is a backward move
        int i;
        for (i = 0; i < num; i++)
        {
            this->elements[toIndex + i] = this->elements[fromIndex + i];
        }

        // destroy remaining elements
        for (i = (fromIndex + i) - 1; i < this->numElements; i++)
        {
            this->Destroy(&(this->elements[i]));
        }
    }