feat: build a meldable heap

6 files changed, 204 insertions, 3 deletions

diff --git a/src/03/07/README.md b/src/03/07/README.md
index 2024b4e..9df3078 100644
--- a/src/03/07/README.md
+++ b/src/03/07/README.md
@@ -1,4 +1,3 @@
-
 Implement the `remove(u)` method, that removes the node `u` from a
 `MeldableHeap`. This method should run in `O(log n)` expected time.
 
@@ -38,3 +37,7 @@ class MeldableHeap {
 }
 ```
 [Source](https://www.aupress.ca/app/uploads/120226_99Z_Morin_2013-Open_Data_Structures.pdf)
+
+
+
+An implementation of `meldable_heap_remove(u)` can be found in `./meldable_heap.c`.
diff --git a/src/03/Makefile b/src/03/Makefile
index dfaa109..c3aae26 100644
--- a/src/03/Makefile
+++ b/src/03/Makefile
@@ -5,8 +5,8 @@ CC=clang
 TEST_LIBS = -lcgreen
 
 BUILDDIR := build
-OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o sort.o graph.o matrix.o)
-TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o sort_test.o graph_test.o matrix_test.o)
+OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o sort.o graph.o matrix.o meldable_heap.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o sort_test.o graph_test.o matrix_test.o meldable_heap_test.o)
 
 $(BUILDDIR)/%.o : %.c
 	$(COMPILE.c) $(OUTPUT_OPTION) $<
diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c
index 0d280ae..857ae7c 100644
--- a/src/03/avl_tree_test.c
+++ b/src/03/avl_tree_test.c
@@ -383,12 +383,14 @@ TestSuite *graph_tests();
 TestSuite *matrix_tests();
 TestSuite *rb_tree_tests();
 TestSuite *sort_tests();
+TestSuite *meldable_heap_tests();
 
 int main(int argc, char **argv) {
   TestSuite *suite = create_test_suite();
   add_suite(suite, avl_tree_tests());
   add_suite(suite, graph_tests());
   add_suite(suite, matrix_tests());
+  add_suite(suite, meldable_heap_tests());
   add_suite(suite, rb_tree_tests());
   add_suite(suite, sort_tests());
   return run_test_suite(suite, create_text_reporter());
diff --git a/src/03/meldable_heap.c b/src/03/meldable_heap.c
new file mode 100644
index 0000000..710d846
--- /dev/null
+++ b/src/03/meldable_heap.c
@@ -0,0 +1,81 @@
+#include "meldable_heap.h"
+#include <stddef.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+static int compare(int a, int b)
+{
+  return (a < b) ? -1 : ((a > b) ? 1 : 0);
+}
+
+static void print_tree(MeldableHeap *heap, int level) {
+  for (int i = 0; i < level; i++)
+    printf(" ");
+
+  if (heap) {
+    printf("(%d)\n", heap->value);
+
+    if (!heap->left && !heap->right)
+      return;
+    print_tree(heap->left, level + 1);
+    print_tree(heap->right, level + 1);
+  }
+  else {
+    printf("( )\n");
+  }
+}
+
+
+MeldableHeap *meldable_heap_initialize(int value) {
+  MeldableHeap *heap = malloc(sizeof(MeldableHeap));
+  heap->left = NULL;
+  heap->right = NULL;
+  heap->parent = NULL;
+  heap->value = value;
+  return heap;
+};
+
+MeldableHeap *meldable_heap_add(MeldableHeap *heap, int value) {
+  MeldableHeap *root = meldable_heap_merge(meldable_heap_initialize(value), heap);
+  root->parent = NULL;
+  return root;
+}
+
+MeldableHeap *meldable_heap_merge(MeldableHeap *h1, MeldableHeap* h2) {
+  if (h1 == NULL) return h2;
+  if (h2 == NULL) return h1;
+
+  if (compare(h2->value, h1->value) < 0)
+    return meldable_heap_merge(h2, h1);
+
+  if (rand() % 2 == 0) {
+    h1->left = meldable_heap_merge(h1->left, h2);
+    h1->left->parent = h1;
+  }
+  else {
+    h1->right = meldable_heap_merge(h1->right, h2);
+    h1->right->parent = h1;
+  }
+  return h1;
+}
+
+void meldable_heap_inspect(MeldableHeap *heap)
+{
+  print_tree(heap, 0);
+}
+
+void meldable_heap_remove(MeldableHeap *heap)
+{
+  MeldableHeap *replacement = meldable_heap_merge(heap->left, heap->right);
+
+  if (replacement)
+    replacement->parent = heap->parent;
+
+  if (!heap->parent)
+    return;
+
+  if (heap->parent->left == heap)
+    heap->parent->left = replacement;
+  else
+    heap->parent->right = replacement;
+}
diff --git a/src/03/meldable_heap.h b/src/03/meldable_heap.h
new file mode 100644
index 0000000..660691c
--- /dev/null
+++ b/src/03/meldable_heap.h
@@ -0,0 +1,12 @@
+typedef struct mnode {
+  struct mnode *left;
+  struct mnode *parent;
+  struct mnode *right;
+  int value;
+} MeldableHeap;
+
+MeldableHeap *meldable_heap_initialize(int value);
+MeldableHeap *meldable_heap_add(MeldableHeap *heap, int value);
+MeldableHeap *meldable_heap_merge(MeldableHeap *heap, MeldableHeap* other);
+void meldable_heap_inspect(MeldableHeap *heap);
+void meldable_heap_remove(MeldableHeap *heap);
diff --git a/src/03/meldable_heap_test.c b/src/03/meldable_heap_test.c
new file mode 100644
index 0000000..a8503e0
--- /dev/null
+++ b/src/03/meldable_heap_test.c
@@ -0,0 +1,103 @@
+#include "meldable_heap.h"
+#include <cgreen/cgreen.h>
+#include <string.h>
+
+Ensure(add_inserts_item_into_right_subtree) {
+  MeldableHeap *heap = meldable_heap_initialize(5);
+  heap = meldable_heap_add(heap, 3);
+
+  assert_that(heap->value, is_equal_to(3));
+  assert_that(heap->right->value, is_equal_to(5));
+}
+
+Ensure(add_inserts_item_into_left_subtree) {
+  MeldableHeap *heap = meldable_heap_initialize(5);
+  heap = meldable_heap_add(heap, 8);
+
+  assert_that(heap->value, is_equal_to(5));
+  assert_that(heap->right->value, is_equal_to(8));
+}
+
+/*
+          (1)
+        /      \
+      (3)      (2)
+     /  \     /   \
+  (10)  (6) (7)   (4)
+           /  \   /
+         (9)  (8)(5)
+*/
+Ensure(add_inserts_multiple_items_into_the_subtree) {
+  MeldableHeap *heap = NULL;
+
+  for (int i = 1; i <= 10; ++i)
+    heap = meldable_heap_add(heap, i);
+
+  assert_that(heap->value, is_equal_to(1));
+
+  assert_that(heap->right->value, is_equal_to(2));
+  assert_that(heap->right->right->value, is_equal_to(4));
+  assert_that(heap->right->right->left->value, is_equal_to(5));
+
+  assert_that(heap->right->left->value, is_equal_to(7));
+  assert_that(heap->right->left->left->value, is_equal_to(9));
+  assert_that(heap->right->left->right->value, is_equal_to(8));
+
+  assert_that(heap->left->value, is_equal_to(3));
+  assert_that(heap->left->left->value, is_equal_to(10));
+  assert_that(heap->left->right->value, is_equal_to(6));
+}
+
+/*
+          (1)
+        /      \
+      (3)      (2)
+     /  \     /   \
+  (10)  (6) (7)   (4)
+           /  \   /
+         (9)  (8)(5)
+
+         to
+
+          (1)
+        /      \
+      (3)      (2)
+     /  \     /   \
+  (10)  (6)       (4)
+           /  \   /
+         (9)  (8)(5)
+*/
+Ensure(remove_removes_the_node_from_the_tree) {
+  MeldableHeap *heap = NULL;
+
+  for (int i = 1; i <= 10; ++i)
+    heap = meldable_heap_add(heap, i);
+
+  meldable_heap_inspect(heap);
+  meldable_heap_remove(heap->right->left);
+  meldable_heap_inspect(heap);
+
+  assert_that(heap->value, is_equal_to(1));
+
+  assert_that(heap->right->value, is_equal_to(2));
+  assert_that(heap->right->right->value, is_equal_to(4));
+  assert_that(heap->right->right->left->value, is_equal_to(5));
+
+  assert_that(heap->right->left->value, is_equal_to(8));
+  assert_that(heap->right->left->left->value, is_equal_to(9));
+  assert_that(heap->right->left->right, is_equal_to(NULL));
+
+  assert_that(heap->left->value, is_equal_to(3));
+  assert_that(heap->left->left->value, is_equal_to(10));
+  assert_that(heap->left->right->value, is_equal_to(6));
+}
+
+TestSuite *meldable_heap_tests() {
+  TestSuite *x = create_test_suite();
+
+  add_test(x, add_inserts_item_into_right_subtree);
+  add_test(x, add_inserts_item_into_left_subtree);
+  add_test(x, add_inserts_multiple_items_into_the_subtree);
+  add_test(x, remove_removes_the_node_from_the_tree);
+  return x;
+}