#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "avl_tree.h"
#include "print_ascii_tree.h"

AvlTree make_empty(AvlTree t)
{
    if(t != NULL) {
        make_empty(t->left);
        make_empty(t->right);
        free(t);
    }

    return NULL;
}

Position find(elem_t x, AvlTree t)
{
    if(t == NULL)
        return NULL;
    else if(x == t->elem)
        return t;
    else if(x > t->elem)
        return find(x, t->right);
    else if(x < t->elem)
        return find(x, t->left);
}

Position find_min(AvlTree t)
{
    if(t == NULL)
        return NULL;
    else if(t->left == NULL)
        return t;
    else
        return find_min(t->left);
}

Position find_max(AvlTree t)
{
    if(t == NULL)
        return NULL;
    else if(t->right == NULL)
        return t;
    else
        return find_max(t->right);
}

static int height(Position p)
{
    return p == NULL ? -1 : p->height;
}

static Position single_rotate_with_left(Position p)
{
    Position p_left;

    p_left = p->left;
    p->left = p_left->right;
    p_left->right = p;

    /* derectly use ->height may case some problem */
    p->height = MAX(height(p->left), height(p->right)) + 1;
    p_left->height = MAX(height(p_left->left), p->height) + 1;

    /* return new Node */
    return p_left;
}

static Position single_rotate_with_right(Position p)
{
    Position p_right;

    p_right = p->right;
    p->right = p_right->left;
    p_right->left = p;

    p->height = MAX(height(p->left), height(p->right)) + 1;
    p_right->height = MAX(height(p_right->right), p->height) + 1;

    /* return new node */
    return p_right;

}

static Position double_rotate_with_left(Position p)
{
    p->left = single_rotate_with_right(p->left);

    return single_rotate_with_left(p);
}


static Position double_rotate_with_right(Position p)
{

    p->right = single_rotate_with_left(p->right);

    return single_rotate_with_right(p);
}

AvlTree insert(elem_t x, AvlTree t)
{
    if(t == NULL) {
        t = malloc(sizeof(struct AvlNode));
        t->elem = x;
        t->height = 0;
        t->left = t->right = NULL;
    } else if(x > t->elem) {
        t->right = insert(x, t->right);
        /* > 1 or == 2? */
        if(height(t->right) - height(t->left) > 1) {
            if(x > t->right->elem)
                t = single_rotate_with_right(t);
            if(x < t->right->elem)
                t = double_rotate_with_right(t);
        }
    } else if(x < t->elem) {
        t->left = insert(x, t->left);

        if(height(t->left) - height(t->right) == 2) {
            if(x < t->left->elem)
                t = single_rotate_with_left(t);
            if(x > t->left->elem)
                t = double_rotate_with_left(t);
        }
    }

    /* else do nothing, but update the height */
    t->height = MAX(height(t->left), height(t->right)) + 1;

    return t;
}

/* lazy delete ? */
AvlTree delete(elem_t x, AvlTree t)
{

}

void test()
{
    AvlTree t = NULL;

    t = insert(4, t);
    t = insert(3, t);
    t = insert(2, t);
    t = insert(1, t);
    t = insert(8, t);
    t = insert(9, t);

    printf("min:%d\n", find_min(t)->elem);
    printf("max:%d\n", find_max(t)->elem);
    printf("find 2:%d\n", find(2, t)->elem);
    print_ascii_tree(t);
}

int main()
{
    test();
    return 0;
}