xref: /haiku/src/tests/system/kernel/util/OrderedMapTest.h (revision 02354704729d38c3b078c696adc1bbbd33cbcf72) 
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)
62 		: fDifferentValues(differentValues)
63 	{
64 		srand(0);
65 	}
66 
67 	Value Generate();
68 
69 private:
70 	int32	fDifferentValues;
71 };
72 
73 template<>
74 int
75 SimpleValueStrategy<int>::Generate()
76 {
77 	return rand() % fDifferentValues;
78 }
79 
80 template<>
81 string
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 
98 	inline Key GenerateKey()
99 	{
100 		return fKeyStrategy.Generate();
101 	}
102 
103 	inline Value GenerateValue()
104 	{
105 		return fValueStrategy.Generate();
106 	}
107 
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 
128 	inline Key GenerateKey()
129 	{
130 		return fKeyStrategy.Generate();
131 	}
132 
133 	inline Value GenerateValue()
134 	{
135 		return fValueStrategy.Generate();
136 	}
137 
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:
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:
189 	inline TestIterator(TestMap *s, MyIterator myIt, ReferenceIterator refIt)
190 		: fMap(s),
191 		  fMyIterator(myIt),
192 		  fReferenceIterator(refIt)
193 	{
194 	}
195 
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 
322 	TestMap()
323 		: fMyMap(),
324 		  fReferenceMap(),
325 		  fChecking(true)
326 	{
327 	}
328 
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 
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 
343 	Value &Get(const Key &key)
344 	{
345 		Value &value = fMyMap.Get(key);
346 		CHK(value == fReferenceMap[key]);
347 		return value;
348 	}
349 
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 
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 
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 
398 	inline int32 Count() const
399 	{
400 		int32 count = fReferenceMap.size();
401 		CHK(fMyMap.Count() == count);
402 		return count;
403 	}
404 
405 	inline bool IsEmpty() const
406 	{
407 		bool result = fReferenceMap.empty();
408 		CHK(fMyMap.IsEmpty() == result);
409 		return result;
410 	}
411 
412 	void MakeEmpty()
413 	{
414 		fMyMap.MakeEmpty();
415 		fReferenceMap.clear();
416 		Check();
417 	}
418 
419 	inline Iterator Begin()
420 	{
421 		return Iterator(this, fMyMap.Begin(), fReferenceMap.begin());
422 	}
423 
424 	inline ConstIterator Begin() const
425 	{
426 		return ConstIterator(this, fMyMap.Begin(),
427 							 fReferenceMap.begin());
428 	}
429 
430 	inline Iterator End()
431 	{
432 		return Iterator(this, fMyMap.End(), fReferenceMap.end());
433 	}
434 
435 	inline ConstIterator End() const
436 	{
437 		return ConstIterator(this, fMyMap.End(), fReferenceMap.end());
438 	}
439 
440 	inline Iterator Null()
441 	{
442 		return Iterator(this, fMyMap.Null(), fReferenceMap.end());
443 	}
444 
445 	inline ConstIterator Null() const
446 	{
447 		return ConstIterator(this, fMyMap.Null(), fReferenceMap.end());
448 	}
449 
450 	// for testing only
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
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 
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 
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 
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 
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 
562 	void SetChecking(bool enable)
563 	{
564 		fChecking = enable;
565 	}
566 
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
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*
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
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
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
686 GenericInsertTest()
687 {
688 	GenericInsertTest<_TestStrategy>(30);
689 	GenericInsertTest<_TestStrategy>(200);
690 }
691 
692 // InsertTest
693 _ORDERED_MAP_TEST_TEMPLATE_LIST
694 void
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
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
727 GenericPutTest()
728 {
729 	GenericPutTest<_TestStrategy>(30);
730 	GenericPutTest<_TestStrategy>(200);
731 }
732 
733 // PutTest
734 _ORDERED_MAP_TEST_TEMPLATE_LIST
735 void
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
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
773 GenericGetTest()
774 {
775 	GenericGetTest<_TestStrategy>(30);
776 	GenericGetTest<_TestStrategy>(200);
777 }
778 
779 // GetTest
780 _ORDERED_MAP_TEST_TEMPLATE_LIST
781 void
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
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
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
833 GenericRemoveTest()
834 {
835 	GenericRemoveTest<_TestStrategy>(30);
836 	GenericRemoveTest<_TestStrategy>(200);
837 }
838 
839 // RemoveTest
840 _ORDERED_MAP_TEST_TEMPLATE_LIST
841 void
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
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
871 GenericEraseTest()
872 {
873 	GenericEraseTest<_TestStrategy>(30);
874 	GenericEraseTest<_TestStrategy>(200);
875 }
876 
877 // EraseTest
878 _ORDERED_MAP_TEST_TEMPLATE_LIST
879 void
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
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
908 GenericMakeEmptyTest()
909 {
910 	GenericMakeEmptyTest<_TestStrategy>(30);
911 	GenericMakeEmptyTest<_TestStrategy>(200);
912 }
913 
914 // MakeEmptyTest
915 _ORDERED_MAP_TEST_TEMPLATE_LIST
916 void
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
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
970 GenericFindTest()
971 {
972 	GenericFindTest<_TestStrategy>(30);
973 	GenericFindTest<_TestStrategy>(200);
974 }
975 
976 // FindTest
977 _ORDERED_MAP_TEST_TEMPLATE_LIST
978 void
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
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
1050 GenericFindCloseTest()
1051 {
1052 	GenericFindCloseTest<_TestStrategy>(30);
1053 	GenericFindCloseTest<_TestStrategy>(200);
1054 }
1055 
1056 // FindCloseTest
1057 _ORDERED_MAP_TEST_TEMPLATE_LIST
1058 void
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
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
1123 GenericIteratorTest()
1124 {
1125 	GenericIteratorTest<_TestStrategy>(30);
1126 	GenericIteratorTest<_TestStrategy>(200);
1127 }
1128 
1129 // IteratorTest
1130 _ORDERED_MAP_TEST_TEMPLATE_LIST
1131 void
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