text: /* 
  ** Copyright 2004, Michael Pfeiffer (laplace@users.sourceforge.net).
  ** Distributed under the terms of the MIT License.
  **
  */
  
  #include "ObjectList.h"
  #include <StopWatch.h>
  #include <stdio.h>
  #include <stdlib.h>
  
  #include "PointerListTest.h"
  
  AssertStatistics *AssertStatistics::fStatistics = NULL;
  
  AssertStatistics::AssertStatistics()
  {
  	fAssertions = 0;
  	fPassed = 0;
  	fFailed = 0;
  }
  
  AssertStatistics* AssertStatistics::GetInstance()
  {
  	if (fStatistics == NULL) {
  		fStatistics = new AssertStatistics();
  	}
  	return fStatistics;
  }
  
  void AssertStatistics::Print()
  {
  	fprintf(stderr, "Assert Statistics:\n");
  	fprintf(stderr, "Assertions: %d\n", fAssertions);
  	fprintf(stderr, "Passed: %d\n", fPassed);
  	fprintf(stderr, "Failed: %d\n", fFailed);
  }
  
  #undef assert
  #define assert(expr) \
  	if (!(expr)) {\
  		fprintf(stderr, "FAILED [%d] ("#expr")\n", __LINE__); \
  		AssertStatistics::GetInstance()->AssertFailed(); \
  	}\
  	else {\
  		AssertStatistics::GetInstance()->AssertPassed(); \
  	}
  	
  
  int Item::Compare(const void* a, const void* b)
  {
  	Item* itemA = (Item*)a;
  	Item* itemB = (Item*)b;
  	if (itemA == itemB) return 0;
  	if (itemA == NULL) return -1;
  	if (itemB == NULL) return 1;
  	return itemA->Value() - itemB->Value();
  }
  
  int Item::fNextID = 0;
  int Item::fInstances = 0;
  
  class PointerListTest
  {
  public:
  	Item* CreateItem();
  	void Initialize(_PointerList_& list, int size);
  	void Print(const _PointerList_& list);
  	void MakeEmpty(_PointerList_& list);
  	bool Equals(const _PointerList_& list1, const _PointerList_& list2);
  	bool IsSorted(const _PointerList_& list, int32 n);
  	bool IsSorted(const _PointerList_& list) { return IsSorted(list, list.CountItems()); }
  	bool IsHSorted(const _PointerList_& list) { return IsSorted(list, list.CountItems()-1); }
  	int  IndexOf(const _PointerList_& list, int value);
  	Item* ItemFor(const _PointerList_& list, int value);
  
  	void CreationTest();
  	void OwningTest();
  	void SortTest();
  	void SortTestWithState();
  	void EachElementTest();
  	void BinarySearchTest();
  	void BinarySearchIndexTest();
  	void NullTest();
  	void Run();	
  };
  
  #define MAX_ID 10000
  #define NOT_USED_ID -1
  #define NOT_USED_ID_HIGH (MAX_ID+1)
  
  // Create an Item with a random value
  Item* PointerListTest::CreateItem()
  {
  	return new Item(rand() % (MAX_ID+1));
  }
  
  // Add size number of new items to the list.
  void PointerListTest::Initialize(_PointerList_& list, int size)
  {
  	for (int32 i = 0; i < size; i ++) {
  		list.AddItem(CreateItem());
  	}
  }
  
  // Print the list to stderr
  void PointerListTest::Print(const _PointerList_& list)
  {
  	const int32 n = list.CountItems();
  	for (int32 i = 0; i < n; i ++) {
  		Item* item = (Item*)list.ItemAt(i);
  		if (i > 0) {
  			fprintf(stderr, ", ");
  		}
  		if (item != NULL) {
  			item->Print();
  		} else {
  			fprintf(stderr, "NULL");
  		}
  	}
  	fprintf(stderr, "\n");
  }
  
  // delete the Items in the list
  void PointerListTest::MakeEmpty(_PointerList_& list)
  {
  	const int32 n = list.CountItems();
  	for (int32 i = 0; i < n; i ++) {
  		Item* item = (Item*)list.ItemAt(i);
  		if (item != NULL) {
  			delete item;
  		}
  	}
  	list.MakeEmpty();
  }
  
  // contain the lists the same items or values
  bool PointerListTest::Equals(const _PointerList_& list1, const _PointerList_& list2)
  {
  	const int32 n = list1.CountItems();
  
  	if (n != list2.CountItems()) return false;
  	
  	for (int32 i = 0; i < n; i ++) {
  		Item* item1 = (Item*)list1.ItemAt(i);
  		Item* item2 = (Item*)list2.ItemAt(i);
  		if (item1 == item2) continue;
  		if (item1 == NULL || !item1->Equals(item2)) return false;
  	}
  	
  	return true;
  }
  
  // is the list sorted
  bool PointerListTest::IsSorted(const _PointerList_& list, int32 n)
  {
  	int prevValue = -1; // item values are >= 0
  	for (int32 i = 0; i < n; i ++) {
  		Item* item = (Item*)list.ItemAt(i);
  		assert(item != NULL);
  		int value = item->Value();
  		if (value < prevValue) {
  			return false;
  		}
  		prevValue = value;
  	}
  	return true;
  }
  
  int PointerListTest::IndexOf(const _PointerList_& list, int value)
  {
  	int n = list.CountItems();
  	for (int32 i = 0; i < n; i ++) {
  		Item* item = (Item*)list.ItemAt(i);
  		if (item != NULL && item->Value() == value) {
  			return i;
  		}
  	}
  	return -1;
  }
  
  Item* PointerListTest::ItemFor(const _PointerList_& list, int value)
  {
  	int32 index = IndexOf(list, value);
  	if (index >= 0) {
  		list.ItemAt(index);
  	}
  	return NULL;
  }
  
  
  
  void PointerListTest::CreationTest()
  {
  	_PointerList_ list;
  	int numberOfInstances = Item::GetNumberOfInstances();
  	assert(list.Owning() == false);
  		
  	assert(list.CountItems() == 0);
  	Initialize(list, 10);
  	
  	assert(list.CountItems() == 10);
  	
  	int newInstances = Item::GetNumberOfInstances() - numberOfInstances;
  	assert(newInstances == 10);
  
  	numberOfInstances = Item::GetNumberOfInstances();
  	MakeEmpty(list);
  	int deletedInstances = numberOfInstances - Item::GetNumberOfInstances();
  	assert(deletedInstances == 10);
  }
  
  void PointerListTest::OwningTest()
  {
  	_PointerList_ list(10, true);
  	assert(list.CountItems() == 0);
  	assert(list.Owning() == true);
  	
  	int numberOfInstances = Item::GetNumberOfInstances();
  	Initialize(list, 10);
  	assert(list.CountItems() == 10);
  	assert(Item::GetNumberOfInstances() - numberOfInstances == 10);
  	
  	_PointerList_* clone = new _PointerList_(list);
  	assert(Item::GetNumberOfInstances() - numberOfInstances == 10);
  	assert(clone->Owning() == true);
  	
  	MakeEmpty(list);
  	assert(Item::GetNumberOfInstances() - numberOfInstances == 0);
  
  	delete clone;	
  	assert(Item::GetNumberOfInstances() - numberOfInstances == 0);
  }
  
  void PointerListTest::SortTest()
  {
  	for (int i = 0; i < 10; i ++) {
  		_PointerList_ list;
  		Initialize(list, i);
  	
  		_PointerList_ clone(list);
  		assert(Equals(list, clone));
  		assert(clone.Owning() == false);
  
  		list.SortItems(Item::Compare);
  		assert(IsSorted(list));
  
  		int lastItem = clone.CountItems()-1;
  		bool hasItems = clone.CountItems() > 0;
  		Item* item = NULL;
  		if (hasItems) {
  			item = (Item*)clone.ItemAt(0);
  		}
  		
  		// HSortItems seems to put the first item at the end of the list
  		// and sort the rest.
  		clone.HSortItems(Item::Compare);
  		assert(IsHSorted(clone));
  		assert(!hasItems || item == (Item*)clone.ItemAt(lastItem));
  		
  		MakeEmpty(list);
  	}
  }
  
  static void* gData = NULL;
  
  int Compare(const void* a, const void* b, void* data)
  {
  	// check data has the expected value
  	assert(gData == data);
  	return Item::Compare(a, b);
  }
  #define FROM 10000
  #define TO   10000
  void PointerListTest::SortTestWithState()
  {
  	gData = (void*)0x4711;
  	
  	for (int i = FROM; i < (TO+1); i ++) {
  		BStopWatch* watch = new BStopWatch("Initialize");
  		_PointerList_ list;
  		Initialize(list, i);
  		delete watch;
  	
  		watch = new BStopWatch("Clone");
  		_PointerList_ clone(list);
  		delete watch;
  		assert(Equals(list, clone));
  		assert(clone.Owning() == false);
  
  		watch = new BStopWatch("SortItems");
  		list.SortItems(::Compare, gData);
  		delete watch;
  		assert(IsSorted(list));
  		
  		watch = new BStopWatch("SortItems (sorted list)");
  		list.SortItems(::Compare, gData);
  		delete watch;
  		assert(IsSorted(list));
  
  		int lastItem = clone.CountItems()-1;
  		bool hasItems = clone.CountItems() > 0;
  		Item* item = NULL;
  		if (hasItems) {
  			item = (Item*)clone.ItemAt(0);
  		}
  		
  		// HSortItems seems to put the first item at the end of the list
  		// and sort the rest.
  		watch = new BStopWatch("HSortItems");
  		clone.HSortItems(Compare, gData);
  		delete watch;
  		assert(IsHSorted(clone));
  		assert(!hasItems || item == (Item*)clone.ItemAt(lastItem));
  		
  		watch = new BStopWatch("MakeEmpty");
  		MakeEmpty(list);
  		delete watch;
  	}
  }
  
  void* CopyTo(void* item, void* data)
  {
  	_PointerList_* list = (_PointerList_*)data;
  	list->AddItem(item);
  	return NULL;
  }
  
  void* FirstItem(void* item, void* data)
  {
  	return item;
  }
  
  void PointerListTest::EachElementTest()
  {
  	_PointerList_ list;
  	Initialize(list, 10);
  	assert(list.CountItems() == 10);
  	
  	_PointerList_ clone;
  	list.EachElement(CopyTo, &clone);
  	assert(clone.CountItems() == list.CountItems());
  
  	void* item = list.EachElement(FirstItem, NULL);
  	assert (item == list.ItemAt(0));
  	
  	MakeEmpty(list);
  }
  
  void PointerListTest::BinarySearchTest()
  {
  	_PointerList_ list;
  	Initialize(list, 10);
  	list.SortItems(Item::Compare);
  	assert(IsSorted(list));
  	
  	gData = (void*)0x4711;
  	
  	Item notInListLow(NOT_USED_ID);
  	Item notInListHigh(NOT_USED_ID_HIGH);
  	
  	for (int32 i = 0; i < 10; i ++) {
  		Item* item = (Item*)list.ItemAt(i);
  		assert(item != NULL);
  		
  		Item* found = (Item*)list.BinarySearch(item, Item::Compare);
  		assert(item->Equals(found));
  
  		found = (Item*)list.BinarySearch(item, ::Compare, gData);
  		assert(item->Equals(found));
  
  		found = (Item*)list.BinarySearch(&notInListLow, Item::Compare);
  		assert(found == NULL);
  
  		found = (Item*)list.BinarySearch(&notInListLow, ::Compare, gData);
  		assert(found == NULL);
  
  		found = (Item*)list.BinarySearch(&notInListHigh, Item::Compare);
  		assert(found == NULL);
  
  		found = (Item*)list.BinarySearch(&notInListHigh, ::Compare, gData);
  		assert(found == NULL);
  	}	
  	
  	MakeEmpty(list);
  }
  
  class Value
  {
  public:
  	Value(int value) : value(value) {};
  	int value;
  };
  
  static int ValuePredicate(const void* _item, void* _value)
  {
  	Item* item = (Item*)_item;
  	Value* value = (Value*)_value;
  	return item->Value() - value->value;
  }
  
  void PointerListTest::BinarySearchIndexTest()
  {
  	_PointerList_ list;
  	Initialize(list, 10);
  	list.SortItems(Item::Compare);
  	assert(IsSorted(list));
  	
  	Item notInListLow(NOT_USED_ID);
  	Item notInListHigh(NOT_USED_ID_HIGH);
  	gData = (void*)0x4711;
  	
  	for (int32 i = 0; i < 10; i ++) {
  		Item* item = (Item*)list.ItemAt(i);
  		assert(item != NULL);
  		Value value(item->Value());
  
  		int index = IndexOf(list, item->Value());
  		int searchIndex;
  		searchIndex = list.BinarySearchIndex(item, Item::Compare);
  		assert(index == searchIndex);
  
  		searchIndex = list.BinarySearchIndex(item, ::Compare, gData);
  		assert(index == searchIndex);
  		
  		searchIndex = list.BinarySearchIndexByPredicate(&value, ValuePredicate);
  		assert(index == searchIndex);
  
  		// notInListLow
  		searchIndex = list.BinarySearchIndex(&notInListLow, Item::Compare);
  		assert(searchIndex == -1);
  
  		searchIndex = list.BinarySearchIndex(&notInListLow, ::Compare, gData);
  		assert(searchIndex == -1);
  		
  		value.value = notInListLow.Value();
  		searchIndex = list.BinarySearchIndexByPredicate(&value, ValuePredicate);
  		assert(searchIndex == -1);
  
  		// notInListHigh
  		searchIndex = list.BinarySearchIndex(&notInListHigh, Item::Compare);
  		assert(searchIndex == -(list.CountItems()+1));
  
  		searchIndex = list.BinarySearchIndex(&notInListHigh, ::Compare, gData);
  		assert(searchIndex == -(list.CountItems()+1));
  		
  		value.value = notInListHigh.Value();
  		searchIndex = list.BinarySearchIndexByPredicate(&value, ValuePredicate);
  		assert(searchIndex == -(list.CountItems()+1));
  	}
  
  	MakeEmpty(list);
  	
  	for (int i = 0; i < 3; i ++) {
  		list.AddItem(new Item(2 * i));
  	}
  	Item notInList(3);
  	assert(IndexOf(list, 3) == -1);
  	
  	int index = list.BinarySearchIndex(&notInList, Item::Compare);
  	assert (index == -3);
  	
  	index = list.BinarySearchIndex(&notInList, ::Compare, gData);
  	assert (index == -3);
  	
  	Value value(notInList.Value());
  	index = list.BinarySearchIndexByPredicate(&value, ValuePredicate);
  	assert (index == -3);
  		
  	MakeEmpty(list);
  }
  
  void PointerListTest::NullTest()
  {
  	_PointerList_ list;
  	Initialize(list, 10);
  	// R5 crashes
  	// list.EachElement(NULL, NULL);
  	// list.SortItems(NULL);
  	// list.SortItems(NULL, NULL);
  	// list.HSortItems(NULL);
  	// list.HSortItems(NULL, NULL);
  	// list.BinarySearch(NULL, NULL);
  	// list.BinarySearch(NULL, NULL, NULL);
  	// list.BinarySearchIndex(NULL, NULL);
  	// list.BinarySearchIndex(NULL, NULL, NULL);
  	// list.BinarySearchIndexByPredicate(NULL, NULL);
  	assert(!list.ReplaceItem(-1, NULL));
  	assert(!list.ReplaceItem(100, NULL));
  }
  
  void PointerListTest::Run() 
  {
  	CreationTest();	
  	OwningTest();
  	SortTest();
  	SortTestWithState();
  	EachElementTest();
  	BinarySearchTest();
  	BinarySearchIndexTest();
  	NullTest();
  }
  
  int main(int argc, char* argv[]) 
  {
  	// initialize srand with constant to get reproducable results
  	srand(0);
  	PointerListTest test;
  	test.Run();
  	AssertStatistics::GetInstance()->Print();
  }