tVector.h

Public Functions

VectorResize(U32 * aSize, U32 * aCount, void ** arrayPtr, U32 newCount, U32 elemSize)

   1
   2//-----------------------------------------------------------------------------
   3// Copyright (c) 2012 GarageGames, LLC
   4//
   5// Permission is hereby granted, free of charge, to any person obtaining a copy
   6// of this software and associated documentation files (the "Software"), to
   7// deal in the Software without restriction, including without limitation the
   8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   9// sell copies of the Software, and to permit persons to whom the Software is
  10// furnished to do so, subject to the following conditions:
  11//
  12// The above copyright notice and this permission notice shall be included in
  13// all copies or substantial portions of the Software.
  14//
  15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21// IN THE SOFTWARE.
  22//-----------------------------------------------------------------------------
  23
  24#ifndef _TVECTOR_H_
  25#define _TVECTOR_H_
  26
  27// TODO: This shouldn't be included in headers... it should
  28// be included by the source file before all other includes.
  29#ifndef _PLATFORM_H_
  30#include "platform/platform.h"
  31#endif
  32#include <algorithm>
  33#include "console/engineTypes.h"
  34#include "console/engineTypeInfo.h"
  35
  36//-----------------------------------------------------------------------------
  37// Helper definitions for the vector class.
  38
  39/// Size of memory blocks to allocate at a time for vectors.
  40const static S32 VectorBlockSize = 16;
  41#ifdef TORQUE_DEBUG_GUARD
  42extern bool VectorResize(U32 *aSize, U32 *aCount, void **arrayPtr, U32 newCount, U32 elemSize,
  43                         const char* fileName,
  44                         const U32   lineNum);
  45#else
  46extern bool VectorResize(U32 *aSize, U32 *aCount, void **arrayPtr, U32 newCount, U32 elemSize);
  47#endif
  48
  49/// Use the following macro to bind a vector to a particular line
  50///  of the owning class for memory tracking purposes
  51#ifdef TORQUE_DEBUG_GUARD
  52#define VECTOR_SET_ASSOCIATION(x) x.setFileAssociation(__FILE__, __LINE__)
  53#else
  54#define VECTOR_SET_ASSOCIATION(x)
  55#endif
  56
  57// =============================================================================
  58/// A dynamic array template class.
  59///
  60/// The vector grows as you insert or append
  61/// elements.  Insertion is fastest at the end of the array.  Resizing
  62/// of the array can be avoided by pre-allocating space using the
  63/// reserve() method.
  64///
  65/// @nosubgrouping
  66template<class T>
  67class Vector
  68{
  69   friend class VectorFieldEngineExport;
  70  protected:
  71   U32 mElementCount; ///< Number of elements currently in the Vector.
  72   U32 mArraySize;    ///< Number of elements allocated for the Vector.
  73   T*  mArray;        ///< Pointer to the Vector elements.
  74
  75#ifdef TORQUE_DEBUG_GUARD
  76   const char* mFileAssociation;
  77   U32         mLineAssociation;
  78#endif
  79
  80   bool  resize(U32); // resizes, but does no construction/destruction
  81   void  destroy(U32 start, U32 end);   ///< Destructs elements from <i>start</i> to <i>end-1</i>
  82   void  construct(U32 start, U32 end); ///< Constructs elements from <i>start</i> to <i>end-1</i>
  83   void  construct(U32 start, U32 end, const T* array);
  84  public:
  85   Vector(const U32 initialSize = 0);
  86   Vector(const U32 initialSize, const char* fileName, const U32 lineNum);
  87   Vector(const char* fileName, const U32 lineNum);
  88   Vector(const Vector&);
  89   ~Vector();
  90
  91#ifdef TORQUE_DEBUG_GUARD
  92   void setFileAssociation(const char* file, const U32 line);
  93#endif
  94
  95   /// @name STL interface
  96   /// @{
  97
  98   typedef T        value_type;
  99   typedef T&       reference;
 100   typedef const T& const_reference;
 101
 102   typedef T*       iterator;
 103   typedef const T* const_iterator;
 104   typedef S32    difference_type;
 105   typedef U32    size_type;
 106
 107   typedef difference_type (QSORT_CALLBACK *compare_func)(const T *a, const T *b);
 108
 109   Vector<T>& operator=(const Vector<T>& p);
 110
 111   iterator       begin();
 112   const_iterator begin() const;
 113   iterator       end();
 114   const_iterator end() const;
 115
 116   S32 size() const;
 117   bool empty() const;
 118   bool contains(const T&) const;
 119
 120   void insert(iterator, const T&);
 121   void erase(iterator);
 122
 123   T&       front();
 124   const T& front() const;
 125   T&       back();
 126   const T& back() const;
 127
 128   void push_front(const T&);
 129   void push_back(const T&);
 130   U32 push_front_unique(const T&);
 131   U32 push_back_unique(const T&);
 132   S32 find_next( const T&, U32 start = 0 ) const;
 133   void pop_front();
 134   void pop_back();
 135
 136   T& operator[](U32);
 137   const T& operator[](U32) const;
 138
 139   T& operator[](S32 i)              { return operator[](U32(i)); }
 140   const T& operator[](S32 i ) const { return operator[](U32(i)); }
 141
 142   void reserve(U32);
 143   U32 capacity() const;
 144
 145   /// @}
 146
 147   /// @name Extended interface
 148   /// @{
 149
 150   U32  memSize() const;
 151   T*   address() const;
 152   U32  setSize(U32);
 153   void increment();
 154   void decrement();
 155   void increment(U32);
 156   void decrement(U32);
 157   void insert(U32);
 158   void insert(U32, const T&);
 159   void erase(U32);
 160   void erase_fast(U32);
 161   void erase(U32 index, U32 count);
 162   void erase_fast(iterator);
 163   void clear();
 164   void compact();
 165   void sort(compare_func f);
 166   void fill( const T& value );
 167
 168   /// Finds the first matching element and erases it.   
 169   /// @return Returns true if a match is found.
 170   bool remove( const T& );
 171
 172   T& first();
 173   T& last();
 174   const T& first() const;
 175   const T& last() const;
 176
 177   void set(void * addr, U32 sz);
 178
 179   /// Appends the content of the vector to this one.
 180   void merge( const Vector &p );
 181
 182   /// Appends the content of the array to the vector.
 183   ///
 184   /// @param addr   A pointer to the first item of the array to merge.
 185   /// @param count  The number of elements in the array to merge.
 186   ///
 187   void merge( const T *addr, U32 count );
 188
 189   // Reverses the order of elements.
 190   void reverse();
 191
 192   /// @}
 193};
 194
 195class VectorFieldEngineExport
 196{
 197public:
 198   template <class T>
 199   static EngineFieldTable::Field getElementCountField()
 200   {
 201      typedef Vector<T> ThisType;
 202      return _FIELD(mElementCount, elementCount, 1, "");
 203   };
 204   template <class T>
 205   static EngineFieldTable::Field getArraySizeField()
 206   {
 207      typedef Vector<T> ThisType;
 208      return _FIELD(mArraySize, arraySize, 1, "");
 209   };
 210   template <class T>
 211   static EngineFieldTable::Field getArrayField()
 212   {
 213      typedef Vector<T> ThisType;
 214      return _FIELD(mArray, array, 1, "");
 215   };
 216};
 217
 218template<class T> inline Vector<T>::~Vector()
 219{
 220   clear();
 221   dFree(mArray);
 222}
 223
 224template<class T> inline Vector<T>::Vector(const U32 initialSize)
 225{
 226#ifdef TORQUE_DEBUG_GUARD
 227   mFileAssociation = NULL;
 228   mLineAssociation = 0;
 229#endif
 230
 231   mArray        = 0;
 232   mElementCount = 0;
 233   mArraySize    = 0;
 234   if(initialSize)
 235      reserve(initialSize);
 236}
 237
 238template<class T> inline Vector<T>::Vector(const U32 initialSize,
 239                                           const char* fileName,
 240                                           const U32   lineNum)
 241{
 242#ifdef TORQUE_DEBUG_GUARD
 243   mFileAssociation = fileName;
 244   mLineAssociation = lineNum;
 245#else
 246//   TORQUE_UNUSED(fileName);
 247//   TORQUE_UNUSED(lineNum);
 248#endif
 249
 250   mArray        = 0;
 251   mElementCount = 0;
 252   mArraySize    = 0;
 253   if(initialSize)
 254      reserve(initialSize);
 255}
 256
 257template<class T> inline Vector<T>::Vector(const char* fileName,
 258                                           const U32   lineNum)
 259{
 260#ifdef TORQUE_DEBUG_GUARD
 261   mFileAssociation = fileName;
 262   mLineAssociation = lineNum;
 263#else
 264//   TORQUE_UNUSED(fileName);
 265//   TORQUE_UNUSED(lineNum);
 266#endif
 267
 268   mArray        = 0;
 269   mElementCount = 0;
 270   mArraySize    = 0;
 271}
 272
 273template<class T> inline Vector<T>::Vector(const Vector& p)
 274{
 275#ifdef TORQUE_DEBUG_GUARD
 276   mFileAssociation = p.mFileAssociation;
 277   mLineAssociation = p.mLineAssociation;
 278#endif
 279
 280   mArray = 0;
 281   resize(p.mElementCount);
 282   construct(0, p.mElementCount, p.mArray);
 283}
 284
 285
 286#ifdef TORQUE_DEBUG_GUARD
 287template<class T> inline void Vector<T>::setFileAssociation(const char* file,
 288                                                            const U32   line)
 289{
 290   mFileAssociation = file;
 291   mLineAssociation = line;
 292}
 293#endif
 294
 295template<class T> inline void  Vector<T>::destroy(U32 start, U32 end) // destroys from start to end-1
 296{
 297   // This check is a little generous as we can legitimately get (0,0) as
 298   // our parameters... so it won't detect every invalid case but it does
 299   // remain simple.
 300   AssertFatal(start <= mElementCount && end <= mElementCount, "Vector<T>::destroy - out of bounds start/end.");
 301
 302   // destroys from start to end-1
 303   while(start < end)
 304      destructInPlace(&mArray[start++]);
 305}
 306
 307template<class T> inline void  Vector<T>::construct(U32 start, U32 end) // destroys from start to end-1
 308{
 309   AssertFatal(start <= mElementCount && end <= mElementCount, "Vector<T>::construct - out of bounds start/end.");
 310   while(start < end)
 311      constructInPlace(&mArray[start++]);
 312}
 313
 314template<class T> inline void  Vector<T>::construct(U32 start, U32 end, const T* array) // destroys from start to end-1
 315{
 316   AssertFatal(start <= mElementCount && end <= mElementCount, "Vector<T>::construct - out of bounds start/end.");
 317   while(start < end)
 318   {
 319      constructInPlace(&mArray[start], &array[start]);
 320      start++;
 321   }
 322}
 323
 324template<class T> inline U32 Vector<T>::memSize() const
 325{
 326   return capacity() * sizeof(T);
 327}
 328
 329template<class T> inline T* Vector<T>::address() const
 330{
 331   return mArray;
 332}
 333
 334template<class T> inline U32 Vector<T>::setSize(U32 size)
 335{
 336   const U32 oldSize = mElementCount;
 337   
 338   if(size > mElementCount)
 339   {
 340      if (size > mArraySize)
 341         resize(size);
 342
 343      // Set count first so we are in a valid state for construct.
 344      mElementCount = size;
 345      construct(oldSize, size);
 346   }
 347   else if(size < mElementCount)
 348   {
 349      destroy(size, oldSize);
 350      mElementCount = size;
 351   }
 352
 353   return mElementCount;
 354}
 355
 356template<class T> inline void Vector<T>::increment()
 357{
 358   if(mElementCount == mArraySize)
 359      resize(mElementCount + 1);
 360   else
 361      mElementCount++;
 362   constructInPlace(&mArray[mElementCount - 1]);
 363}
 364
 365template<class T> inline void Vector<T>::decrement()
 366{
 367   AssertFatal(mElementCount != 0, "Vector<T>::decrement - cannot decrement zero-length vector.");
 368   mElementCount--;
 369   destructInPlace(&mArray[mElementCount]);
 370}
 371
 372template<class T> inline void Vector<T>::increment(U32 delta)
 373{
 374   U32 count = mElementCount;
 375   if ((mElementCount += delta) > mArraySize)
 376      resize(mElementCount);
 377   construct(count, mElementCount);
 378}
 379
 380template<class T> inline void Vector<T>::decrement(U32 delta)
 381{
 382   AssertFatal(mElementCount != 0, "Vector<T>::decrement - cannot decrement zero-length vector.");
 383
 384   const U32 count = mElementCount;
 385
 386   // Determine new count after decrement...
 387   U32 newCount = mElementCount;
 388   if (mElementCount > delta)
 389      newCount -= delta;
 390   else
 391      newCount = 0;
 392
 393   // Destruct removed items...
 394   destroy(newCount, count);
 395
 396   // Note new element count.
 397   mElementCount = newCount;
 398}
 399
 400template<class T> inline void Vector<T>::insert(U32 index)
 401{
 402   AssertFatal(index <= mElementCount, "Vector<T>::insert - out of bounds index.");
 403
 404   if(mElementCount == mArraySize)
 405      resize(mElementCount + 1);
 406   else
 407      mElementCount++;
 408
 409   dMemmove(&mArray[index + 1],
 410                    &mArray[index],
 411                    (mElementCount - index - 1) * sizeof(value_type));
 412   
 413   constructInPlace(&mArray[index]);
 414}
 415
 416template<class T> inline void Vector<T>::insert(U32 index,const T& x)
 417{
 418   insert(index);
 419   mArray[index] = x;
 420}
 421
 422template<class T> inline void Vector<T>::erase(U32 index)
 423{
 424   AssertFatal(index < mElementCount, "Vector<T>::erase - out of bounds index!");
 425
 426   destructInPlace(&mArray[index]);
 427
 428   if (index < (mElementCount - 1))
 429   {
 430      dMemmove(&mArray[index],
 431         &mArray[index + 1],
 432         (mElementCount - index - 1) * sizeof(value_type));
 433   }
 434
 435   mElementCount--;
 436}
 437
 438template<class T> inline bool Vector<T>::remove( const T& x )
 439{
 440   iterator i = begin();
 441   while (i != end())
 442   {
 443      if (*i == x)
 444      {
 445         erase( i );
 446         return true;
 447      }
 448
 449      i++;
 450   }
 451
 452   return false;
 453}
 454
 455template<class T> inline void Vector<T>::erase(U32 index, U32 count)
 456{
 457   AssertFatal(index < mElementCount, "Vector<T>::erase - out of bounds index!");
 458   AssertFatal(count > 0, "Vector<T>::erase - count must be greater than zero!");
 459   AssertFatal(index+count <= mElementCount, "Vector<T>::erase - out of bounds count!");
 460
 461   destroy( index, index+count );
 462
 463   dMemmove(   &mArray[index],
 464               &mArray[index + count],
 465               (mElementCount - index - count) * sizeof(value_type));
 466
 467   mElementCount -= count;
 468}
 469
 470template<class T> inline void Vector<T>::erase_fast(U32 index)
 471{
 472   AssertFatal(index < mElementCount, "Vector<T>::erase_fast - out of bounds index.");
 473
 474   // CAUTION: this operator does NOT maintain list order
 475   // Copy the last element into the deleted 'hole' and decrement the
 476   //   size of the vector.
 477   destructInPlace(&mArray[index]);
 478   if (index < (mElementCount - 1))
 479      dMemmove(&mArray[index], &mArray[mElementCount - 1], sizeof(value_type));
 480   mElementCount--;
 481}
 482
 483template<class T> inline bool Vector<T>::contains(const T& x) const
 484{
 485   const_iterator i = begin();
 486   while (i != end())
 487   {
 488      if (*i == x)
 489         return true;
 490
 491      i++;
 492   }
 493
 494   return false;
 495}
 496
 497template< class T > inline void Vector< T >::fill( const T& value )
 498{
 499   for( U32 i = 0; i < size(); ++ i )
 500      mArray[ i ] = value;
 501}
 502
 503template<class T> inline T& Vector<T>::first()
 504{
 505   AssertFatal(mElementCount != 0, "Vector<T>::first - Error, no first element of a zero sized array!");
 506   return mArray[0];
 507}
 508
 509template<class T> inline const T& Vector<T>::first() const
 510{
 511   AssertFatal(mElementCount != 0, "Vector<T>::first - Error, no first element of a zero sized array! (const)");
 512   return mArray[0];
 513}
 514
 515template<class T> inline T& Vector<T>::last()
 516{
 517   AssertFatal(mElementCount != 0, "Vector<T>::last - Error, no last element of a zero sized array!");
 518   return mArray[mElementCount - 1];
 519}
 520
 521template<class T> inline const T& Vector<T>::last() const
 522{
 523   AssertFatal(mElementCount != 0, "Vector<T>::last - Error, no last element of a zero sized array! (const)");
 524   return mArray[mElementCount - 1];
 525}
 526
 527template<class T> inline void Vector<T>::clear()
 528{
 529   destroy(0, mElementCount);
 530   mElementCount = 0;
 531}
 532
 533template<class T> inline void Vector<T>::compact()
 534{
 535   resize(mElementCount);
 536}
 537
 538typedef S32 (QSORT_CALLBACK *qsort_compare_func)(const void *, const void *);
 539
 540template<class T> inline void Vector<T>::sort(compare_func f)
 541{
 542   qsort(address(), size(), sizeof(T), (qsort_compare_func) f);
 543}
 544
 545//-----------------------------------------------------------------------------
 546
 547template<class T> inline Vector<T>& Vector<T>::operator=(const Vector<T>& p)
 548{
 549   if(mElementCount > p.mElementCount)
 550   {
 551      destroy(p.mElementCount, mElementCount);
 552   }
 553   
 554   U32 count = getMin( mElementCount, p.mElementCount );
 555   U32 i;
 556   for( i=0; i < count; i++ )
 557   {
 558      mArray[i] = p.mArray[i];
 559   }
 560   
 561   resize( p.mElementCount );
 562   
 563   if( i < p.mElementCount )
 564   {
 565      construct(i, p.mElementCount, p.mArray);
 566   }
 567   return *this;
 568}
 569
 570template<class T> inline typename Vector<T>::iterator Vector<T>::begin()
 571{
 572   return mArray;
 573}
 574
 575template<class T> inline typename Vector<T>::const_iterator Vector<T>::begin() const
 576{
 577   return mArray;
 578}
 579
 580template<class T> inline typename Vector<T>::iterator Vector<T>::end()
 581{
 582   return mArray + mElementCount;
 583}
 584
 585template<class T> inline typename Vector<T>::const_iterator Vector<T>::end() const
 586{
 587   return mArray +mElementCount;
 588}
 589
 590template<class T> inline S32 Vector<T>::size() const
 591{
 592   return (S32)mElementCount;
 593}
 594
 595template<class T> inline bool Vector<T>::empty() const
 596{
 597   return (mElementCount == 0);
 598}
 599
 600template<class T> inline void Vector<T>::insert(iterator p,const T& x)
 601{
 602   U32 index = (U32) (p - mArray);
 603   insert(index);
 604   mArray[index] = x;
 605}
 606
 607template<class T> inline void Vector<T>::erase(iterator q)
 608{
 609   erase(U32(q - mArray));
 610}
 611
 612template<class T> inline void Vector<T>::erase_fast(iterator q)
 613{
 614   erase_fast(U32(q - mArray));
 615}
 616
 617template<class T> inline T& Vector<T>::front()
 618{
 619   return *begin();
 620}
 621
 622template<class T> inline const T& Vector<T>::front() const
 623{
 624   return *begin();
 625}
 626
 627template<class T> inline T& Vector<T>::back()
 628{
 629   AssertFatal(mElementCount != 0, "Vector<T>::back - cannot access last element of zero-length vector.");
 630   return *(end()-1);
 631}
 632
 633template<class T> inline const T& Vector<T>::back() const
 634{
 635   AssertFatal(mElementCount != 0, "Vector<T>::back - cannot access last element of zero-length vector.");
 636   return *(end()-1);
 637}
 638
 639template<class T> inline void Vector<T>::push_front(const T& x)
 640{
 641   insert(0);
 642   mArray[0] = x;
 643}
 644
 645template<class T> inline void Vector<T>::push_back(const T& x)
 646{
 647   increment();
 648   mArray[mElementCount - 1] = x;
 649}
 650
 651template<class T> inline U32 Vector<T>::push_front_unique(const T& x)
 652{
 653   S32 index = find_next(x);
 654
 655   if (index == -1)
 656   {
 657      index = 0;
 658
 659      insert(index);
 660      mArray[index] = x;
 661   }
 662
 663   return index;
 664}
 665
 666template<class T> inline U32 Vector<T>::push_back_unique(const T& x)
 667{
 668   S32 index = find_next(x);
 669
 670   if (index == -1)
 671   {
 672      increment();
 673
 674      index = mElementCount - 1;
 675      mArray[index] = x;
 676   }
 677
 678   return index;
 679}
 680
 681template<class T> inline S32 Vector<T>::find_next( const T& x, U32 start ) const
 682{
 683   S32 index = -1;
 684
 685   if (start < mElementCount)
 686   {
 687      for (U32 i = start; i < mElementCount; i++)
 688      {
 689         if (mArray[i] == x)
 690         {
 691            index = i;
 692            break;
 693         }
 694      }
 695   }
 696
 697   return index;
 698}
 699
 700template<class T> inline void Vector<T>::pop_front()
 701{
 702   AssertFatal(mElementCount != 0, "Vector<T>::pop_front - cannot pop the front of a zero-length vector.");
 703   erase(U32(0));
 704}
 705
 706template<class T> inline void Vector<T>::pop_back()
 707{
 708   AssertFatal(mElementCount != 0, "Vector<T>::pop_back - cannot pop the back of a zero-length vector.");
 709   decrement();
 710}
 711
 712template<class T> inline T& Vector<T>::operator[](U32 index)
 713{
 714   AssertFatal(index < mElementCount, avar("Vector<T>::operator[%i/%i] - out of bounds array access!", index, mElementCount));
 715   return mArray[index];
 716}
 717
 718template<class T> inline const T& Vector<T>::operator[](U32 index) const
 719{
 720   AssertFatal(index < mElementCount, avar("Vector<T>::operator[%i/%i] - out of bounds array access!", index, mElementCount));
 721   return mArray[index];
 722}
 723
 724template<class T> inline void Vector<T>::reserve(U32 size)
 725{
 726   if (size <= mArraySize)
 727      return;
 728
 729   const U32 ec = mElementCount;
 730   if (resize(size))
 731      mElementCount = ec;
 732}
 733
 734template<class T> inline U32 Vector<T>::capacity() const
 735{
 736    return mArraySize;
 737}
 738
 739template<class T> inline void Vector<T>::set(void * addr, U32 sz)
 740{
 741   if ( !addr )
 742      sz = 0;
 743
 744   setSize( sz );
 745
 746   if ( addr && sz > 0 )
 747      dMemcpy(address(),addr,sz*sizeof(T));
 748}
 749
 750//-----------------------------------------------------------------------------
 751
 752template<class T> inline bool Vector<T>::resize(U32 ecount)
 753{
 754#ifdef TORQUE_DEBUG_GUARD
 755   return VectorResize(&mArraySize, &mElementCount, (void**) &mArray, ecount, sizeof(T),
 756                       mFileAssociation, mLineAssociation);
 757#else
 758   return VectorResize(&mArraySize, &mElementCount, (void**) &mArray, ecount, sizeof(T));
 759#endif
 760}
 761
 762template<class T> inline void Vector<T>::merge( const Vector &p )
 763{
 764   if ( !p.size() )
 765      return;
 766
 767   const U32 oldSize = mElementCount;
 768   const U32 newSize = oldSize + p.size();
 769   if ( newSize > mArraySize )
 770      resize( newSize );
 771
 772   T *dest = mArray + oldSize;
 773   const T *src = p.mArray;
 774   while ( dest < mArray + newSize )
 775      constructInPlace( dest++, src++ );
 776
 777   mElementCount = newSize;
 778}
 779
 780template<class T> inline void Vector<T>::merge( const T *addr, U32 count )
 781{
 782   const U32 oldSize = mElementCount;
 783   const U32 newSize = oldSize + count;
 784   if ( newSize > mArraySize )
 785      resize( newSize );
 786
 787   T *dest = mArray + oldSize;
 788   while ( dest < mArray + newSize )
 789      constructInPlace( dest++, addr++ );
 790
 791   mElementCount = newSize;
 792}
 793
 794template<class T> inline void Vector<T>::reverse()
 795{
 796   for (U32 i = 0, j = size();  (i != j) && (i != --j);  ++i)
 797      std::swap( mArray[ i ],  mArray[ j ] );
 798}
 799
 800//-----------------------------------------------------------------------------
 801/// Template for vectors of pointers.
 802template <class T>
 803class VectorPtr : public Vector<void *>
 804{
 805   /// @deprecated Disallowed.
 806   VectorPtr(const VectorPtr&);  // Disallowed
 807
 808  public:
 809   VectorPtr();
 810   VectorPtr(const char* fileName, const U32 lineNum);
 811
 812   /// @name STL interface
 813   /// @{
 814
 815   typedef T        value_type;
 816   typedef T&       reference;
 817   typedef const T& const_reference;
 818
 819   typedef T*       iterator;
 820   typedef const T* const_iterator;
 821   typedef U32      difference_type;
 822   typedef U32      size_type;
 823
 824   iterator       begin();
 825   const_iterator begin() const;
 826   iterator       end();
 827   const_iterator end() const;
 828
 829   void insert(iterator,const T&);
 830   void insert(S32 idx) { Parent::insert(idx); }
 831   void erase(iterator);
 832
 833   T&       front();
 834   const T& front() const;
 835   T&       back();
 836   const T& back() const;
 837   void     push_front(const T&);
 838   void     push_back(const T&);
 839
 840   T&       operator[](U32);
 841   const T& operator[](U32) const;
 842
 843   /// @}
 844
 845   /// @name Extended interface
 846   /// @{
 847
 848   typedef Vector<void*> Parent;
 849   T&       first();
 850   T&       last();
 851   const T& first() const;
 852   const T& last() const;
 853   void erase_fast(U32);
 854   void erase_fast(iterator);
 855
 856   /// @}
 857};
 858
 859
 860//-----------------------------------------------------------------------------
 861template<class T> inline VectorPtr<T>::VectorPtr()
 862{
 863   //
 864}
 865
 866template<class T> inline VectorPtr<T>::VectorPtr(const char* fileName,
 867                                                 const U32   lineNum)
 868   : Vector<void*>(fileName, lineNum)
 869{
 870   //
 871}
 872
 873template<class T> inline T& VectorPtr<T>::first()
 874{
 875   return (T&)Parent::first();
 876}
 877
 878template<class T> inline const T& VectorPtr<T>::first() const
 879{
 880   return (const T)Parent::first();
 881}
 882
 883template<class T> inline T& VectorPtr<T>::last()
 884{
 885   return (T&)Parent::last();
 886}
 887
 888template<class T> inline const T& VectorPtr<T>::last() const
 889{
 890   return (const T&)Parent::last();
 891}
 892
 893template<class T> inline typename VectorPtr<T>::iterator VectorPtr<T>::begin()
 894{
 895   return (iterator)Parent::begin();
 896}
 897
 898template<class T> inline typename VectorPtr<T>::const_iterator VectorPtr<T>::begin() const
 899{
 900   return (const_iterator)Parent::begin();
 901}
 902
 903template<class T> inline typename VectorPtr<T>::iterator VectorPtr<T>::end()
 904{
 905   return (iterator)Parent::end();
 906}
 907
 908template<class T> inline typename VectorPtr<T>::const_iterator VectorPtr<T>::end() const
 909{
 910   return (const_iterator)Parent::end();
 911}
 912
 913template<class T> inline void VectorPtr<T>::insert(iterator i,const T& x)
 914{
 915   Parent::insert( (Parent::iterator)i, (Parent::reference)x );
 916}
 917
 918template<class T> inline void VectorPtr<T>::erase(iterator i)
 919{
 920   Parent::erase( (Parent::iterator)i );
 921}
 922
 923template<class T> inline void VectorPtr<T>::erase_fast(U32 index)
 924{
 925   AssertFatal(index < mElementCount, "VectorPtr<T>::erase_fast - out of bounds index." );
 926
 927   // CAUTION: this operator does not maintain list order
 928   // Copy the last element into the deleted 'hole' and decrement the
 929   //   size of the vector.
 930   // Assert: index >= 0 && index < mElementCount
 931   if (index < (mElementCount - 1))
 932      mArray[index] = mArray[mElementCount - 1];
 933   decrement();
 934}
 935
 936template<class T> inline void VectorPtr<T>::erase_fast(iterator i)
 937{
 938   erase_fast(U32(i - iterator(mArray)));
 939}
 940
 941template<class T> inline T& VectorPtr<T>::front()
 942{
 943   return *begin();
 944}
 945
 946template<class T> inline const T& VectorPtr<T>::front() const
 947{
 948   return *begin();
 949}
 950
 951template<class T> inline T& VectorPtr<T>::back()
 952{
 953   AssertFatal(mElementCount != 0, "Vector<T>::back - cannot access last element of zero-length vector.");
 954   return *(end()-1);
 955}
 956
 957template<class T> inline const T& VectorPtr<T>::back() const
 958{
 959   AssertFatal(mElementCount != 0, "Vector<T>::back - cannot access last element of zero-length vector.");
 960   return *(end()-1);
 961}
 962
 963template<class T> inline void VectorPtr<T>::push_front(const T& x)
 964{
 965   Parent::push_front((Parent::const_reference)x);
 966}
 967
 968template<class T> inline void VectorPtr<T>::push_back(const T& x)
 969{
 970   Parent::push_back((Parent::const_reference)x);
 971}
 972
 973template<class T> inline T& VectorPtr<T>::operator[](U32 index)
 974{
 975   return (T&)Parent::operator[](index);
 976}
 977
 978template<class T> inline const T& VectorPtr<T>::operator[](U32 index) const
 979{
 980   return (const T&)Parent::operator[](index);
 981}
 982
 983//------------------------------------------------------------------------------
 984
 985template <class T> class VectorSet : public Vector<T>
 986{
 987public:
 988   void insert(T dat)
 989   {
 990      if(find(this->begin(), this->end(), dat) == this->end())
 991         push_back(dat);
 992   }
 993};
 994
 995// Include vector specializations
 996#ifndef _TVECTORSPEC_H_
 997#include "core/util/tVectorSpecializations.h"
 998#endif
 999
1000#endif //_TVECTOR_H_
1001
1002