1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/LibOVR/Src/Kernel/OVR_Array.h	Wed Jan 14 06:51:16 2015 +0200
     1.3 @@ -0,0 +1,837 @@
     1.4 +/************************************************************************************
     1.5 +
     1.6 +PublicHeader:   OVR_Kernel.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 2014 Oculus VR, LLC All Rights reserved.
    1.13 +
    1.14 +Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
    1.15 +you may not use the Oculus VR Rift SDK except in compliance with the License, 
    1.16 +which is provided at the time of installation or download, or which 
    1.17 +otherwise accompanies this software in either electronic or hard copy form.
    1.18 +
    1.19 +You may obtain a copy of the License at
    1.20 +
    1.21 +http://www.oculusvr.com/licenses/LICENSE-3.2 
    1.22 +
    1.23 +Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
    1.24 +distributed under the License is distributed on an "AS IS" BASIS,
    1.25 +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    1.26 +See the License for the specific language governing permissions and
    1.27 +limitations under the License.
    1.28 +
    1.29 +************************************************************************************/
    1.30 +
    1.31 +#ifndef OVR_Array_h
    1.32 +#define OVR_Array_h
    1.33 +
    1.34 +#include "OVR_ContainerAllocator.h"
    1.35 +
    1.36 +namespace OVR {
    1.37 +
    1.38 +//-----------------------------------------------------------------------------------
    1.39 +// ***** ArrayDefaultPolicy
    1.40 +//
    1.41 +// Default resize behavior. No minimal capacity, Granularity=4, 
    1.42 +// Shrinking as needed. ArrayConstPolicy actually is the same as 
    1.43 +// ArrayDefaultPolicy, but parametrized with constants. 
    1.44 +// This struct is used only in order to reduce the template "matroska".
    1.45 +struct ArrayDefaultPolicy
    1.46 +{
    1.47 +    ArrayDefaultPolicy() : Capacity(0) {}
    1.48 +    ArrayDefaultPolicy(const ArrayDefaultPolicy&) : Capacity(0) {}
    1.49 +
    1.50 +    size_t GetMinCapacity() const { return 0; }
    1.51 +    size_t GetGranularity() const { return 4; }
    1.52 +    bool  NeverShrinking() const { return 0; }
    1.53 +
    1.54 +    size_t GetCapacity()    const      { return Capacity; }
    1.55 +    void  SetCapacity(size_t capacity) { Capacity = capacity; }
    1.56 +private:
    1.57 +    size_t Capacity;
    1.58 +};
    1.59 +
    1.60 +
    1.61 +//-----------------------------------------------------------------------------------
    1.62 +// ***** ArrayConstPolicy
    1.63 +//
    1.64 +// Statically parametrized resizing behavior:
    1.65 +// MinCapacity, Granularity, and Shrinking flag.
    1.66 +template<int MinCapacity=0, int Granularity=4, bool NeverShrink=false>
    1.67 +struct ArrayConstPolicy
    1.68 +{
    1.69 +    typedef ArrayConstPolicy<MinCapacity, Granularity, NeverShrink> SelfType;
    1.70 +
    1.71 +    ArrayConstPolicy() : Capacity(0) {}
    1.72 +    ArrayConstPolicy(const SelfType&) : Capacity(0) {}
    1.73 +
    1.74 +    size_t GetMinCapacity() const { return MinCapacity; }
    1.75 +    size_t GetGranularity() const { return Granularity; }
    1.76 +    bool  NeverShrinking() const { return NeverShrink; }
    1.77 +
    1.78 +    size_t GetCapacity()    const      { return Capacity; }
    1.79 +    void  SetCapacity(size_t capacity) { Capacity = capacity; }
    1.80 +private:
    1.81 +    size_t Capacity;
    1.82 +};
    1.83 +
    1.84 +//-----------------------------------------------------------------------------------
    1.85 +// ***** ArrayDataBase
    1.86 +//
    1.87 +// Basic operations with array data: Reserve, Resize, Free, ArrayPolicy.
    1.88 +// For internal use only: ArrayData,ArrayDataCC and others.
    1.89 +template<class T, class Allocator, class SizePolicy>
    1.90 +struct ArrayDataBase
    1.91 +{
    1.92 +    typedef T                                           ValueType;
    1.93 +    typedef Allocator                                   AllocatorType;
    1.94 +    typedef SizePolicy                                  SizePolicyType;
    1.95 +    typedef ArrayDataBase<T, Allocator, SizePolicy>     SelfType;
    1.96 +
    1.97 +    ArrayDataBase()
    1.98 +        : Data(0), Size(0), Policy() {}
    1.99 +
   1.100 +    ArrayDataBase(const SizePolicy& p)
   1.101 +        : Data(0), Size(0), Policy(p) {}
   1.102 +
   1.103 +    ~ArrayDataBase() 
   1.104 +    {
   1.105 +        Allocator::DestructArray(Data, Size);
   1.106 +        Allocator::Free(Data);
   1.107 +    }
   1.108 +
   1.109 +    size_t GetCapacity() const 
   1.110 +    { 
   1.111 +        return Policy.GetCapacity(); 
   1.112 +    }
   1.113 +
   1.114 +    void ClearAndRelease()
   1.115 +    {
   1.116 +        Allocator::DestructArray(Data, Size);
   1.117 +        Allocator::Free(Data);
   1.118 +        Data = 0;
   1.119 +        Size = 0;
   1.120 +        Policy.SetCapacity(0);
   1.121 +    }
   1.122 +
   1.123 +    void Reserve(size_t newCapacity)
   1.124 +    {
   1.125 +        if (Policy.NeverShrinking() && newCapacity < GetCapacity())
   1.126 +            return;
   1.127 +
   1.128 +        if (newCapacity < Policy.GetMinCapacity())
   1.129 +            newCapacity = Policy.GetMinCapacity();
   1.130 +
   1.131 +        // Resize the buffer.
   1.132 +        if (newCapacity == 0)
   1.133 +        {
   1.134 +            if (Data)
   1.135 +            {
   1.136 +                Allocator::Free(Data);
   1.137 +                Data = 0;
   1.138 +            }
   1.139 +            Policy.SetCapacity(0);
   1.140 +        }
   1.141 +        else
   1.142 +        {
   1.143 +            size_t gran = Policy.GetGranularity();
   1.144 +            newCapacity = (newCapacity + gran - 1) / gran * gran;
   1.145 +            if (Data)
   1.146 +            {
   1.147 +                if (Allocator::IsMovable())
   1.148 +                {
   1.149 +                    Data = (T*)Allocator::Realloc(Data, sizeof(T) * newCapacity);
   1.150 +                }
   1.151 +                else
   1.152 +                {
   1.153 +                    T* newData = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
   1.154 +                    size_t i, s;
   1.155 +                    s = (Size < newCapacity) ? Size : newCapacity;
   1.156 +                    for (i = 0; i < s; ++i)
   1.157 +                    {
   1.158 +                        Allocator::Construct(&newData[i], Data[i]);
   1.159 +                        Allocator::Destruct(&Data[i]);
   1.160 +                    }
   1.161 +                    for (i = s; i < Size; ++i)
   1.162 +                    {
   1.163 +                        Allocator::Destruct(&Data[i]);
   1.164 +                    }
   1.165 +                    Allocator::Free(Data);
   1.166 +                    Data = newData;
   1.167 +                }
   1.168 +            }
   1.169 +            else
   1.170 +            {
   1.171 +                Data = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
   1.172 +                //memset(Buffer, 0, (sizeof(ValueType) * newSize)); // Do we need this?
   1.173 +            }
   1.174 +            Policy.SetCapacity(newCapacity);
   1.175 +            // OVR_ASSERT(Data); // need to throw (or something) on alloc failure!
   1.176 +        }
   1.177 +    }
   1.178 +
   1.179 +    // This version of Resize DOES NOT construct the elements.
   1.180 +    // It's done to optimize PushBack, which uses a copy constructor 
   1.181 +    // instead of the default constructor and assignment
   1.182 +    void ResizeNoConstruct(size_t newSize)
   1.183 +    {
   1.184 +        size_t oldSize = Size;
   1.185 +
   1.186 +        if (newSize < oldSize)
   1.187 +        {
   1.188 +            Allocator::DestructArray(Data + newSize, oldSize - newSize);
   1.189 +            if (newSize < (Policy.GetCapacity() >> 1))
   1.190 +            {
   1.191 +                Reserve(newSize);
   1.192 +            }
   1.193 +        }
   1.194 +        else if(newSize >= Policy.GetCapacity())
   1.195 +        {
   1.196 +            Reserve(newSize + (newSize >> 2));
   1.197 +        }
   1.198 +        //! IMPORTANT to modify Size only after Reserve completes, because garbage collectable
   1.199 +        // array may use this array and may traverse it during Reserve (in the case, if 
   1.200 +        // collection occurs because of heap limit exceeded).
   1.201 +        Size = newSize;
   1.202 +    }
   1.203 +
   1.204 +    ValueType*  Data;
   1.205 +    size_t      Size;
   1.206 +    SizePolicy  Policy;
   1.207 +};
   1.208 +
   1.209 +
   1.210 +
   1.211 +//-----------------------------------------------------------------------------------
   1.212 +// ***** ArrayData
   1.213 +//
   1.214 +// General purpose array data.
   1.215 +// For internal use only in Array, ArrayLH, ArrayPOD and so on.
   1.216 +template<class T, class Allocator, class SizePolicy>
   1.217 +struct ArrayData : ArrayDataBase<T, Allocator, SizePolicy>
   1.218 +{
   1.219 +    typedef T ValueType;
   1.220 +    typedef Allocator                                   AllocatorType;
   1.221 +    typedef SizePolicy                                  SizePolicyType;
   1.222 +    typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
   1.223 +    typedef ArrayData    <T, Allocator, SizePolicy>     SelfType;
   1.224 +
   1.225 +    ArrayData()
   1.226 +        : BaseType() { }
   1.227 +
   1.228 +    ArrayData(size_t size)
   1.229 +        : BaseType() { Resize(size); }
   1.230 +
   1.231 +    ArrayData(const SelfType& a)
   1.232 +        : BaseType(a.Policy) { Append(a.Data, a.Size); }
   1.233 +
   1.234 +
   1.235 +    void Resize(size_t newSize)
   1.236 +    {
   1.237 +        size_t oldSize = this->Size;
   1.238 +        BaseType::ResizeNoConstruct(newSize);
   1.239 +        if(newSize > oldSize)
   1.240 +            Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize);
   1.241 +    }
   1.242 +
   1.243 +    void PushBack(const ValueType& val)
   1.244 +    {
   1.245 +        BaseType::ResizeNoConstruct(this->Size + 1);
   1.246 +        OVR_ASSERT(this->Data != NULL);
   1.247 +        Allocator::Construct(this->Data + this->Size - 1, val);
   1.248 +    }
   1.249 +
   1.250 +    template<class S>
   1.251 +    void PushBackAlt(const S& val)
   1.252 +    {
   1.253 +        BaseType::ResizeNoConstruct(this->Size + 1);
   1.254 +        Allocator::ConstructAlt(this->Data + this->Size - 1, val);
   1.255 +    }
   1.256 +
   1.257 +    // Append the given data to the array.
   1.258 +    void Append(const ValueType other[], size_t count)
   1.259 +    {
   1.260 +        if (count)
   1.261 +        {
   1.262 +            size_t oldSize = this->Size;
   1.263 +            BaseType::ResizeNoConstruct(this->Size + count);
   1.264 +            Allocator::ConstructArray(this->Data + oldSize, count, other);
   1.265 +        }
   1.266 +    }
   1.267 +};
   1.268 +
   1.269 +
   1.270 +
   1.271 +//-----------------------------------------------------------------------------------
   1.272 +// ***** ArrayDataCC
   1.273 +//
   1.274 +// A modification of ArrayData that always copy-constructs new elements
   1.275 +// using a specified DefaultValue. For internal use only in ArrayCC.
   1.276 +template<class T, class Allocator, class SizePolicy>
   1.277 +struct ArrayDataCC : ArrayDataBase<T, Allocator, SizePolicy>
   1.278 +{
   1.279 +    typedef T                                           ValueType;
   1.280 +    typedef Allocator                                   AllocatorType;
   1.281 +    typedef SizePolicy                                  SizePolicyType;
   1.282 +    typedef ArrayDataBase<T, Allocator, SizePolicy>     BaseType;
   1.283 +    typedef ArrayDataCC  <T, Allocator, SizePolicy>     SelfType;
   1.284 +
   1.285 +    ArrayDataCC(const ValueType& defval)
   1.286 +        : BaseType(), DefaultValue(defval) { }
   1.287 +
   1.288 +    ArrayDataCC(const ValueType& defval, size_t size)
   1.289 +        : BaseType(), DefaultValue(defval) { Resize(size); }
   1.290 +
   1.291 +    ArrayDataCC(const SelfType& a)
   1.292 +        : BaseType(a.Policy), DefaultValue(a.DefaultValue) { Append(a.Data, a.Size); }
   1.293 +
   1.294 +
   1.295 +    void Resize(size_t newSize)
   1.296 +    {
   1.297 +        size_t oldSize = this->Size;
   1.298 +        BaseType::ResizeNoConstruct(newSize);
   1.299 +        if(newSize > oldSize)
   1.300 +            Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize, DefaultValue);
   1.301 +    }
   1.302 +
   1.303 +    void PushBack(const ValueType& val)
   1.304 +    {
   1.305 +        BaseType::ResizeNoConstruct(this->Size + 1);
   1.306 +        Allocator::Construct(this->Data + this->Size - 1, val);
   1.307 +    }
   1.308 +
   1.309 +    template<class S>
   1.310 +    void PushBackAlt(const S& val)
   1.311 +    {
   1.312 +        BaseType::ResizeNoConstruct(this->Size + 1);
   1.313 +        Allocator::ConstructAlt(this->Data + this->Size - 1, val);
   1.314 +    }
   1.315 +
   1.316 +    // Append the given data to the array.
   1.317 +    void Append(const ValueType other[], size_t count)
   1.318 +    {
   1.319 +        if (count)
   1.320 +        {
   1.321 +            size_t oldSize = this->Size;
   1.322 +            BaseType::ResizeNoConstruct(this->Size + count);
   1.323 +            Allocator::ConstructArray(this->Data + oldSize, count, other);
   1.324 +        }
   1.325 +    }
   1.326 +
   1.327 +    ValueType   DefaultValue;
   1.328 +};
   1.329 +
   1.330 +
   1.331 +
   1.332 +
   1.333 +
   1.334 +//-----------------------------------------------------------------------------------
   1.335 +// ***** ArrayBase
   1.336 +//
   1.337 +// Resizable array. The behavior can be POD (suffix _POD) and 
   1.338 +// Movable (no suffix) depending on the allocator policy.
   1.339 +// In case of _POD the constructors and destructors are not called.
   1.340 +// 
   1.341 +// Arrays can't handle non-movable objects! Don't put anything in here 
   1.342 +// that can't be moved around by bitwise copy. 
   1.343 +// 
   1.344 +// The addresses of elements are not persistent! Don't keep the address 
   1.345 +// of an element; the array contents will move around as it gets resized.
   1.346 +template<class ArrayData>
   1.347 +class ArrayBase
   1.348 +{
   1.349 +public:
   1.350 +    typedef typename ArrayData::ValueType       ValueType;
   1.351 +    typedef typename ArrayData::AllocatorType   AllocatorType;
   1.352 +    typedef typename ArrayData::SizePolicyType  SizePolicyType;
   1.353 +    typedef ArrayBase<ArrayData>                SelfType;
   1.354 +
   1.355 +
   1.356 +#undef new
   1.357 +    OVR_MEMORY_REDEFINE_NEW(ArrayBase)
   1.358 +// Redefine operator 'new' if necessary.
   1.359 +#if defined(OVR_DEFINE_NEW)
   1.360 +#define new OVR_DEFINE_NEW
   1.361 +#endif
   1.362 +
   1.363 +
   1.364 +    ArrayBase()
   1.365 +        : Data() {}
   1.366 +    ArrayBase(size_t size)
   1.367 +        : Data(size) {}
   1.368 +    ArrayBase(const SelfType& a)
   1.369 +        : Data(a.Data) {}
   1.370 +
   1.371 +    ArrayBase(const ValueType& defval)
   1.372 +        : Data(defval) {}
   1.373 +    ArrayBase(const ValueType& defval, size_t size)
   1.374 +        : Data(defval, size) {}
   1.375 +  
   1.376 +    SizePolicyType* GetSizePolicy() const                  { return Data.Policy; }
   1.377 +    void            SetSizePolicy(const SizePolicyType& p) { Data.Policy = p; }
   1.378 +
   1.379 +    bool    NeverShrinking()const       { return Data.Policy.NeverShrinking(); }
   1.380 +	size_t  GetSize()       const       { return Data.Size; }
   1.381 +	int     GetSizeI()      const       { return (int)Data.Size; }
   1.382 +	bool    IsEmpty()       const       { return Data.Size == 0; }
   1.383 +    size_t  GetCapacity()   const       { return Data.GetCapacity(); }
   1.384 +    size_t  GetNumBytes()   const       { return Data.GetCapacity() * sizeof(ValueType); }
   1.385 +
   1.386 +    void    ClearAndRelease()           { Data.ClearAndRelease(); }
   1.387 +    void    Clear()                     { Data.Resize(0); }
   1.388 +    void    Resize(size_t newSize)       { Data.Resize(newSize); }
   1.389 +
   1.390 +    // Reserve can only increase the capacity
   1.391 +    void    Reserve(size_t newCapacity)  
   1.392 +    { 
   1.393 +        if (newCapacity > Data.GetCapacity())
   1.394 +            Data.Reserve(newCapacity); 
   1.395 +    }
   1.396 +
   1.397 +    // Basic access.
   1.398 +    ValueType& At(size_t index)
   1.399 +    {
   1.400 +        OVR_ASSERT((Data.Data) && (index < Data.Size)); // Asserting that Data.Data is valid helps static analysis tools.
   1.401 +        return Data.Data[index];
   1.402 +    }
   1.403 +    const ValueType& At(size_t index) const
   1.404 +    {
   1.405 +        OVR_ASSERT((Data.Data) && (index < Data.Size));
   1.406 +        return Data.Data[index];
   1.407 +    }
   1.408 +
   1.409 +    ValueType ValueAt(size_t index) const
   1.410 +    {
   1.411 +        OVR_ASSERT((Data.Data) && (index < Data.Size));
   1.412 +        return Data.Data[index];
   1.413 +    }
   1.414 +
   1.415 +    // Basic access.
   1.416 +    ValueType& operator [] (size_t index)
   1.417 +    {
   1.418 +        OVR_ASSERT((Data.Data) && (index < Data.Size));
   1.419 +        return Data.Data[index]; 
   1.420 +    }
   1.421 +    const ValueType& operator [] (size_t index) const
   1.422 +    {
   1.423 +        OVR_ASSERT((Data.Data) && (index < Data.Size));
   1.424 +        return Data.Data[index];
   1.425 +    }
   1.426 +
   1.427 +    // Raw pointer to the data. Use with caution!
   1.428 +    const ValueType* GetDataPtr() const { return Data.Data; }
   1.429 +          ValueType* GetDataPtr()       { return Data.Data; }
   1.430 +
   1.431 +    // Insert the given element at the end of the array.
   1.432 +    void    PushBack(const ValueType& val)
   1.433 +    {
   1.434 +        // DO NOT pass elements of your own vector into
   1.435 +        // push_back()!  Since we're using references,
   1.436 +        // resize() may munge the element storage!
   1.437 +        // OVR_ASSERT(&val < &Buffer[0] || &val > &Buffer[BufferSize]);
   1.438 +        Data.PushBack(val);
   1.439 +    }
   1.440 +
   1.441 +    template<class S>
   1.442 +    void PushBackAlt(const S& val)
   1.443 +    {
   1.444 +        Data.PushBackAlt(val);
   1.445 +    }
   1.446 +
   1.447 +    // Remove the last element.
   1.448 +    void    PopBack(size_t count = 1)
   1.449 +    {
   1.450 +        OVR_ASSERT(Data.Size >= count);
   1.451 +        Data.Resize(Data.Size - count);
   1.452 +    }
   1.453 +
   1.454 +    ValueType& PushDefault()
   1.455 +    {
   1.456 +        Data.PushBack(ValueType());
   1.457 +        return Back();
   1.458 +    }
   1.459 +
   1.460 +    ValueType Pop()
   1.461 +    {
   1.462 +        OVR_ASSERT((Data.Data) && (Data.Size > 0));
   1.463 +        ValueType t = Back();
   1.464 +        PopBack();
   1.465 +        return t;
   1.466 +    }
   1.467 +
   1.468 +
   1.469 +    // Access the first element.
   1.470 +    ValueType&          Front()         { return At(0); }
   1.471 +    const ValueType&    Front() const   { return At(0); }
   1.472 +
   1.473 +    // Access the last element.
   1.474 +    ValueType&          Back()          { return At(Data.Size - 1); }
   1.475 +    const ValueType&    Back() const    { return At(Data.Size - 1); }
   1.476 +
   1.477 +    // Array copy.  Copies the contents of a into this array.
   1.478 +    const SelfType& operator = (const SelfType& a)   
   1.479 +    {
   1.480 +        Resize(a.GetSize());
   1.481 +        OVR_ASSERT((Data.Data != NULL) || (Data.Size == 0));
   1.482 +        for (size_t i = 0; i < Data.Size; i++) {
   1.483 +            *(Data.Data + i) = a[i];
   1.484 +        }
   1.485 +        return *this;
   1.486 +    }
   1.487 +
   1.488 +    // Removing multiple elements from the array.
   1.489 +    void    RemoveMultipleAt(size_t index, size_t num)
   1.490 +    {
   1.491 +        OVR_ASSERT(index + num <= Data.Size);
   1.492 +        if (Data.Size == num)
   1.493 +        {
   1.494 +            Clear();
   1.495 +        }
   1.496 +        else
   1.497 +        {
   1.498 +            AllocatorType::DestructArray(Data.Data + index, num);
   1.499 +            AllocatorType::CopyArrayForward(
   1.500 +                Data.Data + index, 
   1.501 +                Data.Data + index + num,
   1.502 +                Data.Size - num - index);
   1.503 +            Data.Size -= num;
   1.504 +        }
   1.505 +    }
   1.506 +
   1.507 +    // Removing an element from the array is an expensive operation!
   1.508 +    // It compacts only after removing the last element.
   1.509 +    // If order of elements in the array is not important then use 
   1.510 +    // RemoveAtUnordered, that could be much faster than the regular
   1.511 +    // RemoveAt.
   1.512 +    void    RemoveAt(size_t index)
   1.513 +    {
   1.514 +        OVR_ASSERT((Data.Data) && (index < Data.Size));
   1.515 +        if (Data.Size == 1)
   1.516 +        {
   1.517 +            Clear();
   1.518 +        }
   1.519 +        else
   1.520 +        {
   1.521 +            AllocatorType::Destruct(Data.Data + index);
   1.522 +            AllocatorType::CopyArrayForward(
   1.523 +                Data.Data + index, 
   1.524 +                Data.Data + index + 1,
   1.525 +                Data.Size - 1 - index);
   1.526 +            --Data.Size;
   1.527 +        }
   1.528 +    }
   1.529 +
   1.530 +    // Removes an element from the array without respecting of original order of 
   1.531 +    // elements for better performance. Do not use on array where order of elements
   1.532 +    // is important, otherwise use it instead of regular RemoveAt().
   1.533 +    void    RemoveAtUnordered(size_t index)
   1.534 +    {
   1.535 +        OVR_ASSERT((Data.Data) && (index < Data.Size));
   1.536 +        if (Data.Size == 1)
   1.537 +        {
   1.538 +            Clear();
   1.539 +        }
   1.540 +        else
   1.541 +        {
   1.542 +            // copy the last element into the 'index' position 
   1.543 +            // and decrement the size (instead of moving all elements
   1.544 +            // in [index + 1 .. size - 1] range).
   1.545 +            const size_t lastElemIndex = Data.Size - 1;
   1.546 +            if (index < lastElemIndex)
   1.547 +            {
   1.548 +                AllocatorType::Destruct(Data.Data + index);
   1.549 +                AllocatorType::Construct(Data.Data + index, Data.Data[lastElemIndex]);
   1.550 +            }
   1.551 +            AllocatorType::Destruct(Data.Data + lastElemIndex);
   1.552 +            --Data.Size;
   1.553 +        }
   1.554 +    }
   1.555 +
   1.556 +    // Insert the given object at the given index shifting all the elements up.
   1.557 +    void    InsertAt(size_t index, const ValueType& val = ValueType())
   1.558 +    {
   1.559 +        OVR_ASSERT(index <= Data.Size);
   1.560 +
   1.561 +        Data.Resize(Data.Size + 1);
   1.562 +        if (index < Data.Size - 1)
   1.563 +        {
   1.564 +            AllocatorType::CopyArrayBackward(
   1.565 +                Data.Data + index + 1, 
   1.566 +                Data.Data + index, 
   1.567 +                Data.Size - 1 - index);
   1.568 +        }
   1.569 +        AllocatorType::Construct(Data.Data + index, val);
   1.570 +    }
   1.571 +
   1.572 +    // Insert the given object at the given index shifting all the elements up.
   1.573 +    void    InsertMultipleAt(size_t index, size_t num, const ValueType& val = ValueType())
   1.574 +    {
   1.575 +        OVR_ASSERT(index <= Data.Size);
   1.576 +
   1.577 +        Data.Resize(Data.Size + num);
   1.578 +        if (index < Data.Size - num)
   1.579 +        {
   1.580 +            AllocatorType::CopyArrayBackward(
   1.581 +                Data.Data + index + num,
   1.582 +                Data.Data + index,
   1.583 +                Data.Size - num - index);
   1.584 +        }
   1.585 +        for (size_t i = 0; i < num; ++i)
   1.586 +            AllocatorType::Construct(Data.Data + index + i, val);
   1.587 +    }
   1.588 +
   1.589 +    // Append the given data to the array.
   1.590 +    void    Append(const SelfType& other)
   1.591 +    {
   1.592 +        Append(other.Data.Data, other.GetSize());
   1.593 +    }
   1.594 +
   1.595 +    // Append the given data to the array.
   1.596 +    void    Append(const ValueType other[], size_t count)
   1.597 +    {
   1.598 +        Data.Append(other, count);
   1.599 +    }
   1.600 +
   1.601 +    class Iterator
   1.602 +    {
   1.603 +        SelfType*       pArray;
   1.604 +        intptr_t        CurIndex;
   1.605 +
   1.606 +    public:
   1.607 +        Iterator() : pArray(0), CurIndex(-1) {}
   1.608 +        Iterator(SelfType* parr, intptr_t idx = 0) : pArray(parr), CurIndex(idx) {}
   1.609 +
   1.610 +        bool operator==(const Iterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
   1.611 +        bool operator!=(const Iterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
   1.612 +
   1.613 +        Iterator& operator++()
   1.614 +        {
   1.615 +            if (pArray)
   1.616 +            {
   1.617 +                if (CurIndex < (intptr_t)pArray->GetSize())
   1.618 +                    ++CurIndex;
   1.619 +            }
   1.620 +            return *this;
   1.621 +        }
   1.622 +        Iterator operator++(int)
   1.623 +        {
   1.624 +            Iterator it(*this);
   1.625 +            operator++();
   1.626 +            return it;
   1.627 +        }
   1.628 +        Iterator& operator--()
   1.629 +        {
   1.630 +            if (pArray)
   1.631 +            {
   1.632 +                if (CurIndex >= 0)
   1.633 +                    --CurIndex;
   1.634 +            }
   1.635 +            return *this;
   1.636 +        }
   1.637 +        Iterator operator--(int)
   1.638 +        {
   1.639 +            Iterator it(*this);
   1.640 +            operator--();
   1.641 +            return it;
   1.642 +        }
   1.643 +        Iterator operator+(int delta) const
   1.644 +        {
   1.645 +            return Iterator(pArray, CurIndex + delta);
   1.646 +        }
   1.647 +        Iterator operator-(int delta) const
   1.648 +        {
   1.649 +            return Iterator(pArray, CurIndex - delta);
   1.650 +        }
   1.651 +        intptr_t operator-(const Iterator& right) const
   1.652 +        {
   1.653 +            OVR_ASSERT(pArray == right.pArray);
   1.654 +            return CurIndex - right.CurIndex;
   1.655 +        }
   1.656 +        ValueType& operator*() const    { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
   1.657 +        ValueType* operator->() const   { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.658 +        ValueType* GetPtr() const       { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.659 +
   1.660 +        bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
   1.661 +
   1.662 +        void Remove()
   1.663 +        {
   1.664 +            if (!IsFinished())
   1.665 +                pArray->RemoveAt(CurIndex);
   1.666 +        }
   1.667 +
   1.668 +        intptr_t GetIndex() const { return CurIndex; }
   1.669 +    };
   1.670 +
   1.671 +    Iterator Begin() { return Iterator(this); }
   1.672 +    Iterator End()   { return Iterator(this, (intptr_t)GetSize()); }
   1.673 +    Iterator Last()  { return Iterator(this, (intptr_t)GetSize() - 1); }
   1.674 +
   1.675 +    class ConstIterator
   1.676 +    {
   1.677 +        const SelfType* pArray;
   1.678 +        intptr_t        CurIndex;
   1.679 +
   1.680 +    public:
   1.681 +        ConstIterator() : pArray(0), CurIndex(-1) {}
   1.682 +        ConstIterator(const SelfType* parr, intptr_t idx = 0) : pArray(parr), CurIndex(idx) {}
   1.683 +
   1.684 +        bool operator==(const ConstIterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
   1.685 +        bool operator!=(const ConstIterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
   1.686 +
   1.687 +        ConstIterator& operator++()
   1.688 +        {
   1.689 +            if (pArray)
   1.690 +            {
   1.691 +                if (CurIndex < (int)pArray->GetSize())
   1.692 +                    ++CurIndex;
   1.693 +            }
   1.694 +            return *this;
   1.695 +        }
   1.696 +        ConstIterator operator++(int)
   1.697 +        {
   1.698 +            ConstIterator it(*this);
   1.699 +            operator++();
   1.700 +            return it;
   1.701 +        }
   1.702 +        ConstIterator& operator--()
   1.703 +        {
   1.704 +            if (pArray)
   1.705 +            {
   1.706 +                if (CurIndex >= 0)
   1.707 +                    --CurIndex;
   1.708 +            }
   1.709 +            return *this;
   1.710 +        }
   1.711 +        ConstIterator operator--(int)
   1.712 +        {
   1.713 +            ConstIterator it(*this);
   1.714 +            operator--();
   1.715 +            return it;
   1.716 +        }
   1.717 +        ConstIterator operator+(int delta) const
   1.718 +        {
   1.719 +            return ConstIterator(pArray, CurIndex + delta);
   1.720 +        }
   1.721 +        ConstIterator operator-(int delta) const
   1.722 +        {
   1.723 +            return ConstIterator(pArray, CurIndex - delta);
   1.724 +        }
   1.725 +        intptr_t operator-(const ConstIterator& right) const
   1.726 +        {
   1.727 +            OVR_ASSERT(pArray == right.pArray);
   1.728 +            return CurIndex - right.CurIndex;
   1.729 +        }
   1.730 +        const ValueType& operator*() const  { OVR_ASSERT(pArray); return  (*pArray)[CurIndex]; }
   1.731 +        const ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.732 +        const ValueType* GetPtr() const     { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
   1.733 +
   1.734 +        bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
   1.735 +
   1.736 +        intptr_t GetIndex()  const { return CurIndex; }
   1.737 +    };
   1.738 +    ConstIterator Begin() const { return ConstIterator(this); }
   1.739 +    ConstIterator End() const   { return ConstIterator(this, (intptr_t)GetSize()); }
   1.740 +    ConstIterator Last() const  { return ConstIterator(this, (intptr_t)GetSize() - 1); }
   1.741 +
   1.742 +protected:
   1.743 +    ArrayData   Data;
   1.744 +};
   1.745 +
   1.746 +
   1.747 +
   1.748 +//-----------------------------------------------------------------------------------
   1.749 +// ***** Array
   1.750 +//
   1.751 +// General purpose array for movable objects that require explicit 
   1.752 +// construction/destruction.
   1.753 +template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.754 +class Array : public ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> >
   1.755 +{
   1.756 +public:
   1.757 +    typedef T                                                           ValueType;
   1.758 +    typedef ContainerAllocator<T>                                       AllocatorType;
   1.759 +    typedef SizePolicy                                                  SizePolicyType;
   1.760 +    typedef Array<T, SizePolicy>                                        SelfType;
   1.761 +    typedef ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> > BaseType;
   1.762 +
   1.763 +    Array() : BaseType() {}
   1.764 +    Array(size_t size) : BaseType(size) {}
   1.765 +    Array(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
   1.766 +    Array(const SelfType& a) : BaseType(a) {}
   1.767 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.768 +};
   1.769 +
   1.770 +// ***** ArrayPOD
   1.771 +//
   1.772 +// General purpose array for movable objects that DOES NOT require  
   1.773 +// construction/destruction. Constructors and destructors are not called! 
   1.774 +// Global heap is in use.
   1.775 +template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.776 +class ArrayPOD : public ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> >
   1.777 +{
   1.778 +public:
   1.779 +    typedef T                                                               ValueType;
   1.780 +    typedef ContainerAllocator_POD<T>                                       AllocatorType;
   1.781 +    typedef SizePolicy                                                      SizePolicyType;
   1.782 +    typedef ArrayPOD<T, SizePolicy>                                         SelfType;
   1.783 +    typedef ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> > BaseType;
   1.784 +
   1.785 +    ArrayPOD() : BaseType() {}
   1.786 +    ArrayPOD(size_t size) : BaseType(size) {}
   1.787 +    ArrayPOD(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
   1.788 +    ArrayPOD(const SelfType& a) : BaseType(a) {}
   1.789 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.790 +};
   1.791 +
   1.792 +
   1.793 +// ***** ArrayCPP
   1.794 +//
   1.795 +// General purpose, fully C++ compliant array. Can be used with non-movable data.
   1.796 +// Global heap is in use.
   1.797 +template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.798 +class ArrayCPP : public ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> >
   1.799 +{
   1.800 +public:
   1.801 +    typedef T                                                               ValueType;
   1.802 +    typedef ContainerAllocator_CPP<T>                                       AllocatorType;
   1.803 +    typedef SizePolicy                                                      SizePolicyType;
   1.804 +    typedef ArrayCPP<T, SizePolicy>                                         SelfType;
   1.805 +    typedef ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> > BaseType;
   1.806 +
   1.807 +    ArrayCPP() : BaseType() {}
   1.808 +    ArrayCPP(size_t size) : BaseType(size) {}
   1.809 +    ArrayCPP(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
   1.810 +    ArrayCPP(const SelfType& a) : BaseType(a) {}
   1.811 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.812 +};
   1.813 +
   1.814 +
   1.815 +// ***** ArrayCC
   1.816 +//
   1.817 +// A modification of the array that uses the given default value to
   1.818 +// construct the elements. The constructors and destructors are 
   1.819 +// properly called, the objects must be movable.
   1.820 +
   1.821 +template<class T, class SizePolicy=ArrayDefaultPolicy>
   1.822 +class ArrayCC : public ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >
   1.823 +{
   1.824 +public:
   1.825 +    typedef T                                                               ValueType;
   1.826 +    typedef ContainerAllocator<T>                                           AllocatorType;
   1.827 +    typedef SizePolicy                                                      SizePolicyType;
   1.828 +    typedef ArrayCC<T, SizePolicy>                                          SelfType;
   1.829 +    typedef ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >   BaseType;
   1.830 +
   1.831 +    ArrayCC(const ValueType& defval) : BaseType(defval) {}
   1.832 +    ArrayCC(const ValueType& defval, size_t size) : BaseType(defval, size) {}
   1.833 +    ArrayCC(const ValueType& defval, const SizePolicyType& p) : BaseType(defval) { SetSizePolicy(p); }
   1.834 +    ArrayCC(const SelfType& a) : BaseType(a) {}
   1.835 +    const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
   1.836 +};
   1.837 +
   1.838 +} // OVR
   1.839 +
   1.840 +#endif