oculus1

annotate libovr/Src/Kernel/OVR_Array.h @ 24:8419d8a13cee

find changesets by author, revision, files, or words in the commit message
foo
author John Tsiombikas <nuclear@member.fsf.org>
date Fri, 04 Oct 2013 14:50:26 +0300
parents e2f9e4603129
children
rev   line source
nuclear@3 1 /************************************************************************************
nuclear@3 2
nuclear@3 3 PublicHeader: OVR.h
nuclear@3 4 Filename : OVR_Array.h
nuclear@3 5 Content : Template implementation for Array
nuclear@3 6 Created : September 19, 2012
nuclear@3 7 Notes :
nuclear@3 8
nuclear@3 9 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@3 10
nuclear@3 11 Use of this software is subject to the terms of the Oculus license
nuclear@3 12 agreement provided at the time of installation or download, or which
nuclear@3 13 otherwise accompanies this software in either electronic or hard copy form.
nuclear@3 14
nuclear@3 15 ************************************************************************************/
nuclear@3 16
nuclear@3 17 #ifndef OVR_Array_h
nuclear@3 18 #define OVR_Array_h
nuclear@3 19
nuclear@3 20 #include "OVR_ContainerAllocator.h"
nuclear@3 21
nuclear@3 22 namespace OVR {
nuclear@3 23
nuclear@3 24 //-----------------------------------------------------------------------------------
nuclear@3 25 // ***** ArrayDefaultPolicy
nuclear@3 26 //
nuclear@3 27 // Default resize behavior. No minimal capacity, Granularity=4,
nuclear@3 28 // Shrinking as needed. ArrayConstPolicy actually is the same as
nuclear@3 29 // ArrayDefaultPolicy, but parametrized with constants.
nuclear@3 30 // This struct is used only in order to reduce the template "matroska".
nuclear@3 31 struct ArrayDefaultPolicy
nuclear@3 32 {
nuclear@3 33 ArrayDefaultPolicy() : Capacity(0) {}
nuclear@3 34 ArrayDefaultPolicy(const ArrayDefaultPolicy&) : Capacity(0) {}
nuclear@3 35
nuclear@3 36 UPInt GetMinCapacity() const { return 0; }
nuclear@3 37 UPInt GetGranularity() const { return 4; }
nuclear@3 38 bool NeverShrinking() const { return 0; }
nuclear@3 39
nuclear@3 40 UPInt GetCapacity() const { return Capacity; }
nuclear@3 41 void SetCapacity(UPInt capacity) { Capacity = capacity; }
nuclear@3 42 private:
nuclear@3 43 UPInt Capacity;
nuclear@3 44 };
nuclear@3 45
nuclear@3 46
nuclear@3 47 //-----------------------------------------------------------------------------------
nuclear@3 48 // ***** ArrayConstPolicy
nuclear@3 49 //
nuclear@3 50 // Statically parametrized resizing behavior:
nuclear@3 51 // MinCapacity, Granularity, and Shrinking flag.
nuclear@3 52 template<int MinCapacity=0, int Granularity=4, bool NeverShrink=false>
nuclear@3 53 struct ArrayConstPolicy
nuclear@3 54 {
nuclear@3 55 typedef ArrayConstPolicy<MinCapacity, Granularity, NeverShrink> SelfType;
nuclear@3 56
nuclear@3 57 ArrayConstPolicy() : Capacity(0) {}
nuclear@3 58 ArrayConstPolicy(const SelfType&) : Capacity(0) {}
nuclear@3 59
nuclear@3 60 UPInt GetMinCapacity() const { return MinCapacity; }
nuclear@3 61 UPInt GetGranularity() const { return Granularity; }
nuclear@3 62 bool NeverShrinking() const { return NeverShrink; }
nuclear@3 63
nuclear@3 64 UPInt GetCapacity() const { return Capacity; }
nuclear@3 65 void SetCapacity(UPInt capacity) { Capacity = capacity; }
nuclear@3 66 private:
nuclear@3 67 UPInt Capacity;
nuclear@3 68 };
nuclear@3 69
nuclear@3 70 //-----------------------------------------------------------------------------------
nuclear@3 71 // ***** ArrayDataBase
nuclear@3 72 //
nuclear@3 73 // Basic operations with array data: Reserve, Resize, Free, ArrayPolicy.
nuclear@3 74 // For internal use only: ArrayData,ArrayDataCC and others.
nuclear@3 75 template<class T, class Allocator, class SizePolicy>
nuclear@3 76 struct ArrayDataBase
nuclear@3 77 {
nuclear@3 78 typedef T ValueType;
nuclear@3 79 typedef Allocator AllocatorType;
nuclear@3 80 typedef SizePolicy SizePolicyType;
nuclear@3 81 typedef ArrayDataBase<T, Allocator, SizePolicy> SelfType;
nuclear@3 82
nuclear@3 83 ArrayDataBase()
nuclear@3 84 : Data(0), Size(0), Policy() {}
nuclear@3 85
nuclear@3 86 ArrayDataBase(const SizePolicy& p)
nuclear@3 87 : Data(0), Size(0), Policy(p) {}
nuclear@3 88
nuclear@3 89 ~ArrayDataBase()
nuclear@3 90 {
nuclear@3 91 Allocator::DestructArray(Data, Size);
nuclear@3 92 Allocator::Free(Data);
nuclear@3 93 }
nuclear@3 94
nuclear@3 95 UPInt GetCapacity() const
nuclear@3 96 {
nuclear@3 97 return Policy.GetCapacity();
nuclear@3 98 }
nuclear@3 99
nuclear@3 100 void ClearAndRelease()
nuclear@3 101 {
nuclear@3 102 Allocator::DestructArray(Data, Size);
nuclear@3 103 Allocator::Free(Data);
nuclear@3 104 Data = 0;
nuclear@3 105 Size = 0;
nuclear@3 106 Policy.SetCapacity(0);
nuclear@3 107 }
nuclear@3 108
nuclear@3 109 void Reserve(UPInt newCapacity)
nuclear@3 110 {
nuclear@3 111 if (Policy.NeverShrinking() && newCapacity < GetCapacity())
nuclear@3 112 return;
nuclear@3 113
nuclear@3 114 if (newCapacity < Policy.GetMinCapacity())
nuclear@3 115 newCapacity = Policy.GetMinCapacity();
nuclear@3 116
nuclear@3 117 // Resize the buffer.
nuclear@3 118 if (newCapacity == 0)
nuclear@3 119 {
nuclear@3 120 if (Data)
nuclear@3 121 {
nuclear@3 122 Allocator::Free(Data);
nuclear@3 123 Data = 0;
nuclear@3 124 }
nuclear@3 125 Policy.SetCapacity(0);
nuclear@3 126 }
nuclear@3 127 else
nuclear@3 128 {
nuclear@3 129 UPInt gran = Policy.GetGranularity();
nuclear@3 130 newCapacity = (newCapacity + gran - 1) / gran * gran;
nuclear@3 131 if (Data)
nuclear@3 132 {
nuclear@3 133 if (Allocator::IsMovable())
nuclear@3 134 {
nuclear@3 135 Data = (T*)Allocator::Realloc(Data, sizeof(T) * newCapacity);
nuclear@3 136 }
nuclear@3 137 else
nuclear@3 138 {
nuclear@3 139 T* newData = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
nuclear@3 140 UPInt i, s;
nuclear@3 141 s = (Size < newCapacity) ? Size : newCapacity;
nuclear@3 142 for (i = 0; i < s; ++i)
nuclear@3 143 {
nuclear@3 144 Allocator::Construct(&newData[i], Data[i]);
nuclear@3 145 Allocator::Destruct(&Data[i]);
nuclear@3 146 }
nuclear@3 147 for (i = s; i < Size; ++i)
nuclear@3 148 {
nuclear@3 149 Allocator::Destruct(&Data[i]);
nuclear@3 150 }
nuclear@3 151 Allocator::Free(Data);
nuclear@3 152 Data = newData;
nuclear@3 153 }
nuclear@3 154 }
nuclear@3 155 else
nuclear@3 156 {
nuclear@3 157 Data = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
nuclear@3 158 //memset(Buffer, 0, (sizeof(ValueType) * newSize)); // Do we need this?
nuclear@3 159 }
nuclear@3 160 Policy.SetCapacity(newCapacity);
nuclear@3 161 // OVR_ASSERT(Data); // need to throw (or something) on alloc failure!
nuclear@3 162 }
nuclear@3 163 }
nuclear@3 164
nuclear@3 165 // This version of Resize DOES NOT construct the elements.
nuclear@3 166 // It's done to optimize PushBack, which uses a copy constructor
nuclear@3 167 // instead of the default constructor and assignment
nuclear@3 168 void ResizeNoConstruct(UPInt newSize)
nuclear@3 169 {
nuclear@3 170 UPInt oldSize = Size;
nuclear@3 171
nuclear@3 172 if (newSize < oldSize)
nuclear@3 173 {
nuclear@3 174 Allocator::DestructArray(Data + newSize, oldSize - newSize);
nuclear@3 175 if (newSize < (Policy.GetCapacity() >> 1))
nuclear@3 176 {
nuclear@3 177 Reserve(newSize);
nuclear@3 178 }
nuclear@3 179 }
nuclear@3 180 else if(newSize >= Policy.GetCapacity())
nuclear@3 181 {
nuclear@3 182 Reserve(newSize + (newSize >> 2));
nuclear@3 183 }
nuclear@3 184 //! IMPORTANT to modify Size only after Reserve completes, because garbage collectable
nuclear@3 185 // array may use this array and may traverse it during Reserve (in the case, if
nuclear@3 186 // collection occurs because of heap limit exceeded).
nuclear@3 187 Size = newSize;
nuclear@3 188 }
nuclear@3 189
nuclear@3 190 ValueType* Data;
nuclear@3 191 UPInt Size;
nuclear@3 192 SizePolicy Policy;
nuclear@3 193 };
nuclear@3 194
nuclear@3 195
nuclear@3 196
nuclear@3 197 //-----------------------------------------------------------------------------------
nuclear@3 198 // ***** ArrayData
nuclear@3 199 //
nuclear@3 200 // General purpose array data.
nuclear@3 201 // For internal use only in Array, ArrayLH, ArrayPOD and so on.
nuclear@3 202 template<class T, class Allocator, class SizePolicy>
nuclear@3 203 struct ArrayData : ArrayDataBase<T, Allocator, SizePolicy>
nuclear@3 204 {
nuclear@3 205 typedef T ValueType;
nuclear@3 206 typedef Allocator AllocatorType;
nuclear@3 207 typedef SizePolicy SizePolicyType;
nuclear@3 208 typedef ArrayDataBase<T, Allocator, SizePolicy> BaseType;
nuclear@3 209 typedef ArrayData <T, Allocator, SizePolicy> SelfType;
nuclear@3 210
nuclear@3 211 ArrayData()
nuclear@3 212 : BaseType() { }
nuclear@3 213
nuclear@3 214 ArrayData(int size)
nuclear@3 215 : BaseType() { Resize(size); }
nuclear@3 216
nuclear@3 217 ArrayData(const SelfType& a)
nuclear@3 218 : BaseType(a.Policy) { Append(a.Data, a.Size); }
nuclear@3 219
nuclear@3 220
nuclear@3 221 void Resize(UPInt newSize)
nuclear@3 222 {
nuclear@3 223 UPInt oldSize = this->Size;
nuclear@3 224 BaseType::ResizeNoConstruct(newSize);
nuclear@3 225 if(newSize > oldSize)
nuclear@3 226 Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize);
nuclear@3 227 }
nuclear@3 228
nuclear@3 229 void PushBack(const ValueType& val)
nuclear@3 230 {
nuclear@3 231 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3 232 Allocator::Construct(this->Data + this->Size - 1, val);
nuclear@3 233 }
nuclear@3 234
nuclear@3 235 template<class S>
nuclear@3 236 void PushBackAlt(const S& val)
nuclear@3 237 {
nuclear@3 238 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3 239 Allocator::ConstructAlt(this->Data + this->Size - 1, val);
nuclear@3 240 }
nuclear@3 241
nuclear@3 242 // Append the given data to the array.
nuclear@3 243 void Append(const ValueType other[], UPInt count)
nuclear@3 244 {
nuclear@3 245 if (count)
nuclear@3 246 {
nuclear@3 247 UPInt oldSize = this->Size;
nuclear@3 248 BaseType::ResizeNoConstruct(this->Size + count);
nuclear@3 249 Allocator::ConstructArray(this->Data + oldSize, count, other);
nuclear@3 250 }
nuclear@3 251 }
nuclear@3 252 };
nuclear@3 253
nuclear@3 254
nuclear@3 255
nuclear@3 256 //-----------------------------------------------------------------------------------
nuclear@3 257 // ***** ArrayDataCC
nuclear@3 258 //
nuclear@3 259 // A modification of ArrayData that always copy-constructs new elements
nuclear@3 260 // using a specified DefaultValue. For internal use only in ArrayCC.
nuclear@3 261 template<class T, class Allocator, class SizePolicy>
nuclear@3 262 struct ArrayDataCC : ArrayDataBase<T, Allocator, SizePolicy>
nuclear@3 263 {
nuclear@3 264 typedef T ValueType;
nuclear@3 265 typedef Allocator AllocatorType;
nuclear@3 266 typedef SizePolicy SizePolicyType;
nuclear@3 267 typedef ArrayDataBase<T, Allocator, SizePolicy> BaseType;
nuclear@3 268 typedef ArrayDataCC <T, Allocator, SizePolicy> SelfType;
nuclear@3 269
nuclear@3 270 ArrayDataCC(const ValueType& defval)
nuclear@3 271 : BaseType(), DefaultValue(defval) { }
nuclear@3 272
nuclear@3 273 ArrayDataCC(const ValueType& defval, int size)
nuclear@3 274 : BaseType(), DefaultValue(defval) { Resize(size); }
nuclear@3 275
nuclear@3 276 ArrayDataCC(const SelfType& a)
nuclear@3 277 : BaseType(a.Policy), DefaultValue(a.DefaultValue) { Append(a.Data, a.Size); }
nuclear@3 278
nuclear@3 279
nuclear@3 280 void Resize(UPInt newSize)
nuclear@3 281 {
nuclear@3 282 UPInt oldSize = this->Size;
nuclear@3 283 BaseType::ResizeNoConstruct(newSize);
nuclear@3 284 if(newSize > oldSize)
nuclear@3 285 Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize, DefaultValue);
nuclear@3 286 }
nuclear@3 287
nuclear@3 288 void PushBack(const ValueType& val)
nuclear@3 289 {
nuclear@3 290 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3 291 Allocator::Construct(this->Data + this->Size - 1, val);
nuclear@3 292 }
nuclear@3 293
nuclear@3 294 template<class S>
nuclear@3 295 void PushBackAlt(const S& val)
nuclear@3 296 {
nuclear@3 297 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@3 298 Allocator::ConstructAlt(this->Data + this->Size - 1, val);
nuclear@3 299 }
nuclear@3 300
nuclear@3 301 // Append the given data to the array.
nuclear@3 302 void Append(const ValueType other[], UPInt count)
nuclear@3 303 {
nuclear@3 304 if (count)
nuclear@3 305 {
nuclear@3 306 UPInt oldSize = this->Size;
nuclear@3 307 BaseType::ResizeNoConstruct(this->Size + count);
nuclear@3 308 Allocator::ConstructArray(this->Data + oldSize, count, other);
nuclear@3 309 }
nuclear@3 310 }
nuclear@3 311
nuclear@3 312 ValueType DefaultValue;
nuclear@3 313 };
nuclear@3 314
nuclear@3 315
nuclear@3 316
nuclear@3 317
nuclear@3 318
nuclear@3 319 //-----------------------------------------------------------------------------------
nuclear@3 320 // ***** ArrayBase
nuclear@3 321 //
nuclear@3 322 // Resizable array. The behavior can be POD (suffix _POD) and
nuclear@3 323 // Movable (no suffix) depending on the allocator policy.
nuclear@3 324 // In case of _POD the constructors and destructors are not called.
nuclear@3 325 //
nuclear@3 326 // Arrays can't handle non-movable objects! Don't put anything in here
nuclear@3 327 // that can't be moved around by bitwise copy.
nuclear@3 328 //
nuclear@3 329 // The addresses of elements are not persistent! Don't keep the address
nuclear@3 330 // of an element; the array contents will move around as it gets resized.
nuclear@3 331 template<class ArrayData>
nuclear@3 332 class ArrayBase
nuclear@3 333 {
nuclear@3 334 public:
nuclear@3 335 typedef typename ArrayData::ValueType ValueType;
nuclear@3 336 typedef typename ArrayData::AllocatorType AllocatorType;
nuclear@3 337 typedef typename ArrayData::SizePolicyType SizePolicyType;
nuclear@3 338 typedef ArrayBase<ArrayData> SelfType;
nuclear@3 339
nuclear@3 340
nuclear@3 341 #undef new
nuclear@3 342 OVR_MEMORY_REDEFINE_NEW(ArrayBase)
nuclear@3 343 // Redefine operator 'new' if necessary.
nuclear@3 344 #if defined(OVR_DEFINE_NEW)
nuclear@3 345 #define new OVR_DEFINE_NEW
nuclear@3 346 #endif
nuclear@3 347
nuclear@3 348
nuclear@3 349 ArrayBase()
nuclear@3 350 : Data() {}
nuclear@3 351 ArrayBase(int size)
nuclear@3 352 : Data(size) {}
nuclear@3 353 ArrayBase(const SelfType& a)
nuclear@3 354 : Data(a.Data) {}
nuclear@3 355
nuclear@3 356 ArrayBase(const ValueType& defval)
nuclear@3 357 : Data(defval) {}
nuclear@3 358 ArrayBase(const ValueType& defval, int size)
nuclear@3 359 : Data(defval, size) {}
nuclear@3 360
nuclear@3 361 SizePolicyType* GetSizePolicy() const { return Data.Policy; }
nuclear@3 362 void SetSizePolicy(const SizePolicyType& p) { Data.Policy = p; }
nuclear@3 363
nuclear@3 364 bool NeverShrinking()const { return Data.Policy.NeverShrinking(); }
nuclear@3 365 UPInt GetSize() const { return Data.Size; }
nuclear@3 366 bool IsEmpty() const { return Data.Size == 0; }
nuclear@3 367 UPInt GetCapacity() const { return Data.GetCapacity(); }
nuclear@3 368 UPInt GetNumBytes() const { return Data.GetCapacity() * sizeof(ValueType); }
nuclear@3 369
nuclear@3 370 void ClearAndRelease() { Data.ClearAndRelease(); }
nuclear@3 371 void Clear() { Data.Resize(0); }
nuclear@3 372 void Resize(UPInt newSize) { Data.Resize(newSize); }
nuclear@3 373
nuclear@3 374 // Reserve can only increase the capacity
nuclear@3 375 void Reserve(UPInt newCapacity)
nuclear@3 376 {
nuclear@3 377 if (newCapacity > Data.GetCapacity())
nuclear@3 378 Data.Reserve(newCapacity);
nuclear@3 379 }
nuclear@3 380
nuclear@3 381 // Basic access.
nuclear@3 382 ValueType& At(UPInt index)
nuclear@3 383 {
nuclear@3 384 OVR_ASSERT(index < Data.Size);
nuclear@3 385 return Data.Data[index];
nuclear@3 386 }
nuclear@3 387 const ValueType& At(UPInt index) const
nuclear@3 388 {
nuclear@3 389 OVR_ASSERT(index < Data.Size);
nuclear@3 390 return Data.Data[index];
nuclear@3 391 }
nuclear@3 392
nuclear@3 393 ValueType ValueAt(UPInt index) const
nuclear@3 394 {
nuclear@3 395 OVR_ASSERT(index < Data.Size);
nuclear@3 396 return Data.Data[index];
nuclear@3 397 }
nuclear@3 398
nuclear@3 399 // Basic access.
nuclear@3 400 ValueType& operator [] (UPInt index)
nuclear@3 401 {
nuclear@3 402 OVR_ASSERT(index < Data.Size);
nuclear@3 403 return Data.Data[index];
nuclear@3 404 }
nuclear@3 405 const ValueType& operator [] (UPInt index) const
nuclear@3 406 {
nuclear@3 407 OVR_ASSERT(index < Data.Size);
nuclear@3 408 return Data.Data[index];
nuclear@3 409 }
nuclear@3 410
nuclear@3 411 // Raw pointer to the data. Use with caution!
nuclear@3 412 const ValueType* GetDataPtr() const { return Data.Data; }
nuclear@3 413 ValueType* GetDataPtr() { return Data.Data; }
nuclear@3 414
nuclear@3 415 // Insert the given element at the end of the array.
nuclear@3 416 void PushBack(const ValueType& val)
nuclear@3 417 {
nuclear@3 418 // DO NOT pass elements of your own vector into
nuclear@3 419 // push_back()! Since we're using references,
nuclear@3 420 // resize() may munge the element storage!
nuclear@3 421 // OVR_ASSERT(&val < &Buffer[0] || &val > &Buffer[BufferSize]);
nuclear@3 422 Data.PushBack(val);
nuclear@3 423 }
nuclear@3 424
nuclear@3 425 template<class S>
nuclear@3 426 void PushBackAlt(const S& val)
nuclear@3 427 {
nuclear@3 428 Data.PushBackAlt(val);
nuclear@3 429 }
nuclear@3 430
nuclear@3 431 // Remove the last element.
nuclear@3 432 void PopBack(UPInt count = 1)
nuclear@3 433 {
nuclear@3 434 OVR_ASSERT(Data.Size >= count);
nuclear@3 435 Data.Resize(Data.Size - count);
nuclear@3 436 }
nuclear@3 437
nuclear@3 438 ValueType& PushDefault()
nuclear@3 439 {
nuclear@3 440 Data.PushBack(ValueType());
nuclear@3 441 return Back();
nuclear@3 442 }
nuclear@3 443
nuclear@3 444 ValueType Pop()
nuclear@3 445 {
nuclear@3 446 ValueType t = Back();
nuclear@3 447 PopBack();
nuclear@3 448 return t;
nuclear@3 449 }
nuclear@3 450
nuclear@3 451
nuclear@3 452 // Access the first element.
nuclear@3 453 ValueType& Front() { return At(0); }
nuclear@3 454 const ValueType& Front() const { return At(0); }
nuclear@3 455
nuclear@3 456 // Access the last element.
nuclear@3 457 ValueType& Back() { return At(Data.Size - 1); }
nuclear@3 458 const ValueType& Back() const { return At(Data.Size - 1); }
nuclear@3 459
nuclear@3 460 // Array copy. Copies the contents of a into this array.
nuclear@3 461 const SelfType& operator = (const SelfType& a)
nuclear@3 462 {
nuclear@3 463 Resize(a.GetSize());
nuclear@3 464 for (UPInt i = 0; i < Data.Size; i++) {
nuclear@3 465 *(Data.Data + i) = a[i];
nuclear@3 466 }
nuclear@3 467 return *this;
nuclear@3 468 }
nuclear@3 469
nuclear@3 470 // Removing multiple elements from the array.
nuclear@3 471 void RemoveMultipleAt(UPInt index, UPInt num)
nuclear@3 472 {
nuclear@3 473 OVR_ASSERT(index + num <= Data.Size);
nuclear@3 474 if (Data.Size == num)
nuclear@3 475 {
nuclear@3 476 Clear();
nuclear@3 477 }
nuclear@3 478 else
nuclear@3 479 {
nuclear@3 480 AllocatorType::DestructArray(Data.Data + index, num);
nuclear@3 481 AllocatorType::CopyArrayForward(
nuclear@3 482 Data.Data + index,
nuclear@3 483 Data.Data + index + num,
nuclear@3 484 Data.Size - num - index);
nuclear@3 485 Data.Size -= num;
nuclear@3 486 }
nuclear@3 487 }
nuclear@3 488
nuclear@3 489 // Removing an element from the array is an expensive operation!
nuclear@3 490 // It compacts only after removing the last element.
nuclear@3 491 void RemoveAt(UPInt index)
nuclear@3 492 {
nuclear@3 493 OVR_ASSERT(index < Data.Size);
nuclear@3 494 if (Data.Size == 1)
nuclear@3 495 {
nuclear@3 496 Clear();
nuclear@3 497 }
nuclear@3 498 else
nuclear@3 499 {
nuclear@3 500 AllocatorType::Destruct(Data.Data + index);
nuclear@3 501 AllocatorType::CopyArrayForward(
nuclear@3 502 Data.Data + index,
nuclear@3 503 Data.Data + index + 1,
nuclear@3 504 Data.Size - 1 - index);
nuclear@3 505 --Data.Size;
nuclear@3 506 }
nuclear@3 507 }
nuclear@3 508
nuclear@3 509 // Insert the given object at the given index shifting all the elements up.
nuclear@3 510 void InsertAt(UPInt index, const ValueType& val = ValueType())
nuclear@3 511 {
nuclear@3 512 OVR_ASSERT(index <= Data.Size);
nuclear@3 513
nuclear@3 514 Data.Resize(Data.Size + 1);
nuclear@3 515 if (index < Data.Size - 1)
nuclear@3 516 {
nuclear@3 517 AllocatorType::CopyArrayBackward(
nuclear@3 518 Data.Data + index + 1,
nuclear@3 519 Data.Data + index,
nuclear@3 520 Data.Size - 1 - index);
nuclear@3 521 }
nuclear@3 522 AllocatorType::Construct(Data.Data + index, val);
nuclear@3 523 }
nuclear@3 524
nuclear@3 525 // Insert the given object at the given index shifting all the elements up.
nuclear@3 526 void InsertMultipleAt(UPInt index, UPInt num, const ValueType& val = ValueType())
nuclear@3 527 {
nuclear@3 528 OVR_ASSERT(index <= Data.Size);
nuclear@3 529
nuclear@3 530 Data.Resize(Data.Size + num);
nuclear@3 531 if (index < Data.Size - num)
nuclear@3 532 {
nuclear@3 533 AllocatorType::CopyArrayBackward(
nuclear@3 534 Data.Data + index + num,
nuclear@3 535 Data.Data + index,
nuclear@3 536 Data.Size - num - index);
nuclear@3 537 }
nuclear@3 538 for (UPInt i = 0; i < num; ++i)
nuclear@3 539 AllocatorType::Construct(Data.Data + index + i, val);
nuclear@3 540 }
nuclear@3 541
nuclear@3 542 // Append the given data to the array.
nuclear@3 543 void Append(const SelfType& other)
nuclear@3 544 {
nuclear@3 545 Append(other.Data.Data, other.GetSize());
nuclear@3 546 }
nuclear@3 547
nuclear@3 548 // Append the given data to the array.
nuclear@3 549 void Append(const ValueType other[], UPInt count)
nuclear@3 550 {
nuclear@3 551 Data.Append(other, count);
nuclear@3 552 }
nuclear@3 553
nuclear@3 554 class Iterator
nuclear@3 555 {
nuclear@3 556 SelfType* pArray;
nuclear@3 557 SPInt CurIndex;
nuclear@3 558
nuclear@3 559 public:
nuclear@3 560 Iterator() : pArray(0), CurIndex(-1) {}
nuclear@3 561 Iterator(SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
nuclear@3 562
nuclear@3 563 bool operator==(const Iterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
nuclear@3 564 bool operator!=(const Iterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
nuclear@3 565
nuclear@3 566 Iterator& operator++()
nuclear@3 567 {
nuclear@3 568 if (pArray)
nuclear@3 569 {
nuclear@3 570 if (CurIndex < (SPInt)pArray->GetSize())
nuclear@3 571 ++CurIndex;
nuclear@3 572 }
nuclear@3 573 return *this;
nuclear@3 574 }
nuclear@3 575 Iterator operator++(int)
nuclear@3 576 {
nuclear@3 577 Iterator it(*this);
nuclear@3 578 operator++();
nuclear@3 579 return it;
nuclear@3 580 }
nuclear@3 581 Iterator& operator--()
nuclear@3 582 {
nuclear@3 583 if (pArray)
nuclear@3 584 {
nuclear@3 585 if (CurIndex >= 0)
nuclear@3 586 --CurIndex;
nuclear@3 587 }
nuclear@3 588 return *this;
nuclear@3 589 }
nuclear@3 590 Iterator operator--(int)
nuclear@3 591 {
nuclear@3 592 Iterator it(*this);
nuclear@3 593 operator--();
nuclear@3 594 return it;
nuclear@3 595 }
nuclear@3 596 Iterator operator+(int delta) const
nuclear@3 597 {
nuclear@3 598 return Iterator(pArray, CurIndex + delta);
nuclear@3 599 }
nuclear@3 600 Iterator operator-(int delta) const
nuclear@3 601 {
nuclear@3 602 return Iterator(pArray, CurIndex - delta);
nuclear@3 603 }
nuclear@3 604 SPInt operator-(const Iterator& right) const
nuclear@3 605 {
nuclear@3 606 OVR_ASSERT(pArray == right.pArray);
nuclear@3 607 return CurIndex - right.CurIndex;
nuclear@3 608 }
nuclear@3 609 ValueType& operator*() const { OVR_ASSERT(pArray); return (*pArray)[CurIndex]; }
nuclear@3 610 ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3 611 ValueType* GetPtr() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3 612
nuclear@3 613 bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
nuclear@3 614
nuclear@3 615 void Remove()
nuclear@3 616 {
nuclear@3 617 if (!IsFinished())
nuclear@3 618 pArray->RemoveAt(CurIndex);
nuclear@3 619 }
nuclear@3 620
nuclear@3 621 SPInt GetIndex() const { return CurIndex; }
nuclear@3 622 };
nuclear@3 623
nuclear@3 624 Iterator Begin() { return Iterator(this); }
nuclear@3 625 Iterator End() { return Iterator(this, (SPInt)GetSize()); }
nuclear@3 626 Iterator Last() { return Iterator(this, (SPInt)GetSize() - 1); }
nuclear@3 627
nuclear@3 628 class ConstIterator
nuclear@3 629 {
nuclear@3 630 const SelfType* pArray;
nuclear@3 631 SPInt CurIndex;
nuclear@3 632
nuclear@3 633 public:
nuclear@3 634 ConstIterator() : pArray(0), CurIndex(-1) {}
nuclear@3 635 ConstIterator(const SelfType* parr, SPInt idx = 0) : pArray(parr), CurIndex(idx) {}
nuclear@3 636
nuclear@3 637 bool operator==(const ConstIterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
nuclear@3 638 bool operator!=(const ConstIterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
nuclear@3 639
nuclear@3 640 ConstIterator& operator++()
nuclear@3 641 {
nuclear@3 642 if (pArray)
nuclear@3 643 {
nuclear@3 644 if (CurIndex < (int)pArray->GetSize())
nuclear@3 645 ++CurIndex;
nuclear@3 646 }
nuclear@3 647 return *this;
nuclear@3 648 }
nuclear@3 649 ConstIterator operator++(int)
nuclear@3 650 {
nuclear@3 651 ConstIterator it(*this);
nuclear@3 652 operator++();
nuclear@3 653 return it;
nuclear@3 654 }
nuclear@3 655 ConstIterator& operator--()
nuclear@3 656 {
nuclear@3 657 if (pArray)
nuclear@3 658 {
nuclear@3 659 if (CurIndex >= 0)
nuclear@3 660 --CurIndex;
nuclear@3 661 }
nuclear@3 662 return *this;
nuclear@3 663 }
nuclear@3 664 ConstIterator operator--(int)
nuclear@3 665 {
nuclear@3 666 ConstIterator it(*this);
nuclear@3 667 operator--();
nuclear@3 668 return it;
nuclear@3 669 }
nuclear@3 670 ConstIterator operator+(int delta) const
nuclear@3 671 {
nuclear@3 672 return ConstIterator(pArray, CurIndex + delta);
nuclear@3 673 }
nuclear@3 674 ConstIterator operator-(int delta) const
nuclear@3 675 {
nuclear@3 676 return ConstIterator(pArray, CurIndex - delta);
nuclear@3 677 }
nuclear@3 678 SPInt operator-(const ConstIterator& right) const
nuclear@3 679 {
nuclear@3 680 OVR_ASSERT(pArray == right.pArray);
nuclear@3 681 return CurIndex - right.CurIndex;
nuclear@3 682 }
nuclear@3 683 const ValueType& operator*() const { OVR_ASSERT(pArray); return (*pArray)[CurIndex]; }
nuclear@3 684 const ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3 685 const ValueType* GetPtr() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@3 686
nuclear@3 687 bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
nuclear@3 688
nuclear@3 689 SPInt GetIndex() const { return CurIndex; }
nuclear@3 690 };
nuclear@3 691 ConstIterator Begin() const { return ConstIterator(this); }
nuclear@3 692 ConstIterator End() const { return ConstIterator(this, (SPInt)GetSize()); }
nuclear@3 693 ConstIterator Last() const { return ConstIterator(this, (SPInt)GetSize() - 1); }
nuclear@3 694
nuclear@3 695 protected:
nuclear@3 696 ArrayData Data;
nuclear@3 697 };
nuclear@3 698
nuclear@3 699
nuclear@3 700
nuclear@3 701 //-----------------------------------------------------------------------------------
nuclear@3 702 // ***** Array
nuclear@3 703 //
nuclear@3 704 // General purpose array for movable objects that require explicit
nuclear@3 705 // construction/destruction.
nuclear@3 706 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3 707 class Array : public ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> >
nuclear@3 708 {
nuclear@3 709 public:
nuclear@3 710 typedef T ValueType;
nuclear@3 711 typedef ContainerAllocator<T> AllocatorType;
nuclear@3 712 typedef SizePolicy SizePolicyType;
nuclear@3 713 typedef Array<T, SizePolicy> SelfType;
nuclear@3 714 typedef ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> > BaseType;
nuclear@3 715
nuclear@3 716 Array() : BaseType() {}
nuclear@3 717 Array(int size) : BaseType(size) {}
nuclear@3 718 Array(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@3 719 Array(const SelfType& a) : BaseType(a) {}
nuclear@3 720 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3 721 };
nuclear@3 722
nuclear@3 723 // ***** ArrayPOD
nuclear@3 724 //
nuclear@3 725 // General purpose array for movable objects that DOES NOT require
nuclear@3 726 // construction/destruction. Constructors and destructors are not called!
nuclear@3 727 // Global heap is in use.
nuclear@3 728 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3 729 class ArrayPOD : public ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> >
nuclear@3 730 {
nuclear@3 731 public:
nuclear@3 732 typedef T ValueType;
nuclear@3 733 typedef ContainerAllocator_POD<T> AllocatorType;
nuclear@3 734 typedef SizePolicy SizePolicyType;
nuclear@3 735 typedef ArrayPOD<T, SizePolicy> SelfType;
nuclear@3 736 typedef ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> > BaseType;
nuclear@3 737
nuclear@3 738 ArrayPOD() : BaseType() {}
nuclear@3 739 ArrayPOD(int size) : BaseType(size) {}
nuclear@3 740 ArrayPOD(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@3 741 ArrayPOD(const SelfType& a) : BaseType(a) {}
nuclear@3 742 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3 743 };
nuclear@3 744
nuclear@3 745
nuclear@3 746 // ***** ArrayCPP
nuclear@3 747 //
nuclear@3 748 // General purpose, fully C++ compliant array. Can be used with non-movable data.
nuclear@3 749 // Global heap is in use.
nuclear@3 750 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3 751 class ArrayCPP : public ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> >
nuclear@3 752 {
nuclear@3 753 public:
nuclear@3 754 typedef T ValueType;
nuclear@3 755 typedef ContainerAllocator_CPP<T> AllocatorType;
nuclear@3 756 typedef SizePolicy SizePolicyType;
nuclear@3 757 typedef ArrayCPP<T, SizePolicy> SelfType;
nuclear@3 758 typedef ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> > BaseType;
nuclear@3 759
nuclear@3 760 ArrayCPP() : BaseType() {}
nuclear@3 761 ArrayCPP(int size) : BaseType(size) {}
nuclear@3 762 ArrayCPP(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@3 763 ArrayCPP(const SelfType& a) : BaseType(a) {}
nuclear@3 764 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3 765 };
nuclear@3 766
nuclear@3 767
nuclear@3 768 // ***** ArrayCC
nuclear@3 769 //
nuclear@3 770 // A modification of the array that uses the given default value to
nuclear@3 771 // construct the elements. The constructors and destructors are
nuclear@3 772 // properly called, the objects must be movable.
nuclear@3 773
nuclear@3 774 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@3 775 class ArrayCC : public ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >
nuclear@3 776 {
nuclear@3 777 public:
nuclear@3 778 typedef T ValueType;
nuclear@3 779 typedef ContainerAllocator<T> AllocatorType;
nuclear@3 780 typedef SizePolicy SizePolicyType;
nuclear@3 781 typedef ArrayCC<T, SizePolicy> SelfType;
nuclear@3 782 typedef ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> > BaseType;
nuclear@3 783
nuclear@3 784 ArrayCC(const ValueType& defval) : BaseType(defval) {}
nuclear@3 785 ArrayCC(const ValueType& defval, int size) : BaseType(defval, size) {}
nuclear@3 786 ArrayCC(const ValueType& defval, const SizePolicyType& p) : BaseType(defval) { SetSizePolicy(p); }
nuclear@3 787 ArrayCC(const SelfType& a) : BaseType(a) {}
nuclear@3 788 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@3 789 };
nuclear@3 790
nuclear@3 791 } // OVR
nuclear@3 792
nuclear@3 793 #endif