1
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 #include <set>
6 using std::set;
7
8 #include <TestUtils.h>
9 #include <cppunit/Test.h>
10 #include <cppunit/TestCaller.h>
11 #include <cppunit/TestSuite.h>
12
13 #include <VectorSet.h>
14
15 #include "common.h"
16 #include "VectorSetTest.h"
17
18 using VectorSetOrder::Ascending;
19 using VectorSetOrder::Descending;
20
VectorSetTest(std::string name)21 VectorSetTest::VectorSetTest(std::string name)
22 : BTestCase(name)
23 {
24 }
25
26 CppUnit::Test*
Suite()27 VectorSetTest::Suite()
28 {
29 CppUnit::TestSuite *suite = new CppUnit::TestSuite("VectorSet");
30
31 ADD_TEST4(VectorSet, suite, VectorSetTest, ConstructorTest);
32 ADD_TEST4(VectorSet, suite, VectorSetTest, InsertTest);
33 ADD_TEST4(VectorSet, suite, VectorSetTest, RemoveTest);
34 ADD_TEST4(VectorSet, suite, VectorSetTest, EraseTest);
35 ADD_TEST4(VectorSet, suite, VectorSetTest, MakeEmptyTest);
36 ADD_TEST4(VectorSet, suite, VectorSetTest, FindTest);
37 ADD_TEST4(VectorSet, suite, VectorSetTest, FindCloseTest);
38 ADD_TEST4(VectorSet, suite, VectorSetTest, IteratorTest);
39
40 return suite;
41 }
42
43 //! ConstructorTest
44 void
ConstructorTest()45 VectorSetTest::ConstructorTest()
46 {
47 NextSubTest();
48 VectorSet<int> v1(100);
49 CHK(v1.Count() == 0);
50 CHK(v1.IsEmpty());
51
52 NextSubTest();
53 VectorSet<string> v2(100);
54 CHK(v2.Count() == 0);
55 CHK(v2.IsEmpty());
56
57 NextSubTest();
58 VectorSet<int> v3(0);
59 CHK(v3.Count() == 0);
60 CHK(v3.IsEmpty());
61
62 NextSubTest();
63 VectorSet<string> v4(0);
64 CHK(v4.Count() == 0);
65 CHK(v4.IsEmpty());
66 }
67
68 // TestIterator
69 template<typename Value, typename TestSet, typename MyIterator,
70 typename ReferenceIterator>
71 class TestIterator {
72 private:
73 typedef TestIterator<Value, TestSet, MyIterator, ReferenceIterator>
74 Iterator;
75
76 public:
TestIterator(TestSet * s,MyIterator myIt,ReferenceIterator refIt)77 inline TestIterator(TestSet *s, MyIterator myIt, ReferenceIterator refIt)
78 : fSet(s),
79 fMyIterator(myIt),
80 fReferenceIterator(refIt)
81 {
82 }
83
TestIterator(const Iterator & other)84 inline TestIterator(const Iterator &other)
85 : fSet(other.fSet),
86 fMyIterator(other.fMyIterator),
87 fReferenceIterator(other.fReferenceIterator)
88 {
89 CHK(fMyIterator == other.fMyIterator);
90 }
91
operator ++()92 inline Iterator &operator++()
93 {
94 MyIterator &myResult = ++fMyIterator;
95 ReferenceIterator &refResult = ++fReferenceIterator;
96 if (refResult == fSet->fReferenceSet.end())
97 CHK(myResult == fSet->fMySet.End());
98 else
99 CHK(*myResult == *refResult);
100 return *this;
101 }
102
operator ++(int)103 inline Iterator operator++(int)
104 {
105 MyIterator oldMyResult = fMyIterator;
106 MyIterator myResult = fMyIterator++;
107 ReferenceIterator refResult = fReferenceIterator++;
108 CHK(oldMyResult == myResult);
109 if (refResult == fSet->fReferenceSet.end())
110 CHK(myResult == fSet->fMySet.End());
111 else
112 CHK(*myResult == *refResult);
113 return Iterator(fSet, myResult, refResult);
114 }
115
operator --()116 inline Iterator &operator--()
117 {
118 MyIterator &myResult = --fMyIterator;
119 ReferenceIterator &refResult = --fReferenceIterator;
120 CHK(*myResult == *refResult);
121 return *this;
122 }
123
operator --(int)124 inline Iterator operator--(int)
125 {
126 MyIterator oldMyResult = fMyIterator;
127 MyIterator myResult = fMyIterator--;
128 ReferenceIterator refResult = fReferenceIterator--;
129 CHK(oldMyResult == myResult);
130 CHK(*myResult == *refResult);
131 return Iterator(fSet, myResult, refResult);
132 }
133
operator =(const Iterator & other)134 inline Iterator &operator=(const Iterator &other)
135 {
136 fSet = other.fSet;
137 fMyIterator = other.fMyIterator;
138 fReferenceIterator = other.fReferenceIterator;
139 CHK(fMyIterator == other.fMyIterator);
140 return *this;
141 }
142
operator ==(const Iterator & other) const143 inline bool operator==(const Iterator &other) const
144 {
145 bool result = (fMyIterator == other.fMyIterator);
146 CHK((fReferenceIterator == other.fReferenceIterator) == result);
147 return result;
148 }
149
operator !=(const Iterator & other) const150 inline bool operator!=(const Iterator &other) const
151 {
152 bool result = (fMyIterator != other.fMyIterator);
153 CHK((fReferenceIterator != other.fReferenceIterator) == result);
154 return result;
155 }
156
operator *() const157 inline Value &operator*() const
158 {
159 Value &result = *fMyIterator;
160 CHK(result == *fReferenceIterator);
161 return result;
162 }
163
operator ->() const164 inline Value *operator->() const
165 {
166 Value *result = fMyIterator.operator->();
167 CHK(*result == *fReferenceIterator);
168 return result;
169 }
170
operator bool() const171 inline operator bool() const
172 {
173 bool result = fMyIterator;
174 CHK((fMyIterator == fSet->fMySet.Null()) != result);
175 return result;
176 }
177
178 public:
179 TestSet *fSet;
180 MyIterator fMyIterator;
181 ReferenceIterator fReferenceIterator;
182 };
183
184 // TestSet
185 template<typename Value, typename MySet, typename ReferenceSet,
186 typename Compare>
187 class TestSet {
188 public:
189 typedef TestSet<Value, MySet, ReferenceSet, Compare> Class;
190
191 typedef typename MySet::Iterator MyIterator;
192 typedef typename ReferenceSet::iterator ReferenceIterator;
193 typedef typename MySet::ConstIterator MyConstIterator;
194 typedef typename ReferenceSet::const_iterator ReferenceConstIterator;
195 typedef TestIterator<Value, Class, MyIterator,
196 ReferenceIterator> Iterator;
197 typedef TestIterator<const Value, const Class, MyConstIterator,
198 ReferenceConstIterator> ConstIterator;
199
TestSet()200 TestSet()
201 : fMySet(),
202 fReferenceSet(),
203 fChecking(true)
204 {
205 }
206
Insert(const Value & value,bool replace=true)207 void Insert(const Value &value, bool replace = true)
208 {
209 CHK(fMySet.Insert(value, replace) == B_OK);
210 ReferenceIterator it = fReferenceSet.find(value);
211 if (it != fReferenceSet.end())
212 fReferenceSet.erase(it);
213 fReferenceSet.insert(value);
214 Check();
215 }
216
Remove(const Value & value)217 void Remove(const Value &value)
218 {
219 int32 oldCount = Count();
220 fReferenceSet.erase(value);
221 int32 newCount = fReferenceSet.size();
222 CHK(fMySet.Remove(value) == oldCount - newCount);
223 Check();
224 }
225
Erase(const Iterator & iterator)226 Iterator Erase(const Iterator &iterator)
227 {
228 bool outOfRange
229 = (iterator.fReferenceIterator == fReferenceSet.end());
230 MyIterator myIt = fMySet.Erase(iterator.fMyIterator);
231 if (outOfRange) {
232 CHK(myIt == fMySet.Null());
233 return Iterator(this, myIt, fReferenceSet.end());
234 }
235 Value nextValue;
236 ReferenceIterator refIt = iterator.fReferenceIterator;
237 ++refIt;
238 bool noNextValue = (refIt == fReferenceSet.end());
239 if (!noNextValue)
240 nextValue = *refIt;
241 fReferenceSet.erase(iterator.fReferenceIterator);
242 if (noNextValue)
243 refIt = fReferenceSet.end();
244 else
245 refIt = fReferenceSet.find(nextValue);
246 Check();
247 if (refIt == fReferenceSet.end())
248 CHK(myIt == fMySet.End());
249 else
250 CHK(*myIt == *refIt);
251 return Iterator(this, myIt, refIt);
252 }
253
Count() const254 inline int32 Count() const
255 {
256 int32 count = fReferenceSet.size();
257 CHK(fMySet.Count() == count);
258 return count;
259 }
260
IsEmpty() const261 inline bool IsEmpty() const
262 {
263 bool result = fReferenceSet.empty();
264 CHK(fMySet.IsEmpty() == result);
265 return result;
266 }
267
MakeEmpty()268 void MakeEmpty()
269 {
270 fMySet.MakeEmpty();
271 fReferenceSet.clear();
272 Check();
273 }
274
Begin()275 inline Iterator Begin()
276 {
277 return Iterator(this, fMySet.Begin(), fReferenceSet.begin());
278 }
279
Begin() const280 inline ConstIterator Begin() const
281 {
282 return ConstIterator(this, fMySet.Begin(),
283 fReferenceSet.begin());
284 }
285
End()286 inline Iterator End()
287 {
288 return Iterator(this, fMySet.End(), fReferenceSet.end());
289 }
290
End() const291 inline ConstIterator End() const
292 {
293 return ConstIterator(this, fMySet.End(), fReferenceSet.end());
294 }
295
Null()296 inline Iterator Null()
297 {
298 return Iterator(this, fMySet.Null(), fReferenceSet.end());
299 }
300
Null() const301 inline ConstIterator Null() const
302 {
303 return ConstIterator(this, fMySet.Null(), fReferenceSet.end());
304 }
305
306 // for testing only
IteratorForIndex(int32 index)307 inline Iterator IteratorForIndex(int32 index)
308 {
309 if (index < 0 || index > Count())
310 return End();
311 MyIterator myIt = fMySet.Begin();
312 ReferenceIterator refIt = fReferenceSet.begin();
313 for (int32 i = 0; i < index; i++) {
314 ++myIt;
315 ++refIt;
316 }
317 return Iterator(this, myIt, refIt);
318 }
319
320 // for testing only
IteratorForIndex(int32 index) const321 inline ConstIterator IteratorForIndex(int32 index) const
322 {
323 if (index < 0 || index > Count())
324 return End();
325 MyConstIterator myIt = fMySet.Begin();
326 ReferenceConstIterator refIt = fReferenceSet.begin();
327 for (int32 i = 0; i < index; i++) {
328 ++myIt;
329 ++refIt;
330 }
331 return ConstIterator(this, myIt, refIt);
332 }
333
Find(const Value & value)334 Iterator Find(const Value &value)
335 {
336 MyIterator myIt = fMySet.Find(value);
337 ReferenceIterator refIt = fReferenceSet.find(value);
338 if (refIt == fReferenceSet.end())
339 CHK(myIt = fMySet.End());
340 else
341 CHK(*myIt == *refIt);
342 return Iterator(this, myIt, refIt);
343 }
344
Find(const Value & value) const345 ConstIterator Find(const Value &value) const
346 {
347 MyConstIterator myIt = fMySet.Find(value);
348 ReferenceConstIterator refIt = fReferenceSet.find(value);
349 if (refIt == fReferenceSet.end())
350 CHK(myIt = fMySet.End());
351 else
352 CHK(*myIt == *refIt);
353 return ConstIterator(this, myIt, refIt);
354 }
355
FindClose(const Value & value,bool less)356 Iterator FindClose(const Value &value, bool less)
357 {
358 MyIterator myIt = fMySet.FindClose(value, less);
359 if (myIt == fMySet.End()) {
360 if (fMySet.Count() > 0) {
361 if (less)
362 CHK(fCompare(*fMySet.Begin(), value) > 0);
363 else
364 CHK(fCompare(*--MyIterator(myIt), value) < 0);
365 }
366 return End();
367 }
368 if (less) {
369 CHK(fCompare(*myIt, value) <= 0);
370 MyIterator nextMyIt(myIt);
371 ++nextMyIt;
372 if (nextMyIt != fMySet.End())
373 CHK(fCompare(*nextMyIt, value) > 0);
374 } else {
375 CHK(fCompare(*myIt, value) >= 0);
376 if (myIt != fMySet.Begin()) {
377 MyIterator prevMyIt(myIt);
378 --prevMyIt;
379 CHK(fCompare(*prevMyIt, value) < 0);
380 }
381 }
382 return Iterator(this, myIt, fReferenceSet.find(*myIt));
383 }
384
FindClose(const Value & value,bool less) const385 ConstIterator FindClose(const Value &value, bool less) const
386 {
387 MyConstIterator myIt = fMySet.FindClose(value, less);
388 if (myIt == fMySet.End()) {
389 if (fMySet.Count() > 0) {
390 if (less)
391 CHK(fCompare(*fMySet.Begin(), value) > 0);
392 else
393 CHK(fCompare(*--MyConstIterator(myIt), value) < 0);
394 }
395 return End();
396 }
397 if (less) {
398 CHK(fCompare(*myIt, value) <= 0);
399 MyConstIterator nextMyIt(myIt);
400 ++nextMyIt;
401 if (nextMyIt != fMySet.End())
402 CHK(fCompare(*nextMyIt, value) > 0);
403 } else {
404 CHK(fCompare(*myIt, value) >= 0);
405 if (myIt != fMySet.Begin()) {
406 MyConstIterator prevMyIt(myIt);
407 --prevMyIt;
408 CHK(fCompare(*prevMyIt, value) < 0);
409 }
410 }
411 return ConstIterator(this, myIt, fReferenceSet.find(*myIt));
412 }
413
SetChecking(bool enable)414 void SetChecking(bool enable)
415 {
416 fChecking = enable;
417 }
418
Check() const419 void Check() const
420 {
421 if (fChecking) {
422 int32 count = fReferenceSet.size();
423 CHK(fMySet.Count() == count);
424 CHK(fMySet.IsEmpty() == fReferenceSet.empty());
425 MyConstIterator myIt = fMySet.Begin();
426 ReferenceConstIterator refIt = fReferenceSet.begin();
427 for (int32 i = 0; i < count; i++, ++myIt, ++refIt)
428 CHK(*myIt == *refIt);
429 CHK(myIt == fMySet.End());
430 }
431 }
432
433 //private:
434 public:
435 MySet fMySet;
436 ReferenceSet fReferenceSet;
437 bool fChecking;
438 Compare fCompare;
439 };
440
441
442 // IntStrategy
443 class IntStrategy {
444 public:
445 typedef int Value;
446
IntStrategy(int32 differentValues=100000)447 IntStrategy(int32 differentValues = 100000)
448 : fDifferentValues(differentValues)
449 {
450 srand(0);
451 }
452
Generate()453 Value Generate()
454 {
455 return rand() % fDifferentValues;
456 }
457
458 private:
459 int32 fDifferentValues;
460 };
461
462 // StringStrategy
463 class StringStrategy {
464 public:
465 typedef string Value;
466
StringStrategy(int32 differentValues=100000)467 StringStrategy(int32 differentValues = 100000)
468 : fDifferentValues(differentValues)
469 {
470 srand(0);
471 }
472
Generate()473 Value Generate()
474 {
475 char buffer[10];
476 sprintf(buffer, "%ld", rand() % fDifferentValues);
477 return string(buffer);
478 }
479
480 private:
481 int32 fDifferentValues;
482 };
483
484 // CompareWrapper
485 template<typename Value, typename Compare>
486 class CompareWrapper {
487 public:
operator ()(const Value & a,const Value & b) const488 inline bool operator()(const Value &a, const Value &b) const
489 {
490 return (fCompare(a, b) < 0);
491 }
492
493 private:
494 Compare fCompare;
495 };
496
497 // TestStrategy
498 template<typename _ValueStrategy, template<typename> class _CompareStrategy>
499 class TestStrategy {
500 public:
501 typedef _ValueStrategy ValueStrategy;
502 typedef typename ValueStrategy::Value Value;
503 typedef _CompareStrategy<Value> Compare;
504 typedef CompareWrapper<Value, Compare> BoolCompare;
505 typedef VectorSet<Value, Compare> MySet;
506 typedef set<Value, BoolCompare> ReferenceSet;
507 typedef TestSet<Value, MySet, ReferenceSet, Compare> TestClass;
508 };
509
510 typedef TestStrategy<IntStrategy, Ascending> AIntTestStrategy;
511 typedef TestStrategy<StringStrategy, Ascending> AStringTestStrategy;
512 typedef TestStrategy<IntStrategy, Descending> DIntTestStrategy;
513 typedef TestStrategy<StringStrategy, Descending> DStringTestStrategy;
514
515 // GenericInsertTest
516 template<typename _TestStrategy>
517 static
518 void
GenericInsertTest(int32 maxNumber)519 GenericInsertTest(int32 maxNumber)
520 {
521 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
522 typedef typename _TestStrategy::TestClass TestClass;
523 ValueStrategy strategy;
524 TestClass v;
525 for (int32 i = 0; i < maxNumber; i++)
526 v.Insert(strategy.Generate());
527 }
528
529 // InsertTest
530 void
InsertTest()531 VectorSetTest::InsertTest()
532 {
533 NextSubTest();
534 GenericInsertTest<AIntTestStrategy>(30);
535 NextSubTest();
536 GenericInsertTest<DIntTestStrategy>(30);
537 NextSubTest();
538 GenericInsertTest<AIntTestStrategy>(200);
539 NextSubTest();
540 GenericInsertTest<DIntTestStrategy>(200);
541 NextSubTest();
542 GenericInsertTest<AStringTestStrategy>(30);
543 NextSubTest();
544 GenericInsertTest<DStringTestStrategy>(30);
545 NextSubTest();
546 GenericInsertTest<AStringTestStrategy>(200);
547 NextSubTest();
548 GenericInsertTest<DStringTestStrategy>(200);
549 }
550
551 // GenericFill
552 template<typename TestClass, typename ValueStrategy>
553 static
554 void
GenericFill(TestClass & v,ValueStrategy strategy,int32 maxNumber)555 GenericFill(TestClass &v, ValueStrategy strategy, int32 maxNumber)
556 {
557 v.SetChecking(false);
558 for (int32 i = 0; v.Count() < maxNumber; i++)
559 v.Insert(strategy.Generate());
560 v.SetChecking(true);
561 v.Check();
562 }
563
564 // GenericRemoveTest
565 template<typename _TestStrategy>
566 static
567 void
GenericRemoveTest(int32 maxNumber)568 GenericRemoveTest(int32 maxNumber)
569 {
570 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
571 typedef typename _TestStrategy::Value Value;
572 typedef typename _TestStrategy::TestClass TestClass;
573 ValueStrategy strategy;
574 TestClass v;
575 GenericFill(v, strategy, maxNumber);
576 while (v.Count() > 0) {
577 int32 index = rand() % (v.Count());
578 Value value = *v.IteratorForIndex(index);
579 v.Remove(value);
580 v.Remove(value);
581 }
582 }
583
584 // RemoveTest
585 void
RemoveTest()586 VectorSetTest::RemoveTest()
587 {
588 NextSubTest();
589 GenericRemoveTest<AIntTestStrategy>(30);
590 NextSubTest();
591 GenericRemoveTest<DIntTestStrategy>(30);
592 NextSubTest();
593 GenericRemoveTest<AIntTestStrategy>(200);
594 NextSubTest();
595 GenericRemoveTest<DIntTestStrategy>(200);
596 NextSubTest();
597 GenericRemoveTest<AStringTestStrategy>(30);
598 NextSubTest();
599 GenericRemoveTest<DStringTestStrategy>(30);
600 NextSubTest();
601 GenericRemoveTest<AStringTestStrategy>(200);
602 NextSubTest();
603 GenericRemoveTest<DStringTestStrategy>(200);
604 }
605
606 // GenericEraseTest
607 template<typename _TestStrategy>
608 static
609 void
GenericEraseTest(int32 maxNumber)610 GenericEraseTest(int32 maxNumber)
611 {
612 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
613 typedef typename _TestStrategy::TestClass TestClass;
614 ValueStrategy strategy;
615 TestClass v;
616 GenericFill(v, strategy, maxNumber);
617 for (int32 i = maxNumber - 1; i >= 0; i--) {
618 int32 index = rand() % (i + 1);
619 v.Erase(v.IteratorForIndex(index));
620 }
621 }
622
623 // EraseTest
624 void
EraseTest()625 VectorSetTest::EraseTest()
626 {
627 NextSubTest();
628 GenericEraseTest<AIntTestStrategy>(30);
629 NextSubTest();
630 GenericEraseTest<DIntTestStrategy>(30);
631 NextSubTest();
632 GenericEraseTest<AIntTestStrategy>(200);
633 NextSubTest();
634 GenericEraseTest<DIntTestStrategy>(200);
635 NextSubTest();
636 GenericEraseTest<AStringTestStrategy>(30);
637 NextSubTest();
638 GenericEraseTest<DStringTestStrategy>(30);
639 NextSubTest();
640 GenericEraseTest<AStringTestStrategy>(200);
641 NextSubTest();
642 GenericEraseTest<DStringTestStrategy>(200);
643 }
644
645 // GenericMakeEmptyTest
646 template<typename _TestStrategy>
647 static
648 void
GenericMakeEmptyTest(int32 maxNumber)649 GenericMakeEmptyTest(int32 maxNumber)
650 {
651 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
652 typedef typename _TestStrategy::TestClass TestClass;
653 ValueStrategy strategy;
654 TestClass v;
655 v.MakeEmpty();
656 GenericFill(v, strategy, maxNumber);
657 v.MakeEmpty();
658 v.MakeEmpty();
659 }
660
661 // MakeEmptyTest
662 void
MakeEmptyTest()663 VectorSetTest::MakeEmptyTest()
664 {
665 NextSubTest();
666 GenericMakeEmptyTest<AIntTestStrategy>(30);
667 NextSubTest();
668 GenericMakeEmptyTest<DIntTestStrategy>(30);
669 NextSubTest();
670 GenericMakeEmptyTest<AIntTestStrategy>(200);
671 NextSubTest();
672 GenericMakeEmptyTest<DIntTestStrategy>(200);
673 NextSubTest();
674 GenericMakeEmptyTest<AStringTestStrategy>(30);
675 NextSubTest();
676 GenericMakeEmptyTest<DStringTestStrategy>(30);
677 NextSubTest();
678 GenericMakeEmptyTest<AStringTestStrategy>(200);
679 NextSubTest();
680 GenericMakeEmptyTest<DStringTestStrategy>(200);
681 }
682
683 // GenericFindTest
684 template<typename _TestStrategy>
685 static
686 void
GenericFindTest(int32 maxNumber)687 GenericFindTest(int32 maxNumber)
688 {
689 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
690 typedef typename _TestStrategy::Value Value;
691 typedef typename _TestStrategy::TestClass TestClass;
692 typedef typename TestClass::Iterator Iterator;
693 typedef typename TestClass::ConstIterator ConstIterator;
694 ValueStrategy strategy;
695 TestClass v;
696 GenericFill(v, strategy, maxNumber);
697 const TestClass &cv = v;
698 // find the values in the set
699 for (int32 i = 0; i < maxNumber; i++) {
700 const Value &value = *v.IteratorForIndex(i);
701 Iterator it = v.Find(value);
702 ConstIterator cit = cv.Find(value);
703 CHK(&*it == &*cit);
704 }
705 // try to find some random values
706 for (int32 i = 0; i < maxNumber; i++) {
707 Value value = strategy.Generate();
708 Iterator it = v.Find(value);
709 ConstIterator cit = cv.Find(value);
710 if (it != v.End())
711 CHK(&*it == &*cit);
712 }
713 }
714
715 // FindTest
716 void
FindTest()717 VectorSetTest::FindTest()
718 {
719 NextSubTest();
720 GenericFindTest<AIntTestStrategy>(30);
721 NextSubTest();
722 GenericFindTest<DIntTestStrategy>(30);
723 NextSubTest();
724 GenericFindTest<AIntTestStrategy>(200);
725 NextSubTest();
726 GenericFindTest<DIntTestStrategy>(200);
727 NextSubTest();
728 GenericFindTest<AStringTestStrategy>(30);
729 NextSubTest();
730 GenericFindTest<DStringTestStrategy>(30);
731 NextSubTest();
732 GenericFindTest<AStringTestStrategy>(200);
733 NextSubTest();
734 GenericFindTest<DStringTestStrategy>(200);
735 }
736
737 // GenericFindCloseTest
738 template<typename _TestStrategy>
739 static
740 void
GenericFindCloseTest(int32 maxNumber)741 GenericFindCloseTest(int32 maxNumber)
742 {
743 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
744 typedef typename _TestStrategy::Value Value;
745 typedef typename _TestStrategy::TestClass TestClass;
746 typedef typename TestClass::Iterator Iterator;
747 typedef typename TestClass::ConstIterator ConstIterator;
748 ValueStrategy strategy;
749 TestClass v;
750 GenericFill(v, strategy, maxNumber);
751 const TestClass &cv = v;
752 // find the values in the set
753 for (int32 i = 0; i < maxNumber; i++) {
754 const Value &value = *v.IteratorForIndex(i);
755 // less
756 Iterator it = v.FindClose(value, true);
757 ConstIterator cit = cv.FindClose(value, true);
758 CHK(*it == value);
759 CHK(&*it == &*cit);
760 // greater
761 it = v.FindClose(value, false);
762 cit = cv.FindClose(value, false);
763 CHK(*it == value);
764 CHK(&*it == &*cit);
765 }
766 // try to find some random values
767 for (int32 i = 0; i < maxNumber; i++) {
768 Value value = strategy.Generate();
769 // less
770 Iterator it = v.FindClose(value, true);
771 ConstIterator cit = cv.FindClose(value, true);
772 if (it != v.End())
773 CHK(&*it == &*cit);
774 // greater
775 it = v.FindClose(value, false);
776 cit = cv.FindClose(value, false);
777 if (it != v.End())
778 CHK(&*it == &*cit);
779 }
780 }
781
782 // FindCloseTest
783 void
FindCloseTest()784 VectorSetTest::FindCloseTest()
785 {
786 NextSubTest();
787 GenericFindCloseTest<AIntTestStrategy>(30);
788 NextSubTest();
789 GenericFindCloseTest<DIntTestStrategy>(30);
790 NextSubTest();
791 GenericFindCloseTest<AIntTestStrategy>(200);
792 NextSubTest();
793 GenericFindCloseTest<DIntTestStrategy>(200);
794 NextSubTest();
795 GenericFindCloseTest<AStringTestStrategy>(30);
796 NextSubTest();
797 GenericFindCloseTest<DStringTestStrategy>(30);
798 NextSubTest();
799 GenericFindCloseTest<AStringTestStrategy>(200);
800 NextSubTest();
801 GenericFindCloseTest<DStringTestStrategy>(200);
802 }
803
804 // GenericIteratorTest
805 template<typename _TestStrategy>
806 static
807 void
GenericIteratorTest(int32 maxNumber)808 GenericIteratorTest(int32 maxNumber)
809 {
810 typedef typename _TestStrategy::ValueStrategy ValueStrategy;
811 typedef typename _TestStrategy::TestClass TestClass;
812 typedef typename TestClass::Iterator Iterator;
813 typedef typename TestClass::ConstIterator ConstIterator;
814 ValueStrategy strategy;
815 TestClass v;
816 GenericFill(v, strategy, maxNumber);
817 const TestClass &cv = v;
818 Iterator it = v.Begin();
819 ConstIterator cit = cv.Begin();
820 for (; it != v.End(); ++it, ++cit) {
821 CHK(&*it == &*cit);
822 CHK(&*it == it.operator->());
823 CHK(&*cit == cit.operator->());
824 CHK(it);
825 CHK(cit);
826 }
827 CHK(cit == cv.End());
828 while (it != v.Begin()) {
829 --it;
830 --cit;
831 CHK(&*it == &*cit);
832 CHK(&*it == it.operator->());
833 CHK(&*cit == cit.operator->());
834 CHK(it);
835 CHK(cit);
836 }
837 CHK(cit == cv.Begin());
838 CHK(!v.Null());
839 CHK(!cv.Null());
840 }
841
842 // IteratorTest
843 void
IteratorTest()844 VectorSetTest::IteratorTest()
845 {
846 NextSubTest();
847 GenericIteratorTest<AIntTestStrategy>(30);
848 NextSubTest();
849 GenericIteratorTest<DIntTestStrategy>(30);
850 NextSubTest();
851 GenericIteratorTest<AIntTestStrategy>(200);
852 NextSubTest();
853 GenericIteratorTest<DIntTestStrategy>(200);
854 NextSubTest();
855 GenericIteratorTest<AStringTestStrategy>(30);
856 NextSubTest();
857 GenericIteratorTest<DStringTestStrategy>(30);
858 NextSubTest();
859 GenericIteratorTest<AStringTestStrategy>(200);
860 NextSubTest();
861 GenericIteratorTest<DStringTestStrategy>(200);
862 }
863
864