1e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/*********************************************************************************** 2e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott test_algo.cpp 3e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 4e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Copyright (c) 1997 5e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Mark of the Unicorn, Inc. 6e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 7e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Permission to use, copy, modify, distribute and sell this software 8e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * and its documentation for any purpose is hereby granted without fee, 9e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * provided that the above copyright notice appear in all copies and 10e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * that both that copyright notice and this permission notice appear 11e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * in supporting documentation. Mark of the Unicorn makes no 12e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * representations about the suitability of this software for any 13e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * purpose. It is provided "as is" without express or implied warranty. 14e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 15e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott***********************************************************************************/ 16e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "Tests.h" 17e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "LeakCheck.h" 18e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#include "SortClass.h" 19e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 20e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (EH_NEW_HEADERS) 21e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <algorithm> 22e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <cassert> 23e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#else 24e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <algo.h> 25e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <assert.h> 26e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 27e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 28e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (EH_NEW_IOSTREAMS) 29e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <iostream> 30e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#else 31e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <iostream.h> 32e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 33e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 34e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 35e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// SortBuffer -- a buffer of SortClass objects that can be used to test sorting. 36e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 37e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct SortBuffer 38e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 39e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott enum { kBufferSize = 100 }; 40e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 41e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortClass* begin() { return items; } 42e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortClass* begin() const { return items; } 43e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortClass* end() { return items + kBufferSize; } 44e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortClass* end() const { return items + kBufferSize; } 45e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 46e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Sort each half of the buffer and reset the address of each element 47e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // so that merge() can be tested for stability. 48e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void PrepareMerge() 49e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 50e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::sort( begin(), begin() + ( end() - begin() )/2 ); 51e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::sort( begin() + ( end() - begin() )/2, end() ); 52e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( SortClass* p = begin(); p != end(); p++ ) 53e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott p->ResetAddress(); 54e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 55e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 56e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortBuffer() 57e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 58e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott PrepareMerge(); 59e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 60e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 61e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortBuffer( const SortBuffer& rhs ) 62e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 63e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortClass* q = begin(); 64e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( const SortClass* p = rhs.begin() ; p != rhs.end(); p++,q++ ) 65e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott *q = *p; 66e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 67e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 68e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 69e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortClass items[kBufferSize]; 70e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 71e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 72e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 73e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// less_by_reference -- a functor for comparing objects against a 74e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// constant value. 75e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 76e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class T> 77e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct less_by_reference 78e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 79e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott less_by_reference( const T& arg ) : fArg(arg) {} 80e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott bool operator()( const T& x ) const { return x < fArg; } 81e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 82e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const T& fArg; 83e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 84e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 85e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct test_stable_partition 86e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 87e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott test_stable_partition( const SortBuffer& buf ) 88e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott : orig( buf ), partitionPoint(SortClass::kRange / 2) { 89e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.SetCurrentTestName("stable_partition()"); 90e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 91e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 92e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void operator()( SortBuffer& buf ) const 93e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 94e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott less_by_reference<SortClass> throw_cmp( partitionPoint ); 95e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 96e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortClass* d = EH_STD::stable_partition( buf.begin(), buf.end(), throw_cmp ); 97e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 98e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Suppress warning about unused variable. 99e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott d; 100e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 101e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // If we get here no exception occurred during the operation. 102e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Stop any potential failures that might occur during verification. 103e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.CancelFailureCountdown(); 104e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 105e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Prepare an array of counts of the occurrence of each value in 106e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // the legal range. 107e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned counts[SortClass::kRange]; 108e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::fill_n( counts, (int)SortClass::kRange, 0 ); 109e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( const SortClass *q = orig.begin(); q != orig.end(); q++ ) 110e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott counts[ q->value() ]++; 111e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 112e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott less_by_reference<TestClass> cmp( partitionPoint ); 113e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( const SortClass* p = buf.begin(); p != buf.end(); p++ ) 114e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 115e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Check that adjacent items with the same value haven't been 116e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // reordered. This could be a more thorough test. 117e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if ( p != buf.begin() && p->value() == p[-1].value() ) { 118e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_ASSERT( p->GetAddress() > p[-1].GetAddress() ); 119e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 120e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 121e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Check that the partitioning worked. 122e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_ASSERT( (p < d) == cmp( *p ) ); 123e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 124e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Decrement the appropriate count for each value. 125e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott counts[ p->value() ]--; 126e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 127e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 128e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Check that the values were only rearranged, and none were lost. 129e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( unsigned j = 0; j < SortClass::kRange; j++ ) { 130e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_ASSERT( counts[j] == 0 ); 131e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 132e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 133e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 134e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 135e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortBuffer& orig; 136e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortClass partitionPoint; 137e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 138e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 139e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf ); 140e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 141e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/*=================================================================================== 142e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert_sorted_version 143e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 144e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EFFECTS: Asserts that buf is a stable-sorted version of orig. 145e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott====================================================================================*/ 146e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf ) 147e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 148e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Stop any potential failures that might occur during verification. 149e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.CancelFailureCountdown(); 150e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 151e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Prepare an array of counts of the occurrence of each value in 152e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // the legal range. 153e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned counts[SortClass::kRange]; 154e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::fill_n( counts, (int)SortClass::kRange, 0 ); 155e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( const SortClass *q = orig.begin(); q != orig.end(); q++ ) 156e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott counts[ q->value() ]++; 157e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 158e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Check that each element is greater than the previous one, or if they are 159e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // equal, that their order has been preserved. 160e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( const SortClass* p = buf.begin(); p != buf.end(); p++ ) 161e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 162e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if ( p != buf.begin() ) { 163e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_ASSERT( p->value() > p[-1].value() 164e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() ); 165e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 166e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Decrement the appropriate count for each value. 167e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott counts[ p->value() ]--; 168e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 169e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 170e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Check that the values were only rearranged, and none were lost. 171e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for ( unsigned j = 0; j < SortClass::kRange; j++ ) { 172e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_ASSERT( counts[j] == 0 ); 173e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 174e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 175e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 176e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 177e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// The test operators 178e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// 179e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct test_stable_sort_1 180e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 181e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott test_stable_sort_1( const SortBuffer& buf ) 182e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott : orig( buf ) { 183e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.SetCurrentTestName("stable_sort() #1"); 184e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 185e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 186e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void operator()( SortBuffer& buf ) const 187e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 188e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::stable_sort( buf.begin(), buf.end() ); 189e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert_sorted_version( orig, buf ); 190e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 191e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 192e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 193e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortBuffer& orig; 194e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 195e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 196e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct test_stable_sort_2 197e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 198e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott test_stable_sort_2( const SortBuffer& buf ) 199e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott : orig( buf ) { 200e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.SetCurrentTestName("stable_sort() #2"); 201e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 202e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 203e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void operator()( SortBuffer& buf ) const 204e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 205e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() ); 206e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert_sorted_version( orig, buf ); 207e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 208e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 209e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 210e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortBuffer& orig; 211e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 212e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 213e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct test_inplace_merge_1 214e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 215e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott test_inplace_merge_1( SortBuffer& buf ) 216e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott : orig( buf ) { 217e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.SetCurrentTestName("inplace_merge #1()"); 218e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 219e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 220e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void operator()( SortBuffer& buf ) const 221e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 222e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() ); 223e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert_sorted_version( orig, buf ); 224e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 225e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 226e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 227e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortBuffer& orig; 228e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 229e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 230e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct test_inplace_merge_2 231e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 232e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott test_inplace_merge_2( SortBuffer& buf ) 233e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott : orig( buf ) { 234e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott gTestController.SetCurrentTestName("inplace_merge() #2"); 235e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 236e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 237e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void operator()( SortBuffer& buf ) const 238e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 239e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(), 240e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::less<SortClass>() ); 241e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott assert_sorted_version( orig, buf ); 242e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 243e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 244e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 245e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const SortBuffer& orig; 246e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 247e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 248e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottvoid test_algo() 249e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ 250e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortBuffer mergeBuf; 251e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mergeBuf.PrepareMerge(); 252e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 253e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl; 254e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) ); 255e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) ); 256e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 257e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SortBuffer buf; 258e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott WeakCheck( buf, test_stable_sort_1( buf ) ); 259e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott WeakCheck( buf, test_stable_sort_2( buf ) ); 260e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott WeakCheck( buf, test_stable_partition( buf ) ); 261e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 262