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
35struct container_tag {};
36struct sequence_container_tag  {};
37struct associative_container_tag  {};
38
39struct set_tag  {};
40struct multiset_tag  {};
41struct map_tag {};
42struct multimap_tag {};
43
44template <class C, class Iter>
45size_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
57template <class C, class Iter>
58size_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
64template <class C, class Iter>
65size_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
72template <class C, class Iter, class KeyOfValue>
73#ifdef __BORLANDC__
74size_t CountUniqueItems_Aux( const C& original, const Iter& firstNew,
75#else
76size_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)
108EH_BEGIN_NAMESPACE
109template <class T>
110struct identity
111{
112  const T& operator()( const T& x ) const { return x; }
113};
114# if ! defined (__KCC)
115template <class _Pair>
116struct 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
122EH_END_NAMESPACE
123#endif
124
125template <class C, class Iter>
126size_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
134template <class C, class Iter>
135size_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
148template <class C, class Iter>
149size_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
156template <class C, class Iter>
157size_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
164template <class C, class SrcIter>
165inline 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++
217template <class C, class SrcIter>
218inline 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
226template <class C, class SrcIter>
227inline 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
235template <class C, class SrcIter>
236inline 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
244template <class C, class SrcIter>
245inline 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
253template <class C, class SrcIter>
254void 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
280template <class C, class SrcIter>
281inline 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
292template <class C, class Value>
293void 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
317template <class C>
318void 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.
322inline void MakeRandomValue(bool& b) { b = bool(random_number(2) != 0); }
323
324template<class T>
325inline void MakeRandomValue(T&) {}
326
327template <class C>
328struct 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    }
358private:
359    typename C::value_type fInsVal;
360    const C& original;
361    size_t fPos;
362};
363
364template <class C>
365struct 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    }
395private:
396    typename C::value_type fInsVal;
397    const C& original;
398    size_t fPos;
399    size_t fInsCnt;
400};
401
402template <class C>
403struct 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    }
421private:
422    typename C::value_type fInsVal;
423    const C& original;
424};
425
426template <class C>
427struct 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    }
445private:
446    typename C::value_type fInsVal;
447    const C& original;
448};
449
450template <class C, class Position, class Iter>
451void 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
460template <class C, class Position, class Iter>
461void do_insert_range( C& c, Position,
462                      Iter first, Iter last, associative_container_tag )
463{
464    c.insert( first, last );
465}
466
467template <class C, class Position, class Iter>
468void do_insert_range( C& c, Position, Iter first, Iter last, multiset_tag )
469{
470    c.insert( first, last );
471}
472
473template <class C, class Position, class Iter>
474void do_insert_range( C& c, Position, Iter first, Iter last, multimap_tag )
475{
476    c.insert( first, last );
477}
478
479template <class C, class Position, class Iter>
480void do_insert_range( C& c, Position, Iter first, Iter last, set_tag )
481{
482    c.insert( first, last );
483}
484
485template <class C, class Position, class Iter>
486void do_insert_range( C& c, Position, Iter first, Iter last, map_tag )
487{
488    c.insert( first, last );
489}
490
491/*
492template <class C, class Iter>
493void prepare_insert_range( C&, size_t, Iter, Iter) {}
494*/
495
496template <class C, class Iter>
497struct 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    }
528private:
529    Iter fFirst, fLast;
530    const C& original;
531    size_t fPos;
532};
533
534template <class C, class Iter>
535test_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
540template <class C, class Iter>
541test_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
546template <class C, class Iter>
547test_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