oculus1

annotate libovr/Src/Kernel/OVR_Array.h @ 29:9a973ef0e2a3

find changesets by author, revision, files, or words in the commit message
fixed the performance issue under MacOSX by replacing glutSolidTeapot (which uses glEvalMesh) with my own teapot generator.
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 27 Oct 2013 06:31:18 +0200
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