1// OrderedMapTest.h 2#ifndef _ordered_map_test_h_ 3#define _ordered_map_test_h_ 4 5#include <map> 6#include <stdio.h> 7#include <stdlib.h> 8 9using std::map; 10 11#include <TestCase.h> 12#include <TestUtils.h> 13#include <cppunit/Test.h> 14#include <cppunit/TestCaller.h> 15#include <cppunit/TestSuite.h> 16 17#include "common.h" 18 19// That's how it should be, but we need to work around compiler bugs 20// (in this case an unimplemented feature). 21/* 22#define _ORDERED_MAP_TEST_TEMPLATE_LIST \ 23 template<template<template<typename> class CompareStrategy> \ 24 class TestStrategy> 25*/ 26#define _ORDERED_MAP_TEST_TEMPLATE_LIST \ 27 template<template<typename> class TestStrategy> 28#define _ORDERED_MAP_TEST_CLASS_NAME OrderedMapTest<TestStrategy> 29 30//template<template<template<typename> class CompareStrategy> class TestStrategy> 31template<template<typename CompareWrapperStrategy> class TestStrategy> 32class OrderedMapTest : public BTestCase { 33public: 34 OrderedMapTest(std::string name = ""); 35 36 static CppUnit::Test* Suite(); 37 38 void ConstructorTest(); 39 void InsertTest(); 40 void PutTest(); 41 void GetTest(); 42 void RemoveTest(); 43 void EraseTest(); 44 void MakeEmptyTest(); 45 void IndexAccessTest(); 46 void FindTest(); 47 void FindCloseTest(); 48 void IteratorTest(); 49 50private: 51 template <class List> 52 void TestList(List &list, typename List::ValueType *values, int valueCount); 53}; 54 55// SimpleValueStrategy 56template<typename _Value> 57class SimpleValueStrategy { 58public: 59 typedef _Value Value; 60 61 SimpleValueStrategy(int32 differentValues = 100000) 62 : fDifferentValues(differentValues) 63 { 64 srand(0); 65 } 66 67 Value Generate(); 68 69private: 70 int32 fDifferentValues; 71}; 72 73template<> 74int 75SimpleValueStrategy<int>::Generate() 76{ 77 return rand() % fDifferentValues; 78} 79 80template<> 81string 82SimpleValueStrategy<string>::Generate() 83{ 84 char buffer[10]; 85 sprintf(buffer, "%ld", rand() % fDifferentValues); 86 return string(buffer); 87} 88 89// PairEntryStrategy 90template<typename _KeyStrategy, typename _ValueStrategy> 91class PairEntryStrategy { 92public: 93 typedef _KeyStrategy KeyStrategy; 94 typedef _ValueStrategy ValueStrategy; 95 typedef typename KeyStrategy::Value Key; 96 typedef typename ValueStrategy::Value Value; 97 98 inline Key GenerateKey() 99 { 100 return fKeyStrategy.Generate(); 101 } 102 103 inline Value GenerateValue() 104 { 105 return fValueStrategy.Generate(); 106 } 107 108 inline void Generate(Key &key, Value &value) 109 { 110 key = GenerateKey(); 111 value = GenerateValue(); 112 } 113 114private: 115 KeyStrategy fKeyStrategy; 116 ValueStrategy fValueStrategy; 117}; 118 119// ImplicitKeyStrategy 120template<typename _KeyStrategy, typename _ValueStrategy, typename GetKey> 121class ImplicitKeyStrategy { 122public: 123 typedef _KeyStrategy KeyStrategy; 124 typedef _ValueStrategy ValueStrategy; 125 typedef typename KeyStrategy::Value Key; 126 typedef typename ValueStrategy::Value Value; 127 128 inline Key GenerateKey() 129 { 130 return fKeyStrategy.Generate(); 131 } 132 133 inline Value GenerateValue() 134 { 135 return fValueStrategy.Generate(); 136 } 137 138 inline void Generate(Key &key, Value &value) 139 { 140 value = GenerateValue(); 141 key = fGetKey(value); 142 } 143 144private: 145 KeyStrategy fKeyStrategy; 146 ValueStrategy fValueStrategy; 147 GetKey fGetKey; 148}; 149 150// Non-template wrapper for the Ascending compare strategy. 151// Work-around for our compiler not eating nested template template 152// parameters. 153struct Ascending { 154 template<typename Value> 155 class Strategy : public KernelUtilsOrder::Ascending<Value> {}; 156}; 157 158// Non-template wrapper for the Descending compare strategy. 159// Work-around for our compiler not eating nested template template 160// parameters. 161struct Descending { 162 template<typename Value> 163 class Strategy : public KernelUtilsOrder::Descending<Value> {}; 164}; 165 166// CompareWrapper 167template<typename Value, typename Compare> 168class CompareWrapper { 169public: 170 inline bool operator()(const Value &a, const Value &b) const 171 { 172 return (fCompare(a, b) < 0); 173 } 174 175private: 176 Compare fCompare; 177}; 178 179 180// TestIterator 181template<typename Entry, typename TestMap, typename MyIterator, 182 typename ReferenceIterator> 183class TestIterator { 184private: 185 typedef TestIterator<Entry, TestMap, MyIterator, ReferenceIterator> 186 Iterator; 187 188public: 189 inline TestIterator(TestMap *s, MyIterator myIt, ReferenceIterator refIt) 190 : fMap(s), 191 fMyIterator(myIt), 192 fReferenceIterator(refIt) 193 { 194 } 195 196 inline TestIterator(const Iterator &other) 197 : fMap(other.fMap), 198 fMyIterator(other.fMyIterator), 199 fReferenceIterator(other.fReferenceIterator) 200 { 201 CHK(fMyIterator == other.fMyIterator); 202 } 203 204 inline Iterator &operator++() 205 { 206 MyIterator &myResult = ++fMyIterator; 207 ReferenceIterator &refResult = ++fReferenceIterator; 208 if (refResult == fMap->fReferenceMap.end()) 209 CHK(myResult == fMap->fMyMap.End()); 210 else { 211 CHK(myResult->Key() == refResult->first); 212 CHK(myResult->Value() == refResult->second); 213 } 214 return *this; 215 } 216 217 inline Iterator operator++(int) 218 { 219 MyIterator oldMyResult = fMyIterator; 220 MyIterator myResult = fMyIterator++; 221 ReferenceIterator refResult = fReferenceIterator++; 222 CHK(oldMyResult == myResult); 223 if (refResult == fMap->fReferenceMap.end()) 224 CHK(myResult == fMap->fMyMap.End()); 225 else { 226 CHK(myResult->Key() == refResult->first); 227 CHK(myResult->Value() == refResult->second); 228 } 229 return Iterator(fMap, myResult, refResult); 230 } 231 232 inline Iterator &operator--() 233 { 234 MyIterator &myResult = --fMyIterator; 235 ReferenceIterator &refResult = --fReferenceIterator; 236 CHK(myResult->Key() == refResult->first); 237 CHK(myResult->Value() == refResult->second); 238 return *this; 239 } 240 241 inline Iterator operator--(int) 242 { 243 MyIterator oldMyResult = fMyIterator; 244 MyIterator myResult = fMyIterator--; 245 ReferenceIterator refResult = fReferenceIterator--; 246 CHK(oldMyResult == myResult); 247 CHK(myResult->Key() == refResult->first); 248 CHK(myResult->Value() == refResult->second); 249 return Iterator(fMap, myResult, refResult); 250 } 251 252 inline Iterator &operator=(const Iterator &other) 253 { 254 fMap = other.fMap; 255 fMyIterator = other.fMyIterator; 256 fReferenceIterator = other.fReferenceIterator; 257 CHK(fMyIterator == other.fMyIterator); 258 return *this; 259 } 260 261 inline bool operator==(const Iterator &other) const 262 { 263 bool result = (fMyIterator == other.fMyIterator); 264 CHK((fReferenceIterator == other.fReferenceIterator) == result); 265 return result; 266 } 267 268 inline bool operator!=(const Iterator &other) const 269 { 270 bool result = (fMyIterator != other.fMyIterator); 271 CHK((fReferenceIterator != other.fReferenceIterator) == result); 272 return result; 273 } 274 275 inline Entry operator*() const 276 { 277 Entry entry = *fMyIterator; 278 CHK(entry.Key() == fReferenceIterator->first); 279 CHK(entry.Value() == fReferenceIterator->second); 280 return entry; 281 } 282 283 inline Entry operator->() const 284 { 285 Entry entry = fMyIterator.operator->(); 286 CHK(entry.Key() == fReferenceIterator->first); 287 CHK(entry.Value() == fReferenceIterator->second); 288 return entry; 289 } 290 291 inline operator bool() const 292 { 293 bool result = fMyIterator; 294 CHK((fMyIterator == fMap->fMyMap.Null()) != result); 295 return result; 296 } 297 298public: 299 TestMap *fMap; 300 MyIterator fMyIterator; 301 ReferenceIterator fReferenceIterator; 302}; 303 304// TestMap 305template<typename Key, typename Value, typename MyMap, typename ReferenceMap, 306 typename Compare> 307class TestMap { 308public: 309 typedef TestMap<Key, Value, MyMap, ReferenceMap, Compare> Class; 310 311 typedef typename MyMap::Iterator MyIterator; 312 typedef typename ReferenceMap::iterator ReferenceIterator; 313 typedef typename MyMap::ConstIterator MyConstIterator; 314 typedef typename ReferenceMap::const_iterator ReferenceConstIterator; 315 typedef typename MyMap::Entry Entry; 316 typedef typename MyMap::ConstEntry ConstEntry; 317 typedef TestIterator<Entry, Class, MyIterator, 318 ReferenceIterator> Iterator; 319 typedef TestIterator<ConstEntry, const Class, MyConstIterator, 320 ReferenceConstIterator> ConstIterator; 321 322 TestMap() 323 : fMyMap(), 324 fReferenceMap(), 325 fChecking(true) 326 { 327 } 328 329 void Insert(const Key &key, const Value &value) 330 { 331 CHK(fMyMap.Insert(key, value) == B_OK); 332 fReferenceMap[key] = value; 333 Check(); 334 } 335 336 void Put(const Key &key, const Value &value) 337 { 338 CHK(fMyMap.Put(key, value) == B_OK); 339 fReferenceMap[key] = value; 340 Check(); 341 } 342 343 Value &Get(const Key &key) 344 { 345 Value &value = fMyMap.Get(key); 346 CHK(value == fReferenceMap[key]); 347 return value; 348 } 349 350 const Value &Get(const Key &key) const 351 { 352 const Value &value = fMyMap.Get(key); 353 CHK(value == fReferenceMap.find(key)->second); 354 return value; 355 } 356 357 void Remove(const Key &key) 358 { 359 int32 oldCount = Count(); 360 ReferenceIterator it = fReferenceMap.find(key); 361 if (it != fReferenceMap.end()) 362 fReferenceMap.erase(it); 363 int32 newCount = fReferenceMap.size(); 364 CHK(fMyMap.Remove(key) == oldCount - newCount); 365 Check(); 366 } 367 368 Iterator Erase(const Iterator &iterator) 369 { 370 bool outOfRange 371 = (iterator.fReferenceIterator == fReferenceMap.end()); 372 MyIterator myIt = fMyMap.Erase(iterator.fMyIterator); 373 if (outOfRange) { 374 CHK(myIt == fMyMap.Null()); 375 return Iterator(this, myIt, fReferenceMap.end()); 376 } 377 Key nextKey; 378 ReferenceIterator refIt = iterator.fReferenceIterator; 379 ++refIt; 380 bool noNextEntry = (refIt == fReferenceMap.end()); 381 if (!noNextEntry) 382 nextKey = refIt->first; 383 fReferenceMap.erase(iterator.fReferenceIterator); 384 if (noNextEntry) 385 refIt = fReferenceMap.end(); 386 else 387 refIt = fReferenceMap.find(nextKey); 388 Check(); 389 if (refIt == fReferenceMap.end()) 390 CHK(myIt == fMyMap.End()); 391 else { 392 CHK(myIt->Key() == refIt->first); 393 CHK(myIt->Value() == refIt->second); 394 } 395 return Iterator(this, myIt, refIt); 396 } 397 398 inline int32 Count() const 399 { 400 int32 count = fReferenceMap.size(); 401 CHK(fMyMap.Count() == count); 402 return count; 403 } 404 405 inline bool IsEmpty() const 406 { 407 bool result = fReferenceMap.empty(); 408 CHK(fMyMap.IsEmpty() == result); 409 return result; 410 } 411 412 void MakeEmpty() 413 { 414 fMyMap.MakeEmpty(); 415 fReferenceMap.clear(); 416 Check(); 417 } 418 419 inline Iterator Begin() 420 { 421 return Iterator(this, fMyMap.Begin(), fReferenceMap.begin()); 422 } 423 424 inline ConstIterator Begin() const 425 { 426 return ConstIterator(this, fMyMap.Begin(), 427 fReferenceMap.begin()); 428 } 429 430 inline Iterator End() 431 { 432 return Iterator(this, fMyMap.End(), fReferenceMap.end()); 433 } 434 435 inline ConstIterator End() const 436 { 437 return ConstIterator(this, fMyMap.End(), fReferenceMap.end()); 438 } 439 440 inline Iterator Null() 441 { 442 return Iterator(this, fMyMap.Null(), fReferenceMap.end()); 443 } 444 445 inline ConstIterator Null() const 446 { 447 return ConstIterator(this, fMyMap.Null(), fReferenceMap.end()); 448 } 449 450 // for testing only 451 inline Iterator IteratorForIndex(int32 index) 452 { 453 if (index < 0 || index > Count()) 454 return End(); 455 MyIterator myIt = fMyMap.Begin(); 456 ReferenceIterator refIt = fReferenceMap.begin(); 457 for (int32 i = 0; i < index; i++) { 458 ++myIt; 459 ++refIt; 460 } 461 return Iterator(this, myIt, refIt); 462 } 463 464 // for testing only 465 inline ConstIterator IteratorForIndex(int32 index) const 466 { 467 if (index < 0 || index > Count()) 468 return End(); 469 MyConstIterator myIt = fMyMap.Begin(); 470 ReferenceConstIterator refIt = fReferenceMap.begin(); 471 for (int32 i = 0; i < index; i++) { 472 ++myIt; 473 ++refIt; 474 } 475 return ConstIterator(this, myIt, refIt); 476 } 477 478 Iterator Find(const Key &key) 479 { 480 MyIterator myIt = fMyMap.Find(key); 481 ReferenceIterator refIt = fReferenceMap.find(key); 482 if (refIt == fReferenceMap.end()) 483 CHK(myIt = fMyMap.End()); 484 else { 485 CHK(myIt->Key() == refIt->first); 486 CHK(myIt->Value() == refIt->second); 487 } 488 return Iterator(this, myIt, refIt); 489 } 490 491 ConstIterator Find(const Key &key) const 492 { 493 MyConstIterator myIt = fMyMap.Find(key); 494 ReferenceConstIterator refIt = fReferenceMap.find(key); 495 if (refIt == fReferenceMap.end()) 496 CHK(myIt = fMyMap.End()); 497 else { 498 CHK(myIt->Key() == refIt->first); 499 CHK(myIt->Value() == refIt->second); 500 } 501 return ConstIterator(this, myIt, refIt); 502 } 503 504 Iterator FindClose(const Key &key, bool less) 505 { 506 MyIterator myIt = fMyMap.FindClose(key, less); 507 if (myIt == fMyMap.End()) { 508 if (fMyMap.Count() > 0) { 509 if (less) 510 CHK(fCompare(fMyMap.Begin()->Key(), key) > 0); 511 else 512 CHK(fCompare((--MyIterator(myIt))->Key(), key) < 0); 513 } 514 return End(); 515 } 516 if (less) { 517 CHK(fCompare(myIt->Key(), key) <= 0); 518 MyIterator nextMyIt(myIt); 519 ++nextMyIt; 520 if (nextMyIt != fMyMap.End()) 521 CHK(fCompare(nextMyIt->Key(), key) > 0); 522 } else { 523 CHK(fCompare(myIt->Key(), key) >= 0); 524 if (myIt != fMyMap.Begin()) { 525 MyIterator prevMyIt(myIt); 526 --prevMyIt; 527 CHK(fCompare(prevMyIt->Key(), key) < 0); 528 } 529 } 530 return Iterator(this, myIt, fReferenceMap.find(myIt->Key())); 531 } 532 533 ConstIterator FindClose(const Key &key, bool less) const 534 { 535 MyConstIterator myIt = fMyMap.FindClose(key, less); 536 if (myIt == fMyMap.End()) { 537 if (fMyMap.Count() > 0) { 538 if (less) 539 CHK(fCompare(fMyMap.Begin()->Key(), key) > 0); 540 else 541 CHK(fCompare((--MyConstIterator(myIt))->Key(), key) < 0); 542 } 543 return End(); 544 } 545 if (less) { 546 CHK(fCompare(myIt->Key(), key) <= 0); 547 MyConstIterator nextMyIt(myIt); 548 ++nextMyIt; 549 if (nextMyIt != fMyMap.End()) 550 CHK(fCompare(nextMyIt->Key(), key) > 0); 551 } else { 552 CHK(fCompare(myIt->Key(), key) >= 0); 553 if (myIt != fMyMap.Begin()) { 554 MyConstIterator prevMyIt(myIt); 555 --prevMyIt; 556 CHK(fCompare(prevMyIt->Key(), key) < 0); 557 } 558 } 559 return ConstIterator(this, myIt, fReferenceMap.find(myIt->Key())); 560 } 561 562 void SetChecking(bool enable) 563 { 564 fChecking = enable; 565 } 566 567 void Check() const 568 { 569 if (fChecking) { 570 int32 count = fReferenceMap.size(); 571 CHK(fMyMap.Count() == count); 572 CHK(fMyMap.IsEmpty() == fReferenceMap.empty()); 573 MyConstIterator myIt = fMyMap.Begin(); 574 ReferenceConstIterator refIt = fReferenceMap.begin(); 575 for (int32 i = 0; i < count; i++, ++myIt, ++refIt) { 576 CHK(myIt->Key() == refIt->first); 577 CHK(myIt->Value() == refIt->second); 578 CHK((*myIt).Key() == refIt->first); 579 CHK((*myIt).Value() == refIt->second); 580 } 581 CHK(myIt == fMyMap.End()); 582 } 583 } 584 585//private: 586public: 587 MyMap fMyMap; 588 ReferenceMap fReferenceMap; 589 bool fChecking; 590 Compare fCompare; 591}; 592 593 594// TestStrategy 595template<template <typename> class _MyMap, typename _EntryStrategy, 596// template<typename> class _CompareStrategy> 597 class CompareStrategyWrapper> 598class TestStrategy { 599public: 600 typedef _EntryStrategy EntryStrategy; 601 typedef typename EntryStrategy::KeyStrategy KeyStrategy; 602 typedef typename EntryStrategy::ValueStrategy ValueStrategy; 603 typedef typename KeyStrategy::Value Key; 604 typedef typename ValueStrategy::Value Value; 605// typedef _CompareStrategy<Key> Compare; 606 typedef typename CompareStrategyWrapper::template Strategy<Key> Compare; 607 typedef CompareWrapper<Key, Compare> BoolCompare; 608 typedef _MyMap<Compare> MyMap; 609 typedef map<Key, Value, BoolCompare> ReferenceMap; 610 typedef TestMap<Key, Value, MyMap, ReferenceMap, Compare> TestClass; 611}; 612 613 614// constructor 615_ORDERED_MAP_TEST_TEMPLATE_LIST 616_ORDERED_MAP_TEST_CLASS_NAME::OrderedMapTest(std::string name) 617 : BTestCase(name) 618{ 619} 620 621 622#define ADD_ORDERED_MAP_TEST(suitename, funcname) \ 623 (suitename)->addTest(new TestCaller<OrderedMapTest>( \ 624 (string(TestStrategy<Ascending>::kClassName) \ 625 + "::" + #funcname), \ 626 &OrderedMapTest::funcname)); 627 628 629// Suite 630_ORDERED_MAP_TEST_TEMPLATE_LIST 631CppUnit::Test* 632_ORDERED_MAP_TEST_CLASS_NAME::Suite() 633{ 634 CppUnit::TestSuite *suite = new CppUnit::TestSuite("OrderedMap"); 635 636 ADD_ORDERED_MAP_TEST(suite, ConstructorTest); 637 ADD_ORDERED_MAP_TEST(suite, InsertTest); 638 ADD_ORDERED_MAP_TEST(suite, PutTest); 639 ADD_ORDERED_MAP_TEST(suite, GetTest); 640 ADD_ORDERED_MAP_TEST(suite, RemoveTest); 641 ADD_ORDERED_MAP_TEST(suite, EraseTest); 642 ADD_ORDERED_MAP_TEST(suite, MakeEmptyTest); 643 ADD_ORDERED_MAP_TEST(suite, FindTest); 644 ADD_ORDERED_MAP_TEST(suite, FindCloseTest); 645 ADD_ORDERED_MAP_TEST(suite, IteratorTest); 646 647 return suite; 648} 649 650//! ConstructorTest 651_ORDERED_MAP_TEST_TEMPLATE_LIST 652void 653_ORDERED_MAP_TEST_CLASS_NAME::ConstructorTest() 654{ 655 typedef typename TestStrategy<Ascending>::MyMap MyMap; 656 NextSubTest(); 657 MyMap v1; 658 CHK(v1.Count() == 0); 659 CHK(v1.IsEmpty()); 660} 661 662// GenericInsertTest 663template<typename _TestStrategy> 664static 665void 666GenericInsertTest(int32 maxNumber) 667{ 668 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 669 typedef typename _TestStrategy::Key Key; 670 typedef typename _TestStrategy::Value Value; 671 typedef typename _TestStrategy::TestClass TestClass; 672 EntryStrategy entryStrategy; 673 TestClass v; 674 for (int32 i = 0; i < maxNumber; i++) { 675 Key key; 676 Value value; 677 entryStrategy.Generate(key, value); 678 v.Insert(key, value); 679 } 680} 681 682// GenericInsertTest 683template<typename _TestStrategy> 684static 685void 686GenericInsertTest() 687{ 688 GenericInsertTest<_TestStrategy>(30); 689 GenericInsertTest<_TestStrategy>(200); 690} 691 692// InsertTest 693_ORDERED_MAP_TEST_TEMPLATE_LIST 694void 695_ORDERED_MAP_TEST_CLASS_NAME::InsertTest() 696{ 697 NextSubTest(); 698 GenericInsertTest<TestStrategy<Ascending> >(); 699 NextSubTest(); 700 GenericInsertTest<TestStrategy<Descending> >(); 701} 702 703// GenericPutTest 704template<typename _TestStrategy> 705static 706void 707GenericPutTest(int32 maxNumber) 708{ 709 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 710 typedef typename _TestStrategy::Key Key; 711 typedef typename _TestStrategy::Value Value; 712 typedef typename _TestStrategy::TestClass TestClass; 713 EntryStrategy entryStrategy; 714 TestClass v; 715 for (int32 i = 0; i < maxNumber; i++) { 716 Key key; 717 Value value; 718 entryStrategy.Generate(key, value); 719 v.Put(key, value); 720 } 721} 722 723// GenericPutTest 724template<typename _TestStrategy> 725static 726void 727GenericPutTest() 728{ 729 GenericPutTest<_TestStrategy>(30); 730 GenericPutTest<_TestStrategy>(200); 731} 732 733// PutTest 734_ORDERED_MAP_TEST_TEMPLATE_LIST 735void 736_ORDERED_MAP_TEST_CLASS_NAME::PutTest() 737{ 738 NextSubTest(); 739 GenericPutTest<TestStrategy<Ascending> >(); 740 NextSubTest(); 741 GenericPutTest<TestStrategy<Descending> >(); 742} 743 744// GenericGetTest 745template<typename _TestStrategy> 746static 747void 748GenericGetTest(int32 maxNumber) 749{ 750 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 751 typedef typename _TestStrategy::Key Key; 752 typedef typename _TestStrategy::Value Value; 753 typedef typename _TestStrategy::TestClass TestClass; 754 typedef typename TestClass::Iterator Iterator; 755 EntryStrategy entryStrategy; 756 TestClass v; 757 GenericFill(v, entryStrategy, maxNumber); 758 const TestClass &cv = v; 759 // find the keys in the map 760 for (int32 i = 0; i < maxNumber; i++) { 761 Iterator it = v.IteratorForIndex(i); 762 Key key = it->Key(); 763 const Value &value = it->Value(); 764 CHK(&v.Get(key) == &value); 765 CHK(&cv.Get(key) == &value); 766 } 767} 768 769// GenericGetTest 770template<typename _TestStrategy> 771static 772void 773GenericGetTest() 774{ 775 GenericGetTest<_TestStrategy>(30); 776 GenericGetTest<_TestStrategy>(200); 777} 778 779// GetTest 780_ORDERED_MAP_TEST_TEMPLATE_LIST 781void 782_ORDERED_MAP_TEST_CLASS_NAME::GetTest() 783{ 784 NextSubTest(); 785 GenericGetTest<TestStrategy<Ascending> >(); 786 NextSubTest(); 787 GenericGetTest<TestStrategy<Descending> >(); 788} 789 790// GenericFill 791template<typename TestClass, typename EntryStrategy> 792static 793void 794GenericFill(TestClass &v, EntryStrategy strategy, int32 maxNumber) 795{ 796 typedef typename EntryStrategy::Key Key; 797 typedef typename EntryStrategy::Value Value; 798 v.SetChecking(false); 799 for (int32 i = 0; v.Count() < maxNumber; i++) { 800 Key key; 801 Value value; 802 strategy.Generate(key, value); 803 v.Put(key, value); 804 } 805 v.SetChecking(true); 806 v.Check(); 807} 808 809// GenericRemoveTest 810template<typename _TestStrategy> 811static 812void 813GenericRemoveTest(int32 maxNumber) 814{ 815 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 816 typedef typename _TestStrategy::Key Key; 817 typedef typename _TestStrategy::TestClass TestClass; 818 EntryStrategy entryStrategy; 819 TestClass v; 820 GenericFill(v, entryStrategy, maxNumber); 821 while (v.Count() > 0) { 822 int32 index = rand() % (v.Count()); 823 Key key = v.IteratorForIndex(index)->Key(); 824 v.Remove(key); 825 v.Remove(key); 826 } 827} 828 829// GenericRemoveTest 830template<typename _TestStrategy> 831static 832void 833GenericRemoveTest() 834{ 835 GenericRemoveTest<_TestStrategy>(30); 836 GenericRemoveTest<_TestStrategy>(200); 837} 838 839// RemoveTest 840_ORDERED_MAP_TEST_TEMPLATE_LIST 841void 842_ORDERED_MAP_TEST_CLASS_NAME::RemoveTest() 843{ 844 NextSubTest(); 845 GenericRemoveTest<TestStrategy<Ascending> >(); 846 NextSubTest(); 847 GenericRemoveTest<TestStrategy<Descending> >(); 848} 849 850// GenericEraseTest 851template<typename _TestStrategy> 852static 853void 854GenericEraseTest(int32 maxNumber) 855{ 856 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 857 typedef typename _TestStrategy::TestClass TestClass; 858 EntryStrategy entryStrategy; 859 TestClass v; 860 GenericFill(v, entryStrategy, maxNumber); 861 for (int32 i = maxNumber - 1; i >= 0; i--) { 862 int32 index = rand() % (i + 1); 863 v.Erase(v.IteratorForIndex(index)); 864 } 865} 866 867// GenericEraseTest 868template<typename _TestStrategy> 869static 870void 871GenericEraseTest() 872{ 873 GenericEraseTest<_TestStrategy>(30); 874 GenericEraseTest<_TestStrategy>(200); 875} 876 877// EraseTest 878_ORDERED_MAP_TEST_TEMPLATE_LIST 879void 880_ORDERED_MAP_TEST_CLASS_NAME::EraseTest() 881{ 882 NextSubTest(); 883 GenericEraseTest<TestStrategy<Ascending> >(); 884 NextSubTest(); 885 GenericEraseTest<TestStrategy<Descending> >(); 886} 887 888// GenericMakeEmptyTest 889template<typename _TestStrategy> 890static 891void 892GenericMakeEmptyTest(int32 maxNumber) 893{ 894 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 895 typedef typename _TestStrategy::TestClass TestClass; 896 EntryStrategy entryStrategy; 897 TestClass v; 898 v.MakeEmpty(); 899 GenericFill(v, entryStrategy, maxNumber); 900 v.MakeEmpty(); 901 v.MakeEmpty(); 902} 903 904// GenericMakeEmptyTest 905template<typename _TestStrategy> 906static 907void 908GenericMakeEmptyTest() 909{ 910 GenericMakeEmptyTest<_TestStrategy>(30); 911 GenericMakeEmptyTest<_TestStrategy>(200); 912} 913 914// MakeEmptyTest 915_ORDERED_MAP_TEST_TEMPLATE_LIST 916void 917_ORDERED_MAP_TEST_CLASS_NAME::MakeEmptyTest() 918{ 919 NextSubTest(); 920 GenericMakeEmptyTest<TestStrategy<Ascending> >(); 921 NextSubTest(); 922 GenericMakeEmptyTest<TestStrategy<Descending> >(); 923} 924 925// GenericFindTest 926template<typename _TestStrategy> 927static 928void 929GenericFindTest(int32 maxNumber) 930{ 931 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 932 typedef typename _TestStrategy::Key Key; 933 typedef typename _TestStrategy::TestClass TestClass; 934 typedef typename TestClass::Iterator Iterator; 935 typedef typename TestClass::ConstIterator ConstIterator; 936 EntryStrategy entryStrategy; 937 TestClass v; 938 GenericFill(v, entryStrategy, maxNumber); 939 const TestClass &cv = v; 940 // find the values in the set 941 for (int32 i = 0; i < maxNumber; i++) { 942 Key key = v.IteratorForIndex(i)->Key(); 943 Iterator it = v.Find(key); 944 ConstIterator cit = cv.Find(key); 945 CHK(it->Key() == key); 946 CHK(it->Key() == cit->Key()); 947 CHK((*it).Key() == (*it).Key()); 948 CHK(&it->Value() == &cit->Value()); 949 CHK(&(*it).Value() == &(*it).Value()); 950 } 951 // try to find some random values 952 for (int32 i = 0; i < maxNumber; i++) { 953 Key key = v.IteratorForIndex(i)->Key(); 954 Iterator it = v.Find(key); 955 ConstIterator cit = cv.Find(key); 956 if (it != v.End()) { 957 CHK(it->Key() == key); 958 CHK(it->Key() == cit->Key()); 959 CHK((*it).Key() == (*it).Key()); 960 CHK(&it->Value() == &cit->Value()); 961 CHK(&(*it).Value() == &(*it).Value()); 962 } 963 } 964} 965 966// GenericFindTest 967template<typename _TestStrategy> 968static 969void 970GenericFindTest() 971{ 972 GenericFindTest<_TestStrategy>(30); 973 GenericFindTest<_TestStrategy>(200); 974} 975 976// FindTest 977_ORDERED_MAP_TEST_TEMPLATE_LIST 978void 979_ORDERED_MAP_TEST_CLASS_NAME::FindTest() 980{ 981 NextSubTest(); 982 GenericFindTest<TestStrategy<Ascending> >(); 983 NextSubTest(); 984 GenericFindTest<TestStrategy<Descending> >(); 985} 986 987// GenericFindCloseTest 988template<typename _TestStrategy> 989static 990void 991GenericFindCloseTest(int32 maxNumber) 992{ 993 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 994 typedef typename _TestStrategy::Key Key; 995 typedef typename _TestStrategy::TestClass TestClass; 996 typedef typename TestClass::Iterator Iterator; 997 typedef typename TestClass::ConstIterator ConstIterator; 998 EntryStrategy entryStrategy; 999 TestClass v; 1000 GenericFill(v, entryStrategy, maxNumber); 1001 const TestClass &cv = v; 1002 // find the values in the set 1003 for (int32 i = 0; i < maxNumber; i++) { 1004 Key key = v.IteratorForIndex(i)->Key(); 1005 // less 1006 Iterator it = v.FindClose(key, true); 1007 ConstIterator cit = cv.FindClose(key, true); 1008 CHK(it->Key() == key); 1009 CHK(it->Key() == cit->Key()); 1010 CHK((*it).Key() == (*it).Key()); 1011 CHK(&it->Value() == &cit->Value()); 1012 CHK(&(*it).Value() == &(*it).Value()); 1013 // greater 1014 it = v.FindClose(key, false); 1015 cit = cv.FindClose(key, false); 1016 CHK(it->Key() == key); 1017 CHK(it->Key() == cit->Key()); 1018 CHK((*it).Key() == (*it).Key()); 1019 CHK(&it->Value() == &cit->Value()); 1020 CHK(&(*it).Value() == &(*it).Value()); 1021 } 1022 // try to find some random values 1023 for (int32 i = 0; i < maxNumber; i++) { 1024 Key key = entryStrategy.GenerateKey(); 1025 // less 1026 Iterator it = v.FindClose(key, true); 1027 ConstIterator cit = cv.FindClose(key, true); 1028 if (it != v.End()) { 1029 CHK(it->Key() == cit->Key()); 1030 CHK((*it).Key() == (*it).Key()); 1031 CHK(&it->Value() == &cit->Value()); 1032 CHK(&(*it).Value() == &(*it).Value()); 1033 } 1034 // greater 1035 it = v.FindClose(key, false); 1036 cit = cv.FindClose(key, false); 1037 if (it != v.End()) { 1038 CHK(it->Key() == cit->Key()); 1039 CHK((*it).Key() == (*it).Key()); 1040 CHK(&it->Value() == &cit->Value()); 1041 CHK(&(*it).Value() == &(*it).Value()); 1042 } 1043 } 1044} 1045 1046// GenericFindCloseTest 1047template<typename _TestStrategy> 1048static 1049void 1050GenericFindCloseTest() 1051{ 1052 GenericFindCloseTest<_TestStrategy>(30); 1053 GenericFindCloseTest<_TestStrategy>(200); 1054} 1055 1056// FindCloseTest 1057_ORDERED_MAP_TEST_TEMPLATE_LIST 1058void 1059_ORDERED_MAP_TEST_CLASS_NAME::FindCloseTest() 1060{ 1061 NextSubTest(); 1062 GenericFindCloseTest<TestStrategy<Ascending> >(); 1063 NextSubTest(); 1064 GenericFindCloseTest<TestStrategy<Descending> >(); 1065} 1066 1067// GenericIteratorTest 1068template<typename _TestStrategy> 1069static 1070void 1071GenericIteratorTest(int32 maxNumber) 1072{ 1073 typedef typename _TestStrategy::EntryStrategy EntryStrategy; 1074 typedef typename _TestStrategy::TestClass TestClass; 1075 typedef typename TestClass::Iterator Iterator; 1076 typedef typename TestClass::ConstIterator ConstIterator; 1077 EntryStrategy entryStrategy; 1078 TestClass v; 1079 GenericFill(v, entryStrategy, maxNumber); 1080 const TestClass &cv = v; 1081 Iterator it = v.Begin(); 1082 ConstIterator cit = cv.Begin(); 1083 for (; it != v.End(); ++it, ++cit) { 1084 CHK(it->Key() == cit->Key()); 1085 CHK(&it->Value() == &cit->Value()); 1086 CHK(it->Key() == (*it).Key()); 1087 CHK(cit->Key() == (*cit).Key()); 1088 CHK(&it->Value() == &(*it).Value()); 1089 CHK(&cit->Value() == &(*cit).Value()); 1090 CHK(it->Key() == it.operator->().Key()); 1091 CHK(&it->Value() == &it.operator->().Value()); 1092 CHK(cit->Key() == cit.operator->().Key()); 1093 CHK(&cit->Value() == &cit.operator->().Value()); 1094 CHK(it); 1095 CHK(cit); 1096 } 1097 CHK(cit == cv.End()); 1098 while (it != v.Begin()) { 1099 --it; 1100 --cit; 1101 CHK(it->Key() == cit->Key()); 1102 CHK(&it->Value() == &cit->Value()); 1103 CHK(it->Key() == (*it).Key()); 1104 CHK(cit->Key() == (*cit).Key()); 1105 CHK(&it->Value() == &(*it).Value()); 1106 CHK(&cit->Value() == &(*cit).Value()); 1107 CHK(it->Key() == it.operator->().Key()); 1108 CHK(&it->Value() == &it.operator->().Value()); 1109 CHK(cit->Key() == cit.operator->().Key()); 1110 CHK(&cit->Value() == &cit.operator->().Value()); 1111 CHK(it); 1112 CHK(cit); 1113 } 1114 CHK(cit == cv.Begin()); 1115 CHK(!v.Null()); 1116 CHK(!cv.Null()); 1117} 1118 1119// GenericIteratorTest 1120template<typename _TestStrategy> 1121static 1122void 1123GenericIteratorTest() 1124{ 1125 GenericIteratorTest<_TestStrategy>(30); 1126 GenericIteratorTest<_TestStrategy>(200); 1127} 1128 1129// IteratorTest 1130_ORDERED_MAP_TEST_TEMPLATE_LIST 1131void 1132_ORDERED_MAP_TEST_CLASS_NAME::IteratorTest() 1133{ 1134 NextSubTest(); 1135 GenericIteratorTest<TestStrategy<Ascending> >(); 1136 NextSubTest(); 1137 GenericIteratorTest<TestStrategy<Descending> >(); 1138} 1139 1140#endif // _ordered_map_test_h_ 1141