1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/genericopenlibs/cppstdlib/stl/test/eh/test_algo.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,254 @@
1.4 +/***********************************************************************************
1.5 + test_algo.cpp
1.6 +
1.7 + * Copyright (c) 1997
1.8 + * Mark of the Unicorn, Inc.
1.9 + *
1.10 + * Permission to use, copy, modify, distribute and sell this software
1.11 + * and its documentation for any purpose is hereby granted without fee,
1.12 + * provided that the above copyright notice appear in all copies and
1.13 + * that both that copyright notice and this permission notice appear
1.14 + * in supporting documentation. Mark of the Unicorn makes no
1.15 + * representations about the suitability of this software for any
1.16 + * purpose. It is provided "as is" without express or implied warranty.
1.17 +
1.18 +***********************************************************************************/
1.19 +#include "Tests.h"
1.20 +#include "LeakCheck.h"
1.21 +#include "SortClass.h"
1.22 +
1.23 +#if defined (EH_NEW_HEADERS)
1.24 +# include <algorithm>
1.25 +# include <cassert>
1.26 +#else
1.27 +# include <algo.h>
1.28 +# include <assert.h>
1.29 +#endif
1.30 +
1.31 +#if defined (EH_NEW_IOSTREAMS)
1.32 +# include <iostream>
1.33 +#else
1.34 +# include <iostream.h>
1.35 +#endif
1.36 +
1.37 +//
1.38 +// SortBuffer -- a buffer of SortClass objects that can be used to test sorting.
1.39 +//
1.40 +struct SortBuffer
1.41 +{
1.42 + enum { kBufferSize = 100 };
1.43 +
1.44 + SortClass* begin() { return items; }
1.45 + const SortClass* begin() const { return items; }
1.46 + SortClass* end() { return items + kBufferSize; }
1.47 + const SortClass* end() const { return items + kBufferSize; }
1.48 +
1.49 + // Sort each half of the buffer and reset the address of each element
1.50 + // so that merge() can be tested for stability.
1.51 + void PrepareMerge()
1.52 + {
1.53 + EH_STD::sort( begin(), begin() + ( end() - begin() )/2 );
1.54 + EH_STD::sort( begin() + ( end() - begin() )/2, end() );
1.55 + for ( SortClass* p = begin(); p != end(); p++ )
1.56 + p->ResetAddress();
1.57 + }
1.58 +
1.59 + SortBuffer()
1.60 + {
1.61 + PrepareMerge();
1.62 + }
1.63 +
1.64 + SortBuffer( const SortBuffer& rhs )
1.65 + {
1.66 + SortClass* q = begin();
1.67 + for ( const SortClass* p = rhs.begin() ; p != rhs.end(); p++,q++ )
1.68 + *q = *p;
1.69 + }
1.70 +
1.71 +private:
1.72 + SortClass items[kBufferSize];
1.73 +};
1.74 +
1.75 +//
1.76 +// less_by_reference -- a functor for comparing objects against a
1.77 +// constant value.
1.78 +//
1.79 +template <class T>
1.80 +struct less_by_reference
1.81 +{
1.82 + less_by_reference( const T& arg ) : fArg(arg) {}
1.83 + bool operator()( const T& x ) const { return x < fArg; }
1.84 +private:
1.85 + const T& fArg;
1.86 +};
1.87 +
1.88 +struct test_stable_partition
1.89 +{
1.90 + test_stable_partition( const SortBuffer& buf )
1.91 + : orig( buf ), partitionPoint(SortClass::kRange / 2) {
1.92 + gTestController.SetCurrentTestName("stable_partition()");
1.93 + }
1.94 +
1.95 + void operator()( SortBuffer& buf ) const
1.96 + {
1.97 + less_by_reference<SortClass> throw_cmp( partitionPoint );
1.98 +
1.99 + SortClass* d = EH_STD::stable_partition( buf.begin(), buf.end(), throw_cmp );
1.100 +
1.101 + // If we get here no exception occurred during the operation.
1.102 + // Stop any potential failures that might occur during verification.
1.103 + gTestController.CancelFailureCountdown();
1.104 +
1.105 + // Prepare an array of counts of the occurrence of each value in
1.106 + // the legal range.
1.107 + unsigned counts[SortClass::kRange];
1.108 + EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );
1.109 + for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )
1.110 + counts[ q->value() ]++;
1.111 +
1.112 + less_by_reference<TestClass> cmp( partitionPoint );
1.113 + for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )
1.114 + {
1.115 + // Check that adjacent items with the same value haven't been
1.116 + // reordered. This could be a more thorough test.
1.117 + if ( p != buf.begin() && p->value() == p[-1].value() )
1.118 + EH_ASSERT( p->GetAddress() > p[-1].GetAddress() );
1.119 +
1.120 + // Check that the partitioning worked.
1.121 + EH_ASSERT( (p < d) == cmp( *p ) );
1.122 +
1.123 + // Decrement the appropriate count for each value.
1.124 + counts[ p->value() ]--;
1.125 + }
1.126 +
1.127 + // Check that the values were only rearranged, and none were lost.
1.128 + for ( unsigned j = 0; j < SortClass::kRange; j++ )
1.129 + EH_ASSERT( counts[j] == 0 );
1.130 + }
1.131 +
1.132 +private:
1.133 + const SortBuffer& orig;
1.134 + SortClass partitionPoint;
1.135 +};
1.136 +
1.137 +void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf );
1.138 +
1.139 +/*===================================================================================
1.140 + assert_sorted_version
1.141 +
1.142 + EFFECTS: Asserts that buf is a stable-sorted version of orig.
1.143 +====================================================================================*/
1.144 +void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf )
1.145 +{
1.146 + // Stop any potential failures that might occur during verification.
1.147 + gTestController.CancelFailureCountdown();
1.148 +
1.149 + // Prepare an array of counts of the occurrence of each value in
1.150 + // the legal range.
1.151 + unsigned counts[SortClass::kRange];
1.152 + EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );
1.153 + for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )
1.154 + counts[ q->value() ]++;
1.155 +
1.156 + // Check that each element is greater than the previous one, or if they are
1.157 + // equal, that their order has been preserved.
1.158 + for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )
1.159 + {
1.160 + if ( p != buf.begin() )
1.161 + EH_ASSERT( p->value() > p[-1].value()
1.162 + || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() );
1.163 + // Decrement the appropriate count for each value.
1.164 + counts[ p->value() ]--;
1.165 + }
1.166 +
1.167 + // Check that the values were only rearranged, and none were lost.
1.168 + for ( unsigned j = 0; j < SortClass::kRange; j++ )
1.169 + EH_ASSERT( counts[j] == 0 );
1.170 +}
1.171 +
1.172 +//
1.173 +// The test operators
1.174 +//
1.175 +struct test_stable_sort_1
1.176 +{
1.177 + test_stable_sort_1( const SortBuffer& buf )
1.178 + : orig( buf ) {
1.179 + gTestController.SetCurrentTestName("stable_sort() #1");
1.180 + }
1.181 +
1.182 + void operator()( SortBuffer& buf ) const
1.183 + {
1.184 + EH_STD::stable_sort( buf.begin(), buf.end() );
1.185 + assert_sorted_version( orig, buf );
1.186 + }
1.187 +
1.188 +private:
1.189 + const SortBuffer& orig;
1.190 +};
1.191 +
1.192 +struct test_stable_sort_2
1.193 +{
1.194 + test_stable_sort_2( const SortBuffer& buf )
1.195 + : orig( buf ) {
1.196 + gTestController.SetCurrentTestName("stable_sort() #2");
1.197 + }
1.198 +
1.199 + void operator()( SortBuffer& buf ) const
1.200 + {
1.201 + EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() );
1.202 + assert_sorted_version( orig, buf );
1.203 + }
1.204 +
1.205 +private:
1.206 + const SortBuffer& orig;
1.207 +};
1.208 +
1.209 +struct test_inplace_merge_1
1.210 +{
1.211 + test_inplace_merge_1( SortBuffer& buf )
1.212 + : orig( buf ) {
1.213 + gTestController.SetCurrentTestName("inplace_merge #1()");
1.214 + }
1.215 +
1.216 + void operator()( SortBuffer& buf ) const
1.217 + {
1.218 + EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() );
1.219 + assert_sorted_version( orig, buf );
1.220 + }
1.221 +
1.222 +private:
1.223 + const SortBuffer& orig;
1.224 +};
1.225 +
1.226 +struct test_inplace_merge_2
1.227 +{
1.228 + test_inplace_merge_2( SortBuffer& buf )
1.229 + : orig( buf ) {
1.230 + gTestController.SetCurrentTestName("inplace_merge() #2");
1.231 + }
1.232 +
1.233 + void operator()( SortBuffer& buf ) const
1.234 + {
1.235 + EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(),
1.236 + EH_STD::less<SortClass>() );
1.237 + assert_sorted_version( orig, buf );
1.238 + }
1.239 +
1.240 +private:
1.241 + const SortBuffer& orig;
1.242 +};
1.243 +
1.244 +void test_algo()
1.245 +{
1.246 + SortBuffer mergeBuf;
1.247 + mergeBuf.PrepareMerge();
1.248 +
1.249 + EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl;
1.250 + WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) );
1.251 + WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) );
1.252 +
1.253 + SortBuffer buf;
1.254 + WeakCheck( buf, test_stable_sort_1( buf ) );
1.255 + WeakCheck( buf, test_stable_sort_2( buf ) );
1.256 + WeakCheck( buf, test_stable_partition( buf ) );
1.257 +}