summaryrefslogtreecommitdiff
path: root/yapf/unittest/test_binaryheap.h
blob: 114f8698594c14b09a752ca9f1bc089d3e4c5e44 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/* $Id$ */

// this test uses CData structure defined in test_autocopyptr.h

static int TestBinaryHeap1(bool silent)
{
	CData::NumInstances() = 0;
	int res = 0;
	{
		const int max_items = 10000;
		const int total_adds = 1000000;
		CBinaryHeapT<CData> bh(max_items);
		CFixedSizeArrayT<CData, max_items> data;


		DBG("\nFilling BinaryHeap with %d items...", max_items);
		CHECK_INT(0, bh.Size(), 0);
		CHECK_INT(1, CData::NumInstances(), 0);
		int i = 0;
		for (; i < max_items; i++) {
			CData& d = data.Add();
			d.val = rand() & 0xFFFF;
			bh.Push(d);
		}
		CHECK_INT(2, bh.Size(), max_items);
		CHECK_INT(3, CData::NumInstances(), max_items);


		DBG("\nShaking items %d times...", total_adds);
		int num_last = bh.GetHead().val;
		for (i = 0; i < total_adds; i++) {
			CData& d = bh.PopHead();
			//printf("\nd->val = %d, num_last = %d", d->val, num_last);
			CHECK_INT(4, d.val < num_last, 0);
			if(d.val < num_last) {
				printf("Sort error @ item %d", i);
			}
			num_last = d.val;
			d.val += rand() & 0xFFFF;
			bh.Push(d);
		}


		DBG("\nDone!");
		CHECK_INT(5, bh.Size(), max_items);
		CHECK_INT(6, CData::NumInstances(), max_items);
	}
	CHECK_INT(7, CData::NumInstances(), 0);
	return res;
}



// this test uses CData and PData structures defined in test_autocopyptr.h

static int TestBinaryHeap2(bool silent)
{
	CData::NumInstances() = 0;
	int res = 0;
	{
		const int max_items = 10000;
		const int total_adds = 1000000;
		CBinaryHeapT<CData> bh(max_items);
		CFixedSizeArrayT<CData, max_items> data;


		DBG("\nFilling BinaryHeap with %d items...", max_items);
		CHECK_INT(0, bh.Size(), 0);
		CHECK_INT(1, CData::NumInstances(), 0);
		int i = 0;
		for (; i < max_items; i++) {
			CData& d = data.Add();
			d.val = rand() & 0xFFFF;
			bh.Push(d);
		}
		CHECK_INT(2, bh.Size(), max_items);
		CHECK_INT(3, CData::NumInstances(), max_items);


		DBG("\nShaking items %d times...", total_adds);
		int num_last = bh.GetHead().val;
		for (i = 0; i < total_adds; i++) {
			CData& d = bh.GetHead();
			bh.RemoveHead();
			//printf("\nd->val = %d, num_last = %d", d->val, num_last);
			CHECK_INT(4, d.val < num_last, 0);
			if(d.val < num_last) {
				printf("Sort error @ item %d", i);
			}
			num_last = d.val;
			d.val += rand() & 0xFFFF;
			bh.Push(d);
		}


		DBG("\nDone!");
		CHECK_INT(5, bh.Size(), max_items);
		CHECK_INT(6, CData::NumInstances(), max_items);
	}
	CHECK_INT(7, CData::NumInstances(), 0);
	return res;
}