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