nuclear@3: /************************************************************************************
nuclear@3: 
nuclear@3: PublicHeader:   OVR.h
nuclear@3: Filename    :   OVR_Array.h
nuclear@3: Content     :   Template implementation for Array
nuclear@3: Created     :   September 19, 2012
nuclear@3: Notes       : 
nuclear@3: 
nuclear@3: Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@3: 
nuclear@3: Use of this software is subject to the terms of the Oculus license
nuclear@3: agreement provided at the time of installation or download, or which
nuclear@3: otherwise accompanies this software in either electronic or hard copy form.
nuclear@3: 
nuclear@3: ************************************************************************************/
nuclear@3: 
nuclear@3: #ifndef OVR_Array_h
nuclear@3: #define OVR_Array_h
nuclear@3: 
nuclear@3: #include "OVR_ContainerAllocator.h"
nuclear@3: 
nuclear@3: namespace OVR {
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ArrayDefaultPolicy
nuclear@3: //
nuclear@3: // Default resize behavior. No minimal capacity, Granularity=4, 
nuclear@3: // Shrinking as needed. ArrayConstPolicy actually is the same as 
nuclear@3: // ArrayDefaultPolicy, but parametrized with constants. 
nuclear@3: // This struct is used only in order to reduce the template "matroska".
nuclear@3: struct ArrayDefaultPolicy
nuclear@3: {
nuclear@3:     ArrayDefaultPolicy() : Capacity(0) {}
nuclear@3:     ArrayDefaultPolicy(const ArrayDefaultPolicy&) : Capacity(0) {}
nuclear@3: 
nuclear@3:     UPInt GetMinCapacity() const { return 0; }
nuclear@3:     UPInt GetGranularity() const { return 4; }
nuclear@3:     bool  NeverShrinking() const { return 0; }
nuclear@3: 
nuclear@3:     UPInt GetCapacity()    const      { return Capacity; }
nuclear@3:     void  SetCapacity(UPInt capacity) { Capacity = capacity; }
nuclear@3: private:
nuclear@3:     UPInt Capacity;
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ArrayConstPolicy
nuclear@3: //
nuclear@3: // Statically parametrized resizing behavior:
nuclear@3: // MinCapacity, Granularity, and Shrinking flag.
nuclear@3: template<int MinCapacity=0, int Granularity=4, bool NeverShrink=false>
nuclear@3: struct ArrayConstPolicy
nuclear@3: {
nuclear@3:     typedef ArrayConstPolicy<MinCapacity, Granularity, NeverShrink> SelfType;
nuclear@3: 
nuclear@3:     ArrayConstPolicy() : Capacity(0) {}
nuclear@3:     ArrayConstPolicy(const SelfType&) : Capacity(0) {}
nuclear@3: 
nuclear@3:     UPInt GetMinCapacity() const { return MinCapacity; }
nuclear@3:     UPInt GetGranularity() const { return Granularity; }
nuclear@3:     bool  NeverShrinking() const { return NeverShrink; }
nuclear@3: 
nuclear@3:     UPInt GetCapacity()    const      { return Capacity; }
nuclear@3:     void  SetCapacity(UPInt capacity) { Capacity = capacity; }
nuclear@3: private:
nuclear@3:     UPInt Capacity;
nuclear@3: };
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ArrayDataBase
nuclear@3: //
nuclear@3: // Basic operations with array data: Reserve, Resize, Free, ArrayPolicy.
nuclear@3: // For internal use only: ArrayData,ArrayDataCC and others.
nuclear@3: template<class T, class Allocator, class SizePolicy>
nuclear@3: struct ArrayDataBase
nuclear@3: {
nuclear@3:     typedef T                                           ValueType;
nuclear@3:     typedef Allocator                                   AllocatorType;
nuclear@3:     typedef SizePolicy                                  SizePolicyType;
nuclear@3:     typedef ArrayDataBase<T, Allocator, SizePolicy>     SelfType;
nuclear@3: 
nuclear@3:     ArrayDataBase()
nuclear@3:         : Data(0), Size(0), Policy() {}
nuclear@3: 
nuclear@3:     ArrayDataBase(const SizePolicy& p)
nuclear@3:         : Data(0), Size(0), Policy(p) {}
nuclear@3: 
nuclear@3:     ~ArrayDataBase() 
nuclear@3:     {
nuclear@3:         Allocator::DestructArray(Data, Size);
nuclear@3:         Allocator::Free(Data);
nuclear@3:     }
nuclear@3: 
nuclear@3:     UPInt GetCapacity() const 
nuclear@3:     { 
nuclear@3:         return Policy.GetCapacity(); 
nuclear@3:     }
nuclear@3: 
nuclear@3:     void ClearAndRelease()
nuclear@3:     {
nuclear@3:         Allocator::DestructArray(Data, Size);
nuclear@3:         Allocator::Free(Data);
nuclear@3:         Data = 0;
nuclear@3:         Size = 0;
nuclear@3:         Policy.SetCapacity(0);
nuclear@3:     }
nuclear@3: 
nuclear@3:     void Reserve(UPInt newCapacity)
nuclear@3:     {
nuclear@3:         if (Policy.NeverShrinking() && newCapacity < GetCapacity())
nuclear@3:             return;
nuclear@3: 
nuclear@3:         if (newCapacity < Policy.GetMinCapacity())
nuclear@3:             newCapacity = Policy.GetMinCapacity();
nuclear@3: 
nuclear@3:         // Resize the buffer.
nuclear@3:         if (newCapacity == 0)
nuclear@3:         {
nuclear@3:             if (Data)
nuclear@3:             {
nuclear@3:                 Allocator::Free(Data);
nuclear@3:                 Data = 0;
nuclear@3:             }
nuclear@3:             Policy.SetCapacity(0);
nuclear@3:         }
nuclear@3:         else
nuclear@3:         {
nuclear@3:             UPInt gran = Policy.GetGranularity();
nuclear@3:             newCapacity = (newCapacity + gran - 1) / gran * gran;
nuclear@3:             if (Data)
nuclear@3:             {
nuclear@3:                 if (Allocator::IsMovable())
nuclear@3:                 {
nuclear@3:                     Data = (T*)Allocator::Realloc(Data, sizeof(T) * newCapacity);
nuclear@3:                 }
nuclear@3:                 else
nuclear@3:                 {
nuclear@3:                     T* newData = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
nuclear@3:                     UPInt i, s;
nuclear@3:                     s = (Size < newCapacity) ? Size : newCapacity;
nuclear@3:                     for (i = 0; i < s; ++i)
nuclear@3:                     {
nuclear@3:                         Allocator::Construct(&newData[i], Data[i]);
nuclear@3:                         Allocator::Destruct(&Data[i]);
nuclear@3:                     }
nuclear@3:                     for (i = s; i < Size; ++i)
nuclear@3:                     {
nuclear@3:                         Allocator::Destruct(&Data[i]);
nuclear@3:                     }
nuclear@3:                     Allocator::Free(Data);
nuclear@3:                     Data = newData;
nuclear@3:                 }
nuclear@3:             }
nuclear@3:             else
nuclear@3:             {
nuclear@3:                 Data = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
nuclear@3:                 //memset(Buffer, 0, (sizeof(ValueType) * newSize)); // Do we need this?
nuclear@3:             }
nuclear@3:             Policy.SetCapacity(newCapacity);
nuclear@3:             // OVR_ASSERT(Data); // need to throw (or something) on alloc failure!
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     // This version of Resize DOES NOT construct the elements.
nuclear@3:     // It's done to optimize PushBack, which uses a copy constructor 
nuclear@3:     // instead of the default constructor and assignment
nuclear@3:     void ResizeNoConstruct(UPInt newSize)
nuclear@3:     {
nuclear@3:         UPInt oldSize = Size;
nuclear@3: 
nuclear@3:         if (newSize < oldSize)
nuclear@3:         {
nuclear@3:             Allocator::DestructArray(Data + newSize, oldSize - newSize);
nuclear@3:             if (newSize < (Policy.GetCapacity() >> 1))
nuclear@3:             {
nuclear@3:                 Reserve(newSize);
nuclear@3:             }
nuclear@3:         }
nuclear@3:         else if(newSize >= Policy.GetCapacity())
nuclear@3:         {
nuclear@3:             Reserve(newSize + (newSize >> 2));
nuclear@3:         }
nuclear@3:         //! IMPORTANT to modify Size only after Reserve completes, because garbage collectable
nuclear@3:         // array may use this array and may traverse it during Reserve (in the case, if 
nuclear@3:         // collection occurs because of heap limit exceeded).
nuclear@3:         Size = newSize;
nuclear@3:     }
nuclear@3: 
nuclear@3:     ValueType*  Data;
nuclear@3:     UPInt       Size;
nuclear@3:     SizePolicy  Policy;
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ArrayData
nuclear@3: //
nuclear@3: // General purpose array data.
nuclear@3: // For internal use only in Array, ArrayLH, ArrayPOD and so on.
nuclear@3: template<class T, class Allocator, class SizePolicy>
nuclear@3: struct ArrayData : ArrayDataBase<T, Allocator, SizePolicy>
nuclear@3: {
nuclear@3:     typedef T ValueType;
nuclear@3:     typedef Allocator                                   AllocatorType;
nuclear@3:     typedef SizePolicy                                  SizePolicyType;
nuclear@3:     typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
nuclear@3:     typedef ArrayData    <T, Allocator, SizePolicy>     SelfType;
nuclear@3: 
nuclear@3:     ArrayData()
nuclear@3:         : BaseType() { }
nuclear@3: 
nuclear@3:     ArrayData(int size)
nuclear@3:         : BaseType() { Resize(size); }
nuclear@3: 
nuclear@3:     ArrayData(const SelfType& a)
nuclear@3:         : BaseType(a.Policy) { Append(a.Data, a.Size); }
nuclear@3: 
nuclear@3: 
nuclear@3:     void Resize(UPInt newSize)
nuclear@3:     {
nuclear@3:         UPInt oldSize = this->Size;
nuclear@3:         BaseType::ResizeNoConstruct(newSize);
nuclear@3:         if(newSize > oldSize)
nuclear@3:             Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize);
nuclear@3:     }
nuclear@3: 
nuclear@3:     void PushBack(const ValueType& val)
nuclear@3:     {
nuclear@3:         BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3:         Allocator::Construct(this->Data + this->Size - 1, val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     template<class S>
nuclear@3:     void PushBackAlt(const S& val)
nuclear@3:     {
nuclear@3:         BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3:         Allocator::ConstructAlt(this->Data + this->Size - 1, val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Append the given data to the array.
nuclear@3:     void Append(const ValueType other[], UPInt count)
nuclear@3:     {
nuclear@3:         if (count)
nuclear@3:         {
nuclear@3:             UPInt oldSize = this->Size;
nuclear@3:             BaseType::ResizeNoConstruct(this->Size + count);
nuclear@3:             Allocator::ConstructArray(this->Data + oldSize, count, other);
nuclear@3:         }
nuclear@3:     }
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ArrayDataCC
nuclear@3: //
nuclear@3: // A modification of ArrayData that always copy-constructs new elements
nuclear@3: // using a specified DefaultValue. For internal use only in ArrayCC.
nuclear@3: template<class T, class Allocator, class SizePolicy>
nuclear@3: struct ArrayDataCC : ArrayDataBase<T, Allocator, SizePolicy>
nuclear@3: {
nuclear@3:     typedef T                                           ValueType;
nuclear@3:     typedef Allocator                                   AllocatorType;
nuclear@3:     typedef SizePolicy                                  SizePolicyType;
nuclear@3:     typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
nuclear@3:     typedef ArrayDataCC  <T, Allocator, SizePolicy>     SelfType;
nuclear@3: 
nuclear@3:     ArrayDataCC(const ValueType& defval)
nuclear@3:         : BaseType(), DefaultValue(defval) { }
nuclear@3: 
nuclear@3:     ArrayDataCC(const ValueType& defval, int size)
nuclear@3:         : BaseType(), DefaultValue(defval) { Resize(size); }
nuclear@3: 
nuclear@3:     ArrayDataCC(const SelfType& a)
nuclear@3:         : BaseType(a.Policy), DefaultValue(a.DefaultValue) { Append(a.Data, a.Size); }
nuclear@3: 
nuclear@3: 
nuclear@3:     void Resize(UPInt newSize)
nuclear@3:     {
nuclear@3:         UPInt oldSize = this->Size;
nuclear@3:         BaseType::ResizeNoConstruct(newSize);
nuclear@3:         if(newSize > oldSize)
nuclear@3:             Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize, DefaultValue);
nuclear@3:     }
nuclear@3: 
nuclear@3:     void PushBack(const ValueType& val)
nuclear@3:     {
nuclear@3:         BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3:         Allocator::Construct(this->Data + this->Size - 1, val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     template<class S>
nuclear@3:     void PushBackAlt(const S& val)
nuclear@3:     {
nuclear@3:         BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3:         Allocator::ConstructAlt(this->Data + this->Size - 1, val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Append the given data to the array.
nuclear@3:     void Append(const ValueType other[], UPInt count)
nuclear@3:     {
nuclear@3:         if (count)
nuclear@3:         {
nuclear@3:             UPInt oldSize = this->Size;
nuclear@3:             BaseType::ResizeNoConstruct(this->Size + count);
nuclear@3:             Allocator::ConstructArray(this->Data + oldSize, count, other);
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     ValueType   DefaultValue;
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** ArrayBase
nuclear@3: //
nuclear@3: // Resizable array. The behavior can be POD (suffix _POD) and 
nuclear@3: // Movable (no suffix) depending on the allocator policy.
nuclear@3: // In case of _POD the constructors and destructors are not called.
nuclear@3: // 
nuclear@3: // Arrays can't handle non-movable objects! Don't put anything in here 
nuclear@3: // that can't be moved around by bitwise copy. 
nuclear@3: // 
nuclear@3: // The addresses of elements are not persistent! Don't keep the address 
nuclear@3: // of an element; the array contents will move around as it gets resized.
nuclear@3: template<class ArrayData>
nuclear@3: class ArrayBase
nuclear@3: {
nuclear@3: public:
nuclear@3:     typedef typename ArrayData::ValueType       ValueType;
nuclear@3:     typedef typename ArrayData::AllocatorType   AllocatorType;
nuclear@3:     typedef typename ArrayData::SizePolicyType  SizePolicyType;
nuclear@3:     typedef ArrayBase<ArrayData>                SelfType;
nuclear@3: 
nuclear@3: 
nuclear@3: #undef new
nuclear@3:     OVR_MEMORY_REDEFINE_NEW(ArrayBase)
nuclear@3: // Redefine operator 'new' if necessary.
nuclear@3: #if defined(OVR_DEFINE_NEW)
nuclear@3: #define new OVR_DEFINE_NEW
nuclear@3: #endif
nuclear@3: 
nuclear@3: 
nuclear@3:     ArrayBase()
nuclear@3:         : Data() {}
nuclear@3:     ArrayBase(int size)
nuclear@3:         : Data(size) {}
nuclear@3:     ArrayBase(const SelfType& a)
nuclear@3:         : Data(a.Data) {}
nuclear@3: 
nuclear@3:     ArrayBase(const ValueType& defval)
nuclear@3:         : Data(defval) {}
nuclear@3:     ArrayBase(const ValueType& defval, int size)
nuclear@3:         : Data(defval, size) {}
nuclear@3:   
nuclear@3:     SizePolicyType* GetSizePolicy() const                  { return Data.Policy; }
nuclear@3:     void            SetSizePolicy(const SizePolicyType& p) { Data.Policy = p; }
nuclear@3: 
nuclear@3:     bool    NeverShrinking()const       { return Data.Policy.NeverShrinking(); }
nuclear@3:     UPInt   GetSize()       const       { return Data.Size;  }
nuclear@3:     bool    IsEmpty()       const       { return Data.Size == 0; }
nuclear@3:     UPInt   GetCapacity()   const       { return Data.GetCapacity(); }
nuclear@3:     UPInt   GetNumBytes()   const       { return Data.GetCapacity() * sizeof(ValueType); }
nuclear@3: 
nuclear@3:     void    ClearAndRelease()           { Data.ClearAndRelease(); }
nuclear@3:     void    Clear()                     { Data.Resize(0); }
nuclear@3:     void    Resize(UPInt newSize)       { Data.Resize(newSize); }
nuclear@3: 
nuclear@3:     // Reserve can only increase the capacity
nuclear@3:     void    Reserve(UPInt newCapacity)  
nuclear@3:     { 
nuclear@3:         if (newCapacity > Data.GetCapacity())
nuclear@3:             Data.Reserve(newCapacity); 
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Basic access.
nuclear@3:     ValueType& At(UPInt index)
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < Data.Size);
nuclear@3:         return Data.Data[index]; 
nuclear@3:     }
nuclear@3:     const ValueType& At(UPInt index) const
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < Data.Size);
nuclear@3:         return Data.Data[index]; 
nuclear@3:     }
nuclear@3: 
nuclear@3:     ValueType ValueAt(UPInt index) const
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < Data.Size);
nuclear@3:         return Data.Data[index]; 
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Basic access.
nuclear@3:     ValueType& operator [] (UPInt index)
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < Data.Size);
nuclear@3:         return Data.Data[index]; 
nuclear@3:     }
nuclear@3:     const ValueType& operator [] (UPInt index) const
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < Data.Size);
nuclear@3:         return Data.Data[index]; 
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Raw pointer to the data. Use with caution!
nuclear@3:     const ValueType* GetDataPtr() const { return Data.Data; }
nuclear@3:           ValueType* GetDataPtr()       { return Data.Data; }
nuclear@3: 
nuclear@3:     // Insert the given element at the end of the array.
nuclear@3:     void    PushBack(const ValueType& val)
nuclear@3:     {
nuclear@3:         // DO NOT pass elements of your own vector into
nuclear@3:         // push_back()!  Since we're using references,
nuclear@3:         // resize() may munge the element storage!
nuclear@3:         // OVR_ASSERT(&val < &Buffer[0] || &val > &Buffer[BufferSize]);
nuclear@3:         Data.PushBack(val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     template<class S>
nuclear@3:     void PushBackAlt(const S& val)
nuclear@3:     {
nuclear@3:         Data.PushBackAlt(val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Remove the last element.
nuclear@3:     void    PopBack(UPInt count = 1)
nuclear@3:     {
nuclear@3:         OVR_ASSERT(Data.Size >= count);
nuclear@3:         Data.Resize(Data.Size - count);
nuclear@3:     }
nuclear@3: 
nuclear@3:     ValueType& PushDefault()
nuclear@3:     {
nuclear@3:         Data.PushBack(ValueType());
nuclear@3:         return Back();
nuclear@3:     }
nuclear@3: 
nuclear@3:     ValueType Pop()
nuclear@3:     {
nuclear@3:         ValueType t = Back();
nuclear@3:         PopBack();
nuclear@3:         return t;
nuclear@3:     }
nuclear@3: 
nuclear@3: 
nuclear@3:     // Access the first element.
nuclear@3:     ValueType&          Front()         { return At(0); }
nuclear@3:     const ValueType&    Front() const   { return At(0); }
nuclear@3: 
nuclear@3:     // Access the last element.
nuclear@3:     ValueType&          Back()          { return At(Data.Size - 1); }
nuclear@3:     const ValueType&    Back() const    { return At(Data.Size - 1); }
nuclear@3: 
nuclear@3:     // Array copy.  Copies the contents of a into this array.
nuclear@3:     const SelfType& operator = (const SelfType& a)   
nuclear@3:     {
nuclear@3:         Resize(a.GetSize());
nuclear@3:         for (UPInt i = 0; i < Data.Size; i++) {
nuclear@3:             *(Data.Data + i) = a[i];
nuclear@3:         }
nuclear@3:         return *this;
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Removing multiple elements from the array.
nuclear@3:     void    RemoveMultipleAt(UPInt index, UPInt num)
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index + num <= Data.Size);
nuclear@3:         if (Data.Size == num)
nuclear@3:         {
nuclear@3:             Clear();
nuclear@3:         }
nuclear@3:         else
nuclear@3:         {
nuclear@3:             AllocatorType::DestructArray(Data.Data + index, num);
nuclear@3:             AllocatorType::CopyArrayForward(
nuclear@3:                 Data.Data + index, 
nuclear@3:                 Data.Data + index + num,
nuclear@3:                 Data.Size - num - index);
nuclear@3:             Data.Size -= num;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Removing an element from the array is an expensive operation!
nuclear@3:     // It compacts only after removing the last element.
nuclear@3:     void    RemoveAt(UPInt index)
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < Data.Size);
nuclear@3:         if (Data.Size == 1)
nuclear@3:         {
nuclear@3:             Clear();
nuclear@3:         }
nuclear@3:         else
nuclear@3:         {
nuclear@3:             AllocatorType::Destruct(Data.Data + index);
nuclear@3:             AllocatorType::CopyArrayForward(
nuclear@3:                 Data.Data + index, 
nuclear@3:                 Data.Data + index + 1,
nuclear@3:                 Data.Size - 1 - index);
nuclear@3:             --Data.Size;
nuclear@3:         }
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Insert the given object at the given index shifting all the elements up.
nuclear@3:     void    InsertAt(UPInt index, const ValueType& val = ValueType())
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index <= Data.Size);
nuclear@3: 
nuclear@3:         Data.Resize(Data.Size + 1);
nuclear@3:         if (index < Data.Size - 1)
nuclear@3:         {
nuclear@3:             AllocatorType::CopyArrayBackward(
nuclear@3:                 Data.Data + index + 1, 
nuclear@3:                 Data.Data + index, 
nuclear@3:                 Data.Size - 1 - index);
nuclear@3:         }
nuclear@3:         AllocatorType::Construct(Data.Data + index, val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Insert the given object at the given index shifting all the elements up.
nuclear@3:     void    InsertMultipleAt(UPInt index, UPInt num, const ValueType& val = ValueType())
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index <= Data.Size);
nuclear@3: 
nuclear@3:         Data.Resize(Data.Size + num);
nuclear@3:         if (index < Data.Size - num)
nuclear@3:         {
nuclear@3:             AllocatorType::CopyArrayBackward(
nuclear@3:                 Data.Data + index + num,
nuclear@3:                 Data.Data + index,
nuclear@3:                 Data.Size - num - index);
nuclear@3:         }
nuclear@3:         for (UPInt i = 0; i < num; ++i)
nuclear@3:             AllocatorType::Construct(Data.Data + index + i, val);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Append the given data to the array.
nuclear@3:     void    Append(const SelfType& other)
nuclear@3:     {
nuclear@3:         Append(other.Data.Data, other.GetSize());
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Append the given data to the array.
nuclear@3:     void    Append(const ValueType other[], UPInt count)
nuclear@3:     {
nuclear@3:         Data.Append(other, count);
nuclear@3:     }
nuclear@3: 
nuclear@3:     class Iterator
nuclear@3:     {
nuclear@3:         SelfType*       pArray;
nuclear@3:         SPInt           CurIndex;
nuclear@3: 
nuclear@3:     public:
nuclear@3:         Iterator() : pArray(0), CurIndex(-1) {}
nuclear@3:         Iterator(SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
nuclear@3: 
nuclear@3:         bool operator==(const Iterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
nuclear@3:         bool operator!=(const Iterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
nuclear@3: 
nuclear@3:         Iterator& operator++()
nuclear@3:         {
nuclear@3:             if (pArray)
nuclear@3:             {
nuclear@3:                 if (CurIndex < (SPInt)pArray->GetSize())
nuclear@3:                     ++CurIndex;
nuclear@3:             }
nuclear@3:             return *this;
nuclear@3:         }
nuclear@3:         Iterator operator++(int)
nuclear@3:         {
nuclear@3:             Iterator it(*this);
nuclear@3:             operator++();
nuclear@3:             return it;
nuclear@3:         }
nuclear@3:         Iterator& operator--()
nuclear@3:         {
nuclear@3:             if (pArray)
nuclear@3:             {
nuclear@3:                 if (CurIndex >= 0)
nuclear@3:                     --CurIndex;
nuclear@3:             }
nuclear@3:             return *this;
nuclear@3:         }
nuclear@3:         Iterator operator--(int)
nuclear@3:         {
nuclear@3:             Iterator it(*this);
nuclear@3:             operator--();
nuclear@3:             return it;
nuclear@3:         }
nuclear@3:         Iterator operator+(int delta) const
nuclear@3:         {
nuclear@3:             return Iterator(pArray, CurIndex + delta);
nuclear@3:         }
nuclear@3:         Iterator operator-(int delta) const
nuclear@3:         {
nuclear@3:             return Iterator(pArray, CurIndex - delta);
nuclear@3:         }
nuclear@3:         SPInt operator-(const Iterator& right) const
nuclear@3:         {
nuclear@3:             OVR_ASSERT(pArray == right.pArray);
nuclear@3:             return CurIndex - right.CurIndex;
nuclear@3:         }
nuclear@3:         ValueType& operator*() const    { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
nuclear@3:         ValueType* operator->() const   { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3:         ValueType* GetPtr() const       { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3: 
nuclear@3:         bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
nuclear@3: 
nuclear@3:         void Remove()
nuclear@3:         {
nuclear@3:             if (!IsFinished())
nuclear@3:                 pArray->RemoveAt(CurIndex);
nuclear@3:         }
nuclear@3: 
nuclear@3:         SPInt GetIndex() const { return CurIndex; }
nuclear@3:     };
nuclear@3: 
nuclear@3:     Iterator Begin() { return Iterator(this); }
nuclear@3:     Iterator End()   { return Iterator(this, (SPInt)GetSize()); }
nuclear@3:     Iterator Last()  { return Iterator(this, (SPInt)GetSize() - 1); }
nuclear@3: 
nuclear@3:     class ConstIterator
nuclear@3:     {
nuclear@3:         const SelfType* pArray;
nuclear@3:         SPInt           CurIndex;
nuclear@3: 
nuclear@3:     public:
nuclear@3:         ConstIterator() : pArray(0), CurIndex(-1) {}
nuclear@3:         ConstIterator(const SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
nuclear@3: 
nuclear@3:         bool operator==(const ConstIterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
nuclear@3:         bool operator!=(const ConstIterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
nuclear@3: 
nuclear@3:         ConstIterator& operator++()
nuclear@3:         {
nuclear@3:             if (pArray)
nuclear@3:             {
nuclear@3:                 if (CurIndex < (int)pArray->GetSize())
nuclear@3:                     ++CurIndex;
nuclear@3:             }
nuclear@3:             return *this;
nuclear@3:         }
nuclear@3:         ConstIterator operator++(int)
nuclear@3:         {
nuclear@3:             ConstIterator it(*this);
nuclear@3:             operator++();
nuclear@3:             return it;
nuclear@3:         }
nuclear@3:         ConstIterator& operator--()
nuclear@3:         {
nuclear@3:             if (pArray)
nuclear@3:             {
nuclear@3:                 if (CurIndex >= 0)
nuclear@3:                     --CurIndex;
nuclear@3:             }
nuclear@3:             return *this;
nuclear@3:         }
nuclear@3:         ConstIterator operator--(int)
nuclear@3:         {
nuclear@3:             ConstIterator it(*this);
nuclear@3:             operator--();
nuclear@3:             return it;
nuclear@3:         }
nuclear@3:         ConstIterator operator+(int delta) const
nuclear@3:         {
nuclear@3:             return ConstIterator(pArray, CurIndex + delta);
nuclear@3:         }
nuclear@3:         ConstIterator operator-(int delta) const
nuclear@3:         {
nuclear@3:             return ConstIterator(pArray, CurIndex - delta);
nuclear@3:         }
nuclear@3:         SPInt operator-(const ConstIterator& right) const
nuclear@3:         {
nuclear@3:             OVR_ASSERT(pArray == right.pArray);
nuclear@3:             return CurIndex - right.CurIndex;
nuclear@3:         }
nuclear@3:         const ValueType& operator*() const  { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
nuclear@3:         const ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3:         const ValueType* GetPtr() const     { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3: 
nuclear@3:         bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
nuclear@3: 
nuclear@3:         SPInt GetIndex()  const { return CurIndex; }
nuclear@3:     };
nuclear@3:     ConstIterator Begin() const { return ConstIterator(this); }
nuclear@3:     ConstIterator End() const   { return ConstIterator(this, (SPInt)GetSize()); }
nuclear@3:     ConstIterator Last() const  { return ConstIterator(this, (SPInt)GetSize() - 1); }
nuclear@3: 
nuclear@3: protected:
nuclear@3:     ArrayData   Data;
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: //-----------------------------------------------------------------------------------
nuclear@3: // ***** Array
nuclear@3: //
nuclear@3: // General purpose array for movable objects that require explicit 
nuclear@3: // construction/destruction.
nuclear@3: template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3: class Array : public ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> >
nuclear@3: {
nuclear@3: public:
nuclear@3:     typedef T                                                           ValueType;
nuclear@3:     typedef ContainerAllocator<T>                                       AllocatorType;
nuclear@3:     typedef SizePolicy                                                  SizePolicyType;
nuclear@3:     typedef Array<T, SizePolicy>                                        SelfType;
nuclear@3:     typedef ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> > BaseType;
nuclear@3: 
nuclear@3:     Array() : BaseType() {}
nuclear@3:     Array(int size) : BaseType(size) {}
nuclear@3:     Array(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@3:     Array(const SelfType& a) : BaseType(a) {}
nuclear@3:     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3: };
nuclear@3: 
nuclear@3: // ***** ArrayPOD
nuclear@3: //
nuclear@3: // General purpose array for movable objects that DOES NOT require  
nuclear@3: // construction/destruction. Constructors and destructors are not called! 
nuclear@3: // Global heap is in use.
nuclear@3: template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3: class ArrayPOD : public ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> >
nuclear@3: {
nuclear@3: public:
nuclear@3:     typedef T                                                               ValueType;
nuclear@3:     typedef ContainerAllocator_POD<T>                                       AllocatorType;
nuclear@3:     typedef SizePolicy                                                      SizePolicyType;
nuclear@3:     typedef ArrayPOD<T, SizePolicy>                                         SelfType;
nuclear@3:     typedef ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> > BaseType;
nuclear@3: 
nuclear@3:     ArrayPOD() : BaseType() {}
nuclear@3:     ArrayPOD(int size) : BaseType(size) {}
nuclear@3:     ArrayPOD(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@3:     ArrayPOD(const SelfType& a) : BaseType(a) {}
nuclear@3:     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: // ***** ArrayCPP
nuclear@3: //
nuclear@3: // General purpose, fully C++ compliant array. Can be used with non-movable data.
nuclear@3: // Global heap is in use.
nuclear@3: template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3: class ArrayCPP : public ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> >
nuclear@3: {
nuclear@3: public:
nuclear@3:     typedef T                                                               ValueType;
nuclear@3:     typedef ContainerAllocator_CPP<T>                                       AllocatorType;
nuclear@3:     typedef SizePolicy                                                      SizePolicyType;
nuclear@3:     typedef ArrayCPP<T, SizePolicy>                                         SelfType;
nuclear@3:     typedef ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> > BaseType;
nuclear@3: 
nuclear@3:     ArrayCPP() : BaseType() {}
nuclear@3:     ArrayCPP(int size) : BaseType(size) {}
nuclear@3:     ArrayCPP(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@3:     ArrayCPP(const SelfType& a) : BaseType(a) {}
nuclear@3:     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: // ***** ArrayCC
nuclear@3: //
nuclear@3: // A modification of the array that uses the given default value to
nuclear@3: // construct the elements. The constructors and destructors are 
nuclear@3: // properly called, the objects must be movable.
nuclear@3: 
nuclear@3: template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3: class ArrayCC : public ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >
nuclear@3: {
nuclear@3: public:
nuclear@3:     typedef T                                                               ValueType;
nuclear@3:     typedef ContainerAllocator<T>                                           AllocatorType;
nuclear@3:     typedef SizePolicy                                                      SizePolicyType;
nuclear@3:     typedef ArrayCC<T, SizePolicy>                                          SelfType;
nuclear@3:     typedef ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >   BaseType;
nuclear@3: 
nuclear@3:     ArrayCC(const ValueType& defval) : BaseType(defval) {}
nuclear@3:     ArrayCC(const ValueType& defval, int size) : BaseType(defval, size) {}
nuclear@3:     ArrayCC(const ValueType& defval, const SizePolicyType& p) : BaseType(defval) { SetSizePolicy(p); }
nuclear@3:     ArrayCC(const SelfType& a) : BaseType(a) {}
nuclear@3:     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3: };
nuclear@3: 
nuclear@3: } // OVR
nuclear@3: 
nuclear@3: #endif