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