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_