1 /*********************************************************************************** 2 test_insert.h 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 #ifndef test_insert_H_ 17 #define test_insert_H_ 18 19 # include "Prefix.h" 20 # if defined (EH_NEW_HEADERS) 21 # include <utility> 22 # include <vector> 23 # include <cassert> 24 # include <climits> 25 # else 26 # include <vector.h> 27 # include <assert.h> 28 # include <limits.h> 29 # endif 30 #include "random_number.h" 31 #include "nc_alloc.h" 32 #include "ThrowCompare.h" 33 34 // A classification system for containers, for verification 35 struct container_tag {}; 36 struct sequence_container_tag {}; 37 struct associative_container_tag {}; 38 39 struct set_tag {}; 40 struct multiset_tag {}; 41 struct map_tag {}; 42 struct multimap_tag {}; 43 44 template <class C, class Iter> 45 size_t CountNewItems( const C&, const Iter& firstNew, 46 const Iter& lastNew, sequence_container_tag ) 47 { 48 size_t dist = 0; 49 #if 0 //def __SUNPRO_CC 50 EH_DISTANCE( firstNew, lastNew, dist ); 51 #else 52 EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist ); 53 #endif 54 return dist; 55 } 56 57 template <class C, class Iter> 58 size_t CountNewItems( const C& c, const Iter& firstNew, 59 const Iter& lastNew, multimap_tag ) 60 { 61 return CountNewItems( c, firstNew, lastNew, sequence_container_tag() ); 62 } 63 64 template <class C, class Iter> 65 size_t CountNewItems( const C& c, const Iter& firstNew, 66 const Iter& lastNew, multiset_tag ) 67 { 68 return CountNewItems( c, firstNew, lastNew, sequence_container_tag() ); 69 } 70 71 72 template <class C, class Iter, class KeyOfValue> 73 #ifdef __BORLANDC__ 74 size_t CountUniqueItems_Aux( const C& original, const Iter& firstNew, 75 #else 76 size_t CountUniqueItems_Aux( const C& original, Iter firstNew, 77 #endif 78 Iter lastNew, const KeyOfValue& keyOfValue ) 79 { 80 typedef typename C::key_type key; 81 typedef typename C::const_iterator const_iter; 82 typedef EH_STD::vector<key> key_list; 83 typedef typename key_list::iterator key_iterator; 84 key_list keys; 85 size_t dist = 0; 86 #ifdef __SUNPRO_CC 87 EH_DISTANCE( firstNew, lastNew, dist ); 88 #else 89 EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist ); 90 #endif 91 keys.reserve( dist ); 92 for ( Iter x = firstNew; x != lastNew; ++x ) 93 keys.push_back( keyOfValue(*x) ); 94 95 EH_STD::sort( keys.begin(), keys.end() ); 96 key_iterator last = EH_STD::unique( keys.begin(), keys.end() ); 97 98 size_t cnt = 0; 99 for ( key_iterator tmp = keys.begin(); tmp != last; ++tmp ) 100 { 101 if ( const_iter(original.find( *tmp )) == const_iter(original.end()) ) 102 ++cnt; 103 } 104 return cnt; 105 } 106 107 #if ! defined (__SGI_STL) 108 EH_BEGIN_NAMESPACE 109 template <class T> 110 struct identity 111 { 112 const T& operator()( const T& x ) const { return x; } 113 }; 114 # if ! defined (__KCC) 115 template <class _Pair> 116 struct select1st : public unary_function<_Pair, typename _Pair::first_type> { 117 const typename _Pair::first_type& operator()(const _Pair& __x) const { 118 return __x.first; 119 } 120 }; 121 # endif 122 EH_END_NAMESPACE 123 #endif 124 125 template <class C, class Iter> 126 size_t CountUniqueItems( const C& original, const Iter& firstNew, 127 const Iter& lastNew, set_tag ) 128 { 129 typedef typename C::value_type value_type; 130 return CountUniqueItems_Aux( original, firstNew, lastNew, 131 EH_STD::identity<value_type>() ); 132 } 133 134 template <class C, class Iter> 135 size_t CountUniqueItems( const C& original, const Iter& firstNew, 136 const Iter& lastNew, map_tag ) 137 { 138 #ifdef EH_MULTI_CONST_TEMPLATE_ARG_BUG 139 return CountUniqueItems_Aux( original, firstNew, lastNew, 140 EH_SELECT1ST_HINT<C::value_type, C::key_type>() ); 141 #else 142 typedef typename C::value_type value_type; 143 return CountUniqueItems_Aux( original, firstNew, lastNew, 144 EH_STD::select1st<value_type>() ); 145 #endif 146 } 147 148 template <class C, class Iter> 149 size_t CountNewItems( const C& original, const Iter& firstNew, 150 const Iter& lastNew, map_tag ) 151 { 152 return CountUniqueItems( original, firstNew, lastNew, 153 container_category( original ) ); 154 } 155 156 template <class C, class Iter> 157 size_t CountNewItems( const C& original, const Iter& firstNew, 158 const Iter& lastNew, set_tag ) 159 { 160 return CountUniqueItems( original, firstNew, lastNew, 161 container_category( original ) ); 162 } 163 164 template <class C, class SrcIter> 165 inline void VerifyInsertion( const C& original, const C& result, 166 const SrcIter& firstNew, const SrcIter& lastNew, 167 size_t, associative_container_tag ) 168 { 169 typedef typename C::const_iterator DstIter; 170 DstIter first1 = original.begin(); 171 DstIter first2 = result.begin(); 172 173 DstIter* from_orig = new DstIter[original.size()]; 174 DstIter* last_from_orig = from_orig; 175 176 // fbp : for hashed containers, the following is needed : 177 while ( first2 != result.end() ) 178 { 179 EH_STD::pair<DstIter, DstIter> p = EH_STD::mismatch( first1, original.end(), first2 ); 180 if ( p.second != result.end() ) 181 { 182 SrcIter srcItem = EH_STD::find( SrcIter(firstNew), SrcIter(lastNew), *p.second ); 183 184 if (srcItem == lastNew) 185 { 186 // not found in input range, probably re-ordered from the orig 187 DstIter* tmp; 188 tmp = EH_STD::find( from_orig, last_from_orig, p.first ); 189 190 // if already here, exclude 191 if (tmp != last_from_orig) 192 { 193 EH_STD::copy(tmp+1, last_from_orig, tmp); 194 last_from_orig--; 195 } 196 else 197 { 198 // register re-ordered element 199 DstIter dstItem; 200 dstItem = EH_STD::find( first1, original.end(), *p.first ); 201 EH_ASSERT( dstItem != original.end() ); 202 *last_from_orig = dstItem; 203 last_from_orig++; 204 ++p.first; 205 } 206 } 207 ++p.second; 208 } 209 first1 = p.first; 210 first2 = p.second; 211 } 212 213 delete [] from_orig; 214 } 215 216 // VC++ 217 template <class C, class SrcIter> 218 inline void VerifyInsertion( 219 const C& original, const C& result, const SrcIter& firstNew, 220 const SrcIter& lastNew, size_t, set_tag ) 221 { 222 VerifyInsertion( original, result, firstNew, lastNew, 223 size_t(0), associative_container_tag() ); 224 } 225 226 template <class C, class SrcIter> 227 inline void VerifyInsertion(const C& original, const C& result, 228 const SrcIter& firstNew, const SrcIter& lastNew, 229 size_t, multiset_tag ) 230 { 231 VerifyInsertion( original, result, firstNew, lastNew, 232 size_t(0), associative_container_tag() ); 233 } 234 235 template <class C, class SrcIter> 236 inline void VerifyInsertion( 237 const C& original, const C& result, const SrcIter& firstNew, 238 const SrcIter& lastNew, size_t, map_tag ) 239 { 240 VerifyInsertion( original, result, firstNew, lastNew, 241 size_t(0), associative_container_tag() ); 242 } 243 244 template <class C, class SrcIter> 245 inline void VerifyInsertion( 246 const C& original, const C& result, const SrcIter& firstNew, 247 const SrcIter& lastNew, size_t, multimap_tag ) 248 { 249 VerifyInsertion( original, result, firstNew, lastNew, 250 size_t(0), associative_container_tag() ); 251 } 252 253 template <class C, class SrcIter> 254 void VerifyInsertion( 255 # ifdef _MSC_VER 256 const C& original, const C& result, SrcIter firstNew, 257 SrcIter lastNew, size_t insPos, sequence_container_tag ) 258 # else 259 const C& original, const C& result, const SrcIter& firstNew, 260 const SrcIter& lastNew, size_t insPos, sequence_container_tag ) 261 # endif 262 { 263 typename C::const_iterator p1 = original.begin(); 264 typename C::const_iterator p2 = result.begin(); 265 SrcIter tmp(firstNew); 266 267 for ( size_t n = 0; n < insPos; n++, ++p1, ++p2) 268 EH_ASSERT( *p1 == *p2 ); 269 270 for (; tmp != lastNew; ++p2, ++tmp ) { 271 EH_ASSERT(p2 != result.end()); 272 EH_ASSERT(*p2 == *tmp); 273 } 274 275 for (; p2 != result.end(); ++p1, ++p2 ) 276 EH_ASSERT( *p1 == *p2 ); 277 EH_ASSERT( p1 == original.end() ); 278 } 279 280 template <class C, class SrcIter> 281 inline void VerifyInsertion( const C& original, const C& result, 282 const SrcIter& firstNew, 283 const SrcIter& lastNew, size_t insPos ) 284 { 285 EH_ASSERT( result.size() == original.size() + 286 CountNewItems( original, firstNew, lastNew, 287 container_category(original) ) ); 288 VerifyInsertion( original, result, firstNew, lastNew, insPos, 289 container_category(original) ); 290 } 291 292 template <class C, class Value> 293 void VerifyInsertN( const C& original, const C& result, size_t insCnt, 294 const Value& val, size_t insPos ) 295 { 296 typename C::const_iterator p1 = original.begin(); 297 typename C::const_iterator p2 = result.begin(); 298 (void)val; //*TY 02/06/2000 - to suppress unused variable warning under nondebug build 299 300 for ( size_t n = 0; n < insPos; n++ ) 301 EH_ASSERT( *p1++ == *p2++ ); 302 303 while ( insCnt-- > 0 ) 304 { 305 EH_ASSERT(p2 != result.end()); 306 EH_ASSERT(*p2 == val ); 307 ++p2; 308 } 309 310 while ( p2 != result.end() ) { 311 EH_ASSERT( *p1 == *p2 ); 312 ++p1; ++p2; 313 } 314 EH_ASSERT( p1 == original.end() ); 315 } 316 317 template <class C> 318 void prepare_insert_n( C&, size_t ) {} 319 320 // Metrowerks 1.8 compiler requires that specializations appear first (!!) 321 // or it won't call them. Fixed in 1.9, though. 322 inline void MakeRandomValue(bool& b) { b = bool(random_number(2) != 0); } 323 324 template<class T> 325 inline void MakeRandomValue(T&) {} 326 327 template <class C> 328 struct test_insert_one 329 { 330 test_insert_one( const C& orig, int pos =-1 ) 331 : original( orig ), fPos( random_number( orig.size() )) 332 { 333 MakeRandomValue( fInsVal ); 334 if ( pos != -1 ) 335 { 336 fPos = size_t(pos); 337 if ( pos == 0 ) 338 gTestController.SetCurrentTestName("single insertion at begin()"); 339 else 340 gTestController.SetCurrentTestName("single insertion at end()"); 341 } 342 else 343 gTestController.SetCurrentTestName("single insertion at random position"); 344 } 345 346 void operator()( C& c ) const 347 { 348 prepare_insert_n( c, (size_t)1 ); 349 typename C::iterator pos = c.begin(); 350 EH_STD::advance( pos, size_t(fPos) ); 351 c.insert( pos, fInsVal ); 352 353 // Prevent simulated failures during verification 354 gTestController.CancelFailureCountdown(); 355 // Success. Check results. 356 VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, fPos ); 357 } 358 private: 359 typename C::value_type fInsVal; 360 const C& original; 361 size_t fPos; 362 }; 363 364 template <class C> 365 struct test_insert_n 366 { 367 test_insert_n( const C& orig, size_t insCnt, int pos =-1 ) 368 : original( orig ), fPos( random_number( orig.size() )), fInsCnt(insCnt) 369 { 370 MakeRandomValue( fInsVal ); 371 if (pos!=-1) 372 { 373 fPos=size_t(pos); 374 if (pos==0) 375 gTestController.SetCurrentTestName("n-ary insertion at begin()"); 376 else 377 gTestController.SetCurrentTestName("n-ary insertion at end()"); 378 } 379 else 380 gTestController.SetCurrentTestName("n-ary insertion at random position"); 381 } 382 383 void operator()( C& c ) const 384 { 385 prepare_insert_n( c, fInsCnt ); 386 typename C::iterator pos = c.begin(); 387 EH_STD::advance( pos, fPos ); 388 c.insert( pos, fInsCnt, fInsVal ); 389 390 // Prevent simulated failures during verification 391 gTestController.CancelFailureCountdown(); 392 // Success. Check results. 393 VerifyInsertN( original, c, fInsCnt, fInsVal, fPos ); 394 } 395 private: 396 typename C::value_type fInsVal; 397 const C& original; 398 size_t fPos; 399 size_t fInsCnt; 400 }; 401 402 template <class C> 403 struct test_insert_value 404 { 405 test_insert_value( const C& orig ) 406 : original( orig ) 407 { 408 MakeRandomValue( fInsVal ); 409 gTestController.SetCurrentTestName("insertion of random value"); 410 } 411 412 void operator()( C& c ) const 413 { 414 c.insert( fInsVal ); 415 416 // Prevent simulated failures during verification 417 gTestController.CancelFailureCountdown(); 418 // Success. Check results. 419 VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) ); 420 } 421 private: 422 typename C::value_type fInsVal; 423 const C& original; 424 }; 425 426 template <class C> 427 struct test_insert_noresize 428 { 429 test_insert_noresize( const C& orig ) 430 : original( orig ) 431 { 432 MakeRandomValue( fInsVal ); 433 gTestController.SetCurrentTestName("insertion of random value without resize"); 434 } 435 436 void operator()( C& c ) const 437 { 438 c.insert_noresize( fInsVal ); 439 440 // Prevent simulated failures during verification 441 gTestController.CancelFailureCountdown(); 442 // Success. Check results. 443 VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) ); 444 } 445 private: 446 typename C::value_type fInsVal; 447 const C& original; 448 }; 449 450 template <class C, class Position, class Iter> 451 void do_insert_range( C& c_inst, Position offset, 452 Iter first, Iter last, sequence_container_tag ) 453 { 454 typedef typename C::iterator CIter; 455 CIter pos = c_inst.begin(); 456 EH_STD::advance( pos, offset ); 457 c_inst.insert( pos, first, last ); 458 } 459 460 template <class C, class Position, class Iter> 461 void do_insert_range( C& c, Position, 462 Iter first, Iter last, associative_container_tag ) 463 { 464 c.insert( first, last ); 465 } 466 467 template <class C, class Position, class Iter> 468 void do_insert_range( C& c, Position, Iter first, Iter last, multiset_tag ) 469 { 470 c.insert( first, last ); 471 } 472 473 template <class C, class Position, class Iter> 474 void do_insert_range( C& c, Position, Iter first, Iter last, multimap_tag ) 475 { 476 c.insert( first, last ); 477 } 478 479 template <class C, class Position, class Iter> 480 void do_insert_range( C& c, Position, Iter first, Iter last, set_tag ) 481 { 482 c.insert( first, last ); 483 } 484 485 template <class C, class Position, class Iter> 486 void do_insert_range( C& c, Position, Iter first, Iter last, map_tag ) 487 { 488 c.insert( first, last ); 489 } 490 491 /* 492 template <class C, class Iter> 493 void prepare_insert_range( C&, size_t, Iter, Iter) {} 494 */ 495 496 template <class C, class Iter> 497 struct test_insert_range 498 { 499 test_insert_range( const C& orig, Iter first, Iter last, int pos=-1 ) 500 : fFirst( first ), 501 fLast( last ), 502 original( orig ), 503 fPos( random_number( orig.size() )) 504 { 505 gTestController.SetCurrentTestName("range insertion"); 506 if ( pos != -1 ) 507 { 508 fPos = size_t(pos); 509 if ( pos == 0 ) 510 gTestController.SetCurrentTestName("range insertion at begin()"); 511 else 512 gTestController.SetCurrentTestName("range insertion at end()"); 513 } 514 else 515 gTestController.SetCurrentTestName("range insertion at random position"); 516 } 517 518 void operator()( C& c ) const 519 { 520 // prepare_insert_range( c, fPos, fFirst, fLast ); 521 do_insert_range( c, fPos, fFirst, fLast, container_category(c) ); 522 523 // Prevent simulated failures during verification 524 gTestController.CancelFailureCountdown(); 525 // Success. Check results. 526 VerifyInsertion( original, c, fFirst, fLast, fPos ); 527 } 528 private: 529 Iter fFirst, fLast; 530 const C& original; 531 size_t fPos; 532 }; 533 534 template <class C, class Iter> 535 test_insert_range<C, Iter> insert_range_tester( const C& orig, const Iter& first, const Iter& last ) 536 { 537 return test_insert_range<C, Iter>( orig, first, last ); 538 } 539 540 template <class C, class Iter> 541 test_insert_range<C, Iter> insert_range_at_begin_tester( const C& orig, const Iter& first, const Iter& last ) 542 { 543 return test_insert_range<C, Iter>( orig, first, last , 0); 544 } 545 546 template <class C, class Iter> 547 test_insert_range<C, Iter> insert_range_at_end_tester( const C& orig, const Iter& first, const Iter& last ) 548 { 549 return test_insert_range<C, Iter>( orig, first, last , (int)orig.size()); 550 } 551 552 #endif // test_insert_H_ 553
