ReactOS 0.4.15-dev-7788-g1ad9096
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
35struct 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)
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
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,
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>
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>
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 }
358private:
359 typename C::value_type fInsVal;
360 const C& original;
361 size_t fPos;
362};
363
364template <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();
387 EH_STD::advance( pos, fPos );
388 c.insert( pos, fInsCnt, fInsVal );
389
390 // Prevent simulated failures during verification
392 // Success. Check results.
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>
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 }
421private:
422 typename C::value_type fInsVal;
423 const C& original;
424};
425
426template <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 }
445private:
446 typename C::value_type fInsVal;
447 const C& original;
448};
449
450template <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();
456 EH_STD::advance( pos, offset );
457 c_inst.insert( pos, first, last );
458}
459
460template <class C, class Position, class Iter>
463{
464 c.insert( first, last );
465}
466
467template <class C, class Position, class Iter>
469{
470 c.insert( first, last );
471}
472
473template <class C, class Position, class Iter>
475{
476 c.insert( first, last );
477}
478
479template <class C, class Position, class Iter>
481{
482 c.insert( first, last );
483}
484
485template <class C, class Position, class Iter>
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>
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 }
528private:
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>
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_
#define EH_END_NAMESPACE
Definition: Prefix.h:65
#define EH_ASSERT
Definition: Prefix.h:37
#define EH_BEGIN_NAMESPACE
Definition: Prefix.h:64
#define EH_DISTANCE(a, b, result)
Definition: Prefix.h:98
Definition: terminate.cpp:24
__kernel_size_t size_t
Definition: linux.h:237
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLsizeiptr size
Definition: glext.h:5919
GLdouble n
Definition: glext.h:7729
const GLubyte * c
Definition: glext.h:8905
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
const GLint * first
Definition: glext.h:5794
GLuint GLfloat * val
Definition: glext.h:7180
GLfloat GLfloat p
Definition: glext.h:8902
GLuint64EXT * result
Definition: glext.h:11304
GLintptr offset
Definition: glext.h:5920
#define T
Definition: mbstring.h:31
static UINT UINT last
Definition: font.c:45
TestController gTestController
Definition: nc_alloc.cpp:46
#define bool
Definition: nsiface.idl:72
unsigned random_number(size_t range)
static void SetCurrentTestName(const char *str)
Definition: nc_alloc.h:172
static void CancelFailureCountdown()
Definition: nc_alloc.h:143
const T & operator()(const T &x) const
Definition: test_insert.h:112
Definition: copy.c:22
const _Pair::first_type & operator()(const _Pair &__x) const
Definition: test_insert.h:117
void operator()(C &c) const
Definition: test_insert.h:383
const C & original
Definition: test_insert.h:397
C::value_type fInsVal
Definition: test_insert.h:396
test_insert_n(const C &orig, size_t insCnt, int pos=-1)
Definition: test_insert.h:367
size_t fInsCnt
Definition: test_insert.h:399
void operator()(C &c) const
Definition: test_insert.h:436
C::value_type fInsVal
Definition: test_insert.h:446
test_insert_noresize(const C &orig)
Definition: test_insert.h:429
test_insert_one(const C &orig, int pos=-1)
Definition: test_insert.h:330
void operator()(C &c) const
Definition: test_insert.h:346
const C & original
Definition: test_insert.h:360
C::value_type fInsVal
Definition: test_insert.h:359
const C & original
Definition: test_insert.h:530
void operator()(C &c) const
Definition: test_insert.h:518
test_insert_range(const C &orig, Iter first, Iter last, int pos=-1)
Definition: test_insert.h:499
void operator()(C &c) const
Definition: test_insert.h:412
C::value_type fInsVal
Definition: test_insert.h:422
const C & original
Definition: test_insert.h:423
test_insert_value(const C &orig)
Definition: test_insert.h:405
static COORD Position
Definition: mouse.c:34
sequence_container_tag container_category(const BitVector &)
EH_END_NAMESPACE size_t CountUniqueItems(const C &original, const Iter &firstNew, const Iter &lastNew, set_tag)
Definition: test_insert.h:126
void do_insert_range(C &c_inst, Position offset, Iter first, Iter last, sequence_container_tag)
Definition: test_insert.h:451
test_insert_range< C, Iter > insert_range_tester(const C &orig, const Iter &first, const Iter &last)
Definition: test_insert.h:535
size_t CountNewItems(const C &, const Iter &firstNew, const Iter &lastNew, sequence_container_tag)
Definition: test_insert.h:45
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
test_insert_range< C, Iter > insert_range_at_begin_tester(const C &orig, const Iter &first, const Iter &last)
Definition: test_insert.h:541
size_t CountUniqueItems_Aux(const C &original, Iter firstNew, Iter lastNew, const KeyOfValue &keyOfValue)
Definition: test_insert.h:76
test_insert_range< C, Iter > insert_range_at_end_tester(const C &orig, const Iter &first, const Iter &last)
Definition: test_insert.h:547
void prepare_insert_n(C &, size_t)
Definition: test_insert.h:318
void MakeRandomValue(bool &b)
Definition: test_insert.h:322
_Must_inspect_result_ _In_ WDFKEY _In_ PCUNICODE_STRING _Out_opt_ PUSHORT _Inout_opt_ PUNICODE_STRING Value
Definition: wdfregistry.h:413