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

AvlTree insert_nonrecursive(elem_t x, AvlTree t)
{
    Position tmp;
    Position prev[100] ;
    Position p = t;
    int i = 0;
    int j;

    /* index 0 not used */
    prev[i] = p;
    while(p) {
        if(x < p->elem) {
            prev[++i] = p;
            p = p->left;
        } else if(x > p->elem) {
            prev[++i] = p;
            p = p->right;
        } else
            return t;
    }

    tmp = malloc(sizeof(struct AvlNode));
    tmp->elem = x;
    tmp->left = tmp->right = NULL;
    tmp->height = 0;

    if(!prev[i]) {
        return tmp;
    } else if(x < prev[i]->elem) {
        prev[i]->left = tmp;
        prev[i]->height++;
        if(i - 1 > 0) {
            if(prev[i - 1]->left == prev[i]
                    && prev[i]->height - height(prev[i - 1]->right) == 2)
                prev[i - 2] = single_rotate_with_left(prev[i - 1]);
            else if(prev[i - 1]->right == prev[i]
                    && prev[i]->height - height(prev[i - 1]->left) == 2)
                prev[i - 2] = double_rotate_with_left(prev[i - 1]);
        }
    }
    else {
        prev[i]->right = tmp;
        prev[i]->height++;
        if(i - 1 > 0) {
            if(prev[i - 1]->right == prev[i]
			   && prev[i]->height - height(prev[i - 1]->left) == 2)
                prev[i - 2] = single_rotate_with_right(prev[i - 1]);
            else if(prev[i - 1]->left == prev[i]
                    && prev[i]->height - height(prev[i - 1]->right) == 2) {
                prev[i - 2] = double_rotate_with_right(prev[i - 2]);
            }
        }
    }

    return t;
}

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

}

void test()
{
    int i;
    AvlTree t = NULL;

    for(i = 0; i < 3; i++) {
        t = insert_nonrecursive(i + 1, t);
    }

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

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