1.1 --- a/libovr/Src/Kernel/OVR_Array.h	Sat Sep 14 17:51:03 2013 +0300
     1.2 +++ b/libovr/Src/Kernel/OVR_Array.h	Sun Sep 15 04:10:05 2013 +0300
     1.3 @@ -1,1 +1,793 @@
     1.4 -/************************************************************************************
     1.5 
     1.6 PublicHeader:   OVR.h
     1.7 Filename    :   OVR_Array.h
     1.8 Content     :   Template implementation for Array
     1.9 Created     :   September 19, 2012
    1.10 Notes       : 
    1.11 
    1.12 Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
    1.13 
    1.14 Use of this software is subject to the terms of the Oculus license
    1.15 agreement provided at the time of installation or download, or which
    1.16 otherwise accompanies this software in either electronic or hard copy form.
    1.17 
    1.18 ************************************************************************************/
    1.19 
    1.20 #ifndef OVR_Array_h
    1.21 #define OVR_Array_h
    1.22 
    1.23 #include "OVR_ContainerAllocator.h"
    1.24 
    1.25 namespace OVR {
    1.26 
    1.27 //-----------------------------------------------------------------------------------
    1.28 // ***** ArrayDefaultPolicy
    1.29 //
    1.30 // Default resize behavior. No minimal capacity, Granularity=4, 
    1.31 // Shrinking as needed. ArrayConstPolicy actually is the same as 
    1.32 // ArrayDefaultPolicy, but parametrized with constants. 
    1.33 // This struct is used only in order to reduce the template "matroska".
    1.34 struct ArrayDefaultPolicy
    1.35 {
    1.36     ArrayDefaultPolicy() : Capacity(0) {}
    1.37     ArrayDefaultPolicy(const ArrayDefaultPolicy&) : Capacity(0) {}
    1.38 
    1.39     UPInt GetMinCapacity() const { return 0; }
    1.40     UPInt GetGranularity() const { return 4; }
    1.41     bool  NeverShrinking() const { return 0; }
    1.42 
    1.43     UPInt GetCapacity()    const      { return Capacity; }
    1.44     void  SetCapacity(UPInt capacity) { Capacity = capacity; }
    1.45 private:
    1.46     UPInt Capacity;
    1.47 };
    1.48 
    1.49 
    1.50 //-----------------------------------------------------------------------------------
    1.51 // ***** ArrayConstPolicy
    1.52 //
    1.53 // Statically parametrized resizing behavior:
    1.54 // MinCapacity, Granularity, and Shrinking flag.
    1.55 template<int MinCapacity=0, int Granularity=4, bool NeverShrink=false>
    1.56 struct ArrayConstPolicy
    1.57 {
    1.58     typedef ArrayConstPolicy<MinCapacity, Granularity, NeverShrink> SelfType;
    1.59 
    1.60     ArrayConstPolicy() : Capacity(0) {}
    1.61     ArrayConstPolicy(const SelfType&) : Capacity(0) {}
    1.62 
    1.63     UPInt GetMinCapacity() const { return MinCapacity; }
    1.64     UPInt GetGranularity() const { return Granularity; }
    1.65     bool  NeverShrinking() const { return NeverShrink; }
    1.66 
    1.67     UPInt GetCapacity()    const      { return Capacity; }
    1.68     void  SetCapacity(UPInt capacity) { Capacity = capacity; }
    1.69 private:
    1.70     UPInt Capacity;
    1.71 };
    1.72 
    1.73 //-----------------------------------------------------------------------------------
    1.74 // ***** ArrayDataBase
    1.75 //
    1.76 // Basic operations with array data: Reserve, Resize, Free, ArrayPolicy.
    1.77 // For internal use only: ArrayData,ArrayDataCC and others.
    1.78 template<class T, class Allocator, class SizePolicy>
    1.79 struct ArrayDataBase
    1.80 {
    1.81     typedef T                                           ValueType;
    1.82     typedef Allocator                                   AllocatorType;
    1.83     typedef SizePolicy                                  SizePolicyType;
    1.84     typedef ArrayDataBase<T, Allocator, SizePolicy>     SelfType;
    1.85 
    1.86     ArrayDataBase()
    1.87         : Data(0), Size(0), Policy() {}
    1.88 
    1.89     ArrayDataBase(const SizePolicy& p)
    1.90         : Data(0), Size(0), Policy(p) {}
    1.91 
    1.92     ~ArrayDataBase() 
    1.93     {
    1.94         Allocator::DestructArray(Data, Size);
    1.95         Allocator::Free(Data);
    1.96     }
    1.97 
    1.98     UPInt GetCapacity() const 
    1.99     { 
   1.100         return Policy.GetCapacity(); 
   1.101     }
   1.102 
   1.103     void ClearAndRelease()
   1.104     {
   1.105         Allocator::DestructArray(Data, Size);
   1.106         Allocator::Free(Data);
   1.107         Data = 0;
   1.108         Size = 0;
   1.109         Policy.SetCapacity(0);
   1.110     }
   1.111 
   1.112     void Reserve(UPInt newCapacity)
   1.113     {
   1.114         if (Policy.NeverShrinking() && newCapacity < GetCapacity())
   1.115             return;
   1.116 
   1.117         if (newCapacity < Policy.GetMinCapacity())
   1.118             newCapacity = Policy.GetMinCapacity();
   1.119 
   1.120         // Resize the buffer.
   1.121         if (newCapacity == 0)
   1.122         {
   1.123             if (Data)
   1.124             {
   1.125                 Allocator::Free(Data);
   1.126                 Data = 0;
   1.127             }
   1.128             Policy.SetCapacity(0);
   1.129         }
   1.130         else
   1.131         {
   1.132             UPInt gran = Policy.GetGranularity();
   1.133             newCapacity = (newCapacity + gran - 1) / gran * gran;
   1.134             if (Data)
   1.135             {
   1.136                 if (Allocator::IsMovable())
   1.137                 {
   1.138                     Data = (T*)Allocator::Realloc(Data, sizeof(T) * newCapacity);
   1.139                 }
   1.140                 else
   1.141                 {
   1.142                     T* newData = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
   1.143                     UPInt i, s;
   1.144                     s = (Size < newCapacity) ? Size : newCapacity;
   1.145                     for (i = 0; i < s; ++i)
   1.146                     {
   1.147                         Allocator::Construct(&newData[i], Data[i]);
   1.148                         Allocator::Destruct(&Data[i]);
   1.149                     }
   1.150                     for (i = s; i < Size; ++i)
   1.151                     {
   1.152                         Allocator::Destruct(&Data[i]);
   1.153                     }
   1.154                     Allocator::Free(Data);
   1.155                     Data = newData;
   1.156                 }
   1.157             }
   1.158             else
   1.159             {
   1.160                 Data = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
   1.161                 //memset(Buffer, 0, (sizeof(ValueType) * newSize)); // Do we need this?
   1.162             }
   1.163             Policy.SetCapacity(newCapacity);
   1.164             // OVR_ASSERT(Data); // need to throw (or something) on alloc failure!
   1.165         }
   1.166     }
   1.167 
   1.168     // This version of Resize DOES NOT construct the elements.
   1.169     // It's done to optimize PushBack, which uses a copy constructor 
   1.170     // instead of the default constructor and assignment
   1.171     void ResizeNoConstruct(UPInt newSize)
   1.172     {
   1.173         UPInt oldSize = Size;
   1.174 
   1.175         if (newSize < oldSize)
   1.176         {
   1.177             Allocator::DestructArray(Data + newSize, oldSize - newSize);
   1.178             if (newSize < (Policy.GetCapacity() >> 1))
   1.179             {
   1.180                 Reserve(newSize);
   1.181             }
   1.182         }
   1.183         else if(newSize >= Policy.GetCapacity())
   1.184         {
   1.185             Reserve(newSize + (newSize >> 2));
   1.186         }
   1.187         //! IMPORTANT to modify Size only after Reserve completes, because garbage collectable
   1.188         // array may use this array and may traverse it during Reserve (in the case, if 
   1.189         // collection occurs because of heap limit exceeded).
   1.190         Size = newSize;
   1.191     }
   1.192 
   1.193     ValueType*  Data;
   1.194     UPInt       Size;
   1.195     SizePolicy  Policy;
   1.196 };
   1.197 
   1.198 
   1.199 
   1.200 //-----------------------------------------------------------------------------------
   1.201 // ***** ArrayData
   1.202 //
   1.203 // General purpose array data.
   1.204 // For internal use only in Array, ArrayLH, ArrayPOD and so on.
   1.205 template<class T, class Allocator, class SizePolicy>
   1.206 struct ArrayData : ArrayDataBase<T, Allocator, SizePolicy>
   1.207 {
   1.208     typedef T ValueType;
   1.209     typedef Allocator                                   AllocatorType;
   1.210     typedef SizePolicy                                  SizePolicyType;
   1.211     typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
   1.212     typedef ArrayData    <T, Allocator, SizePolicy>     SelfType;
   1.213 
   1.214     ArrayData()
   1.215         : BaseType() { }
   1.216 
   1.217     ArrayData(int size)
   1.218         : BaseType() { Resize(size); }
   1.219 
   1.220     ArrayData(const SelfType& a)
   1.221         : BaseType(a.Policy) { Append(a.Data, a.Size); }
   1.222 
   1.223 
   1.224     void Resize(UPInt newSize)
   1.225     {
   1.226         UPInt oldSize = this->Size;
   1.227         BaseType::ResizeNoConstruct(newSize);
   1.228         if(newSize > oldSize)
   1.229             Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize);
   1.230     }
   1.231 
   1.232     void PushBack(const ValueType& val)
   1.233     {
   1.234         BaseType::ResizeNoConstruct(this->Size + 1);
   1.235         Allocator::Construct(this->Data + this->Size - 1, val);
   1.236     }
   1.237 
   1.238     template<class S>
   1.239     void PushBackAlt(const S& val)
   1.240     {
   1.241         BaseType::ResizeNoConstruct(this->Size + 1);
   1.242         Allocator::ConstructAlt(this->Data + this->Size - 1, val);
   1.243     }
   1.244 
   1.245     // Append the given data to the array.
   1.246     void Append(const ValueType other[], UPInt count)
   1.247     {
   1.248         if (count)
   1.249         {
   1.250             UPInt oldSize = this->Size;
   1.251             BaseType::ResizeNoConstruct(this->Size + count);
   1.252             Allocator::ConstructArray(this->Data + oldSize, count, other);
   1.253         }
   1.254     }
   1.255 };
   1.256 
   1.257 
   1.258 
   1.259 //-----------------------------------------------------------------------------------
   1.260 // ***** ArrayDataCC
   1.261 //
   1.262 // A modification of ArrayData that always copy-constructs new elements
   1.263 // using a specified DefaultValue. For internal use only in ArrayCC.
   1.264 template<class T, class Allocator, class SizePolicy>
   1.265 struct ArrayDataCC : ArrayDataBase<T, Allocator, SizePolicy>
   1.266 {
   1.267     typedef T                                           ValueType;
   1.268     typedef Allocator                                   AllocatorType;
   1.269     typedef SizePolicy                                  SizePolicyType;
   1.270     typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
   1.271     typedef ArrayDataCC  <T, Allocator, SizePolicy>     SelfType;
   1.272 
   1.273     ArrayDataCC(const ValueType& defval)
   1.274         : BaseType(), DefaultValue(defval) { }
   1.275 
   1.276     ArrayDataCC(const ValueType& defval, int size)
   1.277         : BaseType(), DefaultValue(defval) { Resize(size); }
   1.278 
   1.279     ArrayDataCC(const SelfType& a)
   1.280         : BaseType(a.Policy), DefaultValue(a.DefaultValue) { Append(a.Data, a.Size); }
   1.281 
   1.282 
   1.283     void Resize(UPInt newSize)
   1.284     {
   1.285         UPInt oldSize = this->Size;
   1.286         BaseType::ResizeNoConstruct(newSize);
   1.287         if(newSize > oldSize)
   1.288             Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize, DefaultValue);
   1.289     }
   1.290 
   1.291     void PushBack(const ValueType& val)
   1.292     {
   1.293         BaseType::ResizeNoConstruct(this->Size + 1);
   1.294         Allocator::Construct(this->Data + this->Size - 1, val);
   1.295     }
   1.296 
   1.297     template<class S>
   1.298     void PushBackAlt(const S& val)
   1.299     {
   1.300         BaseType::ResizeNoConstruct(this->Size + 1);
   1.301         Allocator::ConstructAlt(this->Data + this->Size - 1, val);
   1.302     }
   1.303 
   1.304     // Append the given data to the array.
   1.305     void Append(const ValueType other[], UPInt count)
   1.306     {
   1.307         if (count)
   1.308         {
   1.309             UPInt oldSize = this->Size;
   1.310             BaseType::ResizeNoConstruct(this->Size + count);
   1.311             Allocator::ConstructArray(this->Data + oldSize, count, other);
   1.312         }
   1.313     }
   1.314 
   1.315     ValueType   DefaultValue;
   1.316 };
   1.317 
   1.318 
   1.319 
   1.320 
   1.321 
   1.322 //-----------------------------------------------------------------------------------
   1.323 // ***** ArrayBase
   1.324 //
   1.325 // Resizable array. The behavior can be POD (suffix _POD) and 
   1.326 // Movable (no suffix) depending on the allocator policy.
   1.327 // In case of _POD the constructors and destructors are not called.
   1.328 // 
   1.329 // Arrays can't handle non-movable objects! Don't put anything in here 
   1.330 // that can't be moved around by bitwise copy. 
   1.331 // 
   1.332 // The addresses of elements are not persistent! Don't keep the address 
   1.333 // of an element; the array contents will move around as it gets resized.
   1.334 template<class ArrayData>
   1.335 class ArrayBase
   1.336 {
   1.337 public:
   1.338     typedef typename ArrayData::ValueType       ValueType;
   1.339     typedef typename ArrayData::AllocatorType   AllocatorType;
   1.340     typedef typename ArrayData::SizePolicyType  SizePolicyType;
   1.341     typedef ArrayBase<ArrayData>                SelfType;
   1.342 
   1.343 
   1.344 #undef new
   1.345     OVR_MEMORY_REDEFINE_NEW(ArrayBase)
   1.346 // Redefine operator 'new' if necessary.
   1.347 #if defined(OVR_DEFINE_NEW)
   1.348 #define new OVR_DEFINE_NEW
   1.349 #endif
   1.350 
   1.351 
   1.352     ArrayBase()
   1.353         : Data() {}
   1.354     ArrayBase(int size)
   1.355         : Data(size) {}
   1.356     ArrayBase(const SelfType& a)
   1.357         : Data(a.Data) {}
   1.358 
   1.359     ArrayBase(const ValueType& defval)
   1.360         : Data(defval) {}
   1.361     ArrayBase(const ValueType& defval, int size)
   1.362         : Data(defval, size) {}
   1.363   
   1.364     SizePolicyType* GetSizePolicy() const                  { return Data.Policy; }
   1.365     void            SetSizePolicy(const SizePolicyType& p) { Data.Policy = p; }
   1.366 
   1.367     bool    NeverShrinking()const       { return Data.Policy.NeverShrinking(); }
   1.368     UPInt   GetSize()       const       { return Data.Size;  }
   1.369     bool    IsEmpty()       const       { return Data.Size == 0; }
   1.370     UPInt   GetCapacity()   const       { return Data.GetCapacity(); }
   1.371     UPInt   GetNumBytes()   const       { return Data.GetCapacity() * sizeof(ValueType); }
   1.372 
   1.373     void    ClearAndRelease()           { Data.ClearAndRelease(); }
   1.374     void    Clear()                     { Data.Resize(0); }
   1.375     void    Resize(UPInt newSize)       { Data.Resize(newSize); }
   1.376 
   1.377     // Reserve can only increase the capacity
   1.378     void    Reserve(UPInt newCapacity)  
   1.379     { 
   1.380         if (newCapacity > Data.GetCapacity())
   1.381             Data.Reserve(newCapacity); 
   1.382     }
   1.383 
   1.384     // Basic access.
   1.385     ValueType& At(UPInt index)
   1.386     {
   1.387         OVR_ASSERT(index < Data.Size);
   1.388         return Data.Data[index]; 
   1.389     }
   1.390     const ValueType& At(UPInt index) const
   1.391     {
   1.392         OVR_ASSERT(index < Data.Size);
   1.393         return Data.Data[index]; 
   1.394     }
   1.395 
   1.396     ValueType ValueAt(UPInt index) const
   1.397     {
   1.398         OVR_ASSERT(index < Data.Size);
   1.399         return Data.Data[index]; 
   1.400     }
   1.401 
   1.402     // Basic access.
   1.403     ValueType& operator [] (UPInt index)
   1.404     {
   1.405         OVR_ASSERT(index < Data.Size);
   1.406         return Data.Data[index]; 
   1.407     }
   1.408     const ValueType& operator [] (UPInt index) const
   1.409     {
   1.410         OVR_ASSERT(index < Data.Size);
   1.411         return Data.Data[index]; 
   1.412     }
   1.413 
   1.414     // Raw pointer to the data. Use with caution!
   1.415     const ValueType* GetDataPtr() const { return Data.Data; }
   1.416           ValueType* GetDataPtr()       { return Data.Data; }
   1.417 
   1.418     // Insert the given element at the end of the array.
   1.419     void    PushBack(const ValueType& val)
   1.420     {
   1.421         // DO NOT pass elements of your own vector into
   1.422         // push_back()!  Since we're using references,
   1.423         // resize() may munge the element storage!
   1.424         // OVR_ASSERT(&val < &Buffer[0] || &val > &Buffer[BufferSize]);
   1.425         Data.PushBack(val);
   1.426     }
   1.427 
   1.428     template<class S>
   1.429     void PushBackAlt(const S& val)
   1.430     {
   1.431         Data.PushBackAlt(val);
   1.432     }
   1.433 
   1.434     // Remove the last element.
   1.435     void    PopBack(UPInt count = 1)
   1.436     {
   1.437         OVR_ASSERT(Data.Size >= count);
   1.438         Data.Resize(Data.Size - count);
   1.439     }
   1.440 
   1.441     ValueType& PushDefault()
   1.442     {
   1.443         Data.PushBack(ValueType());
   1.444         return Back();
   1.445     }
   1.446 
   1.447     ValueType Pop()
   1.448     {
   1.449         ValueType t = Back();
   1.450         PopBack();
   1.451         return t;
   1.452     }
   1.453 
   1.454 
   1.455     // Access the first element.
   1.456     ValueType&          Front()         { return At(0); }
   1.457     const ValueType&    Front() const   { return At(0); }
   1.458 
   1.459     // Access the last element.
   1.460     ValueType&          Back()          { return At(Data.Size - 1); }
   1.461     const ValueType&    Back() const    { return At(Data.Size - 1); }
   1.462 
   1.463     // Array copy.  Copies the contents of a into this array.
   1.464     const SelfType& operator = (const SelfType& a)   
   1.465     {
   1.466         Resize(a.GetSize());
   1.467         for (UPInt i = 0; i < Data.Size; i++) {
   1.468             *(Data.Data + i) = a[i];
   1.469         }
   1.470         return *this;
   1.471     }
   1.472 
   1.473     // Removing multiple elements from the array.
   1.474     void    RemoveMultipleAt(UPInt index, UPInt num)
   1.475     {
   1.476         OVR_ASSERT(index + num <= Data.Size);
   1.477         if (Data.Size == num)
   1.478         {
   1.479             Clear();
   1.480         }
   1.481         else
   1.482         {
   1.483             AllocatorType::DestructArray(Data.Data + index, num);
   1.484             AllocatorType::CopyArrayForward(
   1.485                 Data.Data + index, 
   1.486                 Data.Data + index + num,
   1.487                 Data.Size - num - index);
   1.488             Data.Size -= num;
   1.489         }
   1.490     }
   1.491 
   1.492     // Removing an element from the array is an expensive operation!
   1.493     // It compacts only after removing the last element.
   1.494     void    RemoveAt(UPInt index)
   1.495     {
   1.496         OVR_ASSERT(index < Data.Size);
   1.497         if (Data.Size == 1)
   1.498         {
   1.499             Clear();
   1.500         }
   1.501         else
   1.502         {
   1.503             AllocatorType::Destruct(Data.Data + index);
   1.504             AllocatorType::CopyArrayForward(
   1.505                 Data.Data + index, 
   1.506                 Data.Data + index + 1,
   1.507                 Data.Size - 1 - index);
   1.508             --Data.Size;
   1.509         }
   1.510     }
   1.511 
   1.512     // Insert the given object at the given index shifting all the elements up.
   1.513     void    InsertAt(UPInt index, const ValueType& val = ValueType())
   1.514     {
   1.515         OVR_ASSERT(index <= Data.Size);
   1.516 
   1.517         Data.Resize(Data.Size + 1);
   1.518         if (index < Data.Size - 1)
   1.519         {
   1.520             AllocatorType::CopyArrayBackward(
   1.521                 Data.Data + index + 1, 
   1.522                 Data.Data + index, 
   1.523                 Data.Size - 1 - index);
   1.524         }
   1.525         AllocatorType::Construct(Data.Data + index, val);
   1.526     }
   1.527 
   1.528     // Insert the given object at the given index shifting all the elements up.
   1.529     void    InsertMultipleAt(UPInt index, UPInt num, const ValueType& val = ValueType())
   1.530     {
   1.531         OVR_ASSERT(index <= Data.Size);
   1.532 
   1.533         Data.Resize(Data.Size + num);
   1.534         if (index < Data.Size - num)
   1.535         {
   1.536             AllocatorType::CopyArrayBackward(
   1.537                 Data.Data + index + num,
   1.538                 Data.Data + index,
   1.539                 Data.Size - num - index);
   1.540         }
   1.541         for (UPInt i = 0; i < num; ++i)
   1.542             AllocatorType::Construct(Data.Data + index + i, val);
   1.543     }
   1.544 
   1.545     // Append the given data to the array.
   1.546     void    Append(const SelfType& other)
   1.547     {
   1.548         Append(other.Data.Data, other.GetSize());
   1.549     }
   1.550 
   1.551     // Append the given data to the array.
   1.552     void    Append(const ValueType other[], UPInt count)
   1.553     {
   1.554         Data.Append(other, count);
   1.555     }
   1.556 
   1.557     class Iterator
   1.558     {
   1.559         SelfType*       pArray;
   1.560         SPInt           CurIndex;
   1.561 
   1.562     public:
   1.563         Iterator() : pArray(0), CurIndex(-1) {}
   1.564         Iterator(SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
   1.565 
   1.566         bool operator==(const Iterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
   1.567         bool operator!=(const Iterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
   1.568 
   1.569         Iterator& operator++()
   1.570         {
   1.571             if (pArray)
   1.572             {
   1.573                 if (CurIndex < (SPInt)pArray->GetSize())
   1.574                     ++CurIndex;
   1.575             }
   1.576             return *this;
   1.577         }
   1.578         Iterator operator++(int)
   1.579         {
   1.580             Iterator it(*this);
   1.581             operator++();
   1.582             return it;
   1.583         }
   1.584         Iterator& operator--()
   1.585         {
   1.586             if (pArray)
   1.587             {
   1.588                 if (CurIndex >= 0)
   1.589                     --CurIndex;
   1.590             }
   1.591             return *this;
   1.592         }
   1.593         Iterator operator--(int)
   1.594         {
   1.595             Iterator it(*this);
   1.596             operator--();
   1.597             return it;
   1.598         }
   1.599         Iterator operator+(int delta) const
   1.600         {
   1.601             return Iterator(pArray, CurIndex + delta);
   1.602         }
   1.603         Iterator operator-(int delta) const
   1.604         {
   1.605             return Iterator(pArray, CurIndex - delta);
   1.606         }
   1.607         SPInt operator-(const Iterator& right) const
   1.608         {
   1.609             OVR_ASSERT(pArray == right.pArray);
   1.610             return CurIndex - right.CurIndex;
   1.611         }
   1.612         ValueType& operator*() const    { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
   1.613         ValueType* operator->() const   { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.614         ValueType* GetPtr() const       { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.615 
   1.616         bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
   1.617 
   1.618         void Remove()
   1.619         {
   1.620             if (!IsFinished())
   1.621                 pArray->RemoveAt(CurIndex);
   1.622         }
   1.623 
   1.624         SPInt GetIndex() const { return CurIndex; }
   1.625     };
   1.626 
   1.627     Iterator Begin() { return Iterator(this); }
   1.628     Iterator End()   { return Iterator(this, (SPInt)GetSize()); }
   1.629     Iterator Last()  { return Iterator(this, (SPInt)GetSize() - 1); }
   1.630 
   1.631     class ConstIterator
   1.632     {
   1.633         const SelfType* pArray;
   1.634         SPInt           CurIndex;
   1.635 
   1.636     public:
   1.637         ConstIterator() : pArray(0), CurIndex(-1) {}
   1.638         ConstIterator(const SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
   1.639 
   1.640         bool operator==(const ConstIterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
   1.641         bool operator!=(const ConstIterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
   1.642 
   1.643         ConstIterator& operator++()
   1.644         {
   1.645             if (pArray)
   1.646             {
   1.647                 if (CurIndex < (int)pArray->GetSize())
   1.648                     ++CurIndex;
   1.649             }
   1.650             return *this;
   1.651         }
   1.652         ConstIterator operator++(int)
   1.653         {
   1.654             ConstIterator it(*this);
   1.655             operator++();
   1.656             return it;
   1.657         }
   1.658         ConstIterator& operator--()
   1.659         {
   1.660             if (pArray)
   1.661             {
   1.662                 if (CurIndex >= 0)
   1.663                     --CurIndex;
   1.664             }
   1.665             return *this;
   1.666         }
   1.667         ConstIterator operator--(int)
   1.668         {
   1.669             ConstIterator it(*this);
   1.670             operator--();
   1.671             return it;
   1.672         }
   1.673         ConstIterator operator+(int delta) const
   1.674         {
   1.675             return ConstIterator(pArray, CurIndex + delta);
   1.676         }
   1.677         ConstIterator operator-(int delta) const
   1.678         {
   1.679             return ConstIterator(pArray, CurIndex - delta);
   1.680         }
   1.681         SPInt operator-(const ConstIterator& right) const
   1.682         {
   1.683             OVR_ASSERT(pArray == right.pArray);
   1.684             return CurIndex - right.CurIndex;
   1.685         }
   1.686         const ValueType& operator*() const  { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
   1.687         const ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.688         const ValueType* GetPtr() const     { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.689 
   1.690         bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
   1.691 
   1.692         SPInt GetIndex()  const { return CurIndex; }
   1.693     };
   1.694     ConstIterator Begin() const { return ConstIterator(this); }
   1.695     ConstIterator End() const   { return ConstIterator(this, (SPInt)GetSize()); }
   1.696     ConstIterator Last() const  { return ConstIterator(this, (SPInt)GetSize() - 1); }
   1.697 
   1.698 protected:
   1.699     ArrayData   Data;
   1.700 };
   1.701 
   1.702 
   1.703 
   1.704 //-----------------------------------------------------------------------------------
   1.705 // ***** Array
   1.706 //
   1.707 // General purpose array for movable objects that require explicit 
   1.708 // construction/destruction.
   1.709 template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.710 class Array : public ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> >
   1.711 {
   1.712 public:
   1.713     typedef T                                                           ValueType;
   1.714     typedef ContainerAllocator<T>                                       AllocatorType;
   1.715     typedef SizePolicy                                                  SizePolicyType;
   1.716     typedef Array<T, SizePolicy>                                        SelfType;
   1.717     typedef ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> > BaseType;
   1.718 
   1.719     Array() : BaseType() {}
   1.720     Array(int size) : BaseType(size) {}
   1.721     Array(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
   1.722     Array(const SelfType& a) : BaseType(a) {}
   1.723     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.724 };
   1.725 
   1.726 // ***** ArrayPOD
   1.727 //
   1.728 // General purpose array for movable objects that DOES NOT require  
   1.729 // construction/destruction. Constructors and destructors are not called! 
   1.730 // Global heap is in use.
   1.731 template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.732 class ArrayPOD : public ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> >
   1.733 {
   1.734 public:
   1.735     typedef T                                                               ValueType;
   1.736     typedef ContainerAllocator_POD<T>                                       AllocatorType;
   1.737     typedef SizePolicy                                                      SizePolicyType;
   1.738     typedef ArrayPOD<T, SizePolicy>                                         SelfType;
   1.739     typedef ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> > BaseType;
   1.740 
   1.741     ArrayPOD() : BaseType() {}
   1.742     ArrayPOD(int size) : BaseType(size) {}
   1.743     ArrayPOD(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
   1.744     ArrayPOD(const SelfType& a) : BaseType(a) {}
   1.745     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.746 };
   1.747 
   1.748 
   1.749 // ***** ArrayCPP
   1.750 //
   1.751 // General purpose, fully C++ compliant array. Can be used with non-movable data.
   1.752 // Global heap is in use.
   1.753 template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.754 class ArrayCPP : public ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> >
   1.755 {
   1.756 public:
   1.757     typedef T                                                               ValueType;
   1.758     typedef ContainerAllocator_CPP<T>                                       AllocatorType;
   1.759     typedef SizePolicy                                                      SizePolicyType;
   1.760     typedef ArrayCPP<T, SizePolicy>                                         SelfType;
   1.761     typedef ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> > BaseType;
   1.762 
   1.763     ArrayCPP() : BaseType() {}
   1.764     ArrayCPP(int size) : BaseType(size) {}
   1.765     ArrayCPP(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
   1.766     ArrayCPP(const SelfType& a) : BaseType(a) {}
   1.767     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.768 };
   1.769 
   1.770 
   1.771 // ***** ArrayCC
   1.772 //
   1.773 // A modification of the array that uses the given default value to
   1.774 // construct the elements. The constructors and destructors are 
   1.775 // properly called, the objects must be movable.
   1.776 
   1.777 template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.778 class ArrayCC : public ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >
   1.779 {
   1.780 public:
   1.781     typedef T                                                               ValueType;
   1.782     typedef ContainerAllocator<T>                                           AllocatorType;
   1.783     typedef SizePolicy                                                      SizePolicyType;
   1.784     typedef ArrayCC<T, SizePolicy>                                          SelfType;
   1.785     typedef ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >   BaseType;
   1.786 
   1.787     ArrayCC(const ValueType& defval) : BaseType(defval) {}
   1.788     ArrayCC(const ValueType& defval, int size) : BaseType(defval, size) {}
   1.789     ArrayCC(const ValueType& defval, const SizePolicyType& p) : BaseType(defval) { SetSizePolicy(p); }
   1.790     ArrayCC(const SelfType& a) : BaseType(a) {}
   1.791     const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.792 };
   1.793 
   1.794 } // OVR
   1.795 
   1.796 #endif
   1.797 \ No newline at end of file
   1.798 +/************************************************************************************
   1.799 +
   1.800 +PublicHeader:   OVR.h
   1.801 +Filename    :   OVR_Array.h
   1.802 +Content     :   Template implementation for Array
   1.803 +Created     :   September 19, 2012
   1.804 +Notes       : 
   1.805 +
   1.806 +Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
   1.807 +
   1.808 +Use of this software is subject to the terms of the Oculus license
   1.809 +agreement provided at the time of installation or download, or which
   1.810 +otherwise accompanies this software in either electronic or hard copy form.
   1.811 +
   1.812 +************************************************************************************/
   1.813 +
   1.814 +#ifndef OVR_Array_h
   1.815 +#define OVR_Array_h
   1.816 +
   1.817 +#include "OVR_ContainerAllocator.h"
   1.818 +
   1.819 +namespace OVR {
   1.820 +
   1.821 +//-----------------------------------------------------------------------------------
   1.822 +// ***** ArrayDefaultPolicy
   1.823 +//
   1.824 +// Default resize behavior. No minimal capacity, Granularity=4, 
   1.825 +// Shrinking as needed. ArrayConstPolicy actually is the same as 
   1.826 +// ArrayDefaultPolicy, but parametrized with constants. 
   1.827 +// This struct is used only in order to reduce the template "matroska".
   1.828 +struct ArrayDefaultPolicy
   1.829 +{
   1.830 +    ArrayDefaultPolicy() : Capacity(0) {}
   1.831 +    ArrayDefaultPolicy(const ArrayDefaultPolicy&) : Capacity(0) {}
   1.832 +
   1.833 +    UPInt GetMinCapacity() const { return 0; }
   1.834 +    UPInt GetGranularity() const { return 4; }
   1.835 +    bool  NeverShrinking() const { return 0; }
   1.836 +
   1.837 +    UPInt GetCapacity()    const      { return Capacity; }
   1.838 +    void  SetCapacity(UPInt capacity) { Capacity = capacity; }
   1.839 +private:
   1.840 +    UPInt Capacity;
   1.841 +};
   1.842 +
   1.843 +
   1.844 +//-----------------------------------------------------------------------------------
   1.845 +// ***** ArrayConstPolicy
   1.846 +//
   1.847 +// Statically parametrized resizing behavior:
   1.848 +// MinCapacity, Granularity, and Shrinking flag.
   1.849 +template<int MinCapacity=0, int Granularity=4, bool NeverShrink=false>
   1.850 +struct ArrayConstPolicy
   1.851 +{
   1.852 +    typedef ArrayConstPolicy<MinCapacity, Granularity, NeverShrink> SelfType;
   1.853 +
   1.854 +    ArrayConstPolicy() : Capacity(0) {}
   1.855 +    ArrayConstPolicy(const SelfType&) : Capacity(0) {}
   1.856 +
   1.857 +    UPInt GetMinCapacity() const { return MinCapacity; }
   1.858 +    UPInt GetGranularity() const { return Granularity; }
   1.859 +    bool  NeverShrinking() const { return NeverShrink; }
   1.860 +
   1.861 +    UPInt GetCapacity()    const      { return Capacity; }
   1.862 +    void  SetCapacity(UPInt capacity) { Capacity = capacity; }
   1.863 +private:
   1.864 +    UPInt Capacity;
   1.865 +};
   1.866 +
   1.867 +//-----------------------------------------------------------------------------------
   1.868 +// ***** ArrayDataBase
   1.869 +//
   1.870 +// Basic operations with array data: Reserve, Resize, Free, ArrayPolicy.
   1.871 +// For internal use only: ArrayData,ArrayDataCC and others.
   1.872 +template<class T, class Allocator, class SizePolicy>
   1.873 +struct ArrayDataBase
   1.874 +{
   1.875 +    typedef T                                           ValueType;
   1.876 +    typedef Allocator                                   AllocatorType;
   1.877 +    typedef SizePolicy                                  SizePolicyType;
   1.878 +    typedef ArrayDataBase<T, Allocator, SizePolicy>     SelfType;
   1.879 +
   1.880 +    ArrayDataBase()
   1.881 +        : Data(0), Size(0), Policy() {}
   1.882 +
   1.883 +    ArrayDataBase(const SizePolicy& p)
   1.884 +        : Data(0), Size(0), Policy(p) {}
   1.885 +
   1.886 +    ~ArrayDataBase() 
   1.887 +    {
   1.888 +        Allocator::DestructArray(Data, Size);
   1.889 +        Allocator::Free(Data);
   1.890 +    }
   1.891 +
   1.892 +    UPInt GetCapacity() const 
   1.893 +    { 
   1.894 +        return Policy.GetCapacity(); 
   1.895 +    }
   1.896 +
   1.897 +    void ClearAndRelease()
   1.898 +    {
   1.899 +        Allocator::DestructArray(Data, Size);
   1.900 +        Allocator::Free(Data);
   1.901 +        Data = 0;
   1.902 +        Size = 0;
   1.903 +        Policy.SetCapacity(0);
   1.904 +    }
   1.905 +
   1.906 +    void Reserve(UPInt newCapacity)
   1.907 +    {
   1.908 +        if (Policy.NeverShrinking() && newCapacity < GetCapacity())
   1.909 +            return;
   1.910 +
   1.911 +        if (newCapacity < Policy.GetMinCapacity())
   1.912 +            newCapacity = Policy.GetMinCapacity();
   1.913 +
   1.914 +        // Resize the buffer.
   1.915 +        if (newCapacity == 0)
   1.916 +        {
   1.917 +            if (Data)
   1.918 +            {
   1.919 +                Allocator::Free(Data);
   1.920 +                Data = 0;
   1.921 +            }
   1.922 +            Policy.SetCapacity(0);
   1.923 +        }
   1.924 +        else
   1.925 +        {
   1.926 +            UPInt gran = Policy.GetGranularity();
   1.927 +            newCapacity = (newCapacity + gran - 1) / gran * gran;
   1.928 +            if (Data)
   1.929 +            {
   1.930 +                if (Allocator::IsMovable())
   1.931 +                {
   1.932 +                    Data = (T*)Allocator::Realloc(Data, sizeof(T) * newCapacity);
   1.933 +                }
   1.934 +                else
   1.935 +                {
   1.936 +                    T* newData = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
   1.937 +                    UPInt i, s;
   1.938 +                    s = (Size < newCapacity) ? Size : newCapacity;
   1.939 +                    for (i = 0; i < s; ++i)
   1.940 +                    {
   1.941 +                        Allocator::Construct(&newData[i], Data[i]);
   1.942 +                        Allocator::Destruct(&Data[i]);
   1.943 +                    }
   1.944 +                    for (i = s; i < Size; ++i)
   1.945 +                    {
   1.946 +                        Allocator::Destruct(&Data[i]);
   1.947 +                    }
   1.948 +                    Allocator::Free(Data);
   1.949 +                    Data = newData;
   1.950 +                }
   1.951 +            }
   1.952 +            else
   1.953 +            {
   1.954 +                Data = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
   1.955 +                //memset(Buffer, 0, (sizeof(ValueType) * newSize)); // Do we need this?
   1.956 +            }
   1.957 +            Policy.SetCapacity(newCapacity);
   1.958 +            // OVR_ASSERT(Data); // need to throw (or something) on alloc failure!
   1.959 +        }
   1.960 +    }
   1.961 +
   1.962 +    // This version of Resize DOES NOT construct the elements.
   1.963 +    // It's done to optimize PushBack, which uses a copy constructor 
   1.964 +    // instead of the default constructor and assignment
   1.965 +    void ResizeNoConstruct(UPInt newSize)
   1.966 +    {
   1.967 +        UPInt oldSize = Size;
   1.968 +
   1.969 +        if (newSize < oldSize)
   1.970 +        {
   1.971 +            Allocator::DestructArray(Data + newSize, oldSize - newSize);
   1.972 +            if (newSize < (Policy.GetCapacity() >> 1))
   1.973 +            {
   1.974 +                Reserve(newSize);
   1.975 +            }
   1.976 +        }
   1.977 +        else if(newSize >= Policy.GetCapacity())
   1.978 +        {
   1.979 +            Reserve(newSize + (newSize >> 2));
   1.980 +        }
   1.981 +        //! IMPORTANT to modify Size only after Reserve completes, because garbage collectable
   1.982 +        // array may use this array and may traverse it during Reserve (in the case, if 
   1.983 +        // collection occurs because of heap limit exceeded).
   1.984 +        Size = newSize;
   1.985 +    }
   1.986 +
   1.987 +    ValueType*  Data;
   1.988 +    UPInt       Size;
   1.989 +    SizePolicy  Policy;
   1.990 +};
   1.991 +
   1.992 +
   1.993 +
   1.994 +//-----------------------------------------------------------------------------------
   1.995 +// ***** ArrayData
   1.996 +//
   1.997 +// General purpose array data.
   1.998 +// For internal use only in Array, ArrayLH, ArrayPOD and so on.
   1.999 +template<class T, class Allocator, class SizePolicy>
  1.1000 +struct ArrayData : ArrayDataBase<T, Allocator, SizePolicy>
  1.1001 +{
  1.1002 +    typedef T ValueType;
  1.1003 +    typedef Allocator                                   AllocatorType;
  1.1004 +    typedef SizePolicy                                  SizePolicyType;
  1.1005 +    typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
  1.1006 +    typedef ArrayData    <T, Allocator, SizePolicy>     SelfType;
  1.1007 +
  1.1008 +    ArrayData()
  1.1009 +        : BaseType() { }
  1.1010 +
  1.1011 +    ArrayData(int size)
  1.1012 +        : BaseType() { Resize(size); }
  1.1013 +
  1.1014 +    ArrayData(const SelfType& a)
  1.1015 +        : BaseType(a.Policy) { Append(a.Data, a.Size); }
  1.1016 +
  1.1017 +
  1.1018 +    void Resize(UPInt newSize)
  1.1019 +    {
  1.1020 +        UPInt oldSize = this->Size;
  1.1021 +        BaseType::ResizeNoConstruct(newSize);
  1.1022 +        if(newSize > oldSize)
  1.1023 +            Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize);
  1.1024 +    }
  1.1025 +
  1.1026 +    void PushBack(const ValueType& val)
  1.1027 +    {
  1.1028 +        BaseType::ResizeNoConstruct(this->Size + 1);
  1.1029 +        Allocator::Construct(this->Data + this->Size - 1, val);
  1.1030 +    }
  1.1031 +
  1.1032 +    template<class S>
  1.1033 +    void PushBackAlt(const S& val)
  1.1034 +    {
  1.1035 +        BaseType::ResizeNoConstruct(this->Size + 1);
  1.1036 +        Allocator::ConstructAlt(this->Data + this->Size - 1, val);
  1.1037 +    }
  1.1038 +
  1.1039 +    // Append the given data to the array.
  1.1040 +    void Append(const ValueType other[], UPInt count)
  1.1041 +    {
  1.1042 +        if (count)
  1.1043 +        {
  1.1044 +            UPInt oldSize = this->Size;
  1.1045 +            BaseType::ResizeNoConstruct(this->Size + count);
  1.1046 +            Allocator::ConstructArray(this->Data + oldSize, count, other);
  1.1047 +        }
  1.1048 +    }
  1.1049 +};
  1.1050 +
  1.1051 +
  1.1052 +
  1.1053 +//-----------------------------------------------------------------------------------
  1.1054 +// ***** ArrayDataCC
  1.1055 +//
  1.1056 +// A modification of ArrayData that always copy-constructs new elements
  1.1057 +// using a specified DefaultValue. For internal use only in ArrayCC.
  1.1058 +template<class T, class Allocator, class SizePolicy>
  1.1059 +struct ArrayDataCC : ArrayDataBase<T, Allocator, SizePolicy>
  1.1060 +{
  1.1061 +    typedef T                                           ValueType;
  1.1062 +    typedef Allocator                                   AllocatorType;
  1.1063 +    typedef SizePolicy                                  SizePolicyType;
  1.1064 +    typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
  1.1065 +    typedef ArrayDataCC  <T, Allocator, SizePolicy>     SelfType;
  1.1066 +
  1.1067 +    ArrayDataCC(const ValueType& defval)
  1.1068 +        : BaseType(), DefaultValue(defval) { }
  1.1069 +
  1.1070 +    ArrayDataCC(const ValueType& defval, int size)
  1.1071 +        : BaseType(), DefaultValue(defval) { Resize(size); }
  1.1072 +
  1.1073 +    ArrayDataCC(const SelfType& a)
  1.1074 +        : BaseType(a.Policy), DefaultValue(a.DefaultValue) { Append(a.Data, a.Size); }
  1.1075 +
  1.1076 +
  1.1077 +    void Resize(UPInt newSize)
  1.1078 +    {
  1.1079 +        UPInt oldSize = this->Size;
  1.1080 +        BaseType::ResizeNoConstruct(newSize);
  1.1081 +        if(newSize > oldSize)
  1.1082 +            Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize, DefaultValue);
  1.1083 +    }
  1.1084 +
  1.1085 +    void PushBack(const ValueType& val)
  1.1086 +    {
  1.1087 +        BaseType::ResizeNoConstruct(this->Size + 1);
  1.1088 +        Allocator::Construct(this->Data + this->Size - 1, val);
  1.1089 +    }
  1.1090 +
  1.1091 +    template<class S>
  1.1092 +    void PushBackAlt(const S& val)
  1.1093 +    {
  1.1094 +        BaseType::ResizeNoConstruct(this->Size + 1);
  1.1095 +        Allocator::ConstructAlt(this->Data + this->Size - 1, val);
  1.1096 +    }
  1.1097 +
  1.1098 +    // Append the given data to the array.
  1.1099 +    void Append(const ValueType other[], UPInt count)
  1.1100 +    {
  1.1101 +        if (count)
  1.1102 +        {
  1.1103 +            UPInt oldSize = this->Size;
  1.1104 +            BaseType::ResizeNoConstruct(this->Size + count);
  1.1105 +            Allocator::ConstructArray(this->Data + oldSize, count, other);
  1.1106 +        }
  1.1107 +    }
  1.1108 +
  1.1109 +    ValueType   DefaultValue;
  1.1110 +};
  1.1111 +
  1.1112 +
  1.1113 +
  1.1114 +
  1.1115 +
  1.1116 +//-----------------------------------------------------------------------------------
  1.1117 +// ***** ArrayBase
  1.1118 +//
  1.1119 +// Resizable array. The behavior can be POD (suffix _POD) and 
  1.1120 +// Movable (no suffix) depending on the allocator policy.
  1.1121 +// In case of _POD the constructors and destructors are not called.
  1.1122 +// 
  1.1123 +// Arrays can't handle non-movable objects! Don't put anything in here 
  1.1124 +// that can't be moved around by bitwise copy. 
  1.1125 +// 
  1.1126 +// The addresses of elements are not persistent! Don't keep the address 
  1.1127 +// of an element; the array contents will move around as it gets resized.
  1.1128 +template<class ArrayData>
  1.1129 +class ArrayBase
  1.1130 +{
  1.1131 +public:
  1.1132 +    typedef typename ArrayData::ValueType       ValueType;
  1.1133 +    typedef typename ArrayData::AllocatorType   AllocatorType;
  1.1134 +    typedef typename ArrayData::SizePolicyType  SizePolicyType;
  1.1135 +    typedef ArrayBase<ArrayData>                SelfType;
  1.1136 +
  1.1137 +
  1.1138 +#undef new
  1.1139 +    OVR_MEMORY_REDEFINE_NEW(ArrayBase)
  1.1140 +// Redefine operator 'new' if necessary.
  1.1141 +#if defined(OVR_DEFINE_NEW)
  1.1142 +#define new OVR_DEFINE_NEW
  1.1143 +#endif
  1.1144 +
  1.1145 +
  1.1146 +    ArrayBase()
  1.1147 +        : Data() {}
  1.1148 +    ArrayBase(int size)
  1.1149 +        : Data(size) {}
  1.1150 +    ArrayBase(const SelfType& a)
  1.1151 +        : Data(a.Data) {}
  1.1152 +
  1.1153 +    ArrayBase(const ValueType& defval)
  1.1154 +        : Data(defval) {}
  1.1155 +    ArrayBase(const ValueType& defval, int size)
  1.1156 +        : Data(defval, size) {}
  1.1157 +  
  1.1158 +    SizePolicyType* GetSizePolicy() const                  { return Data.Policy; }
  1.1159 +    void            SetSizePolicy(const SizePolicyType& p) { Data.Policy = p; }
  1.1160 +
  1.1161 +    bool    NeverShrinking()const       { return Data.Policy.NeverShrinking(); }
  1.1162 +    UPInt   GetSize()       const       { return Data.Size;  }
  1.1163 +    bool    IsEmpty()       const       { return Data.Size == 0; }
  1.1164 +    UPInt   GetCapacity()   const       { return Data.GetCapacity(); }
  1.1165 +    UPInt   GetNumBytes()   const       { return Data.GetCapacity() * sizeof(ValueType); }
  1.1166 +
  1.1167 +    void    ClearAndRelease()           { Data.ClearAndRelease(); }
  1.1168 +    void    Clear()                     { Data.Resize(0); }
  1.1169 +    void    Resize(UPInt newSize)       { Data.Resize(newSize); }
  1.1170 +
  1.1171 +    // Reserve can only increase the capacity
  1.1172 +    void    Reserve(UPInt newCapacity)  
  1.1173 +    { 
  1.1174 +        if (newCapacity > Data.GetCapacity())
  1.1175 +            Data.Reserve(newCapacity); 
  1.1176 +    }
  1.1177 +
  1.1178 +    // Basic access.
  1.1179 +    ValueType& At(UPInt index)
  1.1180 +    {
  1.1181 +        OVR_ASSERT(index < Data.Size);
  1.1182 +        return Data.Data[index]; 
  1.1183 +    }
  1.1184 +    const ValueType& At(UPInt index) const
  1.1185 +    {
  1.1186 +        OVR_ASSERT(index < Data.Size);
  1.1187 +        return Data.Data[index]; 
  1.1188 +    }
  1.1189 +
  1.1190 +    ValueType ValueAt(UPInt index) const
  1.1191 +    {
  1.1192 +        OVR_ASSERT(index < Data.Size);
  1.1193 +        return Data.Data[index]; 
  1.1194 +    }
  1.1195 +
  1.1196 +    // Basic access.
  1.1197 +    ValueType& operator [] (UPInt index)
  1.1198 +    {
  1.1199 +        OVR_ASSERT(index < Data.Size);
  1.1200 +        return Data.Data[index]; 
  1.1201 +    }
  1.1202 +    const ValueType& operator [] (UPInt index) const
  1.1203 +    {
  1.1204 +        OVR_ASSERT(index < Data.Size);
  1.1205 +        return Data.Data[index]; 
  1.1206 +    }
  1.1207 +
  1.1208 +    // Raw pointer to the data. Use with caution!
  1.1209 +    const ValueType* GetDataPtr() const { return Data.Data; }
  1.1210 +          ValueType* GetDataPtr()       { return Data.Data; }
  1.1211 +
  1.1212 +    // Insert the given element at the end of the array.
  1.1213 +    void    PushBack(const ValueType& val)
  1.1214 +    {
  1.1215 +        // DO NOT pass elements of your own vector into
  1.1216 +        // push_back()!  Since we're using references,
  1.1217 +        // resize() may munge the element storage!
  1.1218 +        // OVR_ASSERT(&val < &Buffer[0] || &val > &Buffer[BufferSize]);
  1.1219 +        Data.PushBack(val);
  1.1220 +    }
  1.1221 +
  1.1222 +    template<class S>
  1.1223 +    void PushBackAlt(const S& val)
  1.1224 +    {
  1.1225 +        Data.PushBackAlt(val);
  1.1226 +    }
  1.1227 +
  1.1228 +    // Remove the last element.
  1.1229 +    void    PopBack(UPInt count = 1)
  1.1230 +    {
  1.1231 +        OVR_ASSERT(Data.Size >= count);
  1.1232 +        Data.Resize(Data.Size - count);
  1.1233 +    }
  1.1234 +
  1.1235 +    ValueType& PushDefault()
  1.1236 +    {
  1.1237 +        Data.PushBack(ValueType());
  1.1238 +        return Back();
  1.1239 +    }
  1.1240 +
  1.1241 +    ValueType Pop()
  1.1242 +    {
  1.1243 +        ValueType t = Back();
  1.1244 +        PopBack();
  1.1245 +        return t;
  1.1246 +    }
  1.1247 +
  1.1248 +
  1.1249 +    // Access the first element.
  1.1250 +    ValueType&          Front()         { return At(0); }
  1.1251 +    const ValueType&    Front() const   { return At(0); }
  1.1252 +
  1.1253 +    // Access the last element.
  1.1254 +    ValueType&          Back()          { return At(Data.Size - 1); }
  1.1255 +    const ValueType&    Back() const    { return At(Data.Size - 1); }
  1.1256 +
  1.1257 +    // Array copy.  Copies the contents of a into this array.
  1.1258 +    const SelfType& operator = (const SelfType& a)   
  1.1259 +    {
  1.1260 +        Resize(a.GetSize());
  1.1261 +        for (UPInt i = 0; i < Data.Size; i++) {
  1.1262 +            *(Data.Data + i) = a[i];
  1.1263 +        }
  1.1264 +        return *this;
  1.1265 +    }
  1.1266 +
  1.1267 +    // Removing multiple elements from the array.
  1.1268 +    void    RemoveMultipleAt(UPInt index, UPInt num)
  1.1269 +    {
  1.1270 +        OVR_ASSERT(index + num <= Data.Size);
  1.1271 +        if (Data.Size == num)
  1.1272 +        {
  1.1273 +            Clear();
  1.1274 +        }
  1.1275 +        else
  1.1276 +        {
  1.1277 +            AllocatorType::DestructArray(Data.Data + index, num);
  1.1278 +            AllocatorType::CopyArrayForward(
  1.1279 +                Data.Data + index, 
  1.1280 +                Data.Data + index + num,
  1.1281 +                Data.Size - num - index);
  1.1282 +            Data.Size -= num;
  1.1283 +        }
  1.1284 +    }
  1.1285 +
  1.1286 +    // Removing an element from the array is an expensive operation!
  1.1287 +    // It compacts only after removing the last element.
  1.1288 +    void    RemoveAt(UPInt index)
  1.1289 +    {
  1.1290 +        OVR_ASSERT(index < Data.Size);
  1.1291 +        if (Data.Size == 1)
  1.1292 +        {
  1.1293 +            Clear();
  1.1294 +        }
  1.1295 +        else
  1.1296 +        {
  1.1297 +            AllocatorType::Destruct(Data.Data + index);
  1.1298 +            AllocatorType::CopyArrayForward(
  1.1299 +                Data.Data + index, 
  1.1300 +                Data.Data + index + 1,
  1.1301 +                Data.Size - 1 - index);
  1.1302 +            --Data.Size;
  1.1303 +        }
  1.1304 +    }
  1.1305 +
  1.1306 +    // Insert the given object at the given index shifting all the elements up.
  1.1307 +    void    InsertAt(UPInt index, const ValueType& val = ValueType())
  1.1308 +    {
  1.1309 +        OVR_ASSERT(index <= Data.Size);
  1.1310 +
  1.1311 +        Data.Resize(Data.Size + 1);
  1.1312 +        if (index < Data.Size - 1)
  1.1313 +        {
  1.1314 +            AllocatorType::CopyArrayBackward(
  1.1315 +                Data.Data + index + 1, 
  1.1316 +                Data.Data + index, 
  1.1317 +                Data.Size - 1 - index);
  1.1318 +        }
  1.1319 +        AllocatorType::Construct(Data.Data + index, val);
  1.1320 +    }
  1.1321 +
  1.1322 +    // Insert the given object at the given index shifting all the elements up.
  1.1323 +    void    InsertMultipleAt(UPInt index, UPInt num, const ValueType& val = ValueType())
  1.1324 +    {
  1.1325 +        OVR_ASSERT(index <= Data.Size);
  1.1326 +
  1.1327 +        Data.Resize(Data.Size + num);
  1.1328 +        if (index < Data.Size - num)
  1.1329 +        {
  1.1330 +            AllocatorType::CopyArrayBackward(
  1.1331 +                Data.Data + index + num,
  1.1332 +                Data.Data + index,
  1.1333 +                Data.Size - num - index);
  1.1334 +        }
  1.1335 +        for (UPInt i = 0; i < num; ++i)
  1.1336 +            AllocatorType::Construct(Data.Data + index + i, val);
  1.1337 +    }
  1.1338 +
  1.1339 +    // Append the given data to the array.
  1.1340 +    void    Append(const SelfType& other)
  1.1341 +    {
  1.1342 +        Append(other.Data.Data, other.GetSize());
  1.1343 +    }
  1.1344 +
  1.1345 +    // Append the given data to the array.
  1.1346 +    void    Append(const ValueType other[], UPInt count)
  1.1347 +    {
  1.1348 +        Data.Append(other, count);
  1.1349 +    }
  1.1350 +
  1.1351 +    class Iterator
  1.1352 +    {
  1.1353 +        SelfType*       pArray;
  1.1354 +        SPInt           CurIndex;
  1.1355 +
  1.1356 +    public:
  1.1357 +        Iterator() : pArray(0), CurIndex(-1) {}
  1.1358 +        Iterator(SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
  1.1359 +
  1.1360 +        bool operator==(const Iterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
  1.1361 +        bool operator!=(const Iterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
  1.1362 +
  1.1363 +        Iterator& operator++()
  1.1364 +        {
  1.1365 +            if (pArray)
  1.1366 +            {
  1.1367 +                if (CurIndex < (SPInt)pArray->GetSize())
  1.1368 +                    ++CurIndex;
  1.1369 +            }
  1.1370 +            return *this;
  1.1371 +        }
  1.1372 +        Iterator operator++(int)
  1.1373 +        {
  1.1374 +            Iterator it(*this);
  1.1375 +            operator++();
  1.1376 +            return it;
  1.1377 +        }
  1.1378 +        Iterator& operator--()
  1.1379 +        {
  1.1380 +            if (pArray)
  1.1381 +            {
  1.1382 +                if (CurIndex >= 0)
  1.1383 +                    --CurIndex;
  1.1384 +            }
  1.1385 +            return *this;
  1.1386 +        }
  1.1387 +        Iterator operator--(int)
  1.1388 +        {
  1.1389 +            Iterator it(*this);
  1.1390 +            operator--();
  1.1391 +            return it;
  1.1392 +        }
  1.1393 +        Iterator operator+(int delta) const
  1.1394 +        {
  1.1395 +            return Iterator(pArray, CurIndex + delta);
  1.1396 +        }
  1.1397 +        Iterator operator-(int delta) const
  1.1398 +        {
  1.1399 +            return Iterator(pArray, CurIndex - delta);
  1.1400 +        }
  1.1401 +        SPInt operator-(const Iterator& right) const
  1.1402 +        {
  1.1403 +            OVR_ASSERT(pArray == right.pArray);
  1.1404 +            return CurIndex - right.CurIndex;
  1.1405 +        }
  1.1406 +        ValueType& operator*() const    { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
  1.1407 +        ValueType* operator->() const   { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
  1.1408 +        ValueType* GetPtr() const       { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
  1.1409 +
  1.1410 +        bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
  1.1411 +
  1.1412 +        void Remove()
  1.1413 +        {
  1.1414 +            if (!IsFinished())
  1.1415 +                pArray->RemoveAt(CurIndex);
  1.1416 +        }
  1.1417 +
  1.1418 +        SPInt GetIndex() const { return CurIndex; }
  1.1419 +    };
  1.1420 +
  1.1421 +    Iterator Begin() { return Iterator(this); }
  1.1422 +    Iterator End()   { return Iterator(this, (SPInt)GetSize()); }
  1.1423 +    Iterator Last()  { return Iterator(this, (SPInt)GetSize() - 1); }
  1.1424 +
  1.1425 +    class ConstIterator
  1.1426 +    {
  1.1427 +        const SelfType* pArray;
  1.1428 +        SPInt           CurIndex;
  1.1429 +
  1.1430 +    public:
  1.1431 +        ConstIterator() : pArray(0), CurIndex(-1) {}
  1.1432 +        ConstIterator(const SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
  1.1433 +
  1.1434 +        bool operator==(const ConstIterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
  1.1435 +        bool operator!=(const ConstIterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
  1.1436 +
  1.1437 +        ConstIterator& operator++()
  1.1438 +        {
  1.1439 +            if (pArray)
  1.1440 +            {
  1.1441 +                if (CurIndex < (int)pArray->GetSize())
  1.1442 +                    ++CurIndex;
  1.1443 +            }
  1.1444 +            return *this;
  1.1445 +        }
  1.1446 +        ConstIterator operator++(int)
  1.1447 +        {
  1.1448 +            ConstIterator it(*this);
  1.1449 +            operator++();
  1.1450 +            return it;
  1.1451 +        }
  1.1452 +        ConstIterator& operator--()
  1.1453 +        {
  1.1454 +            if (pArray)
  1.1455 +            {
  1.1456 +                if (CurIndex >= 0)
  1.1457 +                    --CurIndex;
  1.1458 +            }
  1.1459 +            return *this;
  1.1460 +        }
  1.1461 +        ConstIterator operator--(int)
  1.1462 +        {
  1.1463 +            ConstIterator it(*this);
  1.1464 +            operator--();
  1.1465 +            return it;
  1.1466 +        }
  1.1467 +        ConstIterator operator+(int delta) const
  1.1468 +        {
  1.1469 +            return ConstIterator(pArray, CurIndex + delta);
  1.1470 +        }
  1.1471 +        ConstIterator operator-(int delta) const
  1.1472 +        {
  1.1473 +            return ConstIterator(pArray, CurIndex - delta);
  1.1474 +        }
  1.1475 +        SPInt operator-(const ConstIterator& right) const
  1.1476 +        {
  1.1477 +            OVR_ASSERT(pArray == right.pArray);
  1.1478 +            return CurIndex - right.CurIndex;
  1.1479 +        }
  1.1480 +        const ValueType& operator*() const  { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
  1.1481 +        const ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
  1.1482 +        const ValueType* GetPtr() const     { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
  1.1483 +
  1.1484 +        bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
  1.1485 +
  1.1486 +        SPInt GetIndex()  const { return CurIndex; }
  1.1487 +    };
  1.1488 +    ConstIterator Begin() const { return ConstIterator(this); }
  1.1489 +    ConstIterator End() const   { return ConstIterator(this, (SPInt)GetSize()); }
  1.1490 +    ConstIterator Last() const  { return ConstIterator(this, (SPInt)GetSize() - 1); }
  1.1491 +
  1.1492 +protected:
  1.1493 +    ArrayData   Data;
  1.1494 +};
  1.1495 +
  1.1496 +
  1.1497 +
  1.1498 +//-----------------------------------------------------------------------------------
  1.1499 +// ***** Array
  1.1500 +//
  1.1501 +// General purpose array for movable objects that require explicit 
  1.1502 +// construction/destruction.
  1.1503 +template<class T, class SizePolicy=ArrayDefaultPolicy>
  1.1504 +class Array : public ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> >
  1.1505 +{
  1.1506 +public:
  1.1507 +    typedef T                                                           ValueType;
  1.1508 +    typedef ContainerAllocator<T>                                       AllocatorType;
  1.1509 +    typedef SizePolicy                                                  SizePolicyType;
  1.1510 +    typedef Array<T, SizePolicy>                                        SelfType;
  1.1511 +    typedef ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> > BaseType;
  1.1512 +
  1.1513 +    Array() : BaseType() {}
  1.1514 +    Array(int size) : BaseType(size) {}
  1.1515 +    Array(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
  1.1516 +    Array(const SelfType& a) : BaseType(a) {}
  1.1517 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
  1.1518 +};
  1.1519 +
  1.1520 +// ***** ArrayPOD
  1.1521 +//
  1.1522 +// General purpose array for movable objects that DOES NOT require  
  1.1523 +// construction/destruction. Constructors and destructors are not called! 
  1.1524 +// Global heap is in use.
  1.1525 +template<class T, class SizePolicy=ArrayDefaultPolicy>
  1.1526 +class ArrayPOD : public ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> >
  1.1527 +{
  1.1528 +public:
  1.1529 +    typedef T                                                               ValueType;
  1.1530 +    typedef ContainerAllocator_POD<T>                                       AllocatorType;
  1.1531 +    typedef SizePolicy                                                      SizePolicyType;
  1.1532 +    typedef ArrayPOD<T, SizePolicy>                                         SelfType;
  1.1533 +    typedef ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> > BaseType;
  1.1534 +
  1.1535 +    ArrayPOD() : BaseType() {}
  1.1536 +    ArrayPOD(int size) : BaseType(size) {}
  1.1537 +    ArrayPOD(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
  1.1538 +    ArrayPOD(const SelfType& a) : BaseType(a) {}
  1.1539 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
  1.1540 +};
  1.1541 +
  1.1542 +
  1.1543 +// ***** ArrayCPP
  1.1544 +//
  1.1545 +// General purpose, fully C++ compliant array. Can be used with non-movable data.
  1.1546 +// Global heap is in use.
  1.1547 +template<class T, class SizePolicy=ArrayDefaultPolicy>
  1.1548 +class ArrayCPP : public ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> >
  1.1549 +{
  1.1550 +public:
  1.1551 +    typedef T                                                               ValueType;
  1.1552 +    typedef ContainerAllocator_CPP<T>                                       AllocatorType;
  1.1553 +    typedef SizePolicy                                                      SizePolicyType;
  1.1554 +    typedef ArrayCPP<T, SizePolicy>                                         SelfType;
  1.1555 +    typedef ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> > BaseType;
  1.1556 +
  1.1557 +    ArrayCPP() : BaseType() {}
  1.1558 +    ArrayCPP(int size) : BaseType(size) {}
  1.1559 +    ArrayCPP(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
  1.1560 +    ArrayCPP(const SelfType& a) : BaseType(a) {}
  1.1561 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
  1.1562 +};
  1.1563 +
  1.1564 +
  1.1565 +// ***** ArrayCC
  1.1566 +//
  1.1567 +// A modification of the array that uses the given default value to
  1.1568 +// construct the elements. The constructors and destructors are 
  1.1569 +// properly called, the objects must be movable.
  1.1570 +
  1.1571 +template<class T, class SizePolicy=ArrayDefaultPolicy>
  1.1572 +class ArrayCC : public ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >
  1.1573 +{
  1.1574 +public:
  1.1575 +    typedef T                                                               ValueType;
  1.1576 +    typedef ContainerAllocator<T>                                           AllocatorType;
  1.1577 +    typedef SizePolicy                                                      SizePolicyType;
  1.1578 +    typedef ArrayCC<T, SizePolicy>                                          SelfType;
  1.1579 +    typedef ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >   BaseType;
  1.1580 +
  1.1581 +    ArrayCC(const ValueType& defval) : BaseType(defval) {}
  1.1582 +    ArrayCC(const ValueType& defval, int size) : BaseType(defval, size) {}
  1.1583 +    ArrayCC(const ValueType& defval, const SizePolicyType& p) : BaseType(defval) { SetSizePolicy(p); }
  1.1584 +    ArrayCC(const SelfType& a) : BaseType(a) {}
  1.1585 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
  1.1586 +};
  1.1587 +
  1.1588 +} // OVR
  1.1589 +
  1.1590 +#endif