1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/genericopenlibs/cppstdlib/stl/test/eh/test_insert.h Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,552 @@
1.4 +/***********************************************************************************
1.5 + test_insert.h
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 +#ifndef test_insert_H_
1.20 +#define test_insert_H_
1.21 +
1.22 +# include "Prefix.h"
1.23 +# if defined (EH_NEW_HEADERS)
1.24 +# include <utility>
1.25 +# include <vector>
1.26 +# include <cassert>
1.27 +# include <climits>
1.28 +# else
1.29 +# include <vector.h>
1.30 +# include <assert.h>
1.31 +# include <limits.h>
1.32 +# endif
1.33 +#include "random_number.h"
1.34 +#include "nc_alloc.h"
1.35 +#include "ThrowCompare.h"
1.36 +
1.37 +// A classification system for containers, for verification
1.38 +struct container_tag {};
1.39 +struct sequence_container_tag {};
1.40 +struct associative_container_tag {};
1.41 +
1.42 +struct set_tag {};
1.43 +struct multiset_tag {};
1.44 +struct map_tag {};
1.45 +struct multimap_tag {};
1.46 +
1.47 +template <class C, class Iter>
1.48 +size_t CountNewItems( const C&, const Iter& firstNew,
1.49 + const Iter& lastNew, sequence_container_tag )
1.50 +{
1.51 + size_t dist = 0;
1.52 +#if 0 //def __SUNPRO_CC
1.53 + EH_DISTANCE( firstNew, lastNew, dist );
1.54 +#else
1.55 + EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist );
1.56 +#endif
1.57 + return dist;
1.58 +}
1.59 +
1.60 +template <class C, class Iter>
1.61 +size_t CountNewItems( const C& c, const Iter& firstNew,
1.62 + const Iter& lastNew, multimap_tag )
1.63 +{
1.64 + return CountNewItems( c, firstNew, lastNew, sequence_container_tag() );
1.65 +}
1.66 +
1.67 +template <class C, class Iter>
1.68 +size_t CountNewItems( const C& c, const Iter& firstNew,
1.69 + const Iter& lastNew, multiset_tag )
1.70 +{
1.71 + return CountNewItems( c, firstNew, lastNew, sequence_container_tag() );
1.72 +}
1.73 +
1.74 +
1.75 +template <class C, class Iter, class KeyOfValue>
1.76 +#ifdef __BORLANDC__
1.77 +size_t CountUniqueItems_Aux( const C& original, const Iter& firstNew,
1.78 +#else
1.79 +size_t CountUniqueItems_Aux( const C& original, Iter firstNew,
1.80 +#endif
1.81 + Iter lastNew, const KeyOfValue& keyOfValue )
1.82 +{
1.83 + typedef typename C::key_type key;
1.84 + typedef typename C::const_iterator const_iter;
1.85 + typedef EH_STD::vector<key> key_list;
1.86 + typedef typename key_list::iterator key_iterator;
1.87 + key_list keys;
1.88 + size_t dist = 0;
1.89 +#ifdef __SUNPRO_CC
1.90 + EH_DISTANCE( firstNew, lastNew, dist );
1.91 +#else
1.92 + EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist );
1.93 +#endif
1.94 + keys.reserve( dist );
1.95 + for ( Iter x = firstNew; x != lastNew; ++x )
1.96 + keys.push_back( keyOfValue(*x) );
1.97 +
1.98 + EH_STD::sort( keys.begin(), keys.end() );
1.99 + key_iterator last = EH_STD::unique( keys.begin(), keys.end() );
1.100 +
1.101 + size_t cnt = 0;
1.102 + for ( key_iterator tmp = keys.begin(); tmp != last; ++tmp )
1.103 + {
1.104 + if ( const_iter(original.find( *tmp )) == const_iter(original.end()) )
1.105 + ++cnt;
1.106 + }
1.107 + return cnt;
1.108 +}
1.109 +
1.110 +#if ! defined (__SGI_STL)
1.111 +EH_BEGIN_NAMESPACE
1.112 +template <class T>
1.113 +struct identity
1.114 +{
1.115 + const T& operator()( const T& x ) const { return x; }
1.116 +};
1.117 +# if ! defined (__KCC)
1.118 +template <class _Pair>
1.119 +struct select1st : public unary_function<_Pair, typename _Pair::first_type> {
1.120 + const typename _Pair::first_type& operator()(const _Pair& __x) const {
1.121 + return __x.first;
1.122 + }
1.123 +};
1.124 +# endif
1.125 +EH_END_NAMESPACE
1.126 +#endif
1.127 +
1.128 +template <class C, class Iter>
1.129 +size_t CountUniqueItems( const C& original, const Iter& firstNew,
1.130 + const Iter& lastNew, set_tag )
1.131 +{
1.132 + typedef typename C::value_type value_type;
1.133 + return CountUniqueItems_Aux( original, firstNew, lastNew,
1.134 + EH_STD::identity<value_type>() );
1.135 +}
1.136 +
1.137 +template <class C, class Iter>
1.138 +size_t CountUniqueItems( const C& original, const Iter& firstNew,
1.139 + const Iter& lastNew, map_tag )
1.140 +{
1.141 +#ifdef EH_MULTI_CONST_TEMPLATE_ARG_BUG
1.142 + return CountUniqueItems_Aux( original, firstNew, lastNew,
1.143 + EH_SELECT1ST_HINT<C::value_type, C::key_type>() );
1.144 +#else
1.145 + typedef typename C::value_type value_type;
1.146 + return CountUniqueItems_Aux( original, firstNew, lastNew,
1.147 + EH_STD::select1st<value_type>() );
1.148 +#endif
1.149 +}
1.150 +
1.151 +template <class C, class Iter>
1.152 +size_t CountNewItems( const C& original, const Iter& firstNew,
1.153 + const Iter& lastNew, map_tag )
1.154 +{
1.155 + return CountUniqueItems( original, firstNew, lastNew,
1.156 + container_category( original ) );
1.157 +}
1.158 +
1.159 +template <class C, class Iter>
1.160 +size_t CountNewItems( const C& original, const Iter& firstNew,
1.161 + const Iter& lastNew, set_tag )
1.162 +{
1.163 + return CountUniqueItems( original, firstNew, lastNew,
1.164 + container_category( original ) );
1.165 +}
1.166 +
1.167 +template <class C, class SrcIter>
1.168 +inline void VerifyInsertion( const C& original, const C& result,
1.169 + const SrcIter& firstNew, const SrcIter& lastNew,
1.170 + size_t, associative_container_tag )
1.171 +{
1.172 + typedef typename C::const_iterator DstIter;
1.173 + DstIter first1 = original.begin();
1.174 + DstIter first2 = result.begin();
1.175 +
1.176 + DstIter* from_orig = new DstIter[original.size()];
1.177 + DstIter* last_from_orig = from_orig;
1.178 +
1.179 + // fbp : for hashed containers, the following is needed :
1.180 + while ( first2 != result.end() )
1.181 + {
1.182 + EH_STD::pair<DstIter, DstIter> p = EH_STD::mismatch( first1, original.end(), first2 );
1.183 + if ( p.second != result.end() )
1.184 + {
1.185 + SrcIter srcItem = EH_STD::find( SrcIter(firstNew), SrcIter(lastNew), *p.second );
1.186 +
1.187 + if (srcItem == lastNew)
1.188 + {
1.189 + // not found in input range, probably re-ordered from the orig
1.190 + DstIter* tmp;
1.191 + tmp = EH_STD::find( from_orig, last_from_orig, p.first );
1.192 +
1.193 + // if already here, exclude
1.194 + if (tmp != last_from_orig)
1.195 + {
1.196 + EH_STD::copy(tmp+1, last_from_orig, tmp);
1.197 + last_from_orig--;
1.198 + }
1.199 + else
1.200 + {
1.201 + // register re-ordered element
1.202 + DstIter dstItem;
1.203 + dstItem = EH_STD::find( first1, original.end(), *p.first );
1.204 + EH_ASSERT( dstItem != original.end() );
1.205 + *last_from_orig = dstItem;
1.206 + last_from_orig++;
1.207 + ++p.first;
1.208 + }
1.209 + }
1.210 + ++p.second;
1.211 + }
1.212 + first1 = p.first;
1.213 + first2 = p.second;
1.214 + }
1.215 +
1.216 + delete [] from_orig;
1.217 +}
1.218 +
1.219 +// VC++
1.220 +template <class C, class SrcIter>
1.221 +inline void VerifyInsertion(
1.222 + const C& original, const C& result, const SrcIter& firstNew,
1.223 + const SrcIter& lastNew, size_t, set_tag )
1.224 +{
1.225 + VerifyInsertion( original, result, firstNew, lastNew,
1.226 + size_t(0), associative_container_tag() );
1.227 +}
1.228 +
1.229 +template <class C, class SrcIter>
1.230 +inline void VerifyInsertion(const C& original, const C& result,
1.231 + const SrcIter& firstNew, const SrcIter& lastNew,
1.232 + size_t, multiset_tag )
1.233 +{
1.234 + VerifyInsertion( original, result, firstNew, lastNew,
1.235 + size_t(0), associative_container_tag() );
1.236 +}
1.237 +
1.238 +template <class C, class SrcIter>
1.239 +inline void VerifyInsertion(
1.240 + const C& original, const C& result, const SrcIter& firstNew,
1.241 + const SrcIter& lastNew, size_t, map_tag )
1.242 +{
1.243 + VerifyInsertion( original, result, firstNew, lastNew,
1.244 + size_t(0), associative_container_tag() );
1.245 +}
1.246 +
1.247 +template <class C, class SrcIter>
1.248 +inline void VerifyInsertion(
1.249 + const C& original, const C& result, const SrcIter& firstNew,
1.250 + const SrcIter& lastNew, size_t, multimap_tag )
1.251 +{
1.252 + VerifyInsertion( original, result, firstNew, lastNew,
1.253 + size_t(0), associative_container_tag() );
1.254 +}
1.255 +
1.256 +template <class C, class SrcIter>
1.257 +void VerifyInsertion(
1.258 +# ifdef _MSC_VER
1.259 + const C& original, const C& result, SrcIter firstNew,
1.260 + SrcIter lastNew, size_t insPos, sequence_container_tag )
1.261 +# else
1.262 + const C& original, const C& result, const SrcIter& firstNew,
1.263 + const SrcIter& lastNew, size_t insPos, sequence_container_tag )
1.264 +# endif
1.265 +{
1.266 + typename C::const_iterator p1 = original.begin();
1.267 + typename C::const_iterator p2 = result.begin();
1.268 + SrcIter tmp(firstNew);
1.269 +
1.270 + for ( size_t n = 0; n < insPos; n++, ++p1, ++p2)
1.271 + EH_ASSERT( *p1 == *p2 );
1.272 +
1.273 + for (; tmp != lastNew; ++p2, ++tmp ) {
1.274 + EH_ASSERT(p2 != result.end());
1.275 + EH_ASSERT(*p2 == *tmp);
1.276 + }
1.277 +
1.278 + for (; p2 != result.end(); ++p1, ++p2 )
1.279 + EH_ASSERT( *p1 == *p2 );
1.280 + EH_ASSERT( p1 == original.end() );
1.281 +}
1.282 +
1.283 +template <class C, class SrcIter>
1.284 +inline void VerifyInsertion( const C& original, const C& result,
1.285 + const SrcIter& firstNew,
1.286 + const SrcIter& lastNew, size_t insPos )
1.287 +{
1.288 + EH_ASSERT( result.size() == original.size() +
1.289 + CountNewItems( original, firstNew, lastNew,
1.290 + container_category(original) ) );
1.291 + VerifyInsertion( original, result, firstNew, lastNew, insPos,
1.292 + container_category(original) );
1.293 +}
1.294 +
1.295 +template <class C, class Value>
1.296 +void VerifyInsertN( const C& original, const C& result, size_t insCnt,
1.297 + const Value& val, size_t insPos )
1.298 +{
1.299 + typename C::const_iterator p1 = original.begin();
1.300 + typename C::const_iterator p2 = result.begin();
1.301 + (void)val; //*TY 02/06/2000 - to suppress unused variable warning under nondebug build
1.302 +
1.303 + for ( size_t n = 0; n < insPos; n++ )
1.304 + EH_ASSERT( *p1++ == *p2++ );
1.305 +
1.306 + while ( insCnt-- > 0 )
1.307 + {
1.308 + EH_ASSERT(p2 != result.end());
1.309 + EH_ASSERT(*p2 == val );
1.310 + ++p2;
1.311 + }
1.312 +
1.313 + while ( p2 != result.end() ) {
1.314 + EH_ASSERT( *p1 == *p2 );
1.315 + ++p1; ++p2;
1.316 + }
1.317 + EH_ASSERT( p1 == original.end() );
1.318 +}
1.319 +
1.320 +template <class C>
1.321 +void prepare_insert_n( C&, size_t ) {}
1.322 +
1.323 +// Metrowerks 1.8 compiler requires that specializations appear first (!!)
1.324 +// or it won't call them. Fixed in 1.9, though.
1.325 +inline void MakeRandomValue(bool& b) { b = bool(random_number(2) != 0); }
1.326 +
1.327 +template<class T>
1.328 +inline void MakeRandomValue(T&) {}
1.329 +
1.330 +template <class C>
1.331 +struct test_insert_one
1.332 +{
1.333 + test_insert_one( const C& orig, int pos =-1 )
1.334 + : original( orig ), fPos( random_number( orig.size() ))
1.335 + {
1.336 + MakeRandomValue( fInsVal );
1.337 + if ( pos != -1 )
1.338 + {
1.339 + fPos = size_t(pos);
1.340 + if ( pos == 0 )
1.341 + gTestController.SetCurrentTestName("single insertion at begin()");
1.342 + else
1.343 + gTestController.SetCurrentTestName("single insertion at end()");
1.344 + }
1.345 + else
1.346 + gTestController.SetCurrentTestName("single insertion at random position");
1.347 + }
1.348 +
1.349 + void operator()( C& c ) const
1.350 + {
1.351 + prepare_insert_n( c, (size_t)1 );
1.352 + typename C::iterator pos = c.begin();
1.353 + EH_STD::advance( pos, size_t(fPos) );
1.354 + c.insert( pos, fInsVal );
1.355 +
1.356 + // Prevent simulated failures during verification
1.357 + gTestController.CancelFailureCountdown();
1.358 + // Success. Check results.
1.359 + VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, fPos );
1.360 + }
1.361 +private:
1.362 + typename C::value_type fInsVal;
1.363 + const C& original;
1.364 + size_t fPos;
1.365 +};
1.366 +
1.367 +template <class C>
1.368 +struct test_insert_n
1.369 +{
1.370 + test_insert_n( const C& orig, size_t insCnt, int pos =-1 )
1.371 + : original( orig ), fPos( random_number( orig.size() )), fInsCnt(insCnt)
1.372 + {
1.373 + MakeRandomValue( fInsVal );
1.374 + if (pos!=-1)
1.375 + {
1.376 + fPos=size_t(pos);
1.377 + if (pos==0)
1.378 + gTestController.SetCurrentTestName("n-ary insertion at begin()");
1.379 + else
1.380 + gTestController.SetCurrentTestName("n-ary insertion at end()");
1.381 + }
1.382 + else
1.383 + gTestController.SetCurrentTestName("n-ary insertion at random position");
1.384 + }
1.385 +
1.386 + void operator()( C& c ) const
1.387 + {
1.388 + prepare_insert_n( c, fInsCnt );
1.389 + typename C::iterator pos = c.begin();
1.390 + EH_STD::advance( pos, fPos );
1.391 + c.insert( pos, fInsCnt, fInsVal );
1.392 +
1.393 + // Prevent simulated failures during verification
1.394 + gTestController.CancelFailureCountdown();
1.395 + // Success. Check results.
1.396 + VerifyInsertN( original, c, fInsCnt, fInsVal, fPos );
1.397 + }
1.398 +private:
1.399 + typename C::value_type fInsVal;
1.400 + const C& original;
1.401 + size_t fPos;
1.402 + size_t fInsCnt;
1.403 +};
1.404 +
1.405 +template <class C>
1.406 +struct test_insert_value
1.407 +{
1.408 + test_insert_value( const C& orig )
1.409 + : original( orig )
1.410 + {
1.411 + MakeRandomValue( fInsVal );
1.412 + gTestController.SetCurrentTestName("insertion of random value");
1.413 + }
1.414 +
1.415 + void operator()( C& c ) const
1.416 + {
1.417 + c.insert( fInsVal );
1.418 +
1.419 + // Prevent simulated failures during verification
1.420 + gTestController.CancelFailureCountdown();
1.421 + // Success. Check results.
1.422 + VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) );
1.423 + }
1.424 +private:
1.425 + typename C::value_type fInsVal;
1.426 + const C& original;
1.427 +};
1.428 +
1.429 +template <class C>
1.430 +struct test_insert_noresize
1.431 +{
1.432 + test_insert_noresize( const C& orig )
1.433 + : original( orig )
1.434 + {
1.435 + MakeRandomValue( fInsVal );
1.436 + gTestController.SetCurrentTestName("insertion of random value without resize");
1.437 + }
1.438 +
1.439 + void operator()( C& c ) const
1.440 + {
1.441 + c.insert_noresize( fInsVal );
1.442 +
1.443 + // Prevent simulated failures during verification
1.444 + gTestController.CancelFailureCountdown();
1.445 + // Success. Check results.
1.446 + VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) );
1.447 + }
1.448 +private:
1.449 + typename C::value_type fInsVal;
1.450 + const C& original;
1.451 +};
1.452 +
1.453 +template <class C, class Position, class Iter>
1.454 +void do_insert_range( C& c_inst, Position offset,
1.455 + Iter first, Iter last, sequence_container_tag )
1.456 +{
1.457 + typedef typename C::iterator CIter;
1.458 + CIter pos = c_inst.begin();
1.459 + EH_STD::advance( pos, offset );
1.460 + c_inst.insert( pos, first, last );
1.461 +}
1.462 +
1.463 +template <class C, class Position, class Iter>
1.464 +void do_insert_range( C& c, Position,
1.465 + Iter first, Iter last, associative_container_tag )
1.466 +{
1.467 + c.insert( first, last );
1.468 +}
1.469 +
1.470 +template <class C, class Position, class Iter>
1.471 +void do_insert_range( C& c, Position, Iter first, Iter last, multiset_tag )
1.472 +{
1.473 + c.insert( first, last );
1.474 +}
1.475 +
1.476 +template <class C, class Position, class Iter>
1.477 +void do_insert_range( C& c, Position, Iter first, Iter last, multimap_tag )
1.478 +{
1.479 + c.insert( first, last );
1.480 +}
1.481 +
1.482 +template <class C, class Position, class Iter>
1.483 +void do_insert_range( C& c, Position, Iter first, Iter last, set_tag )
1.484 +{
1.485 + c.insert( first, last );
1.486 +}
1.487 +
1.488 +template <class C, class Position, class Iter>
1.489 +void do_insert_range( C& c, Position, Iter first, Iter last, map_tag )
1.490 +{
1.491 + c.insert( first, last );
1.492 +}
1.493 +
1.494 +/*
1.495 +template <class C, class Iter>
1.496 +void prepare_insert_range( C&, size_t, Iter, Iter) {}
1.497 +*/
1.498 +
1.499 +template <class C, class Iter>
1.500 +struct test_insert_range
1.501 +{
1.502 + test_insert_range( const C& orig, Iter first, Iter last, int pos=-1 )
1.503 + : fFirst( first ),
1.504 + fLast( last ),
1.505 + original( orig ),
1.506 + fPos( random_number( orig.size() ))
1.507 + {
1.508 + gTestController.SetCurrentTestName("range insertion");
1.509 + if ( pos != -1 )
1.510 + {
1.511 + fPos = size_t(pos);
1.512 + if ( pos == 0 )
1.513 + gTestController.SetCurrentTestName("range insertion at begin()");
1.514 + else
1.515 + gTestController.SetCurrentTestName("range insertion at end()");
1.516 + }
1.517 + else
1.518 + gTestController.SetCurrentTestName("range insertion at random position");
1.519 + }
1.520 +
1.521 + void operator()( C& c ) const
1.522 + {
1.523 +// prepare_insert_range( c, fPos, fFirst, fLast );
1.524 + do_insert_range( c, fPos, fFirst, fLast, container_category(c) );
1.525 +
1.526 + // Prevent simulated failures during verification
1.527 + gTestController.CancelFailureCountdown();
1.528 + // Success. Check results.
1.529 + VerifyInsertion( original, c, fFirst, fLast, fPos );
1.530 + }
1.531 +private:
1.532 + Iter fFirst, fLast;
1.533 + const C& original;
1.534 + size_t fPos;
1.535 +};
1.536 +
1.537 +template <class C, class Iter>
1.538 +test_insert_range<C, Iter> insert_range_tester( const C& orig, const Iter& first, const Iter& last )
1.539 +{
1.540 + return test_insert_range<C, Iter>( orig, first, last );
1.541 +}
1.542 +
1.543 +template <class C, class Iter>
1.544 +test_insert_range<C, Iter> insert_range_at_begin_tester( const C& orig, const Iter& first, const Iter& last )
1.545 +{
1.546 + return test_insert_range<C, Iter>( orig, first, last , 0);
1.547 +}
1.548 +
1.549 +template <class C, class Iter>
1.550 +test_insert_range<C, Iter> insert_range_at_end_tester( const C& orig, const Iter& first, const Iter& last )
1.551 +{
1.552 + return test_insert_range<C, Iter>( orig, first, last , (int)orig.size());
1.553 +}
1.554 +
1.555 +#endif // test_insert_H_