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
VectorTest(std::string name)17 VectorTest::VectorTest(std::string name)
18 : BTestCase(name)
19 {
20 }
21
22 CppUnit::Test*
Suite()23 VectorTest::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
43 void
ConstructorTest1()44 VectorTest::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
58 void
ConstructorTest2()59 VectorTest::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
73 template<typename Value, typename TestVector, typename MyIterator,
74 typename ReferenceIterator>
75 class TestIterator {
76 private:
77 typedef TestIterator<Value, TestVector, MyIterator, ReferenceIterator>
78 Iterator;
79
80 public:
TestIterator(TestVector * vector,MyIterator myIt,ReferenceIterator refIt)81 inline TestIterator(TestVector *vector, MyIterator myIt,
82 ReferenceIterator refIt)
83 : fVector(vector),
84 fMyIterator(myIt),
85 fReferenceIterator(refIt)
86 {
87 }
88
TestIterator(const Iterator & other)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
operator ++()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
operator ++(int)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
operator --()121 inline Iterator &operator--()
122 {
123 MyIterator &myResult = --fMyIterator;
124 ReferenceIterator &refResult = --fReferenceIterator;
125 CHK(*myResult == *refResult);
126 return *this;
127 }
128
operator --(int)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
operator =(const Iterator & other)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
operator ==(const Iterator & other) const148 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
operator !=(const Iterator & other) const155 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
operator *() const162 inline Value &operator*() const
163 {
164 Value &result = *fMyIterator;
165 CHK(result == *fReferenceIterator);
166 return result;
167 }
168
operator ->() const169 inline Value *operator->() const
170 {
171 Value *result = fMyIterator.operator->();
172 CHK(*result == *fReferenceIterator);
173 return result;
174 }
175
operator bool() const176 inline operator bool() const
177 {
178 bool result = fMyIterator;
179 CHK((fMyIterator == fVector->fMyVector.Null()) != result);
180 return result;
181 }
182
183 public:
184 TestVector *fVector;
185 MyIterator fMyIterator;
186 ReferenceIterator fReferenceIterator;
187 };
188
189 // TestVector
190 template<typename Value>
191 class TestVector {
192 public:
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
TestVector()202 TestVector()
203 : fMyVector(),
204 fReferenceVector(),
205 fChecking(true)
206 {
207 }
208
PushFront(const Value & value)209 void PushFront(const Value &value)
210 {
211 CHK(fMyVector.PushFront(value) == B_OK);
212 fReferenceVector.insert(fReferenceVector.begin(), value);
213 Check();
214 }
215
PushBack(const Value & value)216 void PushBack(const Value &value)
217 {
218 CHK(fMyVector.PushBack(value) == B_OK);
219 fReferenceVector.push_back(value);
220 Check();
221 }
222
PopFront()223 void PopFront()
224 {
225 fMyVector.PopFront();
226 fReferenceVector.erase(fReferenceVector.begin());
227 Check();
228 }
229
PopBack()230 void PopBack()
231 {
232 fMyVector.PopBack();
233 fReferenceVector.pop_back();
234 Check();
235 }
236
Insert(const Value & value,int32 index)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
Insert(const Value & value,const Iterator & iterator)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
Remove(const Value & value)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
Erase(int32 index)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
Erase(const Iterator & iterator)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
Count() const319 inline int32 Count() const
320 {
321 int32 count = fReferenceVector.size();
322 CHK(fMyVector.Count() == count);
323 return count;
324 }
325
IsEmpty() const326 inline bool IsEmpty() const
327 {
328 bool result = fReferenceVector.empty();
329 CHK(fMyVector.IsEmpty() == result);
330 return result;
331 }
332
MakeEmpty()333 void MakeEmpty()
334 {
335 fMyVector.MakeEmpty();
336 fReferenceVector.clear();
337 Check();
338 }
339
Begin()340 inline Iterator Begin()
341 {
342 return Iterator(this, fMyVector.Begin(), fReferenceVector.begin());
343 }
344
Begin() const345 inline ConstIterator Begin() const
346 {
347 return ConstIterator(this, fMyVector.Begin(),
348 fReferenceVector.begin());
349 }
350
End()351 inline Iterator End()
352 {
353 return Iterator(this, fMyVector.End(), fReferenceVector.end());
354 }
355
End() const356 inline ConstIterator End() const
357 {
358 return ConstIterator(this, fMyVector.End(), fReferenceVector.end());
359 }
360
Null()361 inline Iterator Null()
362 {
363 return Iterator(this, fMyVector.Null(), fReferenceVector.end());
364 }
365
Null() const366 inline ConstIterator Null() const
367 {
368 return ConstIterator(this, fMyVector.Null(), fReferenceVector.end());
369 }
370
IteratorForIndex(int32 index)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
IteratorForIndex(int32 index) const385 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
ElementAt(int32 index) const399 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
ElementAt(int32 index)406 inline Value &ElementAt(int32 index)
407 {
408 Value &result = fReferenceVector[index];
409 CHK(result == fMyVector.ElementAt(index));
410 return result;
411 }
412
IndexOf(const Value & value,int32 start=0) const413 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
Find(const Value & value)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
Find(const Value & value,const Iterator & _start)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
Find(const Value & value) const472 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
Find(const Value & value,const ConstIterator & _start) const492 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
operator [](int32 index)513 inline Value &operator[](int32 index)
514 {
515 Value &result = fMyVector[index];
516 CHK(result == fReferenceVector[index]);
517 return result;
518 }
519
operator [](int32 index) const520 inline const Value &operator[](int32 index) const
521 {
522 const Value &result = fMyVector[index];
523 CHK(result == fReferenceVector[index]);
524 return result;
525 }
526
SetChecking(bool enable)527 void SetChecking(bool enable)
528 {
529 fChecking = enable;
530 }
531
Check() const532 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:
544 public:
545 Vector<Value> fMyVector;
546 vector<Value> fReferenceVector;
547 bool fChecking;
548 };
549
550 // IntStrategy
551 class IntStrategy {
552 public:
553 typedef int Value;
554
IntStrategy(int32 differentValues=100000)555 IntStrategy(int32 differentValues = 100000)
556 : fDifferentValues(differentValues)
557 {
558 srand(0);
559 }
560
Generate()561 Value Generate()
562 {
563 return rand() % fDifferentValues;
564 }
565
566 private:
567 int32 fDifferentValues;
568 };
569
570 // StringStrategy
571 class StringStrategy {
572 public:
573 typedef string Value;
574
StringStrategy(int32 differentValues=100000)575 StringStrategy(int32 differentValues = 100000)
576 : fDifferentValues(differentValues)
577 {
578 srand(0);
579 }
580
Generate()581 Value Generate()
582 {
583 char buffer[10];
584 sprintf(buffer, "%ld", rand() % fDifferentValues);
585 return string(buffer);
586 }
587
588 private:
589 int32 fDifferentValues;
590 };
591
592 // GenericPushPopFrontTest
593 template<typename ValueStrategy>
594 static
595 void
GenericPushPopFrontTest(ValueStrategy strategy,int32 maxNumber)596 GenericPushPopFrontTest(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
612 void
PushPopFrontTest()613 VectorTest::PushPopFrontTest()
614 {
615 GenericPushPopFrontTest(IntStrategy(), 30);
616 GenericPushPopFrontTest(IntStrategy(), 200);
617 GenericPushPopFrontTest(StringStrategy(), 30);
618 GenericPushPopFrontTest(StringStrategy(), 200);
619 }
620
621 // GenericPushPopBackTest
622 template<typename ValueStrategy>
623 static
624 void
GenericPushPopBackTest(ValueStrategy strategy,int32 maxNumber)625 GenericPushPopBackTest(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
641 void
PushPopBackTest()642 VectorTest::PushPopBackTest()
643 {
644 GenericPushPopBackTest(IntStrategy(), 30);
645 GenericPushPopBackTest(IntStrategy(), 200);
646 GenericPushPopBackTest(StringStrategy(), 30);
647 GenericPushPopBackTest(StringStrategy(), 200);
648 }
649
650 // GenericInsertTest1
651 template<typename ValueStrategy>
652 static
653 void
GenericInsertTest1(ValueStrategy strategy,int32 maxNumber)654 GenericInsertTest1(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
665 template<typename ValueStrategy>
666 static
667 void
GenericInsertTest2(ValueStrategy strategy,int32 maxNumber)668 GenericInsertTest2(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
679 void
InsertTest()680 VectorTest::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
701 template<typename Value, typename ValueStrategy>
702 static
703 void
GenericFill(TestVector<Value> & v,ValueStrategy strategy,int32 maxNumber)704 GenericFill(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
716 template<typename ValueStrategy>
717 static
718 void
GenericRemoveTest(ValueStrategy strategy,int32 maxNumber)719 GenericRemoveTest(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
733 void
RemoveTest()734 VectorTest::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
755 template<typename ValueStrategy>
756 static
757 void
GenericEraseTest1(ValueStrategy strategy,int32 maxNumber)758 GenericEraseTest1(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
770 template<typename ValueStrategy>
771 static
772 void
GenericEraseTest2(ValueStrategy strategy,int32 maxNumber)773 GenericEraseTest2(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
785 void
EraseTest()786 VectorTest::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
807 template<typename ValueStrategy>
808 static
809 void
GenericMakeEmptyTest(ValueStrategy strategy,int32 maxNumber)810 GenericMakeEmptyTest(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
821 void
MakeEmptyTest()822 VectorTest::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
835 template<typename ValueStrategy>
836 static
837 void
GenericIndexAccessTest(ValueStrategy strategy,int32 maxNumber)838 GenericIndexAccessTest(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
851 void
IndexAccessTest()852 VectorTest::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
865 template<typename ValueStrategy>
866 static
867 void
GenericFindTest(ValueStrategy strategy,int32 maxNumber)868 GenericFindTest(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
899 void
FindTest()900 VectorTest::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
921 template<typename ValueStrategy>
922 static
923 void
GenericIteratorTest(ValueStrategy strategy,int32 maxNumber)924 GenericIteratorTest(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
955 void
IteratorTest()956 VectorTest::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