home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stl2vac.zip / STLport-4_5_3.zip / STLport-4.5.3 / test / eh / test_insert.h < prev    next >
C/C++ Source or Header  |  2000-12-07  |  17KB  |  552 lines
  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. EH_STD::size_t CountNewItems( const C&, const Iter& firstNew, 
  46.                       const Iter& lastNew, sequence_container_tag )
  47. {
  48.     EH_STD::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. EH_STD::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. EH_STD::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. EH_STD::size_t CountUniqueItems_Aux( const C& original, const Iter& firstNew, 
  75. #else
  76. EH_STD::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.     EH_STD::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.     EH_STD::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. EH_STD::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. EH_STD::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. EH_STD::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. EH_STD::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.                              EH_STD::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, EH_STD::size_t, set_tag )
  221. {
  222.     VerifyInsertion( original, result, firstNew, lastNew, 
  223.                      EH_STD::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.                             EH_STD::size_t, multiset_tag )
  230. {
  231.     VerifyInsertion( original, result, firstNew, lastNew, 
  232.                      EH_STD::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, EH_STD::size_t, map_tag )
  239. {
  240.     VerifyInsertion( original, result, firstNew, lastNew, 
  241.                      EH_STD::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, EH_STD::size_t, multimap_tag )
  248. {
  249.     VerifyInsertion( original, result, firstNew, lastNew, 
  250.                      EH_STD::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, EH_STD::size_t insPos, sequence_container_tag )
  258. # else
  259.     const C& original, const C& result, const SrcIter& firstNew, 
  260.     const SrcIter& lastNew, EH_STD::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 ( EH_STD::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, EH_STD::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, EH_STD::size_t insCnt, 
  294.                     const Value& val, EH_STD::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 ( EH_STD::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&, EH_STD::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)); }
  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 = EH_STD::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, (EH_STD::size_t)1 );
  349.         typename C::iterator pos = c.begin();
  350.         EH_STD::advance( pos, EH_STD::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.     EH_STD::size_t fPos;
  362. };
  363.  
  364. template <class C>
  365. struct test_insert_n
  366. {
  367.     test_insert_n( const C& orig, EH_STD::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=EH_STD::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.     EH_STD::size_t fPos;
  399.     EH_STD::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 or 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, EH_STD::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, EH_STD::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 = EH_STD::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. #endif // test_insert_H_
  552.