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