diff options
Diffstat (limited to 'test/source/TestSort.cpp')
| -rw-r--r-- | test/source/TestSort.cpp | 921 |
1 files changed, 921 insertions, 0 deletions
diff --git a/test/source/TestSort.cpp b/test/source/TestSort.cpp new file mode 100644 index 0000000..2d0116f --- /dev/null +++ b/test/source/TestSort.cpp @@ -0,0 +1,921 @@ +///////////////////////////////////////////////////////////////////////////// +// 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; + } + }; + } // namespace Internal + +} // 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 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)); + } + + { + // EATEST_VERIFY deque sorting can compile. + deque<int> intDeque; + vector<int> intVector; + + stable_sort(intDeque.begin(), intDeque.end()); + stable_sort(intVector.begin(), intVector.end()); + } + + + { + // 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; +} + + + + + + + + + |