KUDr@3900: /* $Id$ */
KUDr@3900: 
KUDr@3900: // this test uses CData structure defined in test_autocopyptr.h
KUDr@3900: 
KUDr@3900: static int TestBinaryHeap1(bool silent)
KUDr@3900: {
KUDr@3900: 	CData::NumInstances() = 0;
KUDr@3900: 	int res = 0;
KUDr@3900: 	{
KUDr@3900: 		const int max_items = 10000;
KUDr@3900: 		const int total_adds = 1000000;
KUDr@3900: 		CBinaryHeapT<CData> bh(max_items);
KUDr@3900: 		CFixedSizeArrayT<CData, max_items> data;
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 		DBG("\nFilling BinaryHeap with %d items...", max_items);
KUDr@3900: 		CHECK_INT(0, bh.Size(), 0);
KUDr@3900: 		CHECK_INT(1, CData::NumInstances(), 0);
KUDr@3900: 		int i = 0;
KUDr@3900: 		for (; i < max_items; i++) {
KUDr@3900: 			CData& d = data.Add();
KUDr@3900: 			d.val = rand() & 0xFFFF;
KUDr@3900: 			bh.Push(d);
KUDr@3900: 		}
KUDr@3900: 		CHECK_INT(2, bh.Size(), max_items);
KUDr@3900: 		CHECK_INT(3, CData::NumInstances(), max_items);
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 		DBG("\nShaking items %d times...", total_adds);
KUDr@3900: 		int num_last = bh.GetHead().val;
KUDr@3900: 		for (i = 0; i < total_adds; i++) {
KUDr@3900: 			CData& d = bh.PopHead();
KUDr@3900: 			//printf("\nd->val = %d, num_last = %d", d->val, num_last);
KUDr@3900: 			CHECK_INT(4, d.val < num_last, 0);
KUDr@3900: 			if(d.val < num_last) {
KUDr@3900: 				printf("Sort error @ item %d", i);
KUDr@3900: 			}
KUDr@3900: 			num_last = d.val;
KUDr@3900: 			d.val += rand() & 0xFFFF;
KUDr@3900: 			bh.Push(d);
KUDr@3900: 		}
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 		DBG("\nDone!");
KUDr@3900: 		CHECK_INT(5, bh.Size(), max_items);
KUDr@3900: 		CHECK_INT(6, CData::NumInstances(), max_items);
KUDr@3900: 	}
KUDr@3900: 	CHECK_INT(7, CData::NumInstances(), 0);
KUDr@3900: 	return res;
KUDr@3900: }
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 
KUDr@3900: // this test uses CData and PData structures defined in test_autocopyptr.h
KUDr@3900: 
KUDr@3900: static int TestBinaryHeap2(bool silent)
KUDr@3900: {
KUDr@3900: 	CData::NumInstances() = 0;
KUDr@3900: 	int res = 0;
KUDr@3900: 	{
KUDr@3900: 		const int max_items = 10000;
KUDr@3900: 		const int total_adds = 1000000;
KUDr@3900: 		CBinaryHeapT<CData> bh(max_items);
KUDr@3900: 		CFixedSizeArrayT<CData, max_items> data;
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 		DBG("\nFilling BinaryHeap with %d items...", max_items);
KUDr@3900: 		CHECK_INT(0, bh.Size(), 0);
KUDr@3900: 		CHECK_INT(1, CData::NumInstances(), 0);
KUDr@3900: 		int i = 0;
KUDr@3900: 		for (; i < max_items; i++) {
KUDr@3900: 			CData& d = data.Add();
KUDr@3900: 			d.val = rand() & 0xFFFF;
KUDr@3900: 			bh.Push(d);
KUDr@3900: 		}
KUDr@3900: 		CHECK_INT(2, bh.Size(), max_items);
KUDr@3900: 		CHECK_INT(3, CData::NumInstances(), max_items);
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 		DBG("\nShaking items %d times...", total_adds);
KUDr@3900: 		int num_last = bh.GetHead().val;
KUDr@3900: 		for (i = 0; i < total_adds; i++) {
KUDr@3900: 			CData& d = bh.GetHead();
KUDr@3900: 			bh.RemoveHead();
KUDr@3900: 			//printf("\nd->val = %d, num_last = %d", d->val, num_last);
KUDr@3900: 			CHECK_INT(4, d.val < num_last, 0);
KUDr@3900: 			if(d.val < num_last) {
KUDr@3900: 				printf("Sort error @ item %d", i);
KUDr@3900: 			}
KUDr@3900: 			num_last = d.val;
KUDr@3900: 			d.val += rand() & 0xFFFF;
KUDr@3900: 			bh.Push(d);
KUDr@3900: 		}
KUDr@3900: 
KUDr@3900: 
KUDr@3900: 		DBG("\nDone!");
KUDr@3900: 		CHECK_INT(5, bh.Size(), max_items);
KUDr@3900: 		CHECK_INT(6, CData::NumInstances(), max_items);
KUDr@3900: 	}
KUDr@3900: 	CHECK_INT(7, CData::NumInstances(), 0);
KUDr@3900: 	return res;
KUDr@3900: }