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
14AssertStatistics *AssertStatistics::fStatistics = NULL;
15
16AssertStatistics::AssertStatistics()
17{
18	fAssertions = 0;
19	fPassed = 0;
20	fFailed = 0;
21}
22
23AssertStatistics* AssertStatistics::GetInstance()
24{
25	if (fStatistics == NULL) {
26		fStatistics = new AssertStatistics();
27	}
28	return fStatistics;
29}
30
31void 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
50int 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
60int Item::fNextID = 0;
61int Item::fInstances = 0;
62
63class PointerListTest
64{
65public:
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
93Item* PointerListTest::CreateItem()
94{
95	return new Item(rand() % (MAX_ID+1));
96}
97
98// Add size number of new items to the list.
99void 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
107void 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
125void 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
138bool 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
155bool 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
170int 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
182Item* 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
193void 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
213void 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
235void 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
265static void* gData = NULL;
266
267int 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
275void 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
322void* CopyTo(void* item, void* data)
323{
324	_PointerList_* list = (_PointerList_*)data;
325	list->AddItem(item);
326	return NULL;
327}
328
329void* FirstItem(void* item, void* data)
330{
331	return item;
332}
333
334void 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
350void 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(&notInListLow, Item::Compare);
373		assert(found == NULL);
374
375		found = (Item*)list.BinarySearch(&notInListLow, ::Compare, gData);
376		assert(found == NULL);
377
378		found = (Item*)list.BinarySearch(&notInListHigh, Item::Compare);
379		assert(found == NULL);
380
381		found = (Item*)list.BinarySearch(&notInListHigh, ::Compare, gData);
382		assert(found == NULL);
383	}
384
385	MakeEmpty(list);
386}
387
388class Value
389{
390public:
391	Value(int value) : value(value) {};
392	int value;
393};
394
395static 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
402void 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(&notInListLow, Item::Compare);
431		assert(searchIndex == -1);
432
433		searchIndex = list.BinarySearchIndex(&notInListLow, ::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(&notInListHigh, Item::Compare);
442		assert(searchIndex == -(list.CountItems()+1));
443
444		searchIndex = list.BinarySearchIndex(&notInListHigh, ::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(&notInList, Item::Compare);
461	assert (index == -3);
462
463	index = list.BinarySearchIndex(&notInList, ::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
473void 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
492void PointerListTest::Run()
493{
494	CreationTest();
495	OwningTest();
496	SortTest();
497	SortTestWithState();
498	EachElementTest();
499	BinarySearchTest();
500	BinarySearchIndexTest();
501	NullTest();
502}
503
504int 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}