From 1710871aa1958c2cac38e4b372964ef22032ed4a Mon Sep 17 00:00:00 2001
From: Josh Rahm <joshuarahm@gmail.com>
Date: Sun, 6 Dec 2020 02:00:43 -0700
Subject: Added header files implementing a basic AVL tree and Map based off
 it.

These headers take inspiration from the linked list and array list
headers as a way to provide primitive templates in C. This time
they implement an AVL tree and Map template (which uses the AVL tree).

Included are relatively robust tests, though they could be improved.
---
 tests/test_avl_tree.c | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 149 insertions(+)
 create mode 100644 tests/test_avl_tree.c

(limited to 'tests/test_avl_tree.c')

diff --git a/tests/test_avl_tree.c b/tests/test_avl_tree.c
new file mode 100644
index 0000000..2a7260f
--- /dev/null
+++ b/tests/test_avl_tree.c
@@ -0,0 +1,149 @@
+#include "shared/avl_tree.h"
+#include "test_harness.h"
+
+#define integer_cmp_(a, b) (a - b)
+AVL_TREE_DECL(int);
+AVL_TREE_IMPL(int, integer_cmp_, null_dtor);
+
+static inline void avl_tree_debug_print(avl_tree_node_t(int) * node, int tab)
+{
+  if (node) {
+    avl_tree_debug_print(node->right, tab + 1);
+  }
+  for (int i = 0; i < tab; ++i) {
+    printf(" ");
+  }
+  if (!node) {
+    printf("(nil)\n");
+    return;
+  }
+  printf("%d\n", node->value);
+  avl_tree_debug_print(node->left, tab + 1);
+}
+
+TEST(avl_tree, insert)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+  avl_tree_insert(int)(tree, 5);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 1);
+
+  avl_tree_insert(int)(tree, 4);
+  avl_tree_insert(int)(tree, 6);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 3);
+  ASSERT_EQ(avl_tree_height(int)(tree), 2);
+
+  return 0;
+}
+
+TEST(avl_tree, insert_rotate_asc)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  avl_tree_insert(int)(tree, 1);
+  avl_tree_insert(int)(tree, 2);
+  avl_tree_insert(int)(tree, 3);
+  avl_tree_insert(int)(tree, 4);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 4);
+  ASSERT_EQ(avl_tree_height(int)(tree), 3);
+
+  return 0;
+}
+
+TEST(avl_tree, insert_rotate_desc)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  avl_tree_insert(int)(tree, 4);
+  avl_tree_insert(int)(tree, 3);
+  avl_tree_insert(int)(tree, 2);
+  avl_tree_insert(int)(tree, 1);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 4);
+  ASSERT_EQ(avl_tree_height(int)(tree), 3);
+
+  return 0;
+}
+
+TEST(avl_tree_erase, erase)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  avl_tree_insert(int)(tree, 4);
+  avl_tree_insert(int)(tree, 3);
+  avl_tree_insert(int)(tree, 2);
+  avl_tree_insert(int)(tree, 1);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 4);
+  ASSERT_EQ(avl_tree_height(int)(tree), 3);
+
+  int out;
+  bool b = avl_tree_erase(int)(tree, 3, &out);
+
+  ASSERT_EQ(b, 1);
+  ASSERT_EQ(out, 3);
+  ASSERT_EQ(avl_tree_size(int)(tree), 3);
+  ASSERT_EQ(avl_tree_height(int)(tree), 2);
+
+  b = avl_tree_erase(int)(tree, 1, &out);
+
+  ASSERT_EQ(b, 1);
+  ASSERT_EQ(out, 1);
+  ASSERT_EQ(avl_tree_size(int)(tree), 2);
+  ASSERT_EQ(avl_tree_height(int)(tree), 2);
+
+  return 0;
+}
+
+TEST(avl_tree, erase_onesided)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+  for (int i = 0; i < 16; ++i) {
+    avl_tree_insert(int)(tree, i);
+  }
+
+  ASSERT_EQ(avl_tree_erase(int)(tree, 0, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 1, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 2, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 3, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 4, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 5, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 6, NULL), 1);
+
+  ASSERT_EQ(avl_tree_height(int)(tree), 4);
+  ASSERT_EQ(avl_tree_size(int)(tree), 9);
+
+  avl_tree_free(int)(tree);
+  ASSERT_TRUE(debug_is_heap_empty());
+
+  return 0;
+}
+
+TEST(avl_tree, find)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  for (int i = 0; i < 16; ++ i) {
+    avl_tree_insert(int)(tree, i);
+  }
+
+  ASSERT_EQ(*avl_tree_find(int)(tree, 4), 4);
+  ASSERT_EQ(*avl_tree_find(int)(tree, 3), 3);
+  ASSERT_EQ(*avl_tree_find(int)(tree, 15), 15);
+
+  ASSERT_EQ(avl_tree_find(int)(tree, 100), NULL);
+
+  return 0;
+}
+
+TEST (avl_tree, stress)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+  for (int i = 0; i < 512; ++ i) {
+    avl_tree_insert(int)(tree, i);
+  }
+
+  return 0;
+}
-- 
cgit