Array.h

Go to the documentation of this file.

#ifndef G3D_Array_h
#define G3D_Array_h

#include "G3D/platform.h"
#include "G3D/debug.h"
#include "G3D/MemoryManager.h"
#include "G3D/System.h"
#ifdef G3D_DEBUG
// For formatting error messages
# include "G3D/format.h"
#endif
#include <vector>
#include <algorithm>

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


namespace G3D {

const bool DONT_SHRINK_UNDERLYING_ARRAY = false;

const int SORT_INCREASING = 1;
const int SORT_DECREASING = -1;



template <class T, size_t MIN_ELEMENTS = 10>
class Array {

private:
 static const size_t MIN_BYTES = 32;

 T* data;

 size_t num;
 size_t numAllocated;

 MemoryManager::Ref m_memoryManager;

 void init(size_t n, const MemoryManager::Ref& m) {
 m_memoryManager = m;
 this->num = 0;
 this->numAllocated = 0;
 data = NULL;
 if (n > 0) {
 resize(n);
 } else {
 data = NULL;
 }
 }

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

 inline bool inArray(const T* address) {
 return (address >= data) && (address < data + num);
 }


 static bool __cdecl compareGT(const T& a, const T& b) {
 return a > b;
 }


 void realloc(size_t 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*)m_memoryManager->alloc(sizeof(T) * numAllocated);
 alwaysAssertM(data, "Memory manager returned NULL: out of memory?");

 // Call the copy constructors
 {const size_t N = G3D::min(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();
 }}

 m_memoryManager->free(oldData);
 }

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

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

public:

 typedef T* Iterator;
 typedef const T* ConstIterator;

 typedef Iterator iterator;
 typedef ConstIterator const_iterator;
 typedef T value_type;
 typedef int size_type;
 typedef int difference_type;

 Iterator begin() {
 return data;
 }

 ConstIterator begin() const {
 return data;
 }
 ConstIterator end() const {
 return data + num;
 }

 Iterator end() {
 return data + num;
 }

 T* getCArray() {
 return data;
 }

 static void swap(Array<T, MIN_ELEMENTS>& a, Array<T, MIN_ELEMENTS>& b) {
 alwaysAssertM(a.memoryManager() == b.memoryManager(), "The arrays are required to have the same memory manager");
 std::swap(a.data, b.data);
 std::swap(a.num, b.num);
 std::swap(a.numAllocated, b.numAllocated);
 }

 const T* getCArray() const {
 return data;
 }

 Array() : num(0) {
 init(0, MemoryManager::create());
 }
 

 explicit Array(const T& v0) {
 init(1, MemoryManager::create());
 (*this)[0] = v0;
 }
 
 Array(const T& v0, const T& v1) {
 init(2, MemoryManager::create());
 (*this)[0] = v0;
 (*this)[1] = v1;
 }
 
 Array(const T& v0, const T& v1, const T& v2) {
 init(3, MemoryManager::create());
 (*this)[0] = v0;
 (*this)[1] = v1;
 (*this)[2] = v2;
 }

 Array(const T& v0, const T& v1, const T& v2, const T& v3) {
 init(4, MemoryManager::create());
 (*this)[0] = v0;
 (*this)[1] = v1;
 (*this)[2] = v2;
 (*this)[3] = v3;
 }

 Array(const T& v0, const T& v1, const T& v2, const T& v3, const T& v4) {
 init(5, MemoryManager::create());
 (*this)[0] = v0;
 (*this)[1] = v1;
 (*this)[2] = v2;
 (*this)[3] = v3;
 (*this)[4] = v4;
 }


 //TODO: patch rest of the API to prevent returning Arrays by value, then make explicit 
 Array(const Array& other) : num(0) {
 _copy(other);
 }

 explicit Array(const std::vector<T>& other) : num(0), data(NULL) {
 *this = other;
 }


 /* Sets this to hold the same contents as other, with num = numAllocated (no unused allocated space) */
 void copyFrom(const Array<T>& other) {
 resize(0);
 append(other);
 }


 void copyPOD(const Array<T>& other) {
 if (numAllocated < other.num) {
 m_memoryManager->free(data);
 data = NULL;
 if (other.data) {
 data = (T*)m_memoryManager->alloc(sizeof(T) * other.num);
 }
 numAllocated = other.num;
 }

 num = other.num;
 if (other.data && (num > 0)) {
 System::memcpy(data, other.data, sizeof(T) * num);
 }
 }

 void appendPOD(const Array<T>& other) {
 const size_t oldSize = num;
 num += other.num;
 if (numAllocated < num) {
 alwaysAssertM(other.data, "non-zero array with no allocated space");
 T* old = data;
 data = (T*)m_memoryManager->alloc(sizeof(T) * num);
 System::memcpy(data, old, sizeof(T) * oldSize);
 m_memoryManager->free(old);
 numAllocated = num;
 }
 if (other.data) {
 System::memcpy((data + oldSize), other.data, sizeof(T) * other.num);
 }
 }

 ~Array() {
 // Invoke the destructors on the elements
 for (size_t i = 0; i < num; ++i) {
 (data + i)->~T();
 }
 
 m_memoryManager->free(data);
 // Set to 0 in case this Array is global and gets referenced during app exit
 data = NULL;
 num = 0;
 numAllocated = 0;
 }

 void clear(bool shrink = true) {
 resize(0, shrink);
 }

 void clearAndSetMemoryManager(const MemoryManager::Ref& m) {
 clear();
 debugAssert(data == NULL);
 m_memoryManager = m;
 }

 void fastClear() {
 clear(false);
 }

 inline MemoryManager::Ref memoryManager() const {
 return m_memoryManager;
 }

 inline int size() const {
 return (int)num;
 }

 inline int length() const {
 return size();
 }

 void fastRemove(int index, bool shrinkIfNecessary = false) {
 debugAssert(index < (int)num);
 data[index] = data[num - 1];
 resize(size() - 1, shrinkIfNecessary);
 }


 void insert(int n, const T& value) {
 // Add space for the extra element
 resize(num + 1, false);

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

 void setAll(const T& value) {
 for (size_t i = 0; i < num; ++i) {
 data[i] = value;
 }
 }

 void trimToSize() {
 if (size() != capacity()) {
 size_t oldNum = numAllocated;
 numAllocated = size();
 realloc(oldNum);
 }
 }

 void resize(size_t n, bool shrinkIfNecessary = true) {
 alwaysAssertM(n < 0xFFFFFFFF, "This implementation does not support arrays with more than 2^32 elements, although the size in memory may be larger.");
 if (num == n) {
 return;
 }

 size_t oldNum = num;
 num = n;

 // Call the destructors on newly hidden elements if there are any
 for (size_t i = num; i < oldNum; ++i) {
 (data + i)->~T();
 }
 
 // Once allocated, always maintain MIN_ELEMENTS elements or 32 bytes, whichever is higher.
 const size_t minSize = G3D::max(MIN_ELEMENTS, (size_t)(MIN_BYTES / sizeof(T)));

 if ((MIN_ELEMENTS == 0) && (MIN_BYTES == 0) && (n == 0) && shrinkIfNecessary) {
 // Deallocate the array completely
 numAllocated = 0;
 m_memoryManager->free(data);
 data = NULL;
 return;
 }
 
 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.

 double growFactor = 3.0f;

 size_t oldSizeBytes = numAllocated * sizeof(T);
 if (oldSizeBytes > 10000000) {
 // Conserve memory more tightly above 10 MB
 growFactor = 1.2f;
 } else if (oldSizeBytes > 400000) {
 // Avoid bloat above 400k
 growFactor = 1.5f;
 } else if (oldSizeBytes > 64000) {
 // This is what std:: uses at all times
 growFactor = 2.0f;
 }

 numAllocated = (num - numAllocated) + (size_t)(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(min(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 (size_t i = oldNum; i < num; ++i) {
 new (data + i) T;
 }
 }

 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
 // this simplifies the computation.
 resize(num + 1, DONT_SHRINK_UNDERLYING_ARRAY);
 data[num - 1] = value;
 }
 }


 inline void append(const T& v1, const T& v2) {
 if (inArray(&v1) || inArray(&v2)) {
 // Copy into temporaries so that the references won't break when
 // the array resizes.
 T t1 = v1;
 T t2 = v2;
 append(t1, t2);
 } else if (num + 1 < numAllocated) {
 // This is a simple situation; just stick it in the next free slot using
 // the copy constructor.
 new (data + num) T(v1);
 new (data + num + 1) T(v2);
 num += 2;
 } else {
 // Resize the array. Note that neither value is already in the array.
 resize(num + 2, DONT_SHRINK_UNDERLYING_ARRAY);
 data[num - 2] = v1;
 data[num - 1] = v2;
 }
 }


 inline void append(const T& v1, const T& v2, const T& v3) {
 if (inArray(&v1) || inArray(&v2) || inArray(&v3)) {
 T t1 = v1;
 T t2 = v2;
 T t3 = v3;
 append(t1, t2, t3);
 } else if (num + 2 < numAllocated) {
 // This is a simple situation; just stick it in the next free slot using
 // the copy constructor.
 new (data + num) T(v1);
 new (data + num + 1) T(v2);
 new (data + num + 2) T(v3);
 num += 3;
 } else {
 resize(num + 3, DONT_SHRINK_UNDERLYING_ARRAY);
 data[num - 3] = v1;
 data[num - 2] = v2;
 data[num - 1] = v3;
 }
 }


 inline void append(const T& v1, const T& v2, const T& v3, const T& v4) {
 if (inArray(&v1) || inArray(&v2) || inArray(&v3) || inArray(&v4)) {
 T t1 = v1;
 T t2 = v2;
 T t3 = v3;
 T t4 = v4;
 append(t1, t2, t3, t4);
 } else if (num + 3 < numAllocated) {
 // This is a simple situation; just stick it in the next free slot using
 // the copy constructor.
 new (data + num) T(v1);
 new (data + num + 1) T(v2);
 new (data + num + 2) T(v3);
 new (data + num + 3) T(v4);
 num += 4;
 } else {
 resize(num + 4, DONT_SHRINK_UNDERLYING_ARRAY);
 data[num - 4] = v1;
 data[num - 3] = v2;
 data[num - 2] = v3;
 data[num - 1] = v4;
 }
 }

 void append(const T& v1, const T& v2, const T& v3, const T& v4, const T& v5) {
 if (inArray(&v1) || inArray(&v2) || inArray(&v3) || inArray(&v4) || inArray(&v5)) {
 T t1 = v1;
 T t2 = v2;
 T t3 = v3;
 T t4 = v4;
 T t5 = v5;
 append(t1, t2, t3, t4, t5);
 } else if (num + 4 < numAllocated) {
 // This is a simple situation; just stick it in the next free slot using
 // the copy constructor.
 new (data + num) T(v1);
 new (data + num + 1) T(v2);
 new (data + num + 2) T(v3);
 new (data + num + 3) T(v4);
 new (data + num + 4) T(v5);
 num += 5;
 } else {
 resize(num + 5, DONT_SHRINK_UNDERLYING_ARRAY);
 data[num - 5] = v1;
 data[num - 4] = v2;
 data[num - 3] = v3;
 data[num - 2] = v4;
 data[num - 1] = v5;
 }
 }

 void append(const T& v1, const T& v2, const T& v3, const T& v4, const T& v5, const T& v6) {
 if (inArray(&v1) || inArray(&v2) || inArray(&v3) || inArray(&v4) || inArray(&v5) || inArray(&v6)) {
 T t1 = v1;
 T t2 = v2;
 T t3 = v3;
 T t4 = v4;
 T t5 = v5;
 T t6 = v6;
 append(t1, t2, t3, t4, t5, t6);
 } else if (num + 5 < numAllocated) {
 // This is a simple situation; just stick it in the next free slot using
 // the copy constructor.
 new (data + num) T(v1);
 new (data + num + 1) T(v2);
 new (data + num + 2) T(v3);
 new (data + num + 3) T(v4);
 new (data + num + 4) T(v5);
 new (data + num + 5) T(v6);
 num += 6;
 } else {
 resize(num + 6, DONT_SHRINK_UNDERLYING_ARRAY);
 data[num - 6] = v1;
 data[num - 5] = v2;
 data[num - 4] = v3;
 data[num - 3] = v4;
 data[num - 2] = v5;
 data[num - 1] = v6;
 }
 }
 bool contains(const T& e) const {
 for (int i = 0; i < size(); ++i) {
 if ((*this)[i] == e) {
 return true;
 }
 }

 return false;
 }

 void append(const Array<T>& array) {
 debugAssert(this != &array);
 size_t oldNum = num;
 size_t arrayLength = array.length();

 resize(num + arrayLength, false);

 for (size_t i = 0; i < arrayLength; ++i) {
 data[oldNum + i] = array.data[i];
 }
 }

 inline T& next() {
 resize(num + 1, false);
 return last();
 }

 inline void push(const T& value) {
 append(value);
 }

 inline void push(const Array<T>& array) {
 append(array);
 }

 inline void push_back(const T& v) {
 push(v);
 }

 inline void pop_back() {
 pop();
 }

 int capacity() const {
 return (int)numAllocated;
 }

 T& front() {
 return (*this)[0];
 }

 const T& front() const {
 return (*this)[0];
 }

 T& back() {
 return (*this)[size()-1];
 }

 const T& back() const {
 return (*this)[size()-1];
 }

 inline T pop(bool shrinkUnderlyingArrayIfNecessary = true) {
 debugAssert(num > 0);
 T temp = data[num - 1];
 resize(num - 1, shrinkUnderlyingArrayIfNecessary);
 return temp;
 }

 inline void popDiscard(bool shrinkUnderlyingArrayIfNecessary = false) {
 debugAssert(num > 0);
 resize(num - 1, shrinkUnderlyingArrayIfNecessary);
 }


 void swap(Array<T>& str) {
 Array<T> temp = str;
 str = *this;
 *this = temp;
 }


 inline T& operator[](int n) {
 debugAssertM((n >= 0) && (n < (int)num),
 format("Array index out of bounds. n = %d, size() = %d", (int)n, (int)num));
 debugAssert(data!=NULL);
 return data[n];
 }

 inline T& operator[](uint32 n) {
 debugAssertM(n < (uint32)num, format("Array index out of bounds. n = %d, size() = %d",
 (int)n, (int)num));
 return data[n];
 }
 
 inline T& operator[](uint64 n) {
 debugAssertM(n < (uint64)num, format("Array index out of bounds. n = %d, size() = %d", (int)n, (int)num));
 return data[n];
 }

 inline const T& operator[](int n) const {
 debugAssert((n >= 0) && (n < (int)num));
 debugAssert(data != NULL);
 return data[n];
 }

 inline const T& operator[](uint32 n) const {
 debugAssert((n < (uint32)num));
 debugAssert(data!=NULL);
 return data[n];
 }

 inline const T& operator[](uint64 n) const {
 debugAssert((n < (uint64)num));
 debugAssert(data!=NULL);
 return data[n];
 }

 inline T& randomElement() {
 debugAssert(num > 0);
 debugAssert(data!=NULL);
 return data[iRandom(0, (int)num - 1)];
 }

 inline const T& randomElement() const {
 debugAssert(num > 0);
 debugAssert(data!=NULL);
 return data[iRandom(0, num - 1)];
 }

 inline const T& last() const {
 debugAssert(num > 0);
 debugAssert(data!=NULL);
 return data[num - 1];
 }

 inline T& last() {
 debugAssert(num > 0);
 debugAssert(data!=NULL);
 return data[num - 1];
 }

 inline int lastIndex() const {
 debugAssertM(num > 0, "Array is empty");
 return num - 1;
 }

 inline int firstIndex() const {
 debugAssertM(num > 0, "Array is empty");
 return 0;
 }

 inline T& first() {
 debugAssertM(num > 0, "Array is empty");
 return data[0];
 }

 inline const T& first() const {
 debugAssertM(num > 0, "Array is empty");
 return data[0];
 }

 inline int middleIndex() const {
 debugAssertM(num > 0, "Array is empty");
 return num >> 1;
 }

 inline const T& middle() const {
 debugAssertM(num > 0, "Array is empty");
 return data[num >> 1]; 
 }

 inline T& middle() {
 debugAssertM(num > 0, "Array is empty");
 return data[num >> 1]; 
 }

 void invokeDeleteOnAllElements() {
 for (size_t i = 0; i < num; ++i) {
 delete data[i];
 }
 resize(0);
 }

 void G3D_DEPRECATED deleteAll() {
 invokeDeleteOnAllElements();
 }

 int rfindIndex(const T& value) const {
 for (int i = num -1 ; i >= 0; --i) {
 if (data[i] == value) {
 return i;
 }
 }
 return -1;
 }

 int findIndex(const T& value) const {
 for (size_t i = 0; i < num; ++i) {
 if (data[i] == value) {
 return (int)i;
 }
 }
 return -1;
 }

 Iterator find(const T& value) {
 for (int i = 0; i < num; ++i) {
 if (data[i] == value) {
 return data + i;
 }
 }
 return end();
 }

 ConstIterator find(const T& value) const {
 for (int i = 0; i < num; ++i) {
 if (data[i] == value) {
 return data + i;
 }
 }
 return end();
 }

 void remove(Iterator element, int count = 1) {
 debugAssert((element >= begin()) && (element < end()));
 debugAssert((count > 0) && (element + count) <= end());
 Iterator last = end() - count;

 while(element < last) {
 element[0] = element[count];
 ++element;
 }
 
 resize(num - count);
 }

 void remove(int index, int count = 1) {
 debugAssert((index >= 0) && (index < (int)num));
 debugAssert((count > 0) && (index + count <= (int)num));
 
 remove(begin() + index, count);
 }

 void reverse() {
 T temp;
 
 size_t n2 = num / 2;
 for (size_t i = 0; i < n2; ++i) {
 temp = data[num - 1 - i];
 data[num - 1 - i] = data[i];
 data[i] = temp;
 }
 }

 // void sort(bool (__cdecl *lessThan)(const T& elem1, const T& elem2)) {
 // std::sort(data, data + num, lessThan);
 //}
 template<class LessThan>
 void sort(const LessThan& lessThan) {
 // Using std::sort, which according to http://www.open-std.org/JTC1/SC22/WG21/docs/D_4.cpp
 // was 2x faster than qsort for arrays around size 2000 on intel core2 with gcc
 std::sort(data, data + num, lessThan);
 }

 void sort(int direction = SORT_INCREASING) {
 if (direction == SORT_INCREASING) {
 std::sort(data, data + num);
 } else {
 std::sort(data, data + num, compareGT);
 }
 }

 void sortSubArray(int beginIndex, int endIndex, int direction = SORT_INCREASING) {
 if (direction == SORT_INCREASING) {
 std::sort(data + beginIndex, data + endIndex + 1);
 } else {
 std::sort(data + beginIndex, data + endIndex + 1, compareGT);
 }
 }

 void sortSubArray(int beginIndex, int endIndex, bool (__cdecl *lessThan)(const T& elem1, const T& elem2)) {
 std::sort(data + beginIndex, data + endIndex + 1, lessThan);
 }

 template<typename StrictWeakOrdering>
 void sortSubArray(int beginIndex, int endIndex, StrictWeakOrdering& lessThan) {
 std::sort(data + beginIndex, data + endIndex + 1, lessThan);
 }

 class DefaultComparator {
 public:
 inline int operator()(const T& A, const T& B) const {
 if (A < B) {
 return 1;
 } else if (A == B) {
 return 0;
 } else {
 return -1;
 }
 }
 };

 template<typename Comparator>
 void partition(
 const T& partitionElement, 
 Array<T>& ltArray,
 Array<T>& eqArray,
 Array<T>& gtArray,
 const Comparator& comparator) const {

 // Make sure all arrays are independent
 debugAssert(&ltArray != this);
 debugAssert(&eqArray != this);
 debugAssert(&gtArray != this);
 debugAssert(&ltArray != &eqArray);
 debugAssert(&ltArray != &gtArray);
 debugAssert(&eqArray != &gtArray);

 // Clear the arrays
 ltArray.fastClear();
 eqArray.fastClear();
 gtArray.fastClear();

 // Form a table of buckets for lt, eq, and gt
 Array<T>* bucket[3] = {&ltArray, &eqArray, &gtArray};

 for (size_t i = 0; i < num; ++i) {
 int c = comparator(partitionElement, data[i]);
 debugAssertM(c >= -1 && c <= 1, "Comparator returned an illegal value.");

 // Insert into the correct bucket, 0, 1, or 2
 bucket[c + 1]->append(data[i]);
 }
 }

 void partition(
 const T& partitionElement, 
 Array<T>& ltArray,
 Array<T>& eqArray,
 Array<T>& gtArray) const {

 partition(partitionElement, ltArray, eqArray, gtArray, typename Array<T>::DefaultComparator());
 }

 template<typename Comparator>
 void medianPartition(
 Array<T>& ltMedian, 
 Array<T>& eqMedian, 
 Array<T>& gtMedian,
 Array<T>& tempArray,
 const Comparator& comparator) const {

 ltMedian.fastClear();
 eqMedian.fastClear();
 gtMedian.fastClear();

 // Handle trivial cases first
 switch (size()) {
 case 0:
 // Array is empty; no parition is possible
 return;

 case 1:
 // One element
 eqMedian.append(first());
 return;

 case 2:
 {
 // Two element array; median is the smaller
 int c = comparator(first(), last());
 
 switch (c) {
 case -1:
 // first was bigger
 eqMedian.append(last());
 gtMedian.append(first());
 break;

 case 0:
 // Both equal to the median
 eqMedian.append(first(), last());
 break;

 case 1:
 // Last was bigger
 eqMedian.append(first());
 gtMedian.append(last());
 break;
 }
 }
 return;
 }

 // All other cases use a recursive randomized median

 // Number of values less than all in the current arrays 
 int ltBoost = 0;

 // Number of values greater than all in the current arrays 
 int gtBoost = 0;

 // For even length arrays, force the gt array to be one larger than the
 // lt array: 
 // [1 2 3] size = 3, choose half = (s + 1) /2
 //
 int lowerHalfSize, upperHalfSize;
 if (isEven(size())) {
 lowerHalfSize = size() / 2;
 upperHalfSize = lowerHalfSize + 1;
 } else {
 lowerHalfSize = upperHalfSize = (size() + 1) / 2;
 }
 const T* xPtr = NULL;

 // Maintain pointers to the arrays; we'll switch these around during sorting
 // to avoid copies.
 const Array<T>* source = this;
 Array<T>* lt = &ltMedian;
 Array<T>* eq = &eqMedian;
 Array<T>* gt = &gtMedian;
 Array<T>* extra = &tempArray;

 while (true) {
 // Choose a random element -- choose the middle element; this is theoretically
 // suboptimal, but for loosly sorted array is actually the best strategy

 xPtr = &(source->middle());
 if (source->size() == 1) {
 // Done; there's only one element left
 break;
 }
 const T& x = *xPtr;

 // Note: partition (fast) clears the arrays for us
 source->partition(x, *lt, *eq, *gt, comparator);

 int L = lt->size() + ltBoost + eq->size();
 int U = gt->size() + gtBoost + eq->size();
 if ((L >= lowerHalfSize) &&
 (U >= upperHalfSize)) {

 // x must be the partition median 
 break;

 } else if (L < lowerHalfSize) {

 // x must be smaller than the median. Recurse into the 'gt' array.
 ltBoost += lt->size() + eq->size();

 // The new gt array will be the old source array, unless
 // that was the this pointer (i.e., unless we are on the 
 // first iteration)
 Array<T>* newGt = (source == this) ? extra : const_cast<Array<T>*>(source);
 
 // Now set up the gt array as the new source
 source = gt;
 gt = newGt;

 } else {

 // x must be bigger than the median. Recurse into the 'lt' array.
 gtBoost += gt->size() + eq->size();

 // The new lt array will be the old source array, unless
 // that was the this pointer (i.e., unless we are on the 
 // first iteration)
 Array<T>* newLt = (source == this) ? extra : const_cast<Array<T>*>(source);
 
 // Now set up the lt array as the new source
 source = lt;
 lt = newLt;
 }
 }

 // Now that we know the median, make a copy of it (since we're about to destroy the array that it
 // points into).
 T median = *xPtr;
 xPtr = NULL;

 // Partition the original array (note that this fast clears for us)
 partition(median, ltMedian, eqMedian, gtMedian, comparator);
 }

 void medianPartition(
 Array<T>& ltMedian, 
 Array<T>& eqMedian, 
 Array<T>& gtMedian) const {

 Array<T> temp;
 medianPartition(ltMedian, eqMedian, gtMedian, temp, DefaultComparator());
 }

 


 void randomize() {
 T temp;

 for (int i = size() - 1; i >= 0; --i) {
 int x = iRandom(0, i);

 temp = data[i];
 data[i] = data[x];
 data[x] = temp;
 }
 }


 void reserve(int n) {
 debugAssert(n >= size());
 const int oldSize = size();
 resize(n);
 resize(oldSize, false);
 }

 size_t sizeInMemory() const {
 return sizeof(Array<T>) + (sizeof(T) * numAllocated);
 }

 void removeNulls() {
 int nextNull = 0;
 for (int i = 0; i < size(); ++i) {
 if (notNull(data[i])) {
 if (i > nextNull) {
 // Move value i down to squeeze out NULLs
 data[nextNull] = data[i];
 }
 ++nextNull;
 }
 }

 resize(nextNull, false);
 }
};


template<class T> bool contains(const T* array, int len, const T& e) {
 for (int i = len - 1; i >= 0; --i) {
 if (array[i] == e) {
 return true;
 }
 }
 return false;
}

} // namespace

#ifdef _MSC_VER
# pragma warning (pop)
#endif

#endif