fheap

commit 000c5265f306fedffdd99f5959dcbb79ce64098e
parent 4ef09af99e1a2bf1c81307f9cac3a2a8187d728e
Author: olikru <olikru@tkruger.se>
Date:   Thu, 11 Jan 2024 15:30:56 +0100

added simple unit tests

Diffstat:
M
test_fheap.c
 | 
115
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

1 file changed, 114 insertions(+), 1 deletion(-)
diff --git a/test_fheap.c b/test_fheap.c
@@ -3,6 +3,119 @@
 #include <assert.h>
 #include "fheap.h"
 
+static void test_fnode_inits() {
+  // test fnode init and clear
+  fnode_t node;
+  uint64_t nodev = 12;
+  uint64_t noded = 15;
+  fnode_init(&node, nodev, &noded);
+
+  assert(node.children == NULL);
+  assert(node.parent == NULL);
+  assert(node.left == &node);
+  assert(node.right == &node);
+  assert(node.nchildren == 0);
+  assert(node.marked == 0);
+
+  assert(node.value == nodev);
+  assert(node.data == &noded);
+}
+
+static void test_fnode_clear() {
+  // test fnode init and clear
+  fnode_t *node = malloc(sizeof(*node));
+  uint64_t nodev = 12;
+  uint64_t noded = 15;
+  fnode_init(node, nodev, &noded);
+  fnode_clear(node);
+}
+
+static void test_fnode_sort() {
+  // test to insert and then take out, in increasing order
+  uint64_t values[8] = {1, 5, 7, 0, 10, 3, 4, 11};
+  uint64_t data[8] =   {0, 1, 2, 3,  4, 5, 6,  7};
+  size_t i;
+  uint64_t *tmp;
+  fheap_t heap;
+
+  fheap_init(&heap);
+
+  for(i = 0; i < 8; i++) {
+    fheap_insert(&heap, values[i], &data[i]);
+  }
+
+  assert(fheap_extract_min((void*) &tmp, &heap) == 0);
+  assert(*tmp == 3);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 1);
+  assert(*tmp == 0);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 3);
+  assert(*tmp == 5);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 4);
+  assert(*tmp == 6);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 5);
+  assert(*tmp == 1);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 7);
+  assert(*tmp == 2);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 10);
+  assert(*tmp == 4);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 11);
+  assert(*tmp == 7);
+
+  // now the heap is empty
+  assert(fheap_extract_min((void*) &tmp, &heap) == UINT64_MAX);
+  assert(tmp == NULL);
+}
+
+static void test_fnode_with_decreases() {
+  uint64_t values[8] = {18, 5, 7, 16, 10, 3, 4, 11};
+  uint64_t data[8] =   {32, 1, 2, 11,  4, 5, 6,  7};
+  size_t i;
+  uint64_t *tmp;
+  fheap_t heap;
+
+  fheap_init(&heap);
+  fnode_t *nodes[8];
+
+  for(i = 0; i < 8; i++) {
+    nodes[i] = fheap_insert(&heap, values[i], &data[i]);
+  }
+
+  // decrease value of node[0] to 0, making it min
+  fheap_decrease_value(&heap, nodes[0], 0);
+  assert(heap.min == nodes[0]);
+
+  assert(fheap_extract_min((void*) &tmp, &heap) == 0);
+  assert(*tmp == 32);
+
+  // decrease value of node[7] to 8 making it come just
+  // after node[2] (with value 7)
+  fheap_decrease_value(&heap, nodes[7], 8);
+
+  assert(fheap_extract_min((void*) &tmp, &heap) == 3);
+  assert(*tmp == 5);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 4);
+  assert(*tmp == 6);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 5);
+  assert(*tmp == 1);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 7);
+  assert(*tmp == 2);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 8);
+  assert(*tmp == 7);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 10);
+  assert(*tmp == 4);
+  assert(fheap_extract_min((void*) &tmp, &heap) == 16);
+  assert(*tmp == 11);
+
+  // now the heap is empty
+  assert(fheap_extract_min((void*) &tmp, &heap) == UINT64_MAX);
+  assert(tmp == NULL);
+}
+
 int main() {
-  printf("test unimplemented\n");
+  test_fnode_inits();
+  test_fnode_clear();
+  test_fnode_sort();
+  test_fnode_with_decreases();
+
+  printf("tests ok\n");
 }