jeanlemotan
962 lines
33 KiB
C++
962 lines
33 KiB
C++
/////////////////////////////////////////////////////////////////////////////
|
|
// Copyright (c) Electronic Arts Inc. All rights reserved.
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
|
|
|
|
#include <EABase/eabase.h>
|
|
|
|
// Some versions of GCC generate an array bounds warning in opt builds which
|
|
// doesn't say what line below it comes from and doesn't appear to be a valid
|
|
// warning. In researching this on the Internet it appears that this is a
|
|
// known problem with GCC.
|
|
#if defined(EA_DISABLE_GCC_WARNING)
|
|
EA_DISABLE_GCC_WARNING(-Warray-bounds)
|
|
#endif
|
|
|
|
#include "EASTLTest.h"
|
|
#include <EASTL/sort.h>
|
|
#include <EASTL/bonus/sort_extra.h>
|
|
#include <EASTL/vector.h>
|
|
#include <EASTL/list.h>
|
|
#include <EASTL/deque.h>
|
|
#include <EASTL/algorithm.h>
|
|
#include <EASTL/allocator.h>
|
|
#include <EASTL/numeric.h>
|
|
#include <EASTL/random.h>
|
|
#include <EABase/eahave.h>
|
|
#include <cmath>
|
|
|
|
|
|
namespace eastl
|
|
{
|
|
namespace Internal
|
|
{
|
|
typedef eastl::vector<int> IntArray;
|
|
typedef eastl::vector<IntArray> IntArrayArray;
|
|
|
|
|
|
// IntArrayCompare
|
|
// Used to compare IntArray objects.
|
|
struct IntArrayCompare
|
|
{
|
|
bool operator()(const IntArray& a, const IntArray& b)
|
|
{ return a.front() < b.front(); }
|
|
};
|
|
|
|
|
|
// SafeFloatCompare
|
|
//
|
|
// Float comparison has a problem for the case that either of the floats are a NaN.
|
|
// If you use a NaN in a sort function that uses default floating point comparison then
|
|
// you will get undefined behavior, as all NaNs compare false. This compare function
|
|
// class sorts floats such that all negative NaNs sort lower than all integers, and all
|
|
// positive NaNs sort higher than all integers.
|
|
//
|
|
// Example usage:
|
|
// eastl::sort(floatArray.begin(), floatArray.end(), SafeFloatCompare());
|
|
//
|
|
struct SafeFloatCompare
|
|
{
|
|
union FloatInt32{ float f; int32_t i; };
|
|
|
|
bool operator()(float a, float b) const
|
|
{
|
|
#if defined(EA_HAVE_ISNAN)
|
|
bool aNan = (EA_HAVE_ISNAN(a) != 0);
|
|
bool bNan = (EA_HAVE_ISNAN(b) != 0);
|
|
#else
|
|
bool aNan = (a != a); // This works as long as the compiler doesn't do any tricks to optimize it away.
|
|
bool bNan = (b != b);
|
|
#endif
|
|
|
|
if(!aNan && !bNan)
|
|
return (a < b);
|
|
|
|
FloatInt32 fia = { a };
|
|
FloatInt32 fib = { b };
|
|
|
|
if(aNan)
|
|
{
|
|
if(bNan)
|
|
return (fia.i < fib.i); // Both are NaNs, so do a binary compare.
|
|
else
|
|
return (fia.i < 0); // All negative NaNs are assumed to be less than all non-NaNs.
|
|
}
|
|
else
|
|
return (0 < fib.i); // All negative NaNs are assumed to be less than all non-NaNs.
|
|
}
|
|
};
|
|
|
|
|
|
|
|
// StatefulCompare
|
|
// Used to verify that sort<int, StatefulCompare&>() respects the
|
|
// fact that StatefulCompare is passed by reference instead of by value.
|
|
// All existing commercial STL implementations fail to do what the user
|
|
// wants and instead pass around the compare object by value, even if
|
|
// the user specifically asks to use it by reference. EASTL doesn't
|
|
// have this problem.
|
|
struct StatefulCompare
|
|
{
|
|
static int nCtorCount;
|
|
static int nDtorCount;
|
|
static int nCopyCount;
|
|
|
|
StatefulCompare()
|
|
{ nCtorCount++; }
|
|
|
|
StatefulCompare(StatefulCompare&)
|
|
{ nCopyCount++; }
|
|
|
|
~StatefulCompare()
|
|
{ nDtorCount++; }
|
|
|
|
StatefulCompare& operator=(const StatefulCompare&)
|
|
{ nCopyCount++; return *this; }
|
|
|
|
bool operator()(int a, int b)
|
|
{ return a < b; }
|
|
|
|
static void Reset()
|
|
{ nCtorCount = 0; nDtorCount = 0; nCopyCount = 0; }
|
|
};
|
|
|
|
int StatefulCompare::nCtorCount = 0;
|
|
int StatefulCompare::nDtorCount = 0;
|
|
int StatefulCompare::nCopyCount = 0;
|
|
|
|
|
|
// TestObjectPtrCompare
|
|
// Used to compare sorted objects by pointer instead of value.
|
|
struct TestObjectPtrCompare
|
|
{
|
|
bool operator()(TestObject* a, TestObject* b)
|
|
{ return a->mX < b->mX; }
|
|
};
|
|
|
|
|
|
// TestObjectIndexCompare
|
|
// Used to compare sorted objects by array index instead of value.
|
|
struct TestObjectIndexCompare
|
|
{
|
|
vector<TestObject>* mpArray;
|
|
|
|
TestObjectIndexCompare(vector<TestObject>* pArray) : mpArray(pArray) { }
|
|
TestObjectIndexCompare(const TestObjectIndexCompare& x) : mpArray(x.mpArray){ }
|
|
TestObjectIndexCompare& operator=(const TestObjectIndexCompare& x) { mpArray = x.mpArray; return *this; }
|
|
|
|
bool operator()(eastl_size_t a, eastl_size_t b)
|
|
{ return (*mpArray)[a] < (*mpArray)[b]; }
|
|
};
|
|
|
|
// Radix sort elements
|
|
template <typename Key>
|
|
struct RadixSortElement
|
|
{
|
|
typedef Key radix_type;
|
|
Key mKey;
|
|
uint16_t mData;
|
|
|
|
bool operator<(const RadixSortElement<Key> &other) const
|
|
{
|
|
return mKey < other.mKey;
|
|
}
|
|
};
|
|
|
|
typedef RadixSortElement<uint8_t> RadixSortElement8;
|
|
typedef RadixSortElement<uint16_t> RadixSortElement16;
|
|
typedef RadixSortElement<uint32_t> RadixSortElement32;
|
|
|
|
template <typename integer_type>
|
|
struct identity_extract_radix_key
|
|
{
|
|
typedef integer_type radix_type;
|
|
|
|
const radix_type operator()(const integer_type& x) const
|
|
{
|
|
return x;
|
|
}
|
|
};
|
|
|
|
struct TestNoLessOperator
|
|
{
|
|
int i {};
|
|
};
|
|
} // namespace Internal
|
|
|
|
template <>
|
|
struct less<Internal::TestNoLessOperator>
|
|
{
|
|
bool operator()(const Internal::TestNoLessOperator& lhs, const Internal::TestNoLessOperator& rhs) const noexcept
|
|
{
|
|
return lhs.i < rhs.i;
|
|
}
|
|
};
|
|
|
|
} // namespace eastl
|
|
|
|
int TestSort()
|
|
{
|
|
using namespace eastl;
|
|
using namespace Internal;
|
|
|
|
int nErrorCount = 0;
|
|
|
|
EASTLTest_Rand rng(EA::UnitTest::GetRandSeed());
|
|
|
|
{
|
|
// is_sorted
|
|
int array[] = { 0, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 2, 2, 1, 0 };
|
|
|
|
EATEST_VERIFY( is_sorted(array + 0, array + 0));
|
|
EATEST_VERIFY( is_sorted(array + 2, array + 4));
|
|
EATEST_VERIFY( is_sorted(array + 0, array + 10));
|
|
EATEST_VERIFY(!is_sorted(array + 0, array + 14));
|
|
EATEST_VERIFY( is_sorted(array + 11, array + 23, eastl::greater<int>()));
|
|
}
|
|
|
|
{
|
|
// is_sorted_until
|
|
int sorted[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
|
|
int notsorted[] = { 0, 1, 2, 3, 4, 42, 6, 7, 8, 9 };
|
|
|
|
EATEST_VERIFY( is_sorted_until(sorted + EAArrayCount(sorted), sorted + EAArrayCount(sorted)) == sorted + EAArrayCount(sorted) );
|
|
EATEST_VERIFY( is_sorted_until(sorted , sorted + EAArrayCount(sorted)) == sorted + EAArrayCount(sorted) );
|
|
|
|
EATEST_VERIFY( is_sorted_until(sorted + 0, sorted + 0) == sorted );
|
|
EATEST_VERIFY( is_sorted_until(sorted + 2, sorted + 8) == sorted + 8 );
|
|
|
|
EATEST_VERIFY( is_sorted_until(notsorted + 2, notsorted + 8) == notsorted + 6 );
|
|
|
|
// is_sorted_until (with compare function)
|
|
EATEST_VERIFY( is_sorted_until(sorted + EAArrayCount(sorted), sorted + EAArrayCount(sorted), eastl::less<int>()) == sorted + EAArrayCount(sorted) );
|
|
EATEST_VERIFY( is_sorted_until(notsorted + 2, notsorted + 8, eastl::less<int>()) == notsorted + 6 );
|
|
}
|
|
|
|
// Sort arrays of size 0 - N. Sort M random permutations of each.
|
|
{
|
|
vector<int64_t> intArray, intArraySaved;
|
|
|
|
for(int i = 0; i < (150 + (gEASTL_TestLevel * 200)); i += (i < 5) ? 1 : 37) // array sizes of 0 to 300 - 2100, depending on test level.
|
|
{
|
|
// intArraySaved.clear(); // Do we want to do this?
|
|
|
|
for(int n = 0; n < i; n++)
|
|
{
|
|
intArraySaved.push_back(n);
|
|
|
|
if(rng.RandLimit(10) == 0)
|
|
{
|
|
intArraySaved.push_back(n);
|
|
|
|
if(rng.RandLimit(5) == 0)
|
|
intArraySaved.push_back(n);
|
|
}
|
|
}
|
|
const int64_t expectedSum = eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0));
|
|
|
|
for(int j = 0; j < 300 + (gEASTL_TestLevel * 50); j++)
|
|
{
|
|
eastl::random_shuffle(intArraySaved.begin(), intArraySaved.end(), rng);
|
|
|
|
intArray = intArraySaved;
|
|
bubble_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
shaker_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
insertion_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
selection_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
shell_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
comb_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
heap_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
merge_sort(intArray.begin(), intArray.end(), *get_default_allocator((EASTLAllocatorType*)NULL));
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
vector<int64_t> buffer(intArray.size());
|
|
merge_sort_buffer(intArray.begin(), intArray.end(), buffer.data());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
quick_sort(intArray.begin(), intArray.end());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
|
|
intArray = intArraySaved;
|
|
buffer.resize(intArray.size()/2);
|
|
tim_sort_buffer(intArray.begin(), intArray.end(), buffer.data());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Test tim sort with a specific array size and seed that caused a crash
|
|
{
|
|
vector<int64_t> intArray;
|
|
int i = 1000000;
|
|
{
|
|
EASTLTest_Rand testRng(232526);
|
|
|
|
for (int n = 0; n < i; n++)
|
|
{
|
|
intArray.push_back(testRng.Rand());
|
|
}
|
|
vector<int64_t> buffer(intArray.size() / 2);
|
|
tim_sort_buffer(intArray.begin(), intArray.end(), buffer.data());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
}
|
|
}
|
|
|
|
// Test insertion_sort() does not invalidate a BidirectionalIterator by doing --BidirectionalIterator.begin()
|
|
{
|
|
// Test Passes if the Test doesn't crash
|
|
eastl::deque<int> deque;
|
|
deque.push_back(1);
|
|
|
|
insertion_sort(deque.begin(), deque.end());
|
|
|
|
insertion_sort(deque.begin(), deque.end(), eastl::less<int>{});
|
|
}
|
|
|
|
|
|
// TestObject sorting
|
|
TestObject::Reset();
|
|
{
|
|
vector<TestObject> toArray, toArraySaved;
|
|
|
|
for(int i = 0; i < (150 + (gEASTL_TestLevel * 200)); i += (i < 5) ? 1 : 37) // array sizes of 0 to 300 - 2100, depending on test level.
|
|
{
|
|
for(int n = 0; n < i; n++)
|
|
{
|
|
toArraySaved.push_back(TestObject(n));
|
|
|
|
if(rng.RandLimit(10) == 0)
|
|
{
|
|
toArraySaved.push_back(TestObject(n));
|
|
|
|
if(rng.RandLimit(5) == 0)
|
|
toArraySaved.push_back(TestObject(n));
|
|
}
|
|
}
|
|
|
|
for(int j = 0; j < 300 + (gEASTL_TestLevel * 50); j++)
|
|
{
|
|
eastl::random_shuffle(toArraySaved.begin(), toArraySaved.end(), rng);
|
|
|
|
toArray = toArraySaved;
|
|
bubble_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
shaker_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
insertion_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
selection_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
shell_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
comb_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
heap_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
// Not ready yet:
|
|
toArray = toArraySaved;
|
|
merge_sort(toArray.begin(), toArray.end(), *get_default_allocator((EASTLAllocatorType*)NULL));
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
quick_sort(toArray.begin(), toArray.end());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
|
|
toArray = toArraySaved;
|
|
vector<TestObject> buffer(toArray.size()/2);
|
|
tim_sort_buffer(toArray.begin(), toArray.end(), buffer.data());
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
|
|
}
|
|
}
|
|
}
|
|
|
|
// Test that stable sorting algorithms are actually stable
|
|
{
|
|
struct StableSortTestObj
|
|
{
|
|
StableSortTestObj()
|
|
{
|
|
}
|
|
|
|
StableSortTestObj(int value)
|
|
:value(value)
|
|
,initialPositionIndex(0)
|
|
{
|
|
}
|
|
|
|
int value;
|
|
size_t initialPositionIndex;
|
|
};
|
|
|
|
// During the test this comparison is used to sort elements based on value.
|
|
struct StableSortCompare
|
|
{
|
|
bool operator()(const StableSortTestObj& a, const StableSortTestObj& b)
|
|
{
|
|
return a.value < b.value;
|
|
}
|
|
};
|
|
|
|
// During the test this comparison is used to verify the sort was a stable sort. i.e. if values are the same then
|
|
// their relative position should be maintained.
|
|
struct StableSortCompareForStability
|
|
{
|
|
bool operator()(const StableSortTestObj& a, const StableSortTestObj& b)
|
|
{
|
|
if (a.value != b.value)
|
|
{
|
|
return a.value < b.value;
|
|
}
|
|
else
|
|
{
|
|
return a.initialPositionIndex < b.initialPositionIndex;
|
|
}
|
|
}
|
|
};
|
|
|
|
vector<StableSortTestObj> toArray, toArraySaved;
|
|
StableSortCompare compare;
|
|
StableSortCompareForStability compareForStability;
|
|
|
|
for (int i = 0; i < (150 + (gEASTL_TestLevel * 200)); i += (i < 5) ? 1 : 37) // array sizes of 0 to 300 - 2100, depending on test level.
|
|
{
|
|
for (int n = 0; n < i; n++)
|
|
{
|
|
toArraySaved.push_back(StableSortTestObj(n));
|
|
|
|
if (rng.RandLimit(10) == 0)
|
|
{
|
|
toArraySaved.push_back(StableSortTestObj(n));
|
|
|
|
if (rng.RandLimit(5) == 0)
|
|
toArraySaved.push_back(StableSortTestObj(n));
|
|
}
|
|
}
|
|
vector<StableSortTestObj> tempBuffer;
|
|
tempBuffer.resize(toArraySaved.size());
|
|
|
|
for (int j = 0; j < 300 + (gEASTL_TestLevel * 50); j++)
|
|
{
|
|
eastl::random_shuffle(toArraySaved.begin(), toArraySaved.end(), rng);
|
|
// Store the intial position of each element in the array before sorting. This position can then be used to verify that the sorting operation is stable.
|
|
for (vector<StableSortTestObj>::size_type k = 0; k < toArraySaved.size(); k++)
|
|
{
|
|
toArraySaved[k].initialPositionIndex = k;
|
|
}
|
|
|
|
toArray = toArraySaved;
|
|
bubble_sort(toArray.begin(), toArray.end(), compare);
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
|
|
|
|
toArray = toArraySaved;
|
|
shaker_sort(toArray.begin(), toArray.end(), compare);
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
|
|
|
|
toArray = toArraySaved;
|
|
insertion_sort(toArray.begin(), toArray.end(), compare);
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
|
|
|
|
toArray = toArraySaved;
|
|
tim_sort_buffer(toArray.begin(), toArray.end(), tempBuffer.data(), compare);
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
|
|
|
|
toArray = toArraySaved;
|
|
merge_sort(toArray.begin(), toArray.end(), *get_default_allocator((EASTLAllocatorType*)NULL), compare);
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
|
|
|
|
toArray = toArraySaved;
|
|
merge_sort_buffer(toArray.begin(), toArray.end(), tempBuffer.data(), compare);
|
|
EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
|
|
}
|
|
}
|
|
}
|
|
|
|
{
|
|
// OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
|
|
// This is tested by merge_sort.
|
|
}
|
|
|
|
|
|
{
|
|
// void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
|
|
// This is tested by quick_sort.
|
|
}
|
|
|
|
|
|
{
|
|
// void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
|
|
// void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare compare)
|
|
const int intArrayInit[16] = { 4, 2, 8, 6, 9, 1, 1, 4, 0, 5, 5, 7, 8, 9, 3, 3 };
|
|
int intArraySorted[16]; // Same as intArrayInit but sorted
|
|
int intArray[16];
|
|
size_t i, j;
|
|
|
|
// We test many combinations of nth_element on the int array.
|
|
for(i = 1; i < 16; i++)
|
|
{
|
|
for(j = 0; j < i; j++)
|
|
{
|
|
eastl::copy(intArrayInit, intArrayInit + i, intArraySorted);
|
|
eastl::sort(intArraySorted, intArraySorted + i);
|
|
|
|
eastl::copy(intArrayInit, intArrayInit + i, intArray);
|
|
nth_element(intArray, intArray + j, intArray + i);
|
|
EATEST_VERIFY(intArray[j] == intArraySorted[j]);
|
|
}
|
|
}
|
|
|
|
for(i = 1; i < 16; i++)
|
|
{
|
|
for(j = 0; j < i; j++)
|
|
{
|
|
eastl::copy(intArrayInit, intArrayInit + i, intArraySorted);
|
|
eastl::sort(intArraySorted, intArraySorted + i);
|
|
|
|
eastl::copy(intArrayInit, intArrayInit + 16, intArray);
|
|
nth_element(intArray, intArray + j, intArray + i, eastl::less<int>());
|
|
EATEST_VERIFY(intArray[j] == intArraySorted[j]);
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
{
|
|
// void radix_sort(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator buffer);
|
|
const uint32_t kCount = 100;
|
|
|
|
{
|
|
RadixSortElement32* pRadixSortElementArray32 = new RadixSortElement32[kCount];
|
|
RadixSortElement32* pRadixSortElementArrayTemp32 = new RadixSortElement32[kCount];
|
|
for(uint32_t i = 0; i < kCount; i++)
|
|
{
|
|
pRadixSortElementArray32[i].mKey = (uint16_t)(kCount - i);
|
|
pRadixSortElementArray32[i].mData = (uint16_t)i;
|
|
}
|
|
radix_sort<RadixSortElement32*, extract_radix_key<RadixSortElement32> >(pRadixSortElementArray32, pRadixSortElementArray32 + kCount, pRadixSortElementArrayTemp32);
|
|
EATEST_VERIFY(is_sorted(pRadixSortElementArray32, pRadixSortElementArray32 + kCount));
|
|
delete[] pRadixSortElementArray32;
|
|
delete[] pRadixSortElementArrayTemp32;
|
|
}
|
|
|
|
{
|
|
RadixSortElement16* pRadixSortElementArray16 = new RadixSortElement16[kCount];
|
|
RadixSortElement16* pRadixSortElementArrayTemp16 = new RadixSortElement16[kCount];
|
|
for(uint32_t i = 0; i < kCount; i++)
|
|
{
|
|
pRadixSortElementArray16[i].mKey = (uint16_t)(kCount - i);
|
|
pRadixSortElementArray16[i].mData = (uint16_t)i;
|
|
}
|
|
radix_sort<RadixSortElement16*, extract_radix_key<RadixSortElement16> >(pRadixSortElementArray16, pRadixSortElementArray16 + kCount, pRadixSortElementArrayTemp16);
|
|
EATEST_VERIFY(is_sorted(pRadixSortElementArray16, pRadixSortElementArray16 + kCount));
|
|
delete[] pRadixSortElementArray16;
|
|
delete[] pRadixSortElementArrayTemp16;
|
|
}
|
|
|
|
{
|
|
RadixSortElement8* pRadixSortElementArray8 = new RadixSortElement8[kCount];
|
|
RadixSortElement8* pRadixSortElementArrayTemp8 = new RadixSortElement8[kCount];
|
|
for(uint32_t i = 0; i < kCount; i++)
|
|
{
|
|
pRadixSortElementArray8[i].mKey = (uint8_t)(kCount - i);
|
|
pRadixSortElementArray8[i].mData = (uint8_t)i;
|
|
}
|
|
radix_sort<RadixSortElement8*, extract_radix_key<RadixSortElement8> >(pRadixSortElementArray8, pRadixSortElementArray8 + kCount, pRadixSortElementArrayTemp8);
|
|
EATEST_VERIFY(is_sorted(pRadixSortElementArray8, pRadixSortElementArray8 + kCount));
|
|
delete[] pRadixSortElementArray8;
|
|
delete[] pRadixSortElementArrayTemp8;
|
|
}
|
|
}
|
|
|
|
{
|
|
// Do some white-box testing of radix sort to verify internal optimizations work properly for some edge cases.
|
|
|
|
{
|
|
uint32_t input[] = { 123, 15, 76, 2, 74, 12, 62, 91 };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
// Test values where some digit positions have identical values
|
|
uint32_t input[] = { 0x75000017, 0x74000003, 0x73000045, 0x76000024, 0x78000033, 0x76000099, 0x78000043, 0x75000010 };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
// Test values where some digit positions have identical values
|
|
uint32_t input[] = { 0x00750017, 0x00740003, 0x00730045, 0x00760024, 0x00780033, 0x00760099, 0x00780043, 0x00750010 };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
// Test values where an odd number of scatter operations will be done during sorting (which forces a copy operation to move values back to the input buffer).
|
|
uint32_t input[] = { 0x00000017, 0x00000003, 0x00000045, 0x00000024, 0x00000033, 0x00000099, 0x00000043, 0x00000010 };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
// Test case for bug where the last histogram bucket was not being cleared to zero
|
|
uint32_t input[] = { 0xff00, 0xff };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
}
|
|
|
|
{
|
|
// Test different values for DigitBits
|
|
|
|
{
|
|
uint32_t input[] = {2514513, 6278225, 2726217, 963245656, 35667326, 2625624562, 3562562562, 1556256252};
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>, 1>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
uint32_t input[] = { 2514513, 6278225, 2726217, 963245656, 35667326, 2625624562, 3562562562, 1556256252 };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>, 3>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
uint32_t input[] = { 2514513, 6278225, 2726217, 963245656, 35667326, 2625624562, 3562562562, 1556256252 };
|
|
uint32_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>, 6>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
// Test a value for DigitBits that is more than half the size of the type.
|
|
uint16_t input[] = { 14513, 58225, 26217, 34656, 63326, 24562, 35562, 15652 };
|
|
uint16_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint16_t*, identity_extract_radix_key<uint16_t>, 11>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
{
|
|
// Test a value for DigitBits that is the size of the type itself.
|
|
uint8_t input[] = { 113, 225, 217, 56, 26, 162, 62, 152 };
|
|
uint8_t buffer[EAArrayCount(input)];
|
|
radix_sort<uint8_t*, identity_extract_radix_key<uint8_t>, 8>(begin(input), end(input), buffer);
|
|
EATEST_VERIFY(is_sorted(begin(input), end(input)));
|
|
}
|
|
|
|
}
|
|
|
|
{
|
|
// void bucket_sort(ForwardIterator first, ForwardIterator last, ContainerArray& bucketArray, HashFunction hash)
|
|
|
|
const size_t kElementRange = 32;
|
|
vector<int> intArray(1000);
|
|
|
|
for(int i = 0; i < 1000; i++)
|
|
intArray[i] = rng() % kElementRange;
|
|
|
|
vector< vector<int> > bucketArray(kElementRange);
|
|
bucket_sort(intArray.begin(), intArray.end(), bucketArray, eastl::hash_use_self<int>());
|
|
EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
|
|
}
|
|
|
|
|
|
{
|
|
// stable_sort general test
|
|
typedef eastl::less<int> IntCompare;
|
|
|
|
int intArray[2] = { 0, 1 };
|
|
|
|
stable_sort(intArray, intArray + 2);
|
|
stable_sort(intArray, intArray + 2, IntCompare());
|
|
stable_sort<int*>(intArray, intArray + 2);
|
|
stable_sort<int*, IntCompare>(intArray, intArray + 2, IntCompare());
|
|
|
|
MallocAllocator mallocAllocator;
|
|
|
|
//stable_sort(intArray, intArray + 2, mallocAllocator);
|
|
stable_sort(intArray, intArray + 2, mallocAllocator, IntCompare());
|
|
//stable_sort<int*, MallocAllocator>(intArray, intArray + 2, mallocAllocator);
|
|
stable_sort<int*, MallocAllocator, IntCompare>(intArray, intArray + 2, mallocAllocator, IntCompare());
|
|
}
|
|
|
|
{
|
|
// stable_sort special test
|
|
IntArrayArray intArrayArray(2);
|
|
IntArrayCompare compare;
|
|
|
|
intArrayArray[0].push_back(0);
|
|
intArrayArray[1].push_back(1);
|
|
|
|
stable_sort(intArrayArray.begin(), intArrayArray.end(), compare);
|
|
}
|
|
|
|
|
|
{
|
|
// Test to verify that Compare object references are preserved.
|
|
typedef deque<int> IntDeque;
|
|
typedef IntDeque::iterator IntDequeIterator;
|
|
|
|
IntDeque intDeque, intDequeSaved;
|
|
StatefulCompare compare;
|
|
|
|
// Set up intDequeSaved with random data.
|
|
for(int n = 0; n < 500; n++)
|
|
{
|
|
intDequeSaved.push_back(n);
|
|
|
|
if(rng.RandLimit(10) == 0)
|
|
{
|
|
intDequeSaved.push_back(n);
|
|
|
|
if(rng.RandLimit(5) == 0)
|
|
intDequeSaved.push_back(n);
|
|
}
|
|
}
|
|
|
|
eastl::random_shuffle(intDequeSaved.begin(), intDequeSaved.end(), rng);
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
bubble_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
shaker_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
insertion_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
selection_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
shell_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
comb_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
heap_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
merge_sort<IntDequeIterator, EASTLAllocatorType, StatefulCompare&>(intDeque.begin(), intDeque.end(), *get_default_allocator((EASTLAllocatorType*)NULL), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
intDeque = intDequeSaved;
|
|
quick_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
|
|
StatefulCompare::Reset();
|
|
vector<int> buffer(intDeque.size()/2);
|
|
intDeque = intDequeSaved;
|
|
tim_sort_buffer<IntDequeIterator, int, StatefulCompare&>(intDeque.begin(), intDeque.end(), buffer.data(), compare);
|
|
EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
|
|
}
|
|
|
|
{
|
|
// Test checking that deque sorting can compile.
|
|
deque<int> intDeque;
|
|
vector<int> intVector;
|
|
|
|
stable_sort(intDeque.begin(), intDeque.end());
|
|
stable_sort(intVector.begin(), intVector.end());
|
|
}
|
|
|
|
{
|
|
// Test checking that sorting containers having elements of a type without an operator< compiles correctly
|
|
|
|
vector<TestNoLessOperator> noLessVector;
|
|
|
|
stable_sort(noLessVector.begin(), noLessVector.end());
|
|
bubble_sort(noLessVector.begin(), noLessVector.end());
|
|
shaker_sort(noLessVector.begin(), noLessVector.end());
|
|
insertion_sort(noLessVector.begin(), noLessVector.end());
|
|
selection_sort(noLessVector.begin(), noLessVector.end());
|
|
shell_sort(noLessVector.begin(), noLessVector.end());
|
|
comb_sort(noLessVector.begin(), noLessVector.end());
|
|
heap_sort(noLessVector.begin(), noLessVector.end());
|
|
merge_sort(noLessVector.begin(), noLessVector.end(), *get_default_allocator(nullptr));
|
|
quick_sort(noLessVector.begin(), noLessVector.end());
|
|
|
|
vector<TestNoLessOperator> buffer;
|
|
tim_sort_buffer(noLessVector.begin(), noLessVector.end(), buffer.data());
|
|
}
|
|
|
|
{
|
|
// Test sorting of a container of pointers to objects as opposed to a container of objects themselves.
|
|
vector<TestObject> toArray;
|
|
vector<TestObject*> topArray;
|
|
|
|
for(eastl_size_t i = 0; i < 32; i++)
|
|
toArray.push_back(TestObject((int)rng.RandLimit(20)));
|
|
for(eastl_size_t i = 0; i < 32; i++) // This needs to be a second loop because the addresses might change in the first loop due to container resizing.
|
|
topArray.push_back(&toArray[i]);
|
|
|
|
quick_sort(topArray.begin(), topArray.end(), TestObjectPtrCompare());
|
|
EATEST_VERIFY(is_sorted(topArray.begin(), topArray.end(), TestObjectPtrCompare()));
|
|
}
|
|
|
|
|
|
{
|
|
// Test sorting of a container of array indexes to objects as opposed to a container of objects themselves.
|
|
|
|
vector<TestObject> toArray;
|
|
vector<eastl_size_t> toiArray;
|
|
|
|
for(eastl_size_t i = 0; i < 32; i++)
|
|
{
|
|
toArray.push_back(TestObject((int)rng.RandLimit(20)));
|
|
toiArray.push_back(i);
|
|
}
|
|
|
|
quick_sort(toiArray.begin(), toiArray.end(), TestObjectIndexCompare(&toArray));
|
|
EATEST_VERIFY(is_sorted(toiArray.begin(), toiArray.end(), TestObjectIndexCompare(&toArray)));
|
|
}
|
|
|
|
|
|
{
|
|
// Test of special floating point sort in the presence of NaNs.
|
|
vector<float> floatArray;
|
|
union FloatInt32{ float f; int32_t i; } fi;
|
|
|
|
for(int i = 0; i < 1000; i++)
|
|
{
|
|
fi.i = (int32_t)rng.Rand();
|
|
floatArray.push_back(fi.f);
|
|
}
|
|
|
|
// Without SafeFloatCompare, the following quick_sort will crash, hang, or generate inconsistent results.
|
|
quick_sort(floatArray.begin(), floatArray.end(), SafeFloatCompare());
|
|
EATEST_VERIFY(is_sorted(floatArray.begin(), floatArray.end(), SafeFloatCompare()));
|
|
}
|
|
|
|
{
|
|
auto test_stable_sort = [&](auto testArray, size_t count)
|
|
{
|
|
auto isEven = [](auto val) { return (val % 2) == 0; };
|
|
auto isOdd = [](auto val) { return (val % 2) != 0; };
|
|
|
|
for (size_t i = 0; i < count; i++)
|
|
testArray.push_back((uint16_t)rng.Rand());
|
|
|
|
vector<uint16_t> evenArray;
|
|
vector<uint16_t> oddArray;
|
|
|
|
eastl::copy_if(testArray.begin(), testArray.end(), eastl::back_inserter(evenArray), isEven);
|
|
eastl::copy_if(testArray.begin(), testArray.end(), eastl::back_inserter(oddArray), isOdd);
|
|
|
|
const auto boundary = eastl::stable_partition(testArray.begin(), testArray.end(), isEven);
|
|
|
|
const auto evenCount = eastl::distance(testArray.begin(), boundary);
|
|
const auto oddCount = eastl::distance(boundary, testArray.end());
|
|
|
|
const auto evenExpectedCount = (ptrdiff_t)evenArray.size();
|
|
const auto oddExpectedCount = (ptrdiff_t)oddArray.size();
|
|
|
|
EATEST_VERIFY(evenCount == evenExpectedCount);
|
|
EATEST_VERIFY(oddCount == oddExpectedCount);
|
|
EATEST_VERIFY(eastl::equal(testArray.begin(), boundary, evenArray.begin()));
|
|
EATEST_VERIFY(eastl::equal(boundary, testArray.end(), oddArray.begin()));
|
|
};
|
|
|
|
test_stable_sort(vector<uint16_t>(), 1000); // Test stable_partition
|
|
test_stable_sort(vector<uint16_t>(), 0); // Test stable_partition on empty container
|
|
test_stable_sort(vector<uint16_t>(), 1); // Test stable_partition on container of one element
|
|
test_stable_sort(vector<uint16_t>(), 2); // Test stable_partition on container of two element
|
|
test_stable_sort(list<uint16_t>(), 0); // Test stable_partition on bidirectional iterator (not random access)
|
|
}
|
|
|
|
#if 0 // Disabled because it takes a long time and thus far seems to show no bug in quick_sort.
|
|
{
|
|
// Regression of Coverity report for Madden 2014 that quick_sort is reading beyond an array bounds within insertion_sort_simple.
|
|
// The Madden code was sorting the 11 players on the field for a team by some criteria. We write
|
|
vector<int> intArray(11);
|
|
for(eastl_size_t i = 0; i < intArray.size(); i++)
|
|
intArray[i] = i;
|
|
|
|
do {
|
|
vector<int> intArrayCopy(intArray);
|
|
|
|
// We need to verify that intArray[12] is never accessed. We could do that with a stomp allocator,
|
|
// which we don't currently have set up for the EASTL unit tests, or we could put a breakpoint in
|
|
// the debugger. Until we get a stomp allocator installed, do the breakpoint solution.
|
|
quick_sort(intArrayCopy.begin(), intArrayCopy.end());
|
|
} while(next_permutation(intArray.begin(), intArray.end()));
|
|
}
|
|
#endif
|
|
|
|
EATEST_VERIFY(TestObject::IsClear());
|
|
TestObject::Reset();
|
|
|
|
return nErrorCount;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|