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
AssertStatistics()16 AssertStatistics::AssertStatistics()
17 {
18 fAssertions = 0;
19 fPassed = 0;
20 fFailed = 0;
21 }
22
GetInstance()23 AssertStatistics* AssertStatistics::GetInstance()
24 {
25 if (fStatistics == NULL) {
26 fStatistics = new AssertStatistics();
27 }
28 return fStatistics;
29 }
30
Print()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
Compare(const void * a,const void * b)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);
IsSorted(const _PointerList_ & list)72 bool IsSorted(const _PointerList_& list) { return IsSorted(list, list.CountItems()); }
IsHSorted(const _PointerList_ & list)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
CreateItem()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.
Initialize(_PointerList_ & list,int size)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
Print(const _PointerList_ & list)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
MakeEmpty(_PointerList_ & 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
Equals(const _PointerList_ & list1,const _PointerList_ & list2)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
IsSorted(const _PointerList_ & list,int32 n)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
IndexOf(const _PointerList_ & list,int value)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
ItemFor(const _PointerList_ & list,int value)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
CreationTest()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
OwningTest()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
SortTest()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
Compare(const void * a,const void * b,void * data)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
SortTestWithState()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
CopyTo(void * item,void * data)322 void* CopyTo(void* item, void* data)
323 {
324 _PointerList_* list = (_PointerList_*)data;
325 list->AddItem(item);
326 return NULL;
327 }
328
FirstItem(void * item,void * data)329 void* FirstItem(void* item, void* data)
330 {
331 return item;
332 }
333
EachElementTest()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
BinarySearchTest()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:
Value(int value)391 Value(int value) : value(value) {};
392 int value;
393 };
394
ValuePredicate(const void * _item,void * _value)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
BinarySearchIndexTest()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
NullTest()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
Run()492 void PointerListTest::Run()
493 {
494 CreationTest();
495 OwningTest();
496 SortTest();
497 SortTestWithState();
498 EachElementTest();
499 BinarySearchTest();
500 BinarySearchIndexTest();
501 NullTest();
502 }
503
main(int argc,char * argv[])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 }