1 // OrderedMapTest.h
2 #ifndef _ordered_map_test_h_
3 #define _ordered_map_test_h_
4
5 #include <map>
6 #include <stdio.h>
7 #include <stdlib.h>
8
9 using std::map;
10
11 #include <TestCase.h>
12 #include <TestUtils.h>
13 #include <cppunit/Test.h>
14 #include <cppunit/TestCaller.h>
15 #include <cppunit/TestSuite.h>
16
17 #include "common.h"
18
19 // That's how it should be, but we need to work around compiler bugs
20 // (in this case an unimplemented feature).
21 /*
22 #define _ORDERED_MAP_TEST_TEMPLATE_LIST \
23 template<template<template<typename> class CompareStrategy> \
24 class TestStrategy>
25 */
26 #define _ORDERED_MAP_TEST_TEMPLATE_LIST \
27 template<template<typename> class TestStrategy>
28 #define _ORDERED_MAP_TEST_CLASS_NAME OrderedMapTest<TestStrategy>
29
30 //template<template<template<typename> class CompareStrategy> class TestStrategy>
31 template<template<typename CompareWrapperStrategy> class TestStrategy>
32 class OrderedMapTest : public BTestCase {
33 public:
34 OrderedMapTest(std::string name = "");
35
36 static CppUnit::Test* Suite();
37
38 void ConstructorTest();
39 void InsertTest();
40 void PutTest();
41 void GetTest();
42 void RemoveTest();
43 void EraseTest();
44 void MakeEmptyTest();
45 void IndexAccessTest();
46 void FindTest();
47 void FindCloseTest();
48 void IteratorTest();
49
50 private:
51 template <class List>
52 void TestList(List &list, typename List::ValueType *values, int valueCount);
53 };
54
55 // SimpleValueStrategy
56 template<typename _Value>
57 class SimpleValueStrategy {
58 public:
59 typedef _Value Value;
60
61 SimpleValueStrategy(int32 differentValues = 100000)
fDifferentValues(differentValues)62 : fDifferentValues(differentValues)
63 {
64 srand(0);
65 }
66
67 Value Generate();
68
69 private:
70 int32 fDifferentValues;
71 };
72
73 template<>
74 int
Generate()75 SimpleValueStrategy<int>::Generate()
76 {
77 return rand() % fDifferentValues;
78 }
79
80 template<>
81 string
Generate()82 SimpleValueStrategy<string>::Generate()
83 {
84 char buffer[10];
85 sprintf(buffer, "%ld", rand() % fDifferentValues);
86 return string(buffer);
87 }
88
89 // PairEntryStrategy
90 template<typename _KeyStrategy, typename _ValueStrategy>
91 class PairEntryStrategy {
92 public:
93 typedef _KeyStrategy KeyStrategy;
94 typedef _ValueStrategy ValueStrategy;
95 typedef typename KeyStrategy::Value Key;
96 typedef typename ValueStrategy::Value Value;
97
GenerateKey()98 inline Key GenerateKey()
99 {
100 return fKeyStrategy.Generate();
101 }
102
GenerateValue()103 inline Value GenerateValue()
104 {
105 return fValueStrategy.Generate();
106 }
107
Generate(Key & key,Value & value)108 inline void Generate(Key &key, Value &value)
109 {
110 key = GenerateKey();
111 value = GenerateValue();
112 }
113
114 private:
115 KeyStrategy fKeyStrategy;
116 ValueStrategy fValueStrategy;
117 };
118
119 // ImplicitKeyStrategy
120 template<typename _KeyStrategy, typename _ValueStrategy, typename GetKey>
121 class ImplicitKeyStrategy {
122 public:
123 typedef _KeyStrategy KeyStrategy;
124 typedef _ValueStrategy ValueStrategy;
125 typedef typename KeyStrategy::Value Key;
126 typedef typename ValueStrategy::Value Value;
127
GenerateKey()128 inline Key GenerateKey()
129 {
130 return fKeyStrategy.Generate();
131 }
132
GenerateValue()133 inline Value GenerateValue()
134 {
135 return fValueStrategy.Generate();
136 }
137
Generate(Key & key,Value & value)138 inline void Generate(Key &key, Value &value)
139 {
140 value = GenerateValue();
141 key = fGetKey(value);
142 }
143
144 private:
145 KeyStrategy fKeyStrategy;
146 ValueStrategy fValueStrategy;
147 GetKey fGetKey;
148 };
149
150 // Non-template wrapper for the Ascending compare strategy.
151 // Work-around for our compiler not eating nested template template
152 // parameters.
153 struct Ascending {
154 template<typename Value>
155 class Strategy : public KernelUtilsOrder::Ascending<Value> {};
156 };
157
158 // Non-template wrapper for the Descending compare strategy.
159 // Work-around for our compiler not eating nested template template
160 // parameters.
161 struct Descending {
162 template<typename Value>
163 class Strategy : public KernelUtilsOrder::Descending<Value> {};
164 };
165
166 // CompareWrapper
167 template<typename Value, typename Compare>
168 class CompareWrapper {
169 public:
operator()170 inline bool operator()(const Value &a, const Value &b) const
171 {
172 return (fCompare(a, b) < 0);
173 }
174
175 private:
176 Compare fCompare;
177 };
178
179
180 // TestIterator
181 template<typename Entry, typename TestMap, typename MyIterator,
182 typename ReferenceIterator>
183 class TestIterator {
184 private:
185 typedef TestIterator<Entry, TestMap, MyIterator, ReferenceIterator>
186 Iterator;
187
188 public:
TestIterator(TestMap * s,MyIterator myIt,ReferenceIterator refIt)189 inline TestIterator(TestMap *s, MyIterator myIt, ReferenceIterator refIt)
190 : fMap(s),
191 fMyIterator(myIt),
192 fReferenceIterator(refIt)
193 {
194 }
195
TestIterator(const Iterator & other)196 inline TestIterator(const Iterator &other)
197 : fMap(other.fMap),
198 fMyIterator(other.fMyIterator),
199 fReferenceIterator(other.fReferenceIterator)
200 {
201 CHK(fMyIterator == other.fMyIterator);
202 }
203
204 inline Iterator &operator++()
205 {
206 MyIterator &myResult = ++fMyIterator;
207 ReferenceIterator &refResult = ++fReferenceIterator;
208 if (refResult == fMap->fReferenceMap.end())
209 CHK(myResult == fMap->fMyMap.End());
210 else {
211 CHK(myResult->Key() == refResult->first);
212 CHK(myResult->Value() == refResult->second);
213 }
214 return *this;
215 }
216
217 inline Iterator operator++(int)
218 {
219 MyIterator oldMyResult = fMyIterator;
220 MyIterator myResult = fMyIterator++;
221 ReferenceIterator refResult = fReferenceIterator++;
222 CHK(oldMyResult == myResult);
223 if (refResult == fMap->fReferenceMap.end())
224 CHK(myResult == fMap->fMyMap.End());
225 else {
226 CHK(myResult->Key() == refResult->first);
227 CHK(myResult->Value() == refResult->second);
228 }
229 return Iterator(fMap, myResult, refResult);
230 }
231
232 inline Iterator &operator--()
233 {
234 MyIterator &myResult = --fMyIterator;
235 ReferenceIterator &refResult = --fReferenceIterator;
236 CHK(myResult->Key() == refResult->first);
237 CHK(myResult->Value() == refResult->second);
238 return *this;
239 }
240
241 inline Iterator operator--(int)
242 {
243 MyIterator oldMyResult = fMyIterator;
244 MyIterator myResult = fMyIterator--;
245 ReferenceIterator refResult = fReferenceIterator--;
246 CHK(oldMyResult == myResult);
247 CHK(myResult->Key() == refResult->first);
248 CHK(myResult->Value() == refResult->second);
249 return Iterator(fMap, myResult, refResult);
250 }
251
252 inline Iterator &operator=(const Iterator &other)
253 {
254 fMap = other.fMap;
255 fMyIterator = other.fMyIterator;
256 fReferenceIterator = other.fReferenceIterator;
257 CHK(fMyIterator == other.fMyIterator);
258 return *this;
259 }
260
261 inline bool operator==(const Iterator &other) const
262 {
263 bool result = (fMyIterator == other.fMyIterator);
264 CHK((fReferenceIterator == other.fReferenceIterator) == result);
265 return result;
266 }
267
268 inline bool operator!=(const Iterator &other) const
269 {
270 bool result = (fMyIterator != other.fMyIterator);
271 CHK((fReferenceIterator != other.fReferenceIterator) == result);
272 return result;
273 }
274
275 inline Entry operator*() const
276 {
277 Entry entry = *fMyIterator;
278 CHK(entry.Key() == fReferenceIterator->first);
279 CHK(entry.Value() == fReferenceIterator->second);
280 return entry;
281 }
282
283 inline Entry operator->() const
284 {
285 Entry entry = fMyIterator.operator->();
286 CHK(entry.Key() == fReferenceIterator->first);
287 CHK(entry.Value() == fReferenceIterator->second);
288 return entry;
289 }
290
291 inline operator bool() const
292 {
293 bool result = fMyIterator;
294 CHK((fMyIterator == fMap->fMyMap.Null()) != result);
295 return result;
296 }
297
298 public:
299 TestMap *fMap;
300 MyIterator fMyIterator;
301 ReferenceIterator fReferenceIterator;
302 };
303
304 // TestMap
305 template<typename Key, typename Value, typename MyMap, typename ReferenceMap,
306 typename Compare>
307 class TestMap {
308 public:
309 typedef TestMap<Key, Value, MyMap, ReferenceMap, Compare> Class;
310
311 typedef typename MyMap::Iterator MyIterator;
312 typedef typename ReferenceMap::iterator ReferenceIterator;
313 typedef typename MyMap::ConstIterator MyConstIterator;
314 typedef typename ReferenceMap::const_iterator ReferenceConstIterator;
315 typedef typename MyMap::Entry Entry;
316 typedef typename MyMap::ConstEntry ConstEntry;
317 typedef TestIterator<Entry, Class, MyIterator,
318 ReferenceIterator> Iterator;
319 typedef TestIterator<ConstEntry, const Class, MyConstIterator,
320 ReferenceConstIterator> ConstIterator;
321
TestMap()322 TestMap()
323 : fMyMap(),
324 fReferenceMap(),
325 fChecking(true)
326 {
327 }
328
Insert(const Key & key,const Value & value)329 void Insert(const Key &key, const Value &value)
330 {
331 CHK(fMyMap.Insert(key, value) == B_OK);
332 fReferenceMap[key] = value;
333 Check();
334 }
335
Put(const Key & key,const Value & value)336 void Put(const Key &key, const Value &value)
337 {
338 CHK(fMyMap.Put(key, value) == B_OK);
339 fReferenceMap[key] = value;
340 Check();
341 }
342
Get(const Key & key)343 Value &Get(const Key &key)
344 {
345 Value &value = fMyMap.Get(key);
346 CHK(value == fReferenceMap[key]);
347 return value;
348 }
349
Get(const Key & key)350 const Value &Get(const Key &key) const
351 {
352 const Value &value = fMyMap.Get(key);
353 CHK(value == fReferenceMap.find(key)->second);
354 return value;
355 }
356
Remove(const Key & key)357 void Remove(const Key &key)
358 {
359 int32 oldCount = Count();
360 ReferenceIterator it = fReferenceMap.find(key);
361 if (it != fReferenceMap.end())
362 fReferenceMap.erase(it);
363 int32 newCount = fReferenceMap.size();
364 CHK(fMyMap.Remove(key) == oldCount - newCount);
365 Check();
366 }
367
Erase(const Iterator & iterator)368 Iterator Erase(const Iterator &iterator)
369 {
370 bool outOfRange
371 = (iterator.fReferenceIterator == fReferenceMap.end());
372 MyIterator myIt = fMyMap.Erase(iterator.fMyIterator);
373 if (outOfRange) {
374 CHK(myIt == fMyMap.Null());
375 return Iterator(this, myIt, fReferenceMap.end());
376 }
377 Key nextKey;
378 ReferenceIterator refIt = iterator.fReferenceIterator;
379 ++refIt;
380 bool noNextEntry = (refIt == fReferenceMap.end());
381 if (!noNextEntry)
382 nextKey = refIt->first;
383 fReferenceMap.erase(iterator.fReferenceIterator);
384 if (noNextEntry)
385 refIt = fReferenceMap.end();
386 else
387 refIt = fReferenceMap.find(nextKey);
388 Check();
389 if (refIt == fReferenceMap.end())
390 CHK(myIt == fMyMap.End());
391 else {
392 CHK(myIt->Key() == refIt->first);
393 CHK(myIt->Value() == refIt->second);
394 }
395 return Iterator(this, myIt, refIt);
396 }
397
Count()398 inline int32 Count() const
399 {
400 int32 count = fReferenceMap.size();
401 CHK(fMyMap.Count() == count);
402 return count;
403 }
404
IsEmpty()405 inline bool IsEmpty() const
406 {
407 bool result = fReferenceMap.empty();
408 CHK(fMyMap.IsEmpty() == result);
409 return result;
410 }
411
MakeEmpty()412 void MakeEmpty()
413 {
414 fMyMap.MakeEmpty();
415 fReferenceMap.clear();
416 Check();
417 }
418
Begin()419 inline Iterator Begin()
420 {
421 return Iterator(this, fMyMap.Begin(), fReferenceMap.begin());
422 }
423
Begin()424 inline ConstIterator Begin() const
425 {
426 return ConstIterator(this, fMyMap.Begin(),
427 fReferenceMap.begin());
428 }
429
End()430 inline Iterator End()
431 {
432 return Iterator(this, fMyMap.End(), fReferenceMap.end());
433 }
434
End()435 inline ConstIterator End() const
436 {
437 return ConstIterator(this, fMyMap.End(), fReferenceMap.end());
438 }
439
Null()440 inline Iterator Null()
441 {
442 return Iterator(this, fMyMap.Null(), fReferenceMap.end());
443 }
444
Null()445 inline ConstIterator Null() const
446 {
447 return ConstIterator(this, fMyMap.Null(), fReferenceMap.end());
448 }
449
450 // for testing only
IteratorForIndex(int32 index)451 inline Iterator IteratorForIndex(int32 index)
452 {
453 if (index < 0 || index > Count())
454 return End();
455 MyIterator myIt = fMyMap.Begin();
456 ReferenceIterator refIt = fReferenceMap.begin();
457 for (int32 i = 0; i < index; i++) {
458 ++myIt;
459 ++refIt;
460 }
461 return Iterator(this, myIt, refIt);
462 }
463
464 // for testing only
IteratorForIndex(int32 index)465 inline ConstIterator IteratorForIndex(int32 index) const
466 {
467 if (index < 0 || index > Count())
468 return End();
469 MyConstIterator myIt = fMyMap.Begin();
470 ReferenceConstIterator refIt = fReferenceMap.begin();
471 for (int32 i = 0; i < index; i++) {
472 ++myIt;
473 ++refIt;
474 }
475 return ConstIterator(this, myIt, refIt);
476 }
477
Find(const Key & key)478 Iterator Find(const Key &key)
479 {
480 MyIterator myIt = fMyMap.Find(key);
481 ReferenceIterator refIt = fReferenceMap.find(key);
482 if (refIt == fReferenceMap.end())
483 CHK(myIt = fMyMap.End());
484 else {
485 CHK(myIt->Key() == refIt->first);
486 CHK(myIt->Value() == refIt->second);
487 }
488 return Iterator(this, myIt, refIt);
489 }
490
Find(const Key & key)491 ConstIterator Find(const Key &key) const
492 {
493 MyConstIterator myIt = fMyMap.Find(key);
494 ReferenceConstIterator refIt = fReferenceMap.find(key);
495 if (refIt == fReferenceMap.end())
496 CHK(myIt = fMyMap.End());
497 else {
498 CHK(myIt->Key() == refIt->first);
499 CHK(myIt->Value() == refIt->second);
500 }
501 return ConstIterator(this, myIt, refIt);
502 }
503
FindClose(const Key & key,bool less)504 Iterator FindClose(const Key &key, bool less)
505 {
506 MyIterator myIt = fMyMap.FindClose(key, less);
507 if (myIt == fMyMap.End()) {
508 if (fMyMap.Count() > 0) {
509 if (less)
510 CHK(fCompare(fMyMap.Begin()->Key(), key) > 0);
511 else
512 CHK(fCompare((--MyIterator(myIt))->Key(), key) < 0);
513 }
514 return End();
515 }
516 if (less) {
517 CHK(fCompare(myIt->Key(), key) <= 0);
518 MyIterator nextMyIt(myIt);
519 ++nextMyIt;
520 if (nextMyIt != fMyMap.End())
521 CHK(fCompare(nextMyIt->Key(), key) > 0);
522 } else {
523 CHK(fCompare(myIt->Key(), key) >= 0);
524 if (myIt != fMyMap.Begin()) {
525 MyIterator prevMyIt(myIt);
526 --prevMyIt;
527 CHK(fCompare(prevMyIt->Key(), key) < 0);
528 }
529 }
530 return Iterator(this, myIt, fReferenceMap.find(myIt->Key()));
531 }
532
FindClose(const Key & key,bool less)533 ConstIterator FindClose(const Key &key, bool less) const
534 {
535 MyConstIterator myIt = fMyMap.FindClose(key, less);
536 if (myIt == fMyMap.End()) {
537 if (fMyMap.Count() > 0) {
538 if (less)
539 CHK(fCompare(fMyMap.Begin()->Key(), key) > 0);
540 else
541 CHK(fCompare((--MyConstIterator(myIt))->Key(), key) < 0);
542 }
543 return End();
544 }
545 if (less) {
546 CHK(fCompare(myIt->Key(), key) <= 0);
547 MyConstIterator nextMyIt(myIt);
548 ++nextMyIt;
549 if (nextMyIt != fMyMap.End())
550 CHK(fCompare(nextMyIt->Key(), key) > 0);
551 } else {
552 CHK(fCompare(myIt->Key(), key) >= 0);
553 if (myIt != fMyMap.Begin()) {
554 MyConstIterator prevMyIt(myIt);
555 --prevMyIt;
556 CHK(fCompare(prevMyIt->Key(), key) < 0);
557 }
558 }
559 return ConstIterator(this, myIt, fReferenceMap.find(myIt->Key()));
560 }
561
SetChecking(bool enable)562 void SetChecking(bool enable)
563 {
564 fChecking = enable;
565 }
566
Check()567 void Check() const
568 {
569 if (fChecking) {
570 int32 count = fReferenceMap.size();
571 CHK(fMyMap.Count() == count);
572 CHK(fMyMap.IsEmpty() == fReferenceMap.empty());
573 MyConstIterator myIt = fMyMap.Begin();
574 ReferenceConstIterator refIt = fReferenceMap.begin();
575 for (int32 i = 0; i < count; i++, ++myIt, ++refIt) {
576 CHK(myIt->Key() == refIt->first);
577 CHK(myIt->Value() == refIt->second);
578 CHK((*myIt).Key() == refIt->first);
579 CHK((*myIt).Value() == refIt->second);
580 }
581 CHK(myIt == fMyMap.End());
582 }
583 }
584
585 //private:
586 public:
587 MyMap fMyMap;
588 ReferenceMap fReferenceMap;
589 bool fChecking;
590 Compare fCompare;
591 };
592
593
594 // TestStrategy
595 template<template <typename> class _MyMap, typename _EntryStrategy,
596 // template<typename> class _CompareStrategy>
597 class CompareStrategyWrapper>
598 class TestStrategy {
599 public:
600 typedef _EntryStrategy EntryStrategy;
601 typedef typename EntryStrategy::KeyStrategy KeyStrategy;
602 typedef typename EntryStrategy::ValueStrategy ValueStrategy;
603 typedef typename KeyStrategy::Value Key;
604 typedef typename ValueStrategy::Value Value;
605 // typedef _CompareStrategy<Key> Compare;
606 typedef typename CompareStrategyWrapper::template Strategy<Key> Compare;
607 typedef CompareWrapper<Key, Compare> BoolCompare;
608 typedef _MyMap<Compare> MyMap;
609 typedef map<Key, Value, BoolCompare> ReferenceMap;
610 typedef TestMap<Key, Value, MyMap, ReferenceMap, Compare> TestClass;
611 };
612
613
614 // constructor
615 _ORDERED_MAP_TEST_TEMPLATE_LIST
OrderedMapTest(std::string name)616 _ORDERED_MAP_TEST_CLASS_NAME::OrderedMapTest(std::string name)
617 : BTestCase(name)
618 {
619 }
620
621
622 #define ADD_ORDERED_MAP_TEST(suitename, funcname) \
623 (suitename)->addTest(new TestCaller<OrderedMapTest>( \
624 (string(TestStrategy<Ascending>::kClassName) \
625 + "::" + #funcname), \
626 &OrderedMapTest::funcname));
627
628
629 // Suite
630 _ORDERED_MAP_TEST_TEMPLATE_LIST
631 CppUnit::Test*
Suite()632 _ORDERED_MAP_TEST_CLASS_NAME::Suite()
633 {
634 CppUnit::TestSuite *suite = new CppUnit::TestSuite("OrderedMap");
635
636 ADD_ORDERED_MAP_TEST(suite, ConstructorTest);
637 ADD_ORDERED_MAP_TEST(suite, InsertTest);
638 ADD_ORDERED_MAP_TEST(suite, PutTest);
639 ADD_ORDERED_MAP_TEST(suite, GetTest);
640 ADD_ORDERED_MAP_TEST(suite, RemoveTest);
641 ADD_ORDERED_MAP_TEST(suite, EraseTest);
642 ADD_ORDERED_MAP_TEST(suite, MakeEmptyTest);
643 ADD_ORDERED_MAP_TEST(suite, FindTest);
644 ADD_ORDERED_MAP_TEST(suite, FindCloseTest);
645 ADD_ORDERED_MAP_TEST(suite, IteratorTest);
646
647 return suite;
648 }
649
650 //! ConstructorTest
651 _ORDERED_MAP_TEST_TEMPLATE_LIST
652 void
ConstructorTest()653 _ORDERED_MAP_TEST_CLASS_NAME::ConstructorTest()
654 {
655 typedef typename TestStrategy<Ascending>::MyMap MyMap;
656 NextSubTest();
657 MyMap v1;
658 CHK(v1.Count() == 0);
659 CHK(v1.IsEmpty());
660 }
661
662 // GenericInsertTest
663 template<typename _TestStrategy>
664 static
665 void
GenericInsertTest(int32 maxNumber)666 GenericInsertTest(int32 maxNumber)
667 {
668 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
669 typedef typename _TestStrategy::Key Key;
670 typedef typename _TestStrategy::Value Value;
671 typedef typename _TestStrategy::TestClass TestClass;
672 EntryStrategy entryStrategy;
673 TestClass v;
674 for (int32 i = 0; i < maxNumber; i++) {
675 Key key;
676 Value value;
677 entryStrategy.Generate(key, value);
678 v.Insert(key, value);
679 }
680 }
681
682 // GenericInsertTest
683 template<typename _TestStrategy>
684 static
685 void
GenericInsertTest()686 GenericInsertTest()
687 {
688 GenericInsertTest<_TestStrategy>(30);
689 GenericInsertTest<_TestStrategy>(200);
690 }
691
692 // InsertTest
693 _ORDERED_MAP_TEST_TEMPLATE_LIST
694 void
InsertTest()695 _ORDERED_MAP_TEST_CLASS_NAME::InsertTest()
696 {
697 NextSubTest();
698 GenericInsertTest<TestStrategy<Ascending> >();
699 NextSubTest();
700 GenericInsertTest<TestStrategy<Descending> >();
701 }
702
703 // GenericPutTest
704 template<typename _TestStrategy>
705 static
706 void
GenericPutTest(int32 maxNumber)707 GenericPutTest(int32 maxNumber)
708 {
709 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
710 typedef typename _TestStrategy::Key Key;
711 typedef typename _TestStrategy::Value Value;
712 typedef typename _TestStrategy::TestClass TestClass;
713 EntryStrategy entryStrategy;
714 TestClass v;
715 for (int32 i = 0; i < maxNumber; i++) {
716 Key key;
717 Value value;
718 entryStrategy.Generate(key, value);
719 v.Put(key, value);
720 }
721 }
722
723 // GenericPutTest
724 template<typename _TestStrategy>
725 static
726 void
GenericPutTest()727 GenericPutTest()
728 {
729 GenericPutTest<_TestStrategy>(30);
730 GenericPutTest<_TestStrategy>(200);
731 }
732
733 // PutTest
734 _ORDERED_MAP_TEST_TEMPLATE_LIST
735 void
PutTest()736 _ORDERED_MAP_TEST_CLASS_NAME::PutTest()
737 {
738 NextSubTest();
739 GenericPutTest<TestStrategy<Ascending> >();
740 NextSubTest();
741 GenericPutTest<TestStrategy<Descending> >();
742 }
743
744 // GenericGetTest
745 template<typename _TestStrategy>
746 static
747 void
GenericGetTest(int32 maxNumber)748 GenericGetTest(int32 maxNumber)
749 {
750 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
751 typedef typename _TestStrategy::Key Key;
752 typedef typename _TestStrategy::Value Value;
753 typedef typename _TestStrategy::TestClass TestClass;
754 typedef typename TestClass::Iterator Iterator;
755 EntryStrategy entryStrategy;
756 TestClass v;
757 GenericFill(v, entryStrategy, maxNumber);
758 const TestClass &cv = v;
759 // find the keys in the map
760 for (int32 i = 0; i < maxNumber; i++) {
761 Iterator it = v.IteratorForIndex(i);
762 Key key = it->Key();
763 const Value &value = it->Value();
764 CHK(&v.Get(key) == &value);
765 CHK(&cv.Get(key) == &value);
766 }
767 }
768
769 // GenericGetTest
770 template<typename _TestStrategy>
771 static
772 void
GenericGetTest()773 GenericGetTest()
774 {
775 GenericGetTest<_TestStrategy>(30);
776 GenericGetTest<_TestStrategy>(200);
777 }
778
779 // GetTest
780 _ORDERED_MAP_TEST_TEMPLATE_LIST
781 void
GetTest()782 _ORDERED_MAP_TEST_CLASS_NAME::GetTest()
783 {
784 NextSubTest();
785 GenericGetTest<TestStrategy<Ascending> >();
786 NextSubTest();
787 GenericGetTest<TestStrategy<Descending> >();
788 }
789
790 // GenericFill
791 template<typename TestClass, typename EntryStrategy>
792 static
793 void
GenericFill(TestClass & v,EntryStrategy strategy,int32 maxNumber)794 GenericFill(TestClass &v, EntryStrategy strategy, int32 maxNumber)
795 {
796 typedef typename EntryStrategy::Key Key;
797 typedef typename EntryStrategy::Value Value;
798 v.SetChecking(false);
799 for (int32 i = 0; v.Count() < maxNumber; i++) {
800 Key key;
801 Value value;
802 strategy.Generate(key, value);
803 v.Put(key, value);
804 }
805 v.SetChecking(true);
806 v.Check();
807 }
808
809 // GenericRemoveTest
810 template<typename _TestStrategy>
811 static
812 void
GenericRemoveTest(int32 maxNumber)813 GenericRemoveTest(int32 maxNumber)
814 {
815 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
816 typedef typename _TestStrategy::Key Key;
817 typedef typename _TestStrategy::TestClass TestClass;
818 EntryStrategy entryStrategy;
819 TestClass v;
820 GenericFill(v, entryStrategy, maxNumber);
821 while (v.Count() > 0) {
822 int32 index = rand() % (v.Count());
823 Key key = v.IteratorForIndex(index)->Key();
824 v.Remove(key);
825 v.Remove(key);
826 }
827 }
828
829 // GenericRemoveTest
830 template<typename _TestStrategy>
831 static
832 void
GenericRemoveTest()833 GenericRemoveTest()
834 {
835 GenericRemoveTest<_TestStrategy>(30);
836 GenericRemoveTest<_TestStrategy>(200);
837 }
838
839 // RemoveTest
840 _ORDERED_MAP_TEST_TEMPLATE_LIST
841 void
RemoveTest()842 _ORDERED_MAP_TEST_CLASS_NAME::RemoveTest()
843 {
844 NextSubTest();
845 GenericRemoveTest<TestStrategy<Ascending> >();
846 NextSubTest();
847 GenericRemoveTest<TestStrategy<Descending> >();
848 }
849
850 // GenericEraseTest
851 template<typename _TestStrategy>
852 static
853 void
GenericEraseTest(int32 maxNumber)854 GenericEraseTest(int32 maxNumber)
855 {
856 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
857 typedef typename _TestStrategy::TestClass TestClass;
858 EntryStrategy entryStrategy;
859 TestClass v;
860 GenericFill(v, entryStrategy, maxNumber);
861 for (int32 i = maxNumber - 1; i >= 0; i--) {
862 int32 index = rand() % (i + 1);
863 v.Erase(v.IteratorForIndex(index));
864 }
865 }
866
867 // GenericEraseTest
868 template<typename _TestStrategy>
869 static
870 void
GenericEraseTest()871 GenericEraseTest()
872 {
873 GenericEraseTest<_TestStrategy>(30);
874 GenericEraseTest<_TestStrategy>(200);
875 }
876
877 // EraseTest
878 _ORDERED_MAP_TEST_TEMPLATE_LIST
879 void
EraseTest()880 _ORDERED_MAP_TEST_CLASS_NAME::EraseTest()
881 {
882 NextSubTest();
883 GenericEraseTest<TestStrategy<Ascending> >();
884 NextSubTest();
885 GenericEraseTest<TestStrategy<Descending> >();
886 }
887
888 // GenericMakeEmptyTest
889 template<typename _TestStrategy>
890 static
891 void
GenericMakeEmptyTest(int32 maxNumber)892 GenericMakeEmptyTest(int32 maxNumber)
893 {
894 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
895 typedef typename _TestStrategy::TestClass TestClass;
896 EntryStrategy entryStrategy;
897 TestClass v;
898 v.MakeEmpty();
899 GenericFill(v, entryStrategy, maxNumber);
900 v.MakeEmpty();
901 v.MakeEmpty();
902 }
903
904 // GenericMakeEmptyTest
905 template<typename _TestStrategy>
906 static
907 void
GenericMakeEmptyTest()908 GenericMakeEmptyTest()
909 {
910 GenericMakeEmptyTest<_TestStrategy>(30);
911 GenericMakeEmptyTest<_TestStrategy>(200);
912 }
913
914 // MakeEmptyTest
915 _ORDERED_MAP_TEST_TEMPLATE_LIST
916 void
MakeEmptyTest()917 _ORDERED_MAP_TEST_CLASS_NAME::MakeEmptyTest()
918 {
919 NextSubTest();
920 GenericMakeEmptyTest<TestStrategy<Ascending> >();
921 NextSubTest();
922 GenericMakeEmptyTest<TestStrategy<Descending> >();
923 }
924
925 // GenericFindTest
926 template<typename _TestStrategy>
927 static
928 void
GenericFindTest(int32 maxNumber)929 GenericFindTest(int32 maxNumber)
930 {
931 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
932 typedef typename _TestStrategy::Key Key;
933 typedef typename _TestStrategy::TestClass TestClass;
934 typedef typename TestClass::Iterator Iterator;
935 typedef typename TestClass::ConstIterator ConstIterator;
936 EntryStrategy entryStrategy;
937 TestClass v;
938 GenericFill(v, entryStrategy, maxNumber);
939 const TestClass &cv = v;
940 // find the values in the set
941 for (int32 i = 0; i < maxNumber; i++) {
942 Key key = v.IteratorForIndex(i)->Key();
943 Iterator it = v.Find(key);
944 ConstIterator cit = cv.Find(key);
945 CHK(it->Key() == key);
946 CHK(it->Key() == cit->Key());
947 CHK((*it).Key() == (*it).Key());
948 CHK(&it->Value() == &cit->Value());
949 CHK(&(*it).Value() == &(*it).Value());
950 }
951 // try to find some random values
952 for (int32 i = 0; i < maxNumber; i++) {
953 Key key = v.IteratorForIndex(i)->Key();
954 Iterator it = v.Find(key);
955 ConstIterator cit = cv.Find(key);
956 if (it != v.End()) {
957 CHK(it->Key() == key);
958 CHK(it->Key() == cit->Key());
959 CHK((*it).Key() == (*it).Key());
960 CHK(&it->Value() == &cit->Value());
961 CHK(&(*it).Value() == &(*it).Value());
962 }
963 }
964 }
965
966 // GenericFindTest
967 template<typename _TestStrategy>
968 static
969 void
GenericFindTest()970 GenericFindTest()
971 {
972 GenericFindTest<_TestStrategy>(30);
973 GenericFindTest<_TestStrategy>(200);
974 }
975
976 // FindTest
977 _ORDERED_MAP_TEST_TEMPLATE_LIST
978 void
FindTest()979 _ORDERED_MAP_TEST_CLASS_NAME::FindTest()
980 {
981 NextSubTest();
982 GenericFindTest<TestStrategy<Ascending> >();
983 NextSubTest();
984 GenericFindTest<TestStrategy<Descending> >();
985 }
986
987 // GenericFindCloseTest
988 template<typename _TestStrategy>
989 static
990 void
GenericFindCloseTest(int32 maxNumber)991 GenericFindCloseTest(int32 maxNumber)
992 {
993 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
994 typedef typename _TestStrategy::Key Key;
995 typedef typename _TestStrategy::TestClass TestClass;
996 typedef typename TestClass::Iterator Iterator;
997 typedef typename TestClass::ConstIterator ConstIterator;
998 EntryStrategy entryStrategy;
999 TestClass v;
1000 GenericFill(v, entryStrategy, maxNumber);
1001 const TestClass &cv = v;
1002 // find the values in the set
1003 for (int32 i = 0; i < maxNumber; i++) {
1004 Key key = v.IteratorForIndex(i)->Key();
1005 // less
1006 Iterator it = v.FindClose(key, true);
1007 ConstIterator cit = cv.FindClose(key, true);
1008 CHK(it->Key() == key);
1009 CHK(it->Key() == cit->Key());
1010 CHK((*it).Key() == (*it).Key());
1011 CHK(&it->Value() == &cit->Value());
1012 CHK(&(*it).Value() == &(*it).Value());
1013 // greater
1014 it = v.FindClose(key, false);
1015 cit = cv.FindClose(key, false);
1016 CHK(it->Key() == key);
1017 CHK(it->Key() == cit->Key());
1018 CHK((*it).Key() == (*it).Key());
1019 CHK(&it->Value() == &cit->Value());
1020 CHK(&(*it).Value() == &(*it).Value());
1021 }
1022 // try to find some random values
1023 for (int32 i = 0; i < maxNumber; i++) {
1024 Key key = entryStrategy.GenerateKey();
1025 // less
1026 Iterator it = v.FindClose(key, true);
1027 ConstIterator cit = cv.FindClose(key, true);
1028 if (it != v.End()) {
1029 CHK(it->Key() == cit->Key());
1030 CHK((*it).Key() == (*it).Key());
1031 CHK(&it->Value() == &cit->Value());
1032 CHK(&(*it).Value() == &(*it).Value());
1033 }
1034 // greater
1035 it = v.FindClose(key, false);
1036 cit = cv.FindClose(key, false);
1037 if (it != v.End()) {
1038 CHK(it->Key() == cit->Key());
1039 CHK((*it).Key() == (*it).Key());
1040 CHK(&it->Value() == &cit->Value());
1041 CHK(&(*it).Value() == &(*it).Value());
1042 }
1043 }
1044 }
1045
1046 // GenericFindCloseTest
1047 template<typename _TestStrategy>
1048 static
1049 void
GenericFindCloseTest()1050 GenericFindCloseTest()
1051 {
1052 GenericFindCloseTest<_TestStrategy>(30);
1053 GenericFindCloseTest<_TestStrategy>(200);
1054 }
1055
1056 // FindCloseTest
1057 _ORDERED_MAP_TEST_TEMPLATE_LIST
1058 void
FindCloseTest()1059 _ORDERED_MAP_TEST_CLASS_NAME::FindCloseTest()
1060 {
1061 NextSubTest();
1062 GenericFindCloseTest<TestStrategy<Ascending> >();
1063 NextSubTest();
1064 GenericFindCloseTest<TestStrategy<Descending> >();
1065 }
1066
1067 // GenericIteratorTest
1068 template<typename _TestStrategy>
1069 static
1070 void
GenericIteratorTest(int32 maxNumber)1071 GenericIteratorTest(int32 maxNumber)
1072 {
1073 typedef typename _TestStrategy::EntryStrategy EntryStrategy;
1074 typedef typename _TestStrategy::TestClass TestClass;
1075 typedef typename TestClass::Iterator Iterator;
1076 typedef typename TestClass::ConstIterator ConstIterator;
1077 EntryStrategy entryStrategy;
1078 TestClass v;
1079 GenericFill(v, entryStrategy, maxNumber);
1080 const TestClass &cv = v;
1081 Iterator it = v.Begin();
1082 ConstIterator cit = cv.Begin();
1083 for (; it != v.End(); ++it, ++cit) {
1084 CHK(it->Key() == cit->Key());
1085 CHK(&it->Value() == &cit->Value());
1086 CHK(it->Key() == (*it).Key());
1087 CHK(cit->Key() == (*cit).Key());
1088 CHK(&it->Value() == &(*it).Value());
1089 CHK(&cit->Value() == &(*cit).Value());
1090 CHK(it->Key() == it.operator->().Key());
1091 CHK(&it->Value() == &it.operator->().Value());
1092 CHK(cit->Key() == cit.operator->().Key());
1093 CHK(&cit->Value() == &cit.operator->().Value());
1094 CHK(it);
1095 CHK(cit);
1096 }
1097 CHK(cit == cv.End());
1098 while (it != v.Begin()) {
1099 --it;
1100 --cit;
1101 CHK(it->Key() == cit->Key());
1102 CHK(&it->Value() == &cit->Value());
1103 CHK(it->Key() == (*it).Key());
1104 CHK(cit->Key() == (*cit).Key());
1105 CHK(&it->Value() == &(*it).Value());
1106 CHK(&cit->Value() == &(*cit).Value());
1107 CHK(it->Key() == it.operator->().Key());
1108 CHK(&it->Value() == &it.operator->().Value());
1109 CHK(cit->Key() == cit.operator->().Key());
1110 CHK(&cit->Value() == &cit.operator->().Value());
1111 CHK(it);
1112 CHK(cit);
1113 }
1114 CHK(cit == cv.Begin());
1115 CHK(!v.Null());
1116 CHK(!cv.Null());
1117 }
1118
1119 // GenericIteratorTest
1120 template<typename _TestStrategy>
1121 static
1122 void
GenericIteratorTest()1123 GenericIteratorTest()
1124 {
1125 GenericIteratorTest<_TestStrategy>(30);
1126 GenericIteratorTest<_TestStrategy>(200);
1127 }
1128
1129 // IteratorTest
1130 _ORDERED_MAP_TEST_TEMPLATE_LIST
1131 void
IteratorTest()1132 _ORDERED_MAP_TEST_CLASS_NAME::IteratorTest()
1133 {
1134 NextSubTest();
1135 GenericIteratorTest<TestStrategy<Ascending> >();
1136 NextSubTest();
1137 GenericIteratorTest<TestStrategy<Descending> >();
1138 }
1139
1140 #endif // _ordered_map_test_h_
1141