summaryrefslogtreecommitdiff
path: root/yapf/unittest/test_binaryheap.h
diff options
context:
space:
mode:
authorKUDr <kudr@openttd.org>2006-05-27 16:12:16 +0000
committerKUDr <kudr@openttd.org>2006-05-27 16:12:16 +0000
commit5e73dce0e71791b87e5b096a890578eefcc26639 (patch)
treee4580db6e03032a997fce1392929b7190dc3b03d /yapf/unittest/test_binaryheap.h
parent3d01010440440cfbffd1e5d3b0cf1f23f0503a76 (diff)
downloadopenttd-5e73dce0e71791b87e5b096a890578eefcc26639.tar.xz
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
Diffstat (limited to 'yapf/unittest/test_binaryheap.h')
-rw-r--r--yapf/unittest/test_binaryheap.h103
1 files changed, 103 insertions, 0 deletions
diff --git a/yapf/unittest/test_binaryheap.h b/yapf/unittest/test_binaryheap.h
new file mode 100644
index 000000000..f0ba44749
--- /dev/null
+++ b/yapf/unittest/test_binaryheap.h
@@ -0,0 +1,103 @@
+/* $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;
+}
+