| /*********************************************************************************** |
| test_algo.cpp |
| |
| * Copyright (c) 1997 |
| * Mark of the Unicorn, Inc. |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Mark of the Unicorn makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| |
| ***********************************************************************************/ |
| #include "Tests.h" |
| #include "LeakCheck.h" |
| #include "SortClass.h" |
| |
| #if defined (EH_NEW_HEADERS) |
| # include <algorithm> |
| # include <cassert> |
| #else |
| # include <algo.h> |
| # include <assert.h> |
| #endif |
| |
| #if defined (EH_NEW_IOSTREAMS) |
| # include <iostream> |
| #else |
| # include <iostream.h> |
| #endif |
| |
| // |
| // SortBuffer -- a buffer of SortClass objects that can be used to test sorting. |
| // |
| struct SortBuffer |
| { |
| enum { kBufferSize = 100 }; |
| |
| SortClass* begin() { return items; } |
| const SortClass* begin() const { return items; } |
| SortClass* end() { return items + kBufferSize; } |
| const SortClass* end() const { return items + kBufferSize; } |
| |
| // Sort each half of the buffer and reset the address of each element |
| // so that merge() can be tested for stability. |
| void PrepareMerge() |
| { |
| EH_STD::sort( begin(), begin() + ( end() - begin() )/2 ); |
| EH_STD::sort( begin() + ( end() - begin() )/2, end() ); |
| for ( SortClass* p = begin(); p != end(); p++ ) |
| p->ResetAddress(); |
| } |
| |
| SortBuffer() |
| { |
| PrepareMerge(); |
| } |
| |
| SortBuffer( const SortBuffer& rhs ) |
| { |
| SortClass* q = begin(); |
| for ( const SortClass* p = rhs.begin() ; p != rhs.end(); p++,q++ ) |
| *q = *p; |
| } |
| |
| private: |
| SortClass items[kBufferSize]; |
| }; |
| |
| // |
| // less_by_reference -- a functor for comparing objects against a |
| // constant value. |
| // |
| template <class T> |
| struct less_by_reference |
| { |
| less_by_reference( const T& arg ) : fArg(arg) {} |
| bool operator()( const T& x ) const { return x < fArg; } |
| private: |
| const T& fArg; |
| }; |
| |
| struct test_stable_partition |
| { |
| test_stable_partition( const SortBuffer& buf ) |
| : orig( buf ), partitionPoint(SortClass::kRange / 2) { |
| gTestController.SetCurrentTestName("stable_partition()"); |
| } |
| |
| void operator()( SortBuffer& buf ) const |
| { |
| less_by_reference<SortClass> throw_cmp( partitionPoint ); |
| |
| SortClass* d = EH_STD::stable_partition( buf.begin(), buf.end(), throw_cmp ); |
| |
| // Suppress warning about unused variable. |
| d; |
| |
| // If we get here no exception occurred during the operation. |
| // Stop any potential failures that might occur during verification. |
| gTestController.CancelFailureCountdown(); |
| |
| // Prepare an array of counts of the occurrence of each value in |
| // the legal range. |
| unsigned counts[SortClass::kRange]; |
| EH_STD::fill_n( counts, (int)SortClass::kRange, 0 ); |
| for ( const SortClass *q = orig.begin(); q != orig.end(); q++ ) |
| counts[ q->value() ]++; |
| |
| less_by_reference<TestClass> cmp( partitionPoint ); |
| for ( const SortClass* p = buf.begin(); p != buf.end(); p++ ) |
| { |
| // Check that adjacent items with the same value haven't been |
| // reordered. This could be a more thorough test. |
| if ( p != buf.begin() && p->value() == p[-1].value() ) { |
| EH_ASSERT( p->GetAddress() > p[-1].GetAddress() ); |
| } |
| |
| // Check that the partitioning worked. |
| EH_ASSERT( (p < d) == cmp( *p ) ); |
| |
| // Decrement the appropriate count for each value. |
| counts[ p->value() ]--; |
| } |
| |
| // Check that the values were only rearranged, and none were lost. |
| for ( unsigned j = 0; j < SortClass::kRange; j++ ) { |
| EH_ASSERT( counts[j] == 0 ); |
| } |
| } |
| |
| private: |
| const SortBuffer& orig; |
| SortClass partitionPoint; |
| }; |
| |
| void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf ); |
| |
| /*=================================================================================== |
| assert_sorted_version |
| |
| EFFECTS: Asserts that buf is a stable-sorted version of orig. |
| ====================================================================================*/ |
| void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf ) |
| { |
| // Stop any potential failures that might occur during verification. |
| gTestController.CancelFailureCountdown(); |
| |
| // Prepare an array of counts of the occurrence of each value in |
| // the legal range. |
| unsigned counts[SortClass::kRange]; |
| EH_STD::fill_n( counts, (int)SortClass::kRange, 0 ); |
| for ( const SortClass *q = orig.begin(); q != orig.end(); q++ ) |
| counts[ q->value() ]++; |
| |
| // Check that each element is greater than the previous one, or if they are |
| // equal, that their order has been preserved. |
| for ( const SortClass* p = buf.begin(); p != buf.end(); p++ ) |
| { |
| if ( p != buf.begin() ) { |
| EH_ASSERT( p->value() > p[-1].value() |
| || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() ); |
| } |
| // Decrement the appropriate count for each value. |
| counts[ p->value() ]--; |
| } |
| |
| // Check that the values were only rearranged, and none were lost. |
| for ( unsigned j = 0; j < SortClass::kRange; j++ ) { |
| EH_ASSERT( counts[j] == 0 ); |
| } |
| } |
| |
| // |
| // The test operators |
| // |
| struct test_stable_sort_1 |
| { |
| test_stable_sort_1( const SortBuffer& buf ) |
| : orig( buf ) { |
| gTestController.SetCurrentTestName("stable_sort() #1"); |
| } |
| |
| void operator()( SortBuffer& buf ) const |
| { |
| EH_STD::stable_sort( buf.begin(), buf.end() ); |
| assert_sorted_version( orig, buf ); |
| } |
| |
| private: |
| const SortBuffer& orig; |
| }; |
| |
| struct test_stable_sort_2 |
| { |
| test_stable_sort_2( const SortBuffer& buf ) |
| : orig( buf ) { |
| gTestController.SetCurrentTestName("stable_sort() #2"); |
| } |
| |
| void operator()( SortBuffer& buf ) const |
| { |
| EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() ); |
| assert_sorted_version( orig, buf ); |
| } |
| |
| private: |
| const SortBuffer& orig; |
| }; |
| |
| struct test_inplace_merge_1 |
| { |
| test_inplace_merge_1( SortBuffer& buf ) |
| : orig( buf ) { |
| gTestController.SetCurrentTestName("inplace_merge #1()"); |
| } |
| |
| void operator()( SortBuffer& buf ) const |
| { |
| EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() ); |
| assert_sorted_version( orig, buf ); |
| } |
| |
| private: |
| const SortBuffer& orig; |
| }; |
| |
| struct test_inplace_merge_2 |
| { |
| test_inplace_merge_2( SortBuffer& buf ) |
| : orig( buf ) { |
| gTestController.SetCurrentTestName("inplace_merge() #2"); |
| } |
| |
| void operator()( SortBuffer& buf ) const |
| { |
| EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(), |
| EH_STD::less<SortClass>() ); |
| assert_sorted_version( orig, buf ); |
| } |
| |
| private: |
| const SortBuffer& orig; |
| }; |
| |
| void test_algo() |
| { |
| SortBuffer mergeBuf; |
| mergeBuf.PrepareMerge(); |
| |
| EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl; |
| WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) ); |
| WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) ); |
| |
| SortBuffer buf; |
| WeakCheck( buf, test_stable_sort_1( buf ) ); |
| WeakCheck( buf, test_stable_sort_2( buf ) ); |
| WeakCheck( buf, test_stable_partition( buf ) ); |
| } |