sl@0: /***********************************************************************************
sl@0:   test_insert.h
sl@0: 
sl@0:  * Copyright (c) 1997
sl@0:  * Mark of the Unicorn, Inc.
sl@0:  *
sl@0:  * Permission to use, copy, modify, distribute and sell this software
sl@0:  * and its documentation for any purpose is hereby granted without fee,
sl@0:  * provided that the above copyright notice appear in all copies and
sl@0:  * that both that copyright notice and this permission notice appear
sl@0:  * in supporting documentation.  Mark of the Unicorn makes no
sl@0:  * representations about the suitability of this software for any
sl@0:  * purpose.  It is provided "as is" without express or implied warranty.
sl@0: 
sl@0: ***********************************************************************************/
sl@0: #ifndef test_insert_H_
sl@0: #define test_insert_H_
sl@0: 
sl@0: # include "Prefix.h"
sl@0: # if defined (EH_NEW_HEADERS)
sl@0: #  include <utility>
sl@0: #  include <vector>
sl@0: #  include <cassert>
sl@0: #  include <climits>
sl@0: # else
sl@0: #  include <vector.h>
sl@0: #  include <assert.h>
sl@0: #  include <limits.h>
sl@0: # endif
sl@0: #include "random_number.h"
sl@0: #include "nc_alloc.h"
sl@0: #include "ThrowCompare.h"
sl@0: 
sl@0: // A classification system for containers, for verification
sl@0: struct container_tag {};
sl@0: struct sequence_container_tag  {};
sl@0: struct associative_container_tag  {};
sl@0: 
sl@0: struct set_tag  {};
sl@0: struct multiset_tag  {};
sl@0: struct map_tag {};
sl@0: struct multimap_tag {};
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountNewItems( const C&, const Iter& firstNew,
sl@0:                       const Iter& lastNew, sequence_container_tag )
sl@0: {
sl@0:     size_t dist = 0;
sl@0: #if 0 //def __SUNPRO_CC
sl@0:     EH_DISTANCE( firstNew, lastNew, dist );
sl@0: #else
sl@0:     EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist );
sl@0: #endif
sl@0:     return dist;
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountNewItems( const C& c, const Iter& firstNew,
sl@0:                       const Iter& lastNew, multimap_tag )
sl@0: {
sl@0:     return CountNewItems( c, firstNew, lastNew, sequence_container_tag() );
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountNewItems( const C& c, const Iter& firstNew,
sl@0:                       const Iter& lastNew, multiset_tag )
sl@0: {
sl@0:     return CountNewItems( c, firstNew, lastNew, sequence_container_tag() );
sl@0: }
sl@0: 
sl@0: 
sl@0: template <class C, class Iter, class KeyOfValue>
sl@0: #ifdef __BORLANDC__
sl@0: size_t CountUniqueItems_Aux( const C& original, const Iter& firstNew,
sl@0: #else
sl@0: size_t CountUniqueItems_Aux( const C& original, Iter firstNew,
sl@0: #endif
sl@0:                              Iter lastNew, const KeyOfValue& keyOfValue )
sl@0: {
sl@0:   typedef typename C::key_type key;
sl@0:   typedef typename C::const_iterator const_iter;
sl@0:   typedef EH_STD::vector<key> key_list;
sl@0:   typedef typename key_list::iterator key_iterator;
sl@0:   key_list keys;
sl@0:   size_t dist = 0;
sl@0: #ifdef __SUNPRO_CC
sl@0:   EH_DISTANCE( firstNew, lastNew, dist );
sl@0: #else
sl@0:   EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist );
sl@0: #endif
sl@0:   keys.reserve( dist );
sl@0:   for ( Iter x = firstNew; x != lastNew; ++x )
sl@0:     keys.push_back( keyOfValue(*x) );
sl@0: 
sl@0:   EH_STD::sort( keys.begin(), keys.end() );
sl@0:   key_iterator last = EH_STD::unique( keys.begin(), keys.end() );
sl@0: 
sl@0:     size_t cnt = 0;
sl@0:     for ( key_iterator tmp = keys.begin(); tmp != last; ++tmp )
sl@0:     {
sl@0:         if ( const_iter(original.find( *tmp )) == const_iter(original.end()) )
sl@0:             ++cnt;
sl@0:     }
sl@0:     return cnt;
sl@0: }
sl@0: 
sl@0: #if ! defined (__SGI_STL)
sl@0: EH_BEGIN_NAMESPACE
sl@0: template <class T>
sl@0: struct identity
sl@0: {
sl@0:   const T& operator()( const T& x ) const { return x; }
sl@0: };
sl@0: # if ! defined (__KCC)
sl@0: template <class _Pair>
sl@0: struct select1st : public unary_function<_Pair, typename _Pair::first_type> {
sl@0:   const typename _Pair::first_type& operator()(const _Pair& __x) const {
sl@0:     return __x.first;
sl@0:   }
sl@0: };
sl@0: # endif
sl@0: EH_END_NAMESPACE
sl@0: #endif
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountUniqueItems( const C& original, const Iter& firstNew,
sl@0:                          const Iter& lastNew, set_tag )
sl@0: {
sl@0:     typedef typename C::value_type value_type;
sl@0:     return CountUniqueItems_Aux( original, firstNew, lastNew,
sl@0:                                  EH_STD::identity<value_type>() );
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountUniqueItems( const C& original, const Iter& firstNew,
sl@0:                          const Iter& lastNew, map_tag )
sl@0: {
sl@0: #ifdef EH_MULTI_CONST_TEMPLATE_ARG_BUG
sl@0:     return CountUniqueItems_Aux( original, firstNew, lastNew,
sl@0:                                  EH_SELECT1ST_HINT<C::value_type, C::key_type>() );
sl@0: #else
sl@0:     typedef typename C::value_type value_type;
sl@0:     return CountUniqueItems_Aux( original, firstNew, lastNew,
sl@0:                                  EH_STD::select1st<value_type>() );
sl@0: #endif
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountNewItems( const C& original, const Iter& firstNew,
sl@0:                       const Iter& lastNew, map_tag )
sl@0: {
sl@0:     return CountUniqueItems( original, firstNew, lastNew,
sl@0:                              container_category( original ) );
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: size_t CountNewItems( const C& original, const Iter& firstNew,
sl@0:                       const Iter& lastNew, set_tag )
sl@0: {
sl@0:     return CountUniqueItems( original, firstNew, lastNew,
sl@0:                              container_category( original ) );
sl@0: }
sl@0: 
sl@0: template <class C, class SrcIter>
sl@0: inline void VerifyInsertion( const C& original, const C& result,
sl@0:                              const SrcIter& firstNew, const SrcIter& lastNew,
sl@0:                              size_t, associative_container_tag )
sl@0: {
sl@0:     typedef typename C::const_iterator DstIter;
sl@0:     DstIter first1 = original.begin();
sl@0:     DstIter first2 = result.begin();
sl@0: 
sl@0:     DstIter* from_orig = new DstIter[original.size()];
sl@0:     DstIter* last_from_orig = from_orig;
sl@0: 
sl@0:     // fbp : for hashed containers, the following is needed :
sl@0:     while ( first2 != result.end() )
sl@0:     {
sl@0:         EH_STD::pair<DstIter, DstIter> p = EH_STD::mismatch( first1, original.end(), first2 );
sl@0:         if ( p.second != result.end() )
sl@0:         {
sl@0:             SrcIter srcItem = EH_STD::find( SrcIter(firstNew), SrcIter(lastNew), *p.second );
sl@0: 
sl@0:             if (srcItem == lastNew)
sl@0:             {
sl@0:                 // not found in input range, probably re-ordered from the orig
sl@0:                 DstIter* tmp;
sl@0:                 tmp = EH_STD::find( from_orig, last_from_orig, p.first );
sl@0: 
sl@0:                 // if already here, exclude
sl@0:                 if (tmp != last_from_orig)
sl@0:                 {
sl@0:                     EH_STD::copy(tmp+1, last_from_orig, tmp);
sl@0:                     last_from_orig--;
sl@0:                 }
sl@0:                 else
sl@0:                 {
sl@0:                     // register re-ordered element
sl@0:                     DstIter dstItem;
sl@0:                     dstItem = EH_STD::find( first1, original.end(), *p.first );
sl@0:                     EH_ASSERT( dstItem != original.end() );
sl@0:                     *last_from_orig = dstItem;
sl@0:                     last_from_orig++;
sl@0:                     ++p.first;
sl@0:                 }
sl@0:             }
sl@0:             ++p.second;
sl@0:         }
sl@0:         first1 = p.first;
sl@0:         first2 = p.second;
sl@0:     }
sl@0: 
sl@0:     delete [] from_orig;
sl@0: }
sl@0: 
sl@0: // VC++
sl@0: template <class C, class SrcIter>
sl@0: inline void VerifyInsertion(
sl@0:     const C& original, const C& result, const SrcIter& firstNew,
sl@0:     const SrcIter& lastNew, size_t, set_tag )
sl@0: {
sl@0:     VerifyInsertion( original, result, firstNew, lastNew,
sl@0:                      size_t(0), associative_container_tag() );
sl@0: }
sl@0: 
sl@0: template <class C, class SrcIter>
sl@0: inline void VerifyInsertion(const C& original, const C& result,
sl@0:                             const SrcIter& firstNew, const SrcIter& lastNew,
sl@0:                             size_t, multiset_tag )
sl@0: {
sl@0:     VerifyInsertion( original, result, firstNew, lastNew,
sl@0:                      size_t(0), associative_container_tag() );
sl@0: }
sl@0: 
sl@0: template <class C, class SrcIter>
sl@0: inline void VerifyInsertion(
sl@0:     const C& original, const C& result, const SrcIter& firstNew,
sl@0:     const SrcIter& lastNew, size_t, map_tag )
sl@0: {
sl@0:     VerifyInsertion( original, result, firstNew, lastNew,
sl@0:                      size_t(0), associative_container_tag() );
sl@0: }
sl@0: 
sl@0: template <class C, class SrcIter>
sl@0: inline void VerifyInsertion(
sl@0:     const C& original, const C& result, const SrcIter& firstNew,
sl@0:     const SrcIter& lastNew, size_t, multimap_tag )
sl@0: {
sl@0:     VerifyInsertion( original, result, firstNew, lastNew,
sl@0:                      size_t(0), associative_container_tag() );
sl@0: }
sl@0: 
sl@0: template <class C, class SrcIter>
sl@0: void VerifyInsertion(
sl@0: # ifdef _MSC_VER
sl@0:     const C& original, const C& result, SrcIter firstNew,
sl@0:     SrcIter lastNew, size_t insPos, sequence_container_tag )
sl@0: # else
sl@0:     const C& original, const C& result, const SrcIter& firstNew,
sl@0:     const SrcIter& lastNew, size_t insPos, sequence_container_tag )
sl@0: # endif
sl@0: {
sl@0:     typename C::const_iterator p1 = original.begin();
sl@0:     typename C::const_iterator p2 = result.begin();
sl@0:     SrcIter tmp(firstNew);
sl@0: 
sl@0:     for ( size_t n = 0; n < insPos; n++, ++p1, ++p2)
sl@0:         EH_ASSERT( *p1 == *p2 );
sl@0: 
sl@0:     for (; tmp != lastNew; ++p2, ++tmp ) {
sl@0:         EH_ASSERT(p2 != result.end());
sl@0:         EH_ASSERT(*p2 == *tmp);
sl@0:     }
sl@0: 
sl@0:     for (;  p2 != result.end(); ++p1, ++p2 )
sl@0:         EH_ASSERT( *p1 == *p2 );
sl@0:     EH_ASSERT( p1 == original.end() );
sl@0: }
sl@0: 
sl@0: template <class C, class SrcIter>
sl@0: inline void VerifyInsertion( const C& original, const C& result,
sl@0:                              const SrcIter& firstNew,
sl@0:                              const SrcIter& lastNew, size_t insPos )
sl@0: {
sl@0:     EH_ASSERT( result.size() == original.size() +
sl@0:             CountNewItems( original, firstNew, lastNew,
sl@0:                            container_category(original) ) );
sl@0:     VerifyInsertion( original, result, firstNew, lastNew, insPos,
sl@0:                      container_category(original) );
sl@0: }
sl@0: 
sl@0: template <class C, class Value>
sl@0: void VerifyInsertN( const C& original, const C& result, size_t insCnt,
sl@0:                     const Value& val, size_t insPos )
sl@0: {
sl@0:     typename C::const_iterator p1 = original.begin();
sl@0:     typename C::const_iterator p2 = result.begin();
sl@0:   (void)val;    //*TY 02/06/2000 - to suppress unused variable warning under nondebug build
sl@0: 
sl@0:     for ( size_t n = 0; n < insPos; n++ )
sl@0:         EH_ASSERT( *p1++ == *p2++ );
sl@0: 
sl@0:     while ( insCnt-- > 0 )
sl@0:     {
sl@0:         EH_ASSERT(p2 != result.end());
sl@0:         EH_ASSERT(*p2 == val );
sl@0:         ++p2;
sl@0:     }
sl@0: 
sl@0:     while ( p2 != result.end() ) {
sl@0:         EH_ASSERT( *p1 == *p2 );
sl@0:         ++p1; ++p2;
sl@0:     }
sl@0:     EH_ASSERT( p1 == original.end() );
sl@0: }
sl@0: 
sl@0: template <class C>
sl@0: void prepare_insert_n( C&, size_t ) {}
sl@0: 
sl@0: // Metrowerks 1.8 compiler requires that specializations appear first (!!)
sl@0: // or it won't call them. Fixed in 1.9, though.
sl@0: inline void MakeRandomValue(bool& b) { b = bool(random_number(2) != 0); }
sl@0: 
sl@0: template<class T>
sl@0: inline void MakeRandomValue(T&) {}
sl@0: 
sl@0: template <class C>
sl@0: struct test_insert_one
sl@0: {
sl@0:     test_insert_one( const C& orig, int pos =-1 )
sl@0:         : original( orig ), fPos( random_number( orig.size() ))
sl@0:     {
sl@0:         MakeRandomValue( fInsVal );
sl@0:         if ( pos != -1 )
sl@0:         {
sl@0:             fPos = size_t(pos);
sl@0:             if ( pos == 0 )
sl@0:                 gTestController.SetCurrentTestName("single insertion at begin()");
sl@0:             else
sl@0:                 gTestController.SetCurrentTestName("single insertion at end()");
sl@0:         }
sl@0:         else
sl@0:             gTestController.SetCurrentTestName("single insertion at random position");
sl@0:     }
sl@0: 
sl@0:     void operator()( C& c ) const
sl@0:     {
sl@0:         prepare_insert_n( c, (size_t)1 );
sl@0:         typename C::iterator pos = c.begin();
sl@0:         EH_STD::advance( pos, size_t(fPos) );
sl@0:         c.insert( pos, fInsVal );
sl@0: 
sl@0:         // Prevent simulated failures during verification
sl@0:         gTestController.CancelFailureCountdown();
sl@0:         // Success. Check results.
sl@0:         VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, fPos );
sl@0:     }
sl@0: private:
sl@0:     typename C::value_type fInsVal;
sl@0:     const C& original;
sl@0:     size_t fPos;
sl@0: };
sl@0: 
sl@0: template <class C>
sl@0: struct test_insert_n
sl@0: {
sl@0:     test_insert_n( const C& orig, size_t insCnt, int pos =-1 )
sl@0:         : original( orig ), fPos( random_number( orig.size() )), fInsCnt(insCnt)
sl@0:     {
sl@0:         MakeRandomValue( fInsVal );
sl@0:         if (pos!=-1)
sl@0:         {
sl@0:             fPos=size_t(pos);
sl@0:             if (pos==0)
sl@0:                 gTestController.SetCurrentTestName("n-ary insertion at begin()");
sl@0:             else
sl@0:                 gTestController.SetCurrentTestName("n-ary insertion at end()");
sl@0:         }
sl@0:         else
sl@0:             gTestController.SetCurrentTestName("n-ary insertion at random position");
sl@0:     }
sl@0: 
sl@0:     void operator()( C& c ) const
sl@0:     {
sl@0:         prepare_insert_n( c, fInsCnt );
sl@0:         typename C::iterator pos = c.begin();
sl@0:         EH_STD::advance( pos, fPos );
sl@0:         c.insert( pos, fInsCnt, fInsVal );
sl@0: 
sl@0:         // Prevent simulated failures during verification
sl@0:         gTestController.CancelFailureCountdown();
sl@0:         // Success. Check results.
sl@0:         VerifyInsertN( original, c, fInsCnt, fInsVal, fPos );
sl@0:     }
sl@0: private:
sl@0:     typename C::value_type fInsVal;
sl@0:     const C& original;
sl@0:     size_t fPos;
sl@0:     size_t fInsCnt;
sl@0: };
sl@0: 
sl@0: template <class C>
sl@0: struct test_insert_value
sl@0: {
sl@0:     test_insert_value( const C& orig )
sl@0:         : original( orig )
sl@0:     {
sl@0:         MakeRandomValue( fInsVal );
sl@0:         gTestController.SetCurrentTestName("insertion of random value");
sl@0:     }
sl@0: 
sl@0:     void operator()( C& c ) const
sl@0:     {
sl@0:         c.insert( fInsVal );
sl@0: 
sl@0:         // Prevent simulated failures during verification
sl@0:         gTestController.CancelFailureCountdown();
sl@0:         // Success. Check results.
sl@0:         VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) );
sl@0:     }
sl@0: private:
sl@0:     typename C::value_type fInsVal;
sl@0:     const C& original;
sl@0: };
sl@0: 
sl@0: template <class C>
sl@0: struct test_insert_noresize
sl@0: {
sl@0:     test_insert_noresize( const C& orig )
sl@0:         : original( orig )
sl@0:     {
sl@0:         MakeRandomValue( fInsVal );
sl@0:         gTestController.SetCurrentTestName("insertion of random value without resize");
sl@0:     }
sl@0: 
sl@0:     void operator()( C& c ) const
sl@0:     {
sl@0:         c.insert_noresize( fInsVal );
sl@0: 
sl@0:         // Prevent simulated failures during verification
sl@0:         gTestController.CancelFailureCountdown();
sl@0:         // Success. Check results.
sl@0:         VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) );
sl@0:     }
sl@0: private:
sl@0:     typename C::value_type fInsVal;
sl@0:     const C& original;
sl@0: };
sl@0: 
sl@0: template <class C, class Position, class Iter>
sl@0: void do_insert_range( C& c_inst, Position offset,
sl@0:                       Iter first, Iter last, sequence_container_tag )
sl@0: {
sl@0:     typedef typename C::iterator CIter;
sl@0:     CIter pos = c_inst.begin();
sl@0:     EH_STD::advance( pos, offset );
sl@0:     c_inst.insert( pos, first, last );
sl@0: }
sl@0: 
sl@0: template <class C, class Position, class Iter>
sl@0: void do_insert_range( C& c, Position,
sl@0:                       Iter first, Iter last, associative_container_tag )
sl@0: {
sl@0:     c.insert( first, last );
sl@0: }
sl@0: 
sl@0: template <class C, class Position, class Iter>
sl@0: void do_insert_range( C& c, Position, Iter first, Iter last, multiset_tag )
sl@0: {
sl@0:     c.insert( first, last );
sl@0: }
sl@0: 
sl@0: template <class C, class Position, class Iter>
sl@0: void do_insert_range( C& c, Position, Iter first, Iter last, multimap_tag )
sl@0: {
sl@0:     c.insert( first, last );
sl@0: }
sl@0: 
sl@0: template <class C, class Position, class Iter>
sl@0: void do_insert_range( C& c, Position, Iter first, Iter last, set_tag )
sl@0: {
sl@0:     c.insert( first, last );
sl@0: }
sl@0: 
sl@0: template <class C, class Position, class Iter>
sl@0: void do_insert_range( C& c, Position, Iter first, Iter last, map_tag )
sl@0: {
sl@0:     c.insert( first, last );
sl@0: }
sl@0: 
sl@0: /*
sl@0: template <class C, class Iter>
sl@0: void prepare_insert_range( C&, size_t, Iter, Iter) {}
sl@0: */
sl@0: 
sl@0: template <class C, class Iter>
sl@0: struct test_insert_range
sl@0: {
sl@0:     test_insert_range( const C& orig, Iter first, Iter last, int pos=-1 )
sl@0:         : fFirst( first ),
sl@0:           fLast( last ),
sl@0:           original( orig ),
sl@0:           fPos( random_number( orig.size() ))
sl@0:     {
sl@0:         gTestController.SetCurrentTestName("range insertion");
sl@0:         if ( pos != -1 )
sl@0:         {
sl@0:             fPos = size_t(pos);
sl@0:             if ( pos == 0 )
sl@0:                 gTestController.SetCurrentTestName("range insertion at begin()");
sl@0:             else
sl@0:                 gTestController.SetCurrentTestName("range insertion at end()");
sl@0:         }
sl@0:         else
sl@0:             gTestController.SetCurrentTestName("range insertion at random position");
sl@0:     }
sl@0: 
sl@0:     void operator()( C& c ) const
sl@0:     {
sl@0: //        prepare_insert_range( c, fPos, fFirst, fLast );
sl@0:         do_insert_range( c, fPos, fFirst, fLast, container_category(c) );
sl@0: 
sl@0:         // Prevent simulated failures during verification
sl@0:         gTestController.CancelFailureCountdown();
sl@0:         // Success. Check results.
sl@0:         VerifyInsertion( original, c, fFirst, fLast, fPos );
sl@0:     }
sl@0: private:
sl@0:     Iter fFirst, fLast;
sl@0:     const C& original;
sl@0:     size_t fPos;
sl@0: };
sl@0: 
sl@0: template <class C, class Iter>
sl@0: test_insert_range<C, Iter> insert_range_tester( const C& orig, const Iter& first, const Iter& last )
sl@0: {
sl@0:     return test_insert_range<C, Iter>( orig, first, last );
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: test_insert_range<C, Iter> insert_range_at_begin_tester( const C& orig, const Iter& first, const Iter& last )
sl@0: {
sl@0:   return test_insert_range<C, Iter>( orig, first, last , 0);
sl@0: }
sl@0: 
sl@0: template <class C, class Iter>
sl@0: test_insert_range<C, Iter> insert_range_at_end_tester( const C& orig, const Iter& first, const Iter& last )
sl@0: {
sl@0:   return test_insert_range<C, Iter>( orig, first, last , (int)orig.size());
sl@0: }
sl@0: 
sl@0: #endif // test_insert_H_