ReactOS  0.4.13-dev-73-gcfe54aa
test_insert.h
Go to the documentation of this file.
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 {};
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)
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
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>
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>
329 {
330  test_insert_one( const C& orig, int pos =-1 )
331  : original( orig ), fPos( random_number( orig.size() ))
332  {
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
355  // Success. Check results.
357  }
358 private:
359  typename C::value_type fInsVal;
360  const C& original;
361  size_t fPos;
362 };
363 
364 template <class C>
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  {
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  {
386  typename C::iterator pos = c.begin();
388  c.insert( pos, fInsCnt, fInsVal );
389 
390  // Prevent simulated failures during verification
392  // Success. Check results.
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>
404 {
405  test_insert_value( const C& orig )
406  : original( orig )
407  {
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
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>
428 {
429  test_insert_noresize( const C& orig )
430  : original( orig )
431  {
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
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>
452  Iter first, Iter last, sequence_container_tag )
453 {
454  typedef typename C::iterator CIter;
455  CIter pos = c_inst.begin();
457  c_inst.insert( pos, first, last );
458 }
459 
460 template <class C, class Position, class Iter>
462  Iter first, Iter last, associative_container_tag )
463 {
464  c.insert( first, last );
465 }
466 
467 template <class C, class Position, class Iter>
469 {
470  c.insert( first, last );
471 }
472 
473 template <class C, class Position, class Iter>
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>
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 );
522 
523  // Prevent simulated failures during verification
525  // Success. Check results.
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_
_In_opt_ ULONG _Out_ PULONG Value
Definition: rtlfuncs.h:2327
#define EH_END_NAMESPACE
Definition: Prefix.h:65
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
size_t CountUniqueItems_Aux(const C &original, Iter firstNew, Iter lastNew, const KeyOfValue &keyOfValue)
Definition: test_insert.h:76
#define EH_BEGIN_NAMESPACE
Definition: Prefix.h:64
POINT last
Definition: font.c:46
_STLP_MOVE_TO_STD_NAMESPACE void sort(_RandomAccessIter __first, _RandomAccessIter __last)
Definition: _algo.c:993
static COORD Position
Definition: mouse.c:34
TestController gTestController
Definition: nc_alloc.cpp:46
const GLint * first
Definition: glext.h:5794
GLintptr offset
Definition: glext.h:5920
void operator()(C &c) const
Definition: test_insert.h:383
GLdouble n
Definition: glext.h:7729
C::value_type fInsVal
Definition: test_insert.h:422
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
test_insert_noresize(const C &orig)
Definition: test_insert.h:429
static void SetCurrentTestName(const char *str)
Definition: nc_alloc.h:172
#define T
Definition: mbstring.h:31
#define EH_DISTANCE(a, b, result)
Definition: Prefix.h:98
void do_insert_range(C &c_inst, Position offset, Iter first, Iter last, sequence_container_tag)
Definition: test_insert.h:451
_STLP_INLINE_LOOP _STLP_STD::pair< _InputIter1, _InputIter2 > mismatch(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2)
Definition: _algobase.h:522
const C & original
Definition: test_insert.h:530
void VerifyInsertN(const C &original, const C &result, size_t insCnt, const Value &val, size_t insPos)
Definition: test_insert.h:293
void VerifyInsertion(const C &original, const C &result, const SrcIter &firstNew, const SrcIter &lastNew, size_t, associative_container_tag)
Definition: test_insert.h:165
void operator()(C &c) const
Definition: test_insert.h:518
test_insert_range< C, Iter > insert_range_tester(const C &orig, const Iter &first, const Iter &last)
Definition: test_insert.h:535
const _Pair::first_type & operator()(const _Pair &__x) const
Definition: test_insert.h:117
test_insert_range< C, Iter > insert_range_at_end_tester(const C &orig, const Iter &first, const Iter &last)
Definition: test_insert.h:547
test_insert_value(const C &orig)
Definition: test_insert.h:405
GLuint GLfloat * val
Definition: glext.h:7180
typedef bool(CARDLIBPROC *pCanDragProc)(CardRegion &stackobj
const C & original
Definition: test_insert.h:360
__kernel_size_t size_t
Definition: linux.h:237
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLsizeiptr size
Definition: glext.h:5919
test_insert_n(const C &orig, size_t insCnt, int pos=-1)
Definition: test_insert.h:367
EH_END_NAMESPACE size_t CountUniqueItems(const C &original, const Iter &firstNew, const Iter &lastNew, set_tag)
Definition: test_insert.h:126
void operator()(C &c) const
Definition: test_insert.h:346
test_insert_one(const C &orig, int pos=-1)
Definition: test_insert.h:330
const GLubyte * c
Definition: glext.h:8905
test_insert_range< C, Iter > insert_range_at_begin_tester(const C &orig, const Iter &first, const Iter &last)
Definition: test_insert.h:541
#define EH_ASSERT
Definition: Prefix.h:37
HKEY key
Definition: reg.c:42
unsigned random_number(size_t range)
_STLP_MOVE_TO_STD_NAMESPACE void _STLP_CALL advance(_InputIterator &__i, _Distance __n)
void prepare_insert_n(C &, size_t)
Definition: test_insert.h:318
void operator()(C &c) const
Definition: test_insert.h:436
C::value_type fInsVal
Definition: test_insert.h:396
sequence_container_tag container_category(const BitVector &)
size_t CountNewItems(const C &, const Iter &firstNew, const Iter &lastNew, sequence_container_tag)
Definition: test_insert.h:45
size_t fInsCnt
Definition: test_insert.h:399
Definition: ttei6.cpp:27
INT copy(TCHAR source[MAX_PATH], TCHAR dest[MAX_PATH], INT append, DWORD lpdwFlags, BOOL bTouch)
Definition: copy.c:51
test_insert_range(const C &orig, Iter first, Iter last, int pos=-1)
Definition: test_insert.h:499
static TAGID TAGID find
Definition: db.cpp:153
C::value_type fInsVal
Definition: test_insert.h:446
void MakeRandomValue(bool &b)
Definition: test_insert.h:322
_ForwardIter unique(_ForwardIter __first, _ForwardIter __last)
Definition: _algo.h:298
const T & operator()(const T &x) const
Definition: test_insert.h:112
static void CancelFailureCountdown()
Definition: nc_alloc.h:143
const C & original
Definition: test_insert.h:397
GLfloat GLfloat p
Definition: glext.h:8902
const C & original
Definition: test_insert.h:423
GLuint64EXT * result
Definition: glext.h:11304
void operator()(C &c) const
Definition: test_insert.h:412
C::value_type fInsVal
Definition: test_insert.h:359