#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;
}