1 /* 2 ** Copyright 2004, Michael Pfeiffer (laplace@users.sourceforge.net). 3 ** Distributed under the terms of the MIT License. 4 ** 5 */ 6 7 #include "ObjectList.h" 8 #include <StopWatch.h> 9 #include <stdio.h> 10 #include <stdlib.h> 11 12 #include "PointerListTest.h" 13 14 AssertStatistics *AssertStatistics::fStatistics = NULL; 15 16 AssertStatistics::AssertStatistics() 17 { 18 fAssertions = 0; 19 fPassed = 0; 20 fFailed = 0; 21 } 22 23 AssertStatistics* AssertStatistics::GetInstance() 24 { 25 if (fStatistics == NULL) { 26 fStatistics = new AssertStatistics(); 27 } 28 return fStatistics; 29 } 30 31 void AssertStatistics::Print() 32 { 33 fprintf(stderr, "Assert Statistics:\n"); 34 fprintf(stderr, "Assertions: %d\n", fAssertions); 35 fprintf(stderr, "Passed: %d\n", fPassed); 36 fprintf(stderr, "Failed: %d\n", fFailed); 37 } 38 39 #undef assert 40 #define assert(expr) \ 41 if (!(expr)) {\ 42 fprintf(stderr, "FAILED [%d] ("#expr")\n", __LINE__); \ 43 AssertStatistics::GetInstance()->AssertFailed(); \ 44 }\ 45 else {\ 46 AssertStatistics::GetInstance()->AssertPassed(); \ 47 } 48 49 50 int Item::Compare(const void* a, const void* b) 51 { 52 Item* itemA = (Item*)a; 53 Item* itemB = (Item*)b; 54 if (itemA == itemB) return 0; 55 if (itemA == NULL) return -1; 56 if (itemB == NULL) return 1; 57 return itemA->Value() - itemB->Value(); 58 } 59 60 int Item::fNextID = 0; 61 int Item::fInstances = 0; 62 63 class PointerListTest 64 { 65 public: 66 Item* CreateItem(); 67 void Initialize(_PointerList_& list, int size); 68 void Print(const _PointerList_& list); 69 void MakeEmpty(_PointerList_& list); 70 bool Equals(const _PointerList_& list1, const _PointerList_& list2); 71 bool IsSorted(const _PointerList_& list, int32 n); 72 bool IsSorted(const _PointerList_& list) { return IsSorted(list, list.CountItems()); } 73 bool IsHSorted(const _PointerList_& list) { return IsSorted(list, list.CountItems()-1); } 74 int IndexOf(const _PointerList_& list, int value); 75 Item* ItemFor(const _PointerList_& list, int value); 76 77 void CreationTest(); 78 void OwningTest(); 79 void SortTest(); 80 void SortTestWithState(); 81 void EachElementTest(); 82 void BinarySearchTest(); 83 void BinarySearchIndexTest(); 84 void NullTest(); 85 void Run(); 86 }; 87 88 #define MAX_ID 10000 89 #define NOT_USED_ID -1 90 #define NOT_USED_ID_HIGH (MAX_ID+1) 91 92 // Create an Item with a random value 93 Item* PointerListTest::CreateItem() 94 { 95 return new Item(rand() % (MAX_ID+1)); 96 } 97 98 // Add size number of new items to the list. 99 void PointerListTest::Initialize(_PointerList_& list, int size) 100 { 101 for (int32 i = 0; i < size; i ++) { 102 list.AddItem(CreateItem()); 103 } 104 } 105 106 // Print the list to stderr 107 void PointerListTest::Print(const _PointerList_& list) 108 { 109 const int32 n = list.CountItems(); 110 for (int32 i = 0; i < n; i ++) { 111 Item* item = (Item*)list.ItemAt(i); 112 if (i > 0) { 113 fprintf(stderr, ", "); 114 } 115 if (item != NULL) { 116 item->Print(); 117 } else { 118 fprintf(stderr, "NULL"); 119 } 120 } 121 fprintf(stderr, "\n"); 122 } 123 124 // delete the Items in the list 125 void PointerListTest::MakeEmpty(_PointerList_& list) 126 { 127 const int32 n = list.CountItems(); 128 for (int32 i = 0; i < n; i ++) { 129 Item* item = (Item*)list.ItemAt(i); 130 if (item != NULL) { 131 delete item; 132 } 133 } 134 list.MakeEmpty(); 135 } 136 137 // contain the lists the same items or values 138 bool PointerListTest::Equals(const _PointerList_& list1, const _PointerList_& list2) 139 { 140 const int32 n = list1.CountItems(); 141 142 if (n != list2.CountItems()) return false; 143 144 for (int32 i = 0; i < n; i ++) { 145 Item* item1 = (Item*)list1.ItemAt(i); 146 Item* item2 = (Item*)list2.ItemAt(i); 147 if (item1 == item2) continue; 148 if (item1 == NULL || !item1->Equals(item2)) return false; 149 } 150 151 return true; 152 } 153 154 // is the list sorted 155 bool PointerListTest::IsSorted(const _PointerList_& list, int32 n) 156 { 157 int prevValue = -1; // item values are >= 0 158 for (int32 i = 0; i < n; i ++) { 159 Item* item = (Item*)list.ItemAt(i); 160 assert(item != NULL); 161 int value = item->Value(); 162 if (value < prevValue) { 163 return false; 164 } 165 prevValue = value; 166 } 167 return true; 168 } 169 170 int PointerListTest::IndexOf(const _PointerList_& list, int value) 171 { 172 int n = list.CountItems(); 173 for (int32 i = 0; i < n; i ++) { 174 Item* item = (Item*)list.ItemAt(i); 175 if (item != NULL && item->Value() == value) { 176 return i; 177 } 178 } 179 return -1; 180 } 181 182 Item* PointerListTest::ItemFor(const _PointerList_& list, int value) 183 { 184 int32 index = IndexOf(list, value); 185 if (index >= 0) { 186 list.ItemAt(index); 187 } 188 return NULL; 189 } 190 191 192 193 void PointerListTest::CreationTest() 194 { 195 _PointerList_ list; 196 int numberOfInstances = Item::GetNumberOfInstances(); 197 assert(list.Owning() == false); 198 199 assert(list.CountItems() == 0); 200 Initialize(list, 10); 201 202 assert(list.CountItems() == 10); 203 204 int newInstances = Item::GetNumberOfInstances() - numberOfInstances; 205 assert(newInstances == 10); 206 207 numberOfInstances = Item::GetNumberOfInstances(); 208 MakeEmpty(list); 209 int deletedInstances = numberOfInstances - Item::GetNumberOfInstances(); 210 assert(deletedInstances == 10); 211 } 212 213 void PointerListTest::OwningTest() 214 { 215 _PointerList_ list(10, true); 216 assert(list.CountItems() == 0); 217 assert(list.Owning() == true); 218 219 int numberOfInstances = Item::GetNumberOfInstances(); 220 Initialize(list, 10); 221 assert(list.CountItems() == 10); 222 assert(Item::GetNumberOfInstances() - numberOfInstances == 10); 223 224 _PointerList_* clone = new _PointerList_(list); 225 assert(Item::GetNumberOfInstances() - numberOfInstances == 10); 226 assert(clone->Owning() == true); 227 228 MakeEmpty(list); 229 assert(Item::GetNumberOfInstances() - numberOfInstances == 0); 230 231 delete clone; 232 assert(Item::GetNumberOfInstances() - numberOfInstances == 0); 233 } 234 235 void PointerListTest::SortTest() 236 { 237 for (int i = 0; i < 10; i ++) { 238 _PointerList_ list; 239 Initialize(list, i); 240 241 _PointerList_ clone(list); 242 assert(Equals(list, clone)); 243 assert(clone.Owning() == false); 244 245 list.SortItems(Item::Compare); 246 assert(IsSorted(list)); 247 248 int lastItem = clone.CountItems()-1; 249 bool hasItems = clone.CountItems() > 0; 250 Item* item = NULL; 251 if (hasItems) { 252 item = (Item*)clone.ItemAt(0); 253 } 254 255 // HSortItems seems to put the first item at the end of the list 256 // and sort the rest. 257 clone.HSortItems(Item::Compare); 258 assert(IsHSorted(clone)); 259 assert(!hasItems || item == (Item*)clone.ItemAt(lastItem)); 260 261 MakeEmpty(list); 262 } 263 } 264 265 static void* gData = NULL; 266 267 int Compare(const void* a, const void* b, void* data) 268 { 269 // check data has the expected value 270 assert(gData == data); 271 return Item::Compare(a, b); 272 } 273 #define FROM 10000 274 #define TO 10000 275 void PointerListTest::SortTestWithState() 276 { 277 gData = (void*)0x4711; 278 279 for (int i = FROM; i < (TO+1); i ++) { 280 BStopWatch* watch = new BStopWatch("Initialize"); 281 _PointerList_ list; 282 Initialize(list, i); 283 delete watch; 284 285 watch = new BStopWatch("Clone"); 286 _PointerList_ clone(list); 287 delete watch; 288 assert(Equals(list, clone)); 289 assert(clone.Owning() == false); 290 291 watch = new BStopWatch("SortItems"); 292 list.SortItems(::Compare, gData); 293 delete watch; 294 assert(IsSorted(list)); 295 296 watch = new BStopWatch("SortItems (sorted list)"); 297 list.SortItems(::Compare, gData); 298 delete watch; 299 assert(IsSorted(list)); 300 301 int lastItem = clone.CountItems()-1; 302 bool hasItems = clone.CountItems() > 0; 303 Item* item = NULL; 304 if (hasItems) { 305 item = (Item*)clone.ItemAt(0); 306 } 307 308 // HSortItems seems to put the first item at the end of the list 309 // and sort the rest. 310 watch = new BStopWatch("HSortItems"); 311 clone.HSortItems(Compare, gData); 312 delete watch; 313 assert(IsHSorted(clone)); 314 assert(!hasItems || item == (Item*)clone.ItemAt(lastItem)); 315 316 watch = new BStopWatch("MakeEmpty"); 317 MakeEmpty(list); 318 delete watch; 319 } 320 } 321 322 void* CopyTo(void* item, void* data) 323 { 324 _PointerList_* list = (_PointerList_*)data; 325 list->AddItem(item); 326 return NULL; 327 } 328 329 void* FirstItem(void* item, void* data) 330 { 331 return item; 332 } 333 334 void PointerListTest::EachElementTest() 335 { 336 _PointerList_ list; 337 Initialize(list, 10); 338 assert(list.CountItems() == 10); 339 340 _PointerList_ clone; 341 list.EachElement(CopyTo, &clone); 342 assert(clone.CountItems() == list.CountItems()); 343 344 void* item = list.EachElement(FirstItem, NULL); 345 assert (item == list.ItemAt(0)); 346 347 MakeEmpty(list); 348 } 349 350 void PointerListTest::BinarySearchTest() 351 { 352 _PointerList_ list; 353 Initialize(list, 10); 354 list.SortItems(Item::Compare); 355 assert(IsSorted(list)); 356 357 gData = (void*)0x4711; 358 359 Item notInListLow(NOT_USED_ID); 360 Item notInListHigh(NOT_USED_ID_HIGH); 361 362 for (int32 i = 0; i < 10; i ++) { 363 Item* item = (Item*)list.ItemAt(i); 364 assert(item != NULL); 365 366 Item* found = (Item*)list.BinarySearch(item, Item::Compare); 367 assert(item->Equals(found)); 368 369 found = (Item*)list.BinarySearch(item, ::Compare, gData); 370 assert(item->Equals(found)); 371 372 found = (Item*)list.BinarySearch(¬InListLow, Item::Compare); 373 assert(found == NULL); 374 375 found = (Item*)list.BinarySearch(¬InListLow, ::Compare, gData); 376 assert(found == NULL); 377 378 found = (Item*)list.BinarySearch(¬InListHigh, Item::Compare); 379 assert(found == NULL); 380 381 found = (Item*)list.BinarySearch(¬InListHigh, ::Compare, gData); 382 assert(found == NULL); 383 } 384 385 MakeEmpty(list); 386 } 387 388 class Value 389 { 390 public: 391 Value(int value) : value(value) {}; 392 int value; 393 }; 394 395 static int ValuePredicate(const void* _item, void* _value) 396 { 397 Item* item = (Item*)_item; 398 Value* value = (Value*)_value; 399 return item->Value() - value->value; 400 } 401 402 void PointerListTest::BinarySearchIndexTest() 403 { 404 _PointerList_ list; 405 Initialize(list, 10); 406 list.SortItems(Item::Compare); 407 assert(IsSorted(list)); 408 409 Item notInListLow(NOT_USED_ID); 410 Item notInListHigh(NOT_USED_ID_HIGH); 411 gData = (void*)0x4711; 412 413 for (int32 i = 0; i < 10; i ++) { 414 Item* item = (Item*)list.ItemAt(i); 415 assert(item != NULL); 416 Value value(item->Value()); 417 418 int index = IndexOf(list, item->Value()); 419 int searchIndex; 420 searchIndex = list.BinarySearchIndex(item, Item::Compare); 421 assert(index == searchIndex); 422 423 searchIndex = list.BinarySearchIndex(item, ::Compare, gData); 424 assert(index == searchIndex); 425 426 searchIndex = list.BinarySearchIndexByPredicate(&value, ValuePredicate); 427 assert(index == searchIndex); 428 429 // notInListLow 430 searchIndex = list.BinarySearchIndex(¬InListLow, Item::Compare); 431 assert(searchIndex == -1); 432 433 searchIndex = list.BinarySearchIndex(¬InListLow, ::Compare, gData); 434 assert(searchIndex == -1); 435 436 value.value = notInListLow.Value(); 437 searchIndex = list.BinarySearchIndexByPredicate(&value, ValuePredicate); 438 assert(searchIndex == -1); 439 440 // notInListHigh 441 searchIndex = list.BinarySearchIndex(¬InListHigh, Item::Compare); 442 assert(searchIndex == -(list.CountItems()+1)); 443 444 searchIndex = list.BinarySearchIndex(¬InListHigh, ::Compare, gData); 445 assert(searchIndex == -(list.CountItems()+1)); 446 447 value.value = notInListHigh.Value(); 448 searchIndex = list.BinarySearchIndexByPredicate(&value, ValuePredicate); 449 assert(searchIndex == -(list.CountItems()+1)); 450 } 451 452 MakeEmpty(list); 453 454 for (int i = 0; i < 3; i ++) { 455 list.AddItem(new Item(2 * i)); 456 } 457 Item notInList(3); 458 assert(IndexOf(list, 3) == -1); 459 460 int index = list.BinarySearchIndex(¬InList, Item::Compare); 461 assert (index == -3); 462 463 index = list.BinarySearchIndex(¬InList, ::Compare, gData); 464 assert (index == -3); 465 466 Value value(notInList.Value()); 467 index = list.BinarySearchIndexByPredicate(&value, ValuePredicate); 468 assert (index == -3); 469 470 MakeEmpty(list); 471 } 472 473 void PointerListTest::NullTest() 474 { 475 _PointerList_ list; 476 Initialize(list, 10); 477 // R5 crashes 478 // list.EachElement(NULL, NULL); 479 // list.SortItems(NULL); 480 // list.SortItems(NULL, NULL); 481 // list.HSortItems(NULL); 482 // list.HSortItems(NULL, NULL); 483 // list.BinarySearch(NULL, NULL); 484 // list.BinarySearch(NULL, NULL, NULL); 485 // list.BinarySearchIndex(NULL, NULL); 486 // list.BinarySearchIndex(NULL, NULL, NULL); 487 // list.BinarySearchIndexByPredicate(NULL, NULL); 488 assert(!list.ReplaceItem(-1, NULL)); 489 assert(!list.ReplaceItem(100, NULL)); 490 } 491 492 void PointerListTest::Run() 493 { 494 CreationTest(); 495 OwningTest(); 496 SortTest(); 497 SortTestWithState(); 498 EachElementTest(); 499 BinarySearchTest(); 500 BinarySearchIndexTest(); 501 NullTest(); 502 } 503 504 int main(int argc, char* argv[]) 505 { 506 // initialize srand with constant to get reproducable results 507 srand(0); 508 PointerListTest test; 509 test.Run(); 510 AssertStatistics::GetInstance()->Print(); 511 }