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