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