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 // SortBuffer -- a buffer of SortClass objects that can be used to test sorting.

    36 //

    37 struct SortBuffer

    38 {

    39     enum { kBufferSize = 100 };

    40 

    41     SortClass* begin() { return items; }

    42     const SortClass* begin() const { return items; }

    43     SortClass* end() { return items + kBufferSize; }

    44     const SortClass* end() const { return items + kBufferSize; }

    45 

    46   // Sort each half of the buffer and reset the address of each element

    47   // so that merge() can be tested for stability.

    48     void PrepareMerge()

    49     {

    50         EH_STD::sort( begin(), begin() + ( end() - begin() )/2 );

    51         EH_STD::sort( begin() + ( end() - begin() )/2, end() );

    52         for ( SortClass* p = begin(); p != end(); p++ )

    53             p->ResetAddress();

    54     }

    55 

    56   SortBuffer()

    57   {

    58     PrepareMerge();

    59   }

    60 

    61   SortBuffer( const SortBuffer& rhs )

    62   {

    63     SortClass* q = begin();

    64     for ( const SortClass* p = rhs.begin() ; p != rhs.end(); p++,q++ )

    65       *q = *p;

    66   }

    67 

    68 private:

    69     SortClass items[kBufferSize];

    70 };

    71 

    72 //

    73 // less_by_reference -- a functor for comparing objects against a

    74 //   constant value.

    75 //

    76 template <class T>

    77 struct less_by_reference

    78 {

    79     less_by_reference( const T& arg ) : fArg(arg) {}

    80     bool operator()( const T& x ) const { return x < fArg; }

    81 private:

    82     const T& fArg;

    83 };

    84 

    85 struct test_stable_partition

    86 {

    87     test_stable_partition( const SortBuffer& buf )

    88         : orig( buf ), partitionPoint(SortClass::kRange / 2) {

    89         gTestController.SetCurrentTestName("stable_partition()");

    90         }

    91 

    92     void operator()( SortBuffer& buf ) const

    93     {

    94         less_by_reference<SortClass> throw_cmp( partitionPoint );

    95 

    96         SortClass* d = EH_STD::stable_partition( buf.begin(), buf.end(), throw_cmp );

    97 

    98     // If we get here no exception occurred during the operation.

    99     // Stop any potential failures that might occur during verification.

   100         gTestController.CancelFailureCountdown();

   101 

   102         // Prepare an array of counts of the occurrence of each value in

   103         // the legal range.

   104         unsigned counts[SortClass::kRange];

   105         EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );

   106         for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )

   107             counts[ q->value() ]++;

   108 

   109         less_by_reference<TestClass> cmp( partitionPoint );

   110         for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )

   111         {

   112           // Check that adjacent items with the same value haven't been

   113           // reordered. This could be a more thorough test.

   114             if ( p != buf.begin() && p->value() == p[-1].value() )

   115                 EH_ASSERT( p->GetAddress() > p[-1].GetAddress() );

   116 

   117             // Check that the partitioning worked.

   118             EH_ASSERT( (p < d) == cmp( *p ) );

   119 

   120             // Decrement the appropriate count for each value.

   121             counts[ p->value() ]--;

   122         }

   123 

   124         // Check that the values were only rearranged, and none were lost.

   125         for ( unsigned j = 0; j < SortClass::kRange; j++ )

   126             EH_ASSERT( counts[j] == 0 );

   127     }

   128 

   129 private:

   130     const SortBuffer& orig;

   131     SortClass partitionPoint;

   132 };

   133 

   134 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf );

   135 

   136 /*===================================================================================

   137   assert_sorted_version

   138 

   139   EFFECTS: Asserts that buf is a stable-sorted version of orig.

   140 ====================================================================================*/

   141 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf )

   142 {

   143   // Stop any potential failures that might occur during verification.

   144     gTestController.CancelFailureCountdown();

   145 

   146     // Prepare an array of counts of the occurrence of each value in

   147     // the legal range.

   148     unsigned counts[SortClass::kRange];

   149     EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );

   150     for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )

   151         counts[ q->value() ]++;

   152 

   153   // Check that each element is greater than the previous one, or if they are

   154   // equal, that their order has been preserved.

   155     for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )

   156     {

   157         if ( p != buf.begin() )

   158             EH_ASSERT( p->value() > p[-1].value()

   159                     || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() );

   160     // Decrement the appropriate count for each value.

   161         counts[ p->value() ]--;

   162     }

   163 

   164   // Check that the values were only rearranged, and none were lost.

   165     for ( unsigned j = 0; j < SortClass::kRange; j++ )

   166         EH_ASSERT( counts[j] == 0 );

   167 }

   168 

   169 //

   170 // The test operators

   171 //

   172 struct test_stable_sort_1

   173 {

   174     test_stable_sort_1( const SortBuffer& buf )

   175         : orig( buf ) {

   176         gTestController.SetCurrentTestName("stable_sort() #1");

   177         }

   178 

   179     void operator()( SortBuffer& buf ) const

   180     {

   181         EH_STD::stable_sort( buf.begin(), buf.end() );

   182         assert_sorted_version( orig, buf );

   183     }

   184 

   185 private:

   186     const SortBuffer& orig;

   187 };

   188 

   189 struct test_stable_sort_2

   190 {

   191     test_stable_sort_2( const SortBuffer& buf )

   192         : orig( buf ) {

   193             gTestController.SetCurrentTestName("stable_sort() #2");

   194         }

   195 

   196     void operator()( SortBuffer& buf ) const

   197     {

   198       EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() );

   199       assert_sorted_version( orig, buf );

   200     }

   201 

   202 private:

   203     const SortBuffer& orig;

   204 };

   205 

   206 struct test_inplace_merge_1

   207 {

   208     test_inplace_merge_1( SortBuffer& buf )

   209         : orig( buf ) {

   210         gTestController.SetCurrentTestName("inplace_merge #1()");

   211         }

   212 

   213     void operator()( SortBuffer& buf ) const

   214     {

   215         EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() );

   216         assert_sorted_version( orig, buf );

   217     }

   218 

   219 private:

   220     const SortBuffer& orig;

   221 };

   222 

   223 struct test_inplace_merge_2

   224 {

   225     test_inplace_merge_2( SortBuffer& buf )

   226         : orig( buf ) {

   227         gTestController.SetCurrentTestName("inplace_merge() #2");

   228         }

   229 

   230     void operator()( SortBuffer& buf ) const

   231     {

   232         EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(),

   233                        EH_STD::less<SortClass>() );

   234         assert_sorted_version( orig, buf );

   235     }

   236 

   237 private:

   238     const SortBuffer& orig;

   239 };

   240 

   241 void test_algo()

   242 {

   243     SortBuffer mergeBuf;

   244     mergeBuf.PrepareMerge();

   245 

   246     EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl;

   247     WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) );

   248     WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) );

   249 

   250     SortBuffer buf;

   251     WeakCheck( buf, test_stable_sort_1( buf ) );

   252     WeakCheck( buf, test_stable_sort_2( buf ) );

   253     WeakCheck( buf, test_stable_partition( buf ) );

   254 }