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