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