array.h

WOW 服务模拟端 支持2.4.3版本 来自开源的ASCENT 自己REPACK

/** 
  @file Array.h
 
  @maintainer Morgan McGuire, graphics3d.com
  @cite Portions written by Aaron Orenstein, [e-mail]
 
  @created 2001-03-11
  @edited  2005-09-12

  Copyright 2000-2005, Morgan McGuire.
  All rights reserved.
 */

#ifndef G3D_ARRAY_H
#define G3D_ARRAY_H

#include "G3D/platform.h"
#include "G3D/debug.h"
#include "G3D/System.h"
#include <vector>
#include <algorithm>

#ifdef G3D_WIN32
#   include <new>
    
#   pragma warning (push)
    // debug information too long
#   pragma warning( disable : 4312)
#   pragma warning( disable : 4786)
#endif


namespace G3D {

/**
 Constant for passing to Array::resize
 */
const bool DONT_SHRINK_UNDERLYING_ARRAY = false;

/** Constant for Array::sort */
const int SORT_INCREASING = 1;
/** Constant for Array::sort */
const int SORT_DECREASING = -1;

/**
 Dynamic 1D array.  

 Objects must have a default constructor (constructor that
 takes no arguments) in order to be used with this template.
 You will get the error "no appropriate default constructor found"
 if they do not.

 Do not use with objects that overload placement <code>operator new</code>,
 since the speed of Array is partly due to pooled allocation.

 If SSE is defined Arrays allocate the first element aligned to
 16 bytes.


 Array is highly optimized compared to std::vector.  
 Array operations are less expensive than on std::vector and for large
 amounts of data, Array consumes only 1.5x the total size of the 
 data, while std::vector consumes 2.0x.  The default
 array takes up zero heap space.  The first resize (or append)
 operation grows it to a reasonable internal size so it is efficient
 to append to small arrays.  Memory is allocated using
 System::alignedMalloc, which produces pointers aligned to 16-byte
 boundaries for use with SSE instructions and uses pooled storage for
 fast allocation.  When Array needs to copy
 data internally on a resize operation it correctly invokes copy
 constructors of the elements (the MSVC6 implementation of
 std::vector uses realloc, which can create memory leaks for classes
 containing references and pointers).  Array provides a guaranteed
 safe way to access the underlying data as a flat C array --
 Array::getCArray.  Although (T*)std::vector::begin() can be used for
 this purpose, it is not guaranteed to succeed on all platforms.

 Do not subclass an Array.
 */
template <class T>
class Array {
private:
    /** 0...num-1 are initialized elements, num...numAllocated-1 are not */
    T*              data;

    int             num;
    int             numAllocated;

    void init(int n, int a) {
        debugAssert(n <= a);
        debugAssert(n >= 0);
        this->num = 0;
        this->numAllocated = 0;
        data = NULL;
        if (a > 0) {
            resize(n);
        } else {
            data = NULL;
        }
    }

    void _copy(const Array &other) {
        init(other.num, other.num);
        for (int i = 0; i < num; i++) {
            data[i] = other.data[i];
        }
    }

    /**
     Returns true iff address points to an element of this array.
     Used by append.
     */
    inline bool inArray(const T* address) {
        return (address >= data) && (address < data + num);
    }


    /** Only compiled if you use the sort procedure. */
    static bool compareGT(const T& a, const T& b) {
        return a > b;
    }


    /**
     Allocates a new array of size numAllocated (not a parameter to the method) 
     and then copies at most oldNum elements from the old array to it.  Destructors are
     called for oldNum elements of the old array.
     */
    void realloc(int oldNum) {
         T* oldData = data;
         
         // The allocation is separate from the constructor invocation because we don't want 
         // to pay for the cost of constructors until the newly allocated
         // elements are actually revealed to the application.  They 
         // will be constructed in the resize() method.

         data = (T*)System::alignedMalloc(sizeof(T) * numAllocated, 16);

         // Call the copy constructors
         {const int N = iMin(oldNum, numAllocated);
          const T* end = data + N;
          T* oldPtr = oldData;
          for (T* ptr = data; ptr < end; ++ptr, ++oldPtr) {

             // Use placement new to invoke the constructor at the location
             // that we determined.  Use the copy constructor to make the assignment.
             const T* constructed = new (ptr) T(*oldPtr);

             (void)constructed;
             debugAssertM(constructed == ptr, 
                 "new returned a different address than the one provided by Array.");
         }}

         // Call destructors on the old array (if there is no destructor, this will compile away)
         {const T* end = oldData + oldNum;
          for (T* ptr = oldData; ptr < end; ++ptr) {
              ptr->~T();
         }}


         System::alignedFree(oldData);
    }

public:

    /**
     C++ STL style iterator variable.  Call begin() to get 
     the first iterator, pre-increment (++i) the iterator to get to
     the next value.  Use dereference (*i) to access the element.
     */
    typedef T* Iterator;
    typedef const T* ConstIterator;

    /**
     C++ STL style iterator method.  Returns the first iterator element.
     Do not change the size of the array while iterating.
     */
    Iterator begin() {
        return data;
    }

    ConstIterator begin() const {
        return data;
    }
    /**
     C++ STL style iterator method.  Returns one after the last iterator
     element.
     */
    ConstIterator end() const {
        return data + num;
    }

    Iterator end() {
        return data + num;
    }

   /**
    The array returned is only valid until the next append() or resize call, or 
	the Array is deallocated.
    */
   T* getCArray() {
       return data;
   }

   /**
    The array returned is only valid until the next append() or resize call, or 
	the Array is deallocated.
    */
   const T* getCArray() const {
       return data;
   }

   /** Creates a zero length array (no heap allocation occurs until resize). */
   Array() {
       init(0, 0);
   }

   /**
    Creates an array of size.
    */
   Array(int size) {
       init(size, size);
   }

   /**
    Copy constructor
    */
   Array(const Array& other) {
       _copy(other);
   }

   /**
    Destructor does not delete() the objects if T is a pointer type
    (e.g. T = int*) instead, it deletes the <B>pointers themselves</B> and 
    leaves the objects.  Call deleteAll if you want to dealocate
    the objects referenced.  Do not call deleteAll if <CODE>T</CODE> is not a pointer
    type (e.g. do call Array<Foo*>::deleteAll, do <B>not</B> call Array<Foo>::deleteAll).
    */
   ~Array() {
       // Invoke the destructors on the elements
       for (int i = 0; i < num; i++) {
           (data + i)->~T();
       }
       
       System::alignedFree(data);
       // Set to 0 in case this Array is global and gets referenced during app exit
       data = NULL;
	   num = 0;
       numAllocated = 0;
   }


   /**
    Removes all elements.  Use resize(0, false) or fastClear if you want to 
    remove all elements without deallocating the underlying array
    so that future append() calls will be faster.
    */
   void clear() {
       resize(0);
   }

   /** resize(0, false) */
   void fastClear() {
       resize(0, false);
   }

   /**
    Assignment operator.
    */
   Array& operator=(const Array& other) {
       resize(other.num);
       for (int i = 0; i < num; ++i) {
           data[i] = other[i];
       }
       return *this;
   }

   Array& operator=(const std::vector<T>& other) {
       resize((int)other.size());
       for (int i = 0; i < num; ++i) {
           data[i] = other[i];
       }
       return *this;
   }

   /**
    Number of elements in the array.
    */
   inline int size() const {
      return num;
   }

   /**
    Number of elements in the array.  (Same as size; this is just
    here for convenience).
    */
   inline int length() const {
      return size();
   }

   /**
    Swaps element index with the last element in the array then
    shrinks the array by one.
    */
   void fastRemove(int index) {
       debugAssert(index >= 0);
       debugAssert(index < num);
       data[index] = data[num - 1];
       resize(size() - 1);
   }

   /**
    Resizes, calling the default constructor for 
    newly created objects and shrinking the underlying
    array as needed (and calling destructors as needed).
    */
   void resize(int n) {
      resize(n, true);
   }


   /**
    Inserts at the specified index and shifts all other elements up by one.
    */
   void insert(int n, const T& value) {
       // Add space for the extra element
       resize(num + 1, false);

       for (int i = num - 1; i > n; --i) {
           data[i] = data[i - 1];
       }
       data[n] = value;
   }


   void resize(int n, bool shrinkIfNecessary) {
      int oldNum = num;
      num = n;

      // Call the destructors on newly hidden elements if there are any
      for (int i = num; i < oldNum; ++i) {
          (data + i)->~T();
      }

      // Once allocated, always maintain 10 elements or 32 bytes, whichever is higher.
      static const int minSize = iMax(10, 32 / sizeof(T));

      if (num > numAllocated) {
          // Grow the underlying array

          if (numAllocated == 0) {
              // First allocation; grow to exactly the size requested to avoid wasting space.
              numAllocated = n;
              debugAssert(oldNum == 0);
              realloc(oldNum);
          } else {
         
              if (num < minSize) {
                  // Grow to at least the minimum size
                  numAllocated = minSize;

              } else {

                  // Increase the underlying size of the array.  Grow aggressively
                  // up to 64k, less aggressively up to 400k, and then grow relatively
                  // slowly (1.5x per resize) to avoid excessive space consumption.
                  //
                  // These numbers are tweaked according to performance tests.

                  float growFactor = 3.0;

                  size_t oldSizeBytes = numAllocated * sizeof(T);
                  if (oldSizeBytes > 400000) {
                      // Avoid bloat
                      growFactor = 1.5;
                  } else if (oldSizeBytes > 64000) {
                      // This is what std:: uses at all times
                      growFactor = 2.0;
                  }

                  numAllocated = (num - numAllocated) + (int)(numAllocated * growFactor);

                  if (numAllocated < minSize) {
                      numAllocated = minSize;
                  }
              }

              realloc(oldNum);
          }

      } else if ((num <= numAllocated / 3) && shrinkIfNecessary && (num > minSize)) {
          // Shrink the underlying array

          // Only copy over old elements that still remain after resizing
          // (destructors were called for others if we're shrinking)
          realloc(iMin(num, oldNum));

      }

      // Call the constructors on newly revealed elements.
      // Do not use parens because we don't want the intializer
      // invoked for POD types.
      for (int i = oldNum; i < num; ++i) {
          new (data + i) T;
      }
   }

    /**
     Add an element to the end of the array.  Will not shrink the underlying array
     under any circumstances.  It is safe to append an element that is already
     in the array.
     */
    inline void append(const T& value) {
        
        if (num < numAllocated) {
            // This is a simple situation; just stick it in the next free slot using
            // the copy constructor.
            new (data + num) T(value);
            ++num;
        } else if (inArray(&value)) {
            // The value was in the original array; resizing
            // is dangerous because it may move the value
            // we have a reference to.
            T tmp = value;
            append(tmp);
        } else {
            // Here we run the empty initializer where we don't have to, but