lib/3rdparty/stlport/test/eh/test_algo.cpp

   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         // Suppress warning about unused variable.
  99         d;
 100
 101         // If we get here no exception occurred during the operation.
 102         // Stop any potential failures that might occur during verification.
 103         gTestController.CancelFailureCountdown();
 104
 105         // Prepare an array of counts of the occurrence of each value in
 106         // the legal range.
 107         unsigned counts[SortClass::kRange];
 108         EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );
 109         for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )
 110             counts[ q->value() ]++;
 111
 112         less_by_reference<TestClass> cmp( partitionPoint );
 113         for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )
 114         {
 115           // Check that adjacent items with the same value haven't been
 116           // reordered. This could be a more thorough test.
 117             if ( p != buf.begin() && p->value() == p[-1].value() ) {
 118                 EH_ASSERT( p->GetAddress() > p[-1].GetAddress() );
 119             }
 120
 121             // Check that the partitioning worked.
 122             EH_ASSERT( (p < d) == cmp( *p ) );
 123
 124             // Decrement the appropriate count for each value.
 125             counts[ p->value() ]--;
 126         }
 127
 128         // Check that the values were only rearranged, and none were lost.
 129         for ( unsigned j = 0; j < SortClass::kRange; j++ ) {
 130             EH_ASSERT( counts[j] == 0 );
 131         }
 132     }
 133
 134 private:
 135     const SortBuffer& orig;
 136     SortClass partitionPoint;
 137 };
 138
 139 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf );
 140
 141 /*===================================================================================
 142   assert_sorted_version
 143
 144   EFFECTS: Asserts that buf is a stable-sorted version of orig.
 145 ====================================================================================*/
 146 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf )
 147 {
 148   // Stop any potential failures that might occur during verification.
 149     gTestController.CancelFailureCountdown();
 150
 151     // Prepare an array of counts of the occurrence of each value in
 152     // the legal range.
 153     unsigned counts[SortClass::kRange];
 154     EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );
 155     for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )
 156         counts[ q->value() ]++;
 157
 158   // Check that each element is greater than the previous one, or if they are
 159   // equal, that their order has been preserved.
 160     for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )
 161     {
 162         if ( p != buf.begin() ) {
 163             EH_ASSERT( p->value() > p[-1].value()
 164                     || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() );
 165         }
 166     // Decrement the appropriate count for each value.
 167         counts[ p->value() ]--;
 168     }
 169
 170   // Check that the values were only rearranged, and none were lost.
 171     for ( unsigned j = 0; j < SortClass::kRange; j++ ) {
 172         EH_ASSERT( counts[j] == 0 );
 173     }
 174 }
 175
 176 //
 177 // The test operators
 178 //
 179 struct test_stable_sort_1
 180 {
 181     test_stable_sort_1( const SortBuffer& buf )
 182         : orig( buf ) {
 183         gTestController.SetCurrentTestName("stable_sort() #1");
 184         }
 185
 186     void operator()( SortBuffer& buf ) const
 187     {
 188         EH_STD::stable_sort( buf.begin(), buf.end() );
 189         assert_sorted_version( orig, buf );
 190     }
 191
 192 private:
 193     const SortBuffer& orig;
 194 };
 195
 196 struct test_stable_sort_2
 197 {
 198     test_stable_sort_2( const SortBuffer& buf )
 199         : orig( buf ) {
 200             gTestController.SetCurrentTestName("stable_sort() #2");
 201         }
 202
 203     void operator()( SortBuffer& buf ) const
 204     {
 205       EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() );
 206       assert_sorted_version( orig, buf );
 207     }
 208
 209 private:
 210     const SortBuffer& orig;
 211 };
 212
 213 struct test_inplace_merge_1
 214 {
 215     test_inplace_merge_1( SortBuffer& buf )
 216         : orig( buf ) {
 217         gTestController.SetCurrentTestName("inplace_merge #1()");
 218         }
 219
 220     void operator()( SortBuffer& buf ) const
 221     {
 222         EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() );
 223         assert_sorted_version( orig, buf );
 224     }
 225
 226 private:
 227     const SortBuffer& orig;
 228 };
 229
 230 struct test_inplace_merge_2
 231 {
 232     test_inplace_merge_2( SortBuffer& buf )
 233         : orig( buf ) {
 234         gTestController.SetCurrentTestName("inplace_merge() #2");
 235         }
 236
 237     void operator()( SortBuffer& buf ) const
 238     {
 239         EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(),
 240                        EH_STD::less<SortClass>() );
 241         assert_sorted_version( orig, buf );
 242     }
 243
 244 private:
 245     const SortBuffer& orig;
 246 };
 247
 248 void test_algo()
 249 {
 250     SortBuffer mergeBuf;
 251     mergeBuf.PrepareMerge();
 252
 253     EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl;
 254     WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) );
 255     WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) );
 256
 257     SortBuffer buf;
 258     WeakCheck( buf, test_stable_sort_1( buf ) );
 259     WeakCheck( buf, test_stable_sort_2( buf ) );
 260     WeakCheck( buf, test_stable_partition( buf ) );
 261 }