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