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
9using 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>
31template<template<typename CompareWrapperStrategy> class TestStrategy>
32class OrderedMapTest : public BTestCase {
33public:
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
50private:
51	template <class List>
52	void TestList(List &list, typename List::ValueType *values, int valueCount);
53};
54
55// SimpleValueStrategy
56template<typename _Value>
57class SimpleValueStrategy {
58public:
59	typedef _Value	Value;
60
61	SimpleValueStrategy(int32 differentValues = 100000)
62		: fDifferentValues(differentValues)
63	{
64		srand(0);
65	}
66
67	Value Generate();
68
69private:
70	int32	fDifferentValues;
71};
72
73template<>
74int
75SimpleValueStrategy<int>::Generate()
76{
77	return rand() % fDifferentValues;
78}
79
80template<>
81string
82SimpleValueStrategy<string>::Generate()
83{
84	char buffer[10];
85	sprintf(buffer, "%ld", rand() % fDifferentValues);
86	return string(buffer);
87}
88
89// PairEntryStrategy
90template<typename _KeyStrategy, typename _ValueStrategy>
91class PairEntryStrategy {
92public:
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
114private:
115	KeyStrategy		fKeyStrategy;
116	ValueStrategy	fValueStrategy;
117};
118
119// ImplicitKeyStrategy
120template<typename _KeyStrategy, typename _ValueStrategy, typename GetKey>
121class ImplicitKeyStrategy {
122public:
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
144private:
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.
153struct 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.
161struct Descending {
162	template<typename Value>
163	class Strategy : public KernelUtilsOrder::Descending<Value> {};
164};
165
166// CompareWrapper
167template<typename Value, typename Compare>
168class CompareWrapper {
169public:
170	inline bool operator()(const Value &a, const Value &b) const
171	{
172		return (fCompare(a, b) < 0);
173	}
174
175private:
176	Compare	fCompare;
177};
178
179
180// TestIterator
181template<typename Entry, typename TestMap, typename MyIterator,
182		 typename ReferenceIterator>
183class TestIterator {
184private:
185	typedef TestIterator<Entry, TestMap, MyIterator, ReferenceIterator>
186			Iterator;
187
188public:
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
298public:
299	TestMap				*fMap;
300	MyIterator			fMyIterator;
301	ReferenceIterator	fReferenceIterator;
302};
303
304// TestMap
305template<typename Key, typename Value, typename MyMap, typename ReferenceMap,
306		 typename Compare>
307class TestMap {
308public:
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:
586public:
587	MyMap			fMyMap;
588	ReferenceMap	fReferenceMap;
589	bool			fChecking;
590	Compare			fCompare;
591};
592
593
594// TestStrategy
595template<template <typename> class _MyMap, typename _EntryStrategy,
596//		 template<typename> class _CompareStrategy>
597		 class CompareStrategyWrapper>
598class TestStrategy {
599public:
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
631CppUnit::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
652void
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
663template<typename _TestStrategy>
664static
665void
666GenericInsertTest(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
683template<typename _TestStrategy>
684static
685void
686GenericInsertTest()
687{
688	GenericInsertTest<_TestStrategy>(30);
689	GenericInsertTest<_TestStrategy>(200);
690}
691
692// InsertTest
693_ORDERED_MAP_TEST_TEMPLATE_LIST
694void
695_ORDERED_MAP_TEST_CLASS_NAME::InsertTest()
696{
697	NextSubTest();
698	GenericInsertTest<TestStrategy<Ascending> >();
699	NextSubTest();
700	GenericInsertTest<TestStrategy<Descending> >();
701}
702
703// GenericPutTest
704template<typename _TestStrategy>
705static
706void
707GenericPutTest(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
724template<typename _TestStrategy>
725static
726void
727GenericPutTest()
728{
729	GenericPutTest<_TestStrategy>(30);
730	GenericPutTest<_TestStrategy>(200);
731}
732
733// PutTest
734_ORDERED_MAP_TEST_TEMPLATE_LIST
735void
736_ORDERED_MAP_TEST_CLASS_NAME::PutTest()
737{
738	NextSubTest();
739	GenericPutTest<TestStrategy<Ascending> >();
740	NextSubTest();
741	GenericPutTest<TestStrategy<Descending> >();
742}
743
744// GenericGetTest
745template<typename _TestStrategy>
746static
747void
748GenericGetTest(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
770template<typename _TestStrategy>
771static
772void
773GenericGetTest()
774{
775	GenericGetTest<_TestStrategy>(30);
776	GenericGetTest<_TestStrategy>(200);
777}
778
779// GetTest
780_ORDERED_MAP_TEST_TEMPLATE_LIST
781void
782_ORDERED_MAP_TEST_CLASS_NAME::GetTest()
783{
784	NextSubTest();
785	GenericGetTest<TestStrategy<Ascending> >();
786	NextSubTest();
787	GenericGetTest<TestStrategy<Descending> >();
788}
789
790// GenericFill
791template<typename TestClass, typename EntryStrategy>
792static
793void
794GenericFill(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
810template<typename _TestStrategy>
811static
812void
813GenericRemoveTest(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
830template<typename _TestStrategy>
831static
832void
833GenericRemoveTest()
834{
835	GenericRemoveTest<_TestStrategy>(30);
836	GenericRemoveTest<_TestStrategy>(200);
837}
838
839// RemoveTest
840_ORDERED_MAP_TEST_TEMPLATE_LIST
841void
842_ORDERED_MAP_TEST_CLASS_NAME::RemoveTest()
843{
844	NextSubTest();
845	GenericRemoveTest<TestStrategy<Ascending> >();
846	NextSubTest();
847	GenericRemoveTest<TestStrategy<Descending> >();
848}
849
850// GenericEraseTest
851template<typename _TestStrategy>
852static
853void
854GenericEraseTest(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
868template<typename _TestStrategy>
869static
870void
871GenericEraseTest()
872{
873	GenericEraseTest<_TestStrategy>(30);
874	GenericEraseTest<_TestStrategy>(200);
875}
876
877// EraseTest
878_ORDERED_MAP_TEST_TEMPLATE_LIST
879void
880_ORDERED_MAP_TEST_CLASS_NAME::EraseTest()
881{
882	NextSubTest();
883	GenericEraseTest<TestStrategy<Ascending> >();
884	NextSubTest();
885	GenericEraseTest<TestStrategy<Descending> >();
886}
887
888// GenericMakeEmptyTest
889template<typename _TestStrategy>
890static
891void
892GenericMakeEmptyTest(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
905template<typename _TestStrategy>
906static
907void
908GenericMakeEmptyTest()
909{
910	GenericMakeEmptyTest<_TestStrategy>(30);
911	GenericMakeEmptyTest<_TestStrategy>(200);
912}
913
914// MakeEmptyTest
915_ORDERED_MAP_TEST_TEMPLATE_LIST
916void
917_ORDERED_MAP_TEST_CLASS_NAME::MakeEmptyTest()
918{
919	NextSubTest();
920	GenericMakeEmptyTest<TestStrategy<Ascending> >();
921	NextSubTest();
922	GenericMakeEmptyTest<TestStrategy<Descending> >();
923}
924
925// GenericFindTest
926template<typename _TestStrategy>
927static
928void
929GenericFindTest(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
967template<typename _TestStrategy>
968static
969void
970GenericFindTest()
971{
972	GenericFindTest<_TestStrategy>(30);
973	GenericFindTest<_TestStrategy>(200);
974}
975
976// FindTest
977_ORDERED_MAP_TEST_TEMPLATE_LIST
978void
979_ORDERED_MAP_TEST_CLASS_NAME::FindTest()
980{
981	NextSubTest();
982	GenericFindTest<TestStrategy<Ascending> >();
983	NextSubTest();
984	GenericFindTest<TestStrategy<Descending> >();
985}
986
987// GenericFindCloseTest
988template<typename _TestStrategy>
989static
990void
991GenericFindCloseTest(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
1047template<typename _TestStrategy>
1048static
1049void
1050GenericFindCloseTest()
1051{
1052	GenericFindCloseTest<_TestStrategy>(30);
1053	GenericFindCloseTest<_TestStrategy>(200);
1054}
1055
1056// FindCloseTest
1057_ORDERED_MAP_TEST_TEMPLATE_LIST
1058void
1059_ORDERED_MAP_TEST_CLASS_NAME::FindCloseTest()
1060{
1061	NextSubTest();
1062	GenericFindCloseTest<TestStrategy<Ascending> >();
1063	NextSubTest();
1064	GenericFindCloseTest<TestStrategy<Descending> >();
1065}
1066
1067// GenericIteratorTest
1068template<typename _TestStrategy>
1069static
1070void
1071GenericIteratorTest(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
1120template<typename _TestStrategy>
1121static
1122void
1123GenericIteratorTest()
1124{
1125	GenericIteratorTest<_TestStrategy>(30);
1126	GenericIteratorTest<_TestStrategy>(200);
1127}
1128
1129// IteratorTest
1130_ORDERED_MAP_TEST_TEMPLATE_LIST
1131void
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