1 files changed, 149 insertions, 0 deletions
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;
+}