1 /////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) Electronic Arts Inc. All rights reserved.
3 /////////////////////////////////////////////////////////////////////////////
4
5
6 #include <EABase/eabase.h>
7
8 // Some versions of GCC generate an array bounds warning in opt builds which
9 // doesn't say what line below it comes from and doesn't appear to be a valid
10 // warning. In researching this on the Internet it appears that this is a
11 // known problem with GCC.
12 #if defined(EA_DISABLE_GCC_WARNING)
13 EA_DISABLE_GCC_WARNING(-Warray-bounds)
14 #endif
15
16 #include "EASTLTest.h"
17 #include <EASTL/sort.h>
18 #include <EASTL/bonus/sort_extra.h>
19 #include <EASTL/vector.h>
20 #include <EASTL/deque.h>
21 #include <EASTL/algorithm.h>
22 #include <EASTL/allocator.h>
23 #include <EASTL/numeric.h>
24 #include <EASTL/random.h>
25 #include <EABase/eahave.h>
26 #include <cmath>
27
28
29 namespace eastl
30 {
31 namespace Internal
32 {
33 typedef eastl::vector<int> IntArray;
34 typedef eastl::vector<IntArray> IntArrayArray;
35
36
37 // IntArrayCompare
38 // Used to compare IntArray objects.
39 struct IntArrayCompare
40 {
operator ()eastl::Internal::IntArrayCompare41 bool operator()(const IntArray& a, const IntArray& b)
42 { return a.front() < b.front(); }
43 };
44
45
46 // SafeFloatCompare
47 //
48 // Float comparison has a problem for the case that either of the floats are a NaN.
49 // If you use a NaN in a sort function that uses default floating point comparison then
50 // you will get undefined behavior, as all NaNs compare false. This compare function
51 // class sorts floats such that all negative NaNs sort lower than all integers, and all
52 // positive NaNs sort higher than all integers.
53 //
54 // Example usage:
55 // eastl::sort(floatArray.begin(), floatArray.end(), SafeFloatCompare());
56 //
57 struct SafeFloatCompare
58 {
59 union FloatInt32{ float f; int32_t i; };
60
operator ()eastl::Internal::SafeFloatCompare61 bool operator()(float a, float b) const
62 {
63 #if defined(EA_HAVE_ISNAN)
64 bool aNan = (EA_HAVE_ISNAN(a) != 0);
65 bool bNan = (EA_HAVE_ISNAN(b) != 0);
66 #else
67 bool aNan = (a != a); // This works as long as the compiler doesn't do any tricks to optimize it away.
68 bool bNan = (b != b);
69 #endif
70
71 if(!aNan && !bNan)
72 return (a < b);
73
74 FloatInt32 fia = { a };
75 FloatInt32 fib = { b };
76
77 if(aNan)
78 {
79 if(bNan)
80 return (fia.i < fib.i); // Both are NaNs, so do a binary compare.
81 else
82 return (fia.i < 0); // All negative NaNs are assumed to be less than all non-NaNs.
83 }
84 else
85 return (0 < fib.i); // All negative NaNs are assumed to be less than all non-NaNs.
86 }
87 };
88
89
90
91 // StatefulCompare
92 // Used to verify that sort<int, StatefulCompare&>() respects the
93 // fact that StatefulCompare is passed by reference instead of by value.
94 // All existing commercial STL implementations fail to do what the user
95 // wants and instead pass around the compare object by value, even if
96 // the user specifically asks to use it by reference. EASTL doesn't
97 // have this problem.
98 struct StatefulCompare
99 {
100 static int nCtorCount;
101 static int nDtorCount;
102 static int nCopyCount;
103
StatefulCompareeastl::Internal::StatefulCompare104 StatefulCompare()
105 { nCtorCount++; }
106
StatefulCompareeastl::Internal::StatefulCompare107 StatefulCompare(StatefulCompare&)
108 { nCopyCount++; }
109
~StatefulCompareeastl::Internal::StatefulCompare110 ~StatefulCompare()
111 { nDtorCount++; }
112
operator =eastl::Internal::StatefulCompare113 StatefulCompare& operator=(const StatefulCompare&)
114 { nCopyCount++; return *this; }
115
operator ()eastl::Internal::StatefulCompare116 bool operator()(int a, int b)
117 { return a < b; }
118
Reseteastl::Internal::StatefulCompare119 static void Reset()
120 { nCtorCount = 0; nDtorCount = 0; nCopyCount = 0; }
121 };
122
123 int StatefulCompare::nCtorCount = 0;
124 int StatefulCompare::nDtorCount = 0;
125 int StatefulCompare::nCopyCount = 0;
126
127
128 // TestObjectPtrCompare
129 // Used to compare sorted objects by pointer instead of value.
130 struct TestObjectPtrCompare
131 {
operator ()eastl::Internal::TestObjectPtrCompare132 bool operator()(TestObject* a, TestObject* b)
133 { return a->mX < b->mX; }
134 };
135
136
137 // TestObjectIndexCompare
138 // Used to compare sorted objects by array index instead of value.
139 struct TestObjectIndexCompare
140 {
141 vector<TestObject>* mpArray;
142
TestObjectIndexCompareeastl::Internal::TestObjectIndexCompare143 TestObjectIndexCompare(vector<TestObject>* pArray) : mpArray(pArray) { }
TestObjectIndexCompareeastl::Internal::TestObjectIndexCompare144 TestObjectIndexCompare(const TestObjectIndexCompare& x) : mpArray(x.mpArray){ }
operator =eastl::Internal::TestObjectIndexCompare145 TestObjectIndexCompare& operator=(const TestObjectIndexCompare& x) { mpArray = x.mpArray; return *this; }
146
operator ()eastl::Internal::TestObjectIndexCompare147 bool operator()(eastl_size_t a, eastl_size_t b)
148 { return (*mpArray)[a] < (*mpArray)[b]; }
149 };
150
151 // Radix sort elements
152 template <typename Key>
153 struct RadixSortElement
154 {
155 typedef Key radix_type;
156 Key mKey;
157 uint16_t mData;
158
operator <eastl::Internal::RadixSortElement159 bool operator<(const RadixSortElement<Key> &other) const
160 {
161 return mKey < other.mKey;
162 }
163 };
164
165 typedef RadixSortElement<uint8_t> RadixSortElement8;
166 typedef RadixSortElement<uint16_t> RadixSortElement16;
167 typedef RadixSortElement<uint32_t> RadixSortElement32;
168
169 template <typename integer_type>
170 struct identity_extract_radix_key
171 {
172 typedef integer_type radix_type;
173
operator ()eastl::Internal::identity_extract_radix_key174 const radix_type operator()(const integer_type& x) const
175 {
176 return x;
177 }
178 };
179 } // namespace Internal
180
181 } // namespace eastl
182
TestSort()183 int TestSort()
184 {
185 using namespace eastl;
186 using namespace Internal;
187
188 int nErrorCount = 0;
189
190 EASTLTest_Rand rng(EA::UnitTest::GetRandSeed());
191
192 {
193 // is_sorted
194 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 };
195
196 EATEST_VERIFY( is_sorted(array + 0, array + 0));
197 EATEST_VERIFY( is_sorted(array + 2, array + 4));
198 EATEST_VERIFY( is_sorted(array + 0, array + 10));
199 EATEST_VERIFY(!is_sorted(array + 0, array + 14));
200 EATEST_VERIFY( is_sorted(array + 11, array + 23, eastl::greater<int>()));
201 }
202
203 {
204 // is_sorted_until
205 int sorted[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
206 int notsorted[] = { 0, 1, 2, 3, 4, 42, 6, 7, 8, 9 };
207
208 EATEST_VERIFY( is_sorted_until(sorted + EAArrayCount(sorted), sorted + EAArrayCount(sorted)) == sorted + EAArrayCount(sorted) );
209 EATEST_VERIFY( is_sorted_until(sorted , sorted + EAArrayCount(sorted)) == sorted + EAArrayCount(sorted) );
210
211 EATEST_VERIFY( is_sorted_until(sorted + 0, sorted + 0) == sorted );
212 EATEST_VERIFY( is_sorted_until(sorted + 2, sorted + 8) == sorted + 8 );
213
214 EATEST_VERIFY( is_sorted_until(notsorted + 2, notsorted + 8) == notsorted + 6 );
215
216 // is_sorted_until (with compare function)
217 EATEST_VERIFY( is_sorted_until(sorted + EAArrayCount(sorted), sorted + EAArrayCount(sorted), eastl::less<int>()) == sorted + EAArrayCount(sorted) );
218 EATEST_VERIFY( is_sorted_until(notsorted + 2, notsorted + 8, eastl::less<int>()) == notsorted + 6 );
219 }
220
221 // Sort arrays of size 0 - N. Sort M random permutations of each.
222 {
223 vector<int64_t> intArray, intArraySaved;
224
225 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.
226 {
227 // intArraySaved.clear(); // Do we want to do this?
228
229 for(int n = 0; n < i; n++)
230 {
231 intArraySaved.push_back(n);
232
233 if(rng.RandLimit(10) == 0)
234 {
235 intArraySaved.push_back(n);
236
237 if(rng.RandLimit(5) == 0)
238 intArraySaved.push_back(n);
239 }
240 }
241 const int64_t expectedSum = eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0));
242
243 for(int j = 0; j < 300 + (gEASTL_TestLevel * 50); j++)
244 {
245 eastl::random_shuffle(intArraySaved.begin(), intArraySaved.end(), rng);
246
247 intArray = intArraySaved;
248 bubble_sort(intArray.begin(), intArray.end());
249 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
250 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
251
252 intArray = intArraySaved;
253 shaker_sort(intArray.begin(), intArray.end());
254 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
255 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
256
257 intArray = intArraySaved;
258 insertion_sort(intArray.begin(), intArray.end());
259 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
260 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
261
262 intArray = intArraySaved;
263 selection_sort(intArray.begin(), intArray.end());
264 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
265 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
266
267 intArray = intArraySaved;
268 shell_sort(intArray.begin(), intArray.end());
269 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
270 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
271
272 intArray = intArraySaved;
273 comb_sort(intArray.begin(), intArray.end());
274 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
275 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
276
277 intArray = intArraySaved;
278 heap_sort(intArray.begin(), intArray.end());
279 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
280 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
281
282 intArray = intArraySaved;
283 merge_sort(intArray.begin(), intArray.end(), *get_default_allocator((EASTLAllocatorType*)NULL));
284 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
285 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
286
287 intArray = intArraySaved;
288 vector<int64_t> buffer(intArray.size());
289 merge_sort_buffer(intArray.begin(), intArray.end(), &buffer[0]);
290 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
291 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
292
293 intArray = intArraySaved;
294 quick_sort(intArray.begin(), intArray.end());
295 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
296 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
297
298 intArray = intArraySaved;
299 buffer.resize(intArray.size()/2);
300 tim_sort_buffer(intArray.begin(), intArray.end(), buffer.data());
301 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
302 EATEST_VERIFY(eastl::accumulate(begin(intArraySaved), end(intArraySaved), int64_t(0)) == expectedSum);
303 }
304 }
305 }
306
307
308 // TestObject sorting
309 TestObject::Reset();
310 {
311 vector<TestObject> toArray, toArraySaved;
312
313 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.
314 {
315 for(int n = 0; n < i; n++)
316 {
317 toArraySaved.push_back(TestObject(n));
318
319 if(rng.RandLimit(10) == 0)
320 {
321 toArraySaved.push_back(TestObject(n));
322
323 if(rng.RandLimit(5) == 0)
324 toArraySaved.push_back(TestObject(n));
325 }
326 }
327
328 for(int j = 0; j < 300 + (gEASTL_TestLevel * 50); j++)
329 {
330 eastl::random_shuffle(toArraySaved.begin(), toArraySaved.end(), rng);
331
332 toArray = toArraySaved;
333 bubble_sort(toArray.begin(), toArray.end());
334 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
335
336 toArray = toArraySaved;
337 shaker_sort(toArray.begin(), toArray.end());
338 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
339
340 toArray = toArraySaved;
341 insertion_sort(toArray.begin(), toArray.end());
342 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
343
344 toArray = toArraySaved;
345 selection_sort(toArray.begin(), toArray.end());
346 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
347
348 toArray = toArraySaved;
349 shell_sort(toArray.begin(), toArray.end());
350 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
351
352 toArray = toArraySaved;
353 comb_sort(toArray.begin(), toArray.end());
354 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
355
356 toArray = toArraySaved;
357 heap_sort(toArray.begin(), toArray.end());
358 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
359
360 // Not ready yet:
361 toArray = toArraySaved;
362 merge_sort(toArray.begin(), toArray.end(), *get_default_allocator((EASTLAllocatorType*)NULL));
363 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
364
365 toArray = toArraySaved;
366 quick_sort(toArray.begin(), toArray.end());
367 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
368
369 toArray = toArraySaved;
370 vector<TestObject> buffer(toArray.size()/2);
371 tim_sort_buffer(toArray.begin(), toArray.end(), buffer.data());
372 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end()));
373 }
374 }
375 }
376
377 // Test that stable sorting algorithms are actually stable
378 {
379 struct StableSortTestObj
380 {
381 StableSortTestObj()
382 {
383 }
384
385 StableSortTestObj(int value)
386 :value(value)
387 ,initialPositionIndex(0)
388 {
389 }
390
391 int value;
392 size_t initialPositionIndex;
393 };
394
395 // During the test this comparison is used to sort elements based on value.
396 struct StableSortCompare
397 {
398 bool operator()(const StableSortTestObj& a, const StableSortTestObj& b)
399 {
400 return a.value < b.value;
401 }
402 };
403
404 // During the test this comparison is used to verify the sort was a stable sort. i.e. if values are the same then
405 // their relative position should be maintained.
406 struct StableSortCompareForStability
407 {
408 bool operator()(const StableSortTestObj& a, const StableSortTestObj& b)
409 {
410 if (a.value != b.value)
411 {
412 return a.value < b.value;
413 }
414 else
415 {
416 return a.initialPositionIndex < b.initialPositionIndex;
417 }
418 }
419 };
420
421 vector<StableSortTestObj> toArray, toArraySaved;
422 StableSortCompare compare;
423 StableSortCompareForStability compareForStability;
424
425 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.
426 {
427 for (int n = 0; n < i; n++)
428 {
429 toArraySaved.push_back(StableSortTestObj(n));
430
431 if (rng.RandLimit(10) == 0)
432 {
433 toArraySaved.push_back(StableSortTestObj(n));
434
435 if (rng.RandLimit(5) == 0)
436 toArraySaved.push_back(StableSortTestObj(n));
437 }
438 }
439 vector<StableSortTestObj> tempBuffer;
440 tempBuffer.resize(toArraySaved.size());
441
442 for (int j = 0; j < 300 + (gEASTL_TestLevel * 50); j++)
443 {
444 eastl::random_shuffle(toArraySaved.begin(), toArraySaved.end(), rng);
445 // 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.
446 for (vector<StableSortTestObj>::size_type k = 0; k < toArraySaved.size(); k++)
447 {
448 toArraySaved[k].initialPositionIndex = k;
449 }
450
451 toArray = toArraySaved;
452 bubble_sort(toArray.begin(), toArray.end(), compare);
453 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
454
455 toArray = toArraySaved;
456 shaker_sort(toArray.begin(), toArray.end(), compare);
457 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
458
459 toArray = toArraySaved;
460 insertion_sort(toArray.begin(), toArray.end(), compare);
461 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
462
463 toArray = toArraySaved;
464 tim_sort_buffer(toArray.begin(), toArray.end(), tempBuffer.data(), compare);
465 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
466
467 toArray = toArraySaved;
468 merge_sort(toArray.begin(), toArray.end(), *get_default_allocator((EASTLAllocatorType*)NULL), compare);
469 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
470
471 toArray = toArraySaved;
472 merge_sort_buffer(toArray.begin(), toArray.end(), tempBuffer.data(), compare);
473 EATEST_VERIFY(is_sorted(toArray.begin(), toArray.end(), compareForStability));
474 }
475 }
476 }
477
478 {
479 // OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
480 // This is tested by merge_sort.
481 }
482
483
484 {
485 // void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
486 // This is tested by quick_sort.
487 }
488
489
490 {
491 // void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
492 // void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare compare)
493 const int intArrayInit[16] = { 4, 2, 8, 6, 9, 1, 1, 4, 0, 5, 5, 7, 8, 9, 3, 3 };
494 int intArraySorted[16]; // Same as intArrayInit but sorted
495 int intArray[16];
496 size_t i, j;
497
498 // We test many combinations of nth_element on the int array.
499 for(i = 1; i < 16; i++)
500 {
501 for(j = 0; j < i; j++)
502 {
503 eastl::copy(intArrayInit, intArrayInit + i, intArraySorted);
504 eastl::sort(intArraySorted, intArraySorted + i);
505
506 eastl::copy(intArrayInit, intArrayInit + i, intArray);
507 nth_element(intArray, intArray + j, intArray + i);
508 EATEST_VERIFY(intArray[j] == intArraySorted[j]);
509 }
510 }
511
512 for(i = 1; i < 16; i++)
513 {
514 for(j = 0; j < i; j++)
515 {
516 eastl::copy(intArrayInit, intArrayInit + i, intArraySorted);
517 eastl::sort(intArraySorted, intArraySorted + i);
518
519 eastl::copy(intArrayInit, intArrayInit + 16, intArray);
520 nth_element(intArray, intArray + j, intArray + i, eastl::less<int>());
521 EATEST_VERIFY(intArray[j] == intArraySorted[j]);
522 }
523 }
524 }
525
526
527 {
528 // void radix_sort(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator buffer);
529 const uint32_t kCount = 100;
530
531 {
532 RadixSortElement32* pRadixSortElementArray32 = new RadixSortElement32[kCount];
533 RadixSortElement32* pRadixSortElementArrayTemp32 = new RadixSortElement32[kCount];
534 for(uint32_t i = 0; i < kCount; i++)
535 {
536 pRadixSortElementArray32[i].mKey = (uint16_t)(kCount - i);
537 pRadixSortElementArray32[i].mData = (uint16_t)i;
538 }
539 radix_sort<RadixSortElement32*, extract_radix_key<RadixSortElement32> >(pRadixSortElementArray32, pRadixSortElementArray32 + kCount, pRadixSortElementArrayTemp32);
540 EATEST_VERIFY(is_sorted(pRadixSortElementArray32, pRadixSortElementArray32 + kCount));
541 delete[] pRadixSortElementArray32;
542 delete[] pRadixSortElementArrayTemp32;
543 }
544
545 {
546 RadixSortElement16* pRadixSortElementArray16 = new RadixSortElement16[kCount];
547 RadixSortElement16* pRadixSortElementArrayTemp16 = new RadixSortElement16[kCount];
548 for(uint32_t i = 0; i < kCount; i++)
549 {
550 pRadixSortElementArray16[i].mKey = (uint16_t)(kCount - i);
551 pRadixSortElementArray16[i].mData = (uint16_t)i;
552 }
553 radix_sort<RadixSortElement16*, extract_radix_key<RadixSortElement16> >(pRadixSortElementArray16, pRadixSortElementArray16 + kCount, pRadixSortElementArrayTemp16);
554 EATEST_VERIFY(is_sorted(pRadixSortElementArray16, pRadixSortElementArray16 + kCount));
555 delete[] pRadixSortElementArray16;
556 delete[] pRadixSortElementArrayTemp16;
557 }
558
559 {
560 RadixSortElement8* pRadixSortElementArray8 = new RadixSortElement8[kCount];
561 RadixSortElement8* pRadixSortElementArrayTemp8 = new RadixSortElement8[kCount];
562 for(uint32_t i = 0; i < kCount; i++)
563 {
564 pRadixSortElementArray8[i].mKey = (uint8_t)(kCount - i);
565 pRadixSortElementArray8[i].mData = (uint8_t)i;
566 }
567 radix_sort<RadixSortElement8*, extract_radix_key<RadixSortElement8> >(pRadixSortElementArray8, pRadixSortElementArray8 + kCount, pRadixSortElementArrayTemp8);
568 EATEST_VERIFY(is_sorted(pRadixSortElementArray8, pRadixSortElementArray8 + kCount));
569 delete[] pRadixSortElementArray8;
570 delete[] pRadixSortElementArrayTemp8;
571 }
572 }
573
574 {
575 // Do some white-box testing of radix sort to verify internal optimizations work properly for some edge cases.
576
577 {
578 uint32_t input[] = { 123, 15, 76, 2, 74, 12, 62, 91 };
579 uint32_t buffer[EAArrayCount(input)];
580 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
581 EATEST_VERIFY(is_sorted(begin(input), end(input)));
582 }
583 {
584 // Test values where some digit positions have identical values
585 uint32_t input[] = { 0x75000017, 0x74000003, 0x73000045, 0x76000024, 0x78000033, 0x76000099, 0x78000043, 0x75000010 };
586 uint32_t buffer[EAArrayCount(input)];
587 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
588 EATEST_VERIFY(is_sorted(begin(input), end(input)));
589 }
590 {
591 // Test values where some digit positions have identical values
592 uint32_t input[] = { 0x00750017, 0x00740003, 0x00730045, 0x00760024, 0x00780033, 0x00760099, 0x00780043, 0x00750010 };
593 uint32_t buffer[EAArrayCount(input)];
594 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
595 EATEST_VERIFY(is_sorted(begin(input), end(input)));
596 }
597 {
598 // 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).
599 uint32_t input[] = { 0x00000017, 0x00000003, 0x00000045, 0x00000024, 0x00000033, 0x00000099, 0x00000043, 0x00000010 };
600 uint32_t buffer[EAArrayCount(input)];
601 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>>(begin(input), end(input), buffer);
602 EATEST_VERIFY(is_sorted(begin(input), end(input)));
603 }
604 }
605
606 {
607 // Test different values for DigitBits
608
609 {
610 uint32_t input[] = {2514513, 6278225, 2726217, 963245656, 35667326, 2625624562, 3562562562, 1556256252};
611 uint32_t buffer[EAArrayCount(input)];
612 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>, 1>(begin(input), end(input), buffer);
613 EATEST_VERIFY(is_sorted(begin(input), end(input)));
614 }
615 {
616 uint32_t input[] = { 2514513, 6278225, 2726217, 963245656, 35667326, 2625624562, 3562562562, 1556256252 };
617 uint32_t buffer[EAArrayCount(input)];
618 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>, 3>(begin(input), end(input), buffer);
619 EATEST_VERIFY(is_sorted(begin(input), end(input)));
620 }
621 {
622 uint32_t input[] = { 2514513, 6278225, 2726217, 963245656, 35667326, 2625624562, 3562562562, 1556256252 };
623 uint32_t buffer[EAArrayCount(input)];
624 radix_sort<uint32_t*, identity_extract_radix_key<uint32_t>, 6>(begin(input), end(input), buffer);
625 EATEST_VERIFY(is_sorted(begin(input), end(input)));
626 }
627 {
628 // Test a value for DigitBits that is more than half the size of the type.
629 uint16_t input[] = { 14513, 58225, 26217, 34656, 63326, 24562, 35562, 15652 };
630 uint16_t buffer[EAArrayCount(input)];
631 radix_sort<uint16_t*, identity_extract_radix_key<uint16_t>, 11>(begin(input), end(input), buffer);
632 EATEST_VERIFY(is_sorted(begin(input), end(input)));
633 }
634 {
635 // Test a value for DigitBits that is the size of the type itself.
636 uint8_t input[] = { 113, 225, 217, 56, 26, 162, 62, 152 };
637 uint8_t buffer[EAArrayCount(input)];
638 radix_sort<uint8_t*, identity_extract_radix_key<uint8_t>, 8>(begin(input), end(input), buffer);
639 EATEST_VERIFY(is_sorted(begin(input), end(input)));
640 }
641
642 }
643
644 {
645 // void bucket_sort(ForwardIterator first, ForwardIterator last, ContainerArray& bucketArray, HashFunction hash)
646
647 const size_t kElementRange = 32;
648 vector<int> intArray(1000);
649
650 for(int i = 0; i < 1000; i++)
651 intArray[i] = rng() % kElementRange;
652
653 vector< vector<int> > bucketArray(kElementRange);
654 bucket_sort(intArray.begin(), intArray.end(), bucketArray, eastl::hash_use_self<int>());
655 EATEST_VERIFY(is_sorted(intArray.begin(), intArray.end()));
656 }
657
658
659 {
660 // stable_sort general test
661 typedef eastl::less<int> IntCompare;
662
663 int intArray[2] = { 0, 1 };
664
665 stable_sort(intArray, intArray + 2);
666 stable_sort(intArray, intArray + 2, IntCompare());
667 stable_sort<int*>(intArray, intArray + 2);
668 stable_sort<int*, IntCompare>(intArray, intArray + 2, IntCompare());
669
670 MallocAllocator mallocAllocator;
671
672 //stable_sort(intArray, intArray + 2, mallocAllocator);
673 stable_sort(intArray, intArray + 2, mallocAllocator, IntCompare());
674 //stable_sort<int*, MallocAllocator>(intArray, intArray + 2, mallocAllocator);
675 stable_sort<int*, MallocAllocator, IntCompare>(intArray, intArray + 2, mallocAllocator, IntCompare());
676 }
677
678 {
679 // stable_sort special test
680 IntArrayArray intArrayArray(2);
681 IntArrayCompare compare;
682
683 intArrayArray[0].push_back(0);
684 intArrayArray[1].push_back(1);
685
686 stable_sort(intArrayArray.begin(), intArrayArray.end(), compare);
687 }
688
689
690 {
691 // Test to verify that Compare object references are preserved.
692 typedef deque<int> IntDeque;
693 typedef IntDeque::iterator IntDequeIterator;
694
695 IntDeque intDeque, intDequeSaved;
696 StatefulCompare compare;
697
698 // Set up intDequeSaved with random data.
699 for(int n = 0; n < 500; n++)
700 {
701 intDequeSaved.push_back(n);
702
703 if(rng.RandLimit(10) == 0)
704 {
705 intDequeSaved.push_back(n);
706
707 if(rng.RandLimit(5) == 0)
708 intDequeSaved.push_back(n);
709 }
710 }
711
712 eastl::random_shuffle(intDequeSaved.begin(), intDequeSaved.end(), rng);
713
714 StatefulCompare::Reset();
715 intDeque = intDequeSaved;
716 bubble_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
717 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
718
719 StatefulCompare::Reset();
720 intDeque = intDequeSaved;
721 shaker_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
722 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
723
724 StatefulCompare::Reset();
725 intDeque = intDequeSaved;
726 insertion_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
727 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
728
729 StatefulCompare::Reset();
730 intDeque = intDequeSaved;
731 selection_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
732 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
733
734 StatefulCompare::Reset();
735 intDeque = intDequeSaved;
736 shell_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
737 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
738
739 StatefulCompare::Reset();
740 intDeque = intDequeSaved;
741 comb_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
742 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
743
744 StatefulCompare::Reset();
745 intDeque = intDequeSaved;
746 heap_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
747 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
748
749 StatefulCompare::Reset();
750 intDeque = intDequeSaved;
751 merge_sort<IntDequeIterator, EASTLAllocatorType, StatefulCompare&>(intDeque.begin(), intDeque.end(), *get_default_allocator((EASTLAllocatorType*)NULL), compare);
752 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
753
754 StatefulCompare::Reset();
755 intDeque = intDequeSaved;
756 quick_sort<IntDequeIterator, StatefulCompare&>(intDeque.begin(), intDeque.end(), compare);
757 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
758
759 StatefulCompare::Reset();
760 vector<int> buffer(intDeque.size()/2);
761 intDeque = intDequeSaved;
762 tim_sort_buffer<IntDequeIterator, int, StatefulCompare&>(intDeque.begin(), intDeque.end(), buffer.data(), compare);
763 EATEST_VERIFY((StatefulCompare::nCtorCount == 0) && (StatefulCompare::nDtorCount == 0) && (StatefulCompare::nCopyCount == 0));
764 }
765
766 {
767 // EATEST_VERIFY deque sorting can compile.
768 deque<int> intDeque;
769 vector<int> intVector;
770
771 stable_sort(intDeque.begin(), intDeque.end());
772 stable_sort(intVector.begin(), intVector.end());
773 }
774
775
776 {
777 // Test sorting of a container of pointers to objects as opposed to a container of objects themselves.
778 vector<TestObject> toArray;
779 vector<TestObject*> topArray;
780
781 for(eastl_size_t i = 0; i < 32; i++)
782 toArray.push_back(TestObject((int)rng.RandLimit(20)));
783 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.
784 topArray.push_back(&toArray[i]);
785
786 quick_sort(topArray.begin(), topArray.end(), TestObjectPtrCompare());
787 EATEST_VERIFY(is_sorted(topArray.begin(), topArray.end(), TestObjectPtrCompare()));
788 }
789
790
791 {
792 // Test sorting of a container of array indexes to objects as opposed to a container of objects themselves.
793
794 vector<TestObject> toArray;
795 vector<eastl_size_t> toiArray;
796
797 for(eastl_size_t i = 0; i < 32; i++)
798 {
799 toArray.push_back(TestObject((int)rng.RandLimit(20)));
800 toiArray.push_back(i);
801 }
802
803 quick_sort(toiArray.begin(), toiArray.end(), TestObjectIndexCompare(&toArray));
804 EATEST_VERIFY(is_sorted(toiArray.begin(), toiArray.end(), TestObjectIndexCompare(&toArray)));
805 }
806
807
808 {
809 // Test of special floating point sort in the presence of NaNs.
810 vector<float> floatArray;
811 union FloatInt32{ float f; int32_t i; } fi;
812
813 for(int i = 0; i < 1000; i++)
814 {
815 fi.i = (int32_t)rng.Rand();
816 floatArray.push_back(fi.f);
817 }
818
819 // Without SafeFloatCompare, the following quick_sort will crash, hang, or generate inconsistent results.
820 quick_sort(floatArray.begin(), floatArray.end(), SafeFloatCompare());
821 EATEST_VERIFY(is_sorted(floatArray.begin(), floatArray.end(), SafeFloatCompare()));
822 }
823
824
825 #if 0 // Disabled because it takes a long time and thus far seems to show no bug in quick_sort.
826 {
827 // Regression of Coverity report for Madden 2014 that quick_sort is reading beyond an array bounds within insertion_sort_simple.
828 // The Madden code was sorting the 11 players on the field for a team by some criteria. We write
829 vector<int> intArray(11);
830 for(eastl_size_t i = 0; i < intArray.size(); i++)
831 intArray[i] = i;
832
833 do {
834 vector<int> intArrayCopy(intArray);
835
836 // We need to verify that intArray[12] is never accessed. We could do that with a stomp allocator,
837 // which we don't currently have set up for the EASTL unit tests, or we could put a breakpoint in
838 // the debugger. Until we get a stomp allocator installed, do the breakpoint solution.
839 quick_sort(intArrayCopy.begin(), intArrayCopy.end());
840 } while(next_permutation(intArray.begin(), intArray.end()));
841 }
842 #endif
843
844 EATEST_VERIFY(TestObject::IsClear());
845 TestObject::Reset();
846
847 return nErrorCount;
848 }
849
850
851
852
853
854
855
856
857
858