---

---

AI_Array.h

Go to the documentation of this file.

#ifndef AI_ARRAY_H
#define AI_ARRAY_H

#include "../AI_Global.h"


//------------------------------------------------------------------------------
//#include "kernel/ntypes.h"

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

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

    AI_Array();
    AI_Array(int initialSize, int initialGrow);
    AI_Array(int initialSize, int initialGrow, TYPE initialValue);
    AI_Array(const AI_Array<TYPE>& rhs);
    ~AI_Array();
    AI_Array<TYPE>& operator=(const AI_Array<TYPE>& rhs);
    TYPE& operator[](int index) const;
    //bool operator==(const AI_Array<TYPE>& rhs) const;

    void SetFlags(int f);
    int GetFlags() const;
    void SetFixedSize(int size);
    TYPE& PushBack(const TYPE& elm);
    TYPE& PushBack(void);
    void PopBack(void);
    void PopBack(int num);
    void Append(const TYPE& elm);
    iterator Reserve(int num);
    int Size() const;
    int AllocSize() const;
    TYPE& Set(int index, const TYPE& elm);
    TYPE& At(int index);
    TYPE& Front() const;
    TYPE& Back() const;
    bool Empty() const;
    void Erase(int index);
    void EraseQuick(int index);
    iterator Erase(iterator iter);
    iterator EraseQuick(iterator iter);
    void Insert(int index, const TYPE& elm);
    void Clear();
    void Reset();
    iterator Begin() const;
    iterator End() const;
    iterator Find(const TYPE& elm) const;
    int FindIndex(const TYPE& elm) const;
    void Fill(int first, int num, const TYPE& elm);
    void Reallocate(int initialSize, int grow);

private:
    void CheckIndex(int);
    void Destroy(TYPE* elm);
    void Copy(const AI_Array<TYPE>& src);
    void Delete();
    void Grow();
    void GrowTo(int newAllocSize);
    void Move(int fromIndex, int toIndex);
    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>
AI_Array<TYPE>::AI_Array() :
    growSize(16),
    allocSize(0),
    numElements(0),
    flags(0)
{
    this->elements = 0;
}

//------------------------------------------------------------------------------
template<class TYPE>
AI_Array<TYPE>::AI_Array(int initialSize, int grow) :
    growSize(grow),
    allocSize(initialSize),
    numElements(0),
    flags(0)
{
    ai_assert(initialSize >= 0);
    if (initialSize > 0)
    {
        this->elements = ai_new_array(TYPE,this->allocSize);
    }
    else
    {
        this->elements = 0;
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
AI_Array<TYPE>::AI_Array(int initialSize, int grow, TYPE initialValue) :
    growSize(grow),
    allocSize(initialSize),
    numElements(initialSize),
    flags(0)
{
    ai_assert(initialSize >= 0);
    if (initialSize > 0)
    {
        this->elements = ai_new_array(TYPE, this->allocSize);
        int i;
        for (i = 0; i < initialSize; i++)
        {
            this->elements[i] = initialValue;
        }
    }
    else
    {
        this->elements = 0;
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Copy(const AI_Array<TYPE>& src)
{
    ai_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 = ai_new_array(TYPE, this->allocSize);
        int i;
        for (i = 0; i < this->numElements; i++)
        {
            this->elements[i] = src.elements[i];
        }
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Delete()
{
    this->growSize = 0;
    this->allocSize = 0;
    this->numElements = 0;
    this->flags = 0;
    if (this->elements)
    {
        ai_delete_array(this->elements);
        this->elements = 0;
    }
}

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

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

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

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

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

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

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::SetFixedSize(int size)
{
    this->Reallocate(size, 0);
    this->numElements = size;
}

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

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::GrowTo(int newAllocSize)
{
    TYPE* newArray = ai_new_array(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
        ai_delete_array(this->elements);
    }
    this->elements  = newArray;
    this->allocSize = newAllocSize;
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Grow()
{
    ai_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);
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Move(int fromIndex, int toIndex)
{
    ai_assert(this->elements);
    ai_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]));
        }
    }
    else
    {
        // this is a forward move
        int i;
        for (i = num - 1; i >= 0; --i)
        {
            this->elements[toIndex + i] = this->elements[fromIndex + i];
        }

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

    // adjust array size
    this->numElements = toIndex + num;
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::MoveQuick(int fromIndex, int toIndex)
{
    ai_assert(this->elements);
    ai_assert(fromIndex < this->numElements);

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

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

    // do a direct memory move
    memmove(&(this->elements[toIndex]), &(this->elements[fromIndex]), num * sizeof(TYPE));

    // adjust array size
    this->numElements = toIndex + num;
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::PushBack(const TYPE& elm)
{
    // grow allocated space if exhausted
    if (this->numElements == this->allocSize)
    {
        this->Grow();
    }
    ai_assert(this->elements);
    this->elements[this->numElements] = elm;
    return this->elements[this->numElements++];
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::PushBack(void)
{
    // grow allocated space if exhausted
    if (this->numElements == this->allocSize)
    {
        this->Grow();
    }
    ai_assert(this->elements);
    return this->elements[this->numElements++];
}


//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::PopBack(void)
{
    if (this->numElements > 0)
    {
        this->numElements--;
    }
}


//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::PopBack(int num)
{
    ai_assert(num>0);
    if (this->numElements > num)
    {
        this->numElements-=num;
    }
    else
    {
        Reset();
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Append(const TYPE& elm)
{
    // grow allocated space if exhausted
    if (this->numElements == this->allocSize)
    {
        this->Grow();
    }
    ai_assert(this->elements);
    this->elements[this->numElements++] = elm;
}

//------------------------------------------------------------------------------
template<class TYPE>
typename AI_Array<TYPE>::iterator
AI_Array<TYPE>::Reserve(int num)
{
    ai_assert(num > 0);
    int maxElement = this->numElements + num;
    while (maxElement >= this->allocSize)
    {
        this->Grow();
    }
    ai_assert(this->elements);
    iterator iter = this->elements + this->numElements;
    this->numElements += num;
    return iter;
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::CheckIndex(int index)
{
    if (index >= this->numElements)
    {
        // grow array if necessary
        if (index >= this->allocSize)
        {
            ai_assert(this->growSize > 0);
            this->GrowTo(index + this->growSize);
        }
        // update number of contained elements
        this->numElements = index + 1;
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::Set(int index, const TYPE& elm)
{
    this->CheckIndex(index);
    this->elements[index] = elm;
    return this->elements[index];
}

//------------------------------------------------------------------------------
template<class TYPE>
int
AI_Array<TYPE>::Size() const
{
    return this->numElements;
}

//------------------------------------------------------------------------------
template<class TYPE>
int
AI_Array<TYPE>::AllocSize() const
{
    return this->allocSize;
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::At(int index)
{
    this->CheckIndex(index);
    return this->elements[index];
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::operator[](int index) const
{
    ai_assert(this->elements && (index >= 0) && (index < this->numElements));
    return this->elements[index];
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::Front() const
{
    ai_assert(this->elements && (this->numElements > 0));
    return this->elements[0];
}

//------------------------------------------------------------------------------
template<class TYPE>
TYPE&
AI_Array<TYPE>::Back() const
{
    ai_assert(this->elements && (this->numElements > 0));
    return this->elements[this->numElements - 1];
}

//------------------------------------------------------------------------------
template<class TYPE>
bool
AI_Array<TYPE>::Empty() const
{
    return (this->numElements == 0);
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Erase(int index)
{
    ai_assert(this->elements && (index >= 0) && (index < this->numElements));
    if (index == (this->numElements - 1))
    {
        // special case: last element
        this->Destroy(&(this->elements[index]));
        this->numElements--;
    }
    else
    {
        this->Move(index + 1, index);
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::EraseQuick(int index)
{
    ai_assert(this->elements && (index >= 0) && (index < this->numElements));
    if (index == (this->numElements - 1))
    {
        // special case: last element
        this->numElements--;
    }
    else
    {
        this->MoveQuick(index + 1, index);
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
typename AI_Array<TYPE>::iterator
AI_Array<TYPE>::Erase(typename AI_Array<TYPE>::iterator iter)
{
    ai_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->numElements)));
    this->Erase( (int)(iter - this->elements) );
    return iter;
}

//------------------------------------------------------------------------------
template<class TYPE>
typename AI_Array<TYPE>::iterator
AI_Array<TYPE>::EraseQuick(typename AI_Array<TYPE>::iterator iter)
{
    ai_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->numElements)));
    this->EraseQuick( (int)(iter - this->elements) );
    return iter;
}


//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Insert(int index, const TYPE& elm)
{
    ai_assert((index >= 0) && (index <= this->numElements));
    if (index == this->numElements)
    {
        // special case: append element to back
        this->PushBack(elm);
    }
    else
    {
        this->Move(index, index + 1);
        this->elements[index] = elm;
    }
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Clear()
{
    int i;
    for (i = 0; i < this->numElements; i++)
    {
        this->Destroy(&(this->elements[i]));
    }
    this->numElements = 0;
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Reset()
{
    this->numElements = 0;
}

//------------------------------------------------------------------------------
template<class TYPE>
typename AI_Array<TYPE>::iterator
AI_Array<TYPE>::Begin() const
{
    return this->elements;
}

//------------------------------------------------------------------------------
template<class TYPE>
typename AI_Array<TYPE>::iterator
AI_Array<TYPE>::End() const
{
    return this->elements + this->numElements;
}

//------------------------------------------------------------------------------
template<class TYPE>
typename AI_Array<TYPE>::iterator
AI_Array<TYPE>::Find(const TYPE& elm) const
{
    int index;
    for (index = 0; index < this->numElements; index++)
    {
        if (this->elements[index] == elm)
        {
            return &(this->elements[index]);
        }
    }
    return 0;
}

//------------------------------------------------------------------------------
template<class TYPE>
int
AI_Array<TYPE>::FindIndex(const TYPE& elm) const
{
    int index;
    for (index = 0; index < this->numElements; index++)
    {
        if (this->elements[index] == elm)
        {
            return index;
        }
    }
    return -1;
}

//------------------------------------------------------------------------------
template<class TYPE>
void
AI_Array<TYPE>::Fill(int first, int num, const TYPE& elm)
{
    if ((first + num) > this->numElements)
    {
        this->GrowTo(first + num);
    }
    int i;
    for (i = first; i < (first + num); i++)
    {
        this->elements[i] = elm;
    }
}

//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
template<class TYPE> 
inline bool
operator==(const AI_Array<TYPE> &left, const AI_Array<TYPE> &right)
{
    return ( left.Size()==right.Size() &&
             ::memcmp(left.Begin(), right.Begin(), left.End() - left.Begin()) );
             
}

#endif

---

InExIn pages are hosted by
InExIn documentation generated by doxygen at Tue Dec 18 12:55:27 2007