// AVL Tree
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

/* utils */
#include "util.h"

// TODO: [x] Review: http://www.inr.ac.ru/~info21/ADen/
//       [x] Tests:  https://stackoverflow.com/q/3955680

typedef int T;

struct tree_node {
	struct tree_node *left, *right;
	int bal;
	T key;
	int count;	/* collision counter */
	/* ggf. weitere Felder... */
};

static struct tree_node *
insert_r(T x, struct tree_node *p, bool *h)
{
	struct tree_node *p1, *p2;

	if ( p == NULL ) {
		*h = true;

		p = malloc(sizeof *p);
		if ( p != NULL ) {
			p->left = NULL;
			p->right = NULL;
			p->bal = 0;

			p->key = x;
			p->count = 1;	/* hit counter */
		}
		else
			ERROR("out of memory");
	}
	else if ( x < p->key ) {
		p->left = insert_r(x, p->left, h);

		if ( *h ) {
			if ( p->bal == +1 ) {
				p->bal = 0;
				*h = false;
			}
			else if ( p->bal == 0 ) {
				p->bal = -1;
			}
			else /* if ( p->bal == -1 ) */ {
				p1 = p->left;
				if ( p1->bal == -1 ) {	/* single LL rotation */
					p->left = p1->right; p1->right = p;
					p->bal = 0; p = p1;
				}
				else {					/* double LR rotation */
					p2 = p1->right;
					p1->right = p2->left; p2->left = p1;
					p->left = p2->right; p2->right = p;
					p->bal  = ( p2->bal == -1 ) ? +1 : 0;
					p1->bal = ( p2->bal == +1 ) ? -1 : 0;
					p = p2;
				}
				p->bal = 0;
				*h = false;
			}
		}
	}
	else if ( x > p->key ) {
		p->right = insert_r(x, p->right, h);

		if ( *h ) {
			if ( p->bal == -1 ) {
				p->bal = 0;
				*h = false;
			}
			else if ( p->bal == 0 ) {
				p->bal = +1;
			}
			else /* if ( p->bal == +1 ) */ {
				p1 = p->right;
				if ( p1->bal == +1 ) {	/* single RR rotation */
					p->right = p1->left; p1->left = p;
					p->bal = 0; p = p1;
				}
				else {					/* double RL rotation */
					p2 = p1->left;
					p1->left = p2->right; p2->right = p1;
					p->right = p2->left; p2->left = p;
					p->bal  = ( p2->bal == +1 ) ? -1 : 0;
					p1->bal = ( p2->bal == -1 ) ? +1 : 0;
					p = p2;
				}
				p->bal = 0;
				*h = false;
			}
		}
	}
	else {
		/* handle collision! */
		p->count++;	/* hit counter */
		*h = false;
	}
	if ( p == NULL )
		ERROR("das hier sollte niemals passieren");
	return p;
}

struct tree_node *
insert(struct tree_node *tree, T data)
{
	bool h = false;
	return insert_r(data, tree, &h);
}

static struct tree_node *
balanceL(struct tree_node *p, bool *h)
{
	if ( p->bal == -1 ) {
		p->bal = 0;
	}
	else if ( p->bal == 0 ) {
		p->bal = +1;
		*h = false;
	}
	else /* if ( p->bal == +1 ) */ {		/* rebalance */
		struct tree_node *p1 = p->right;
		if ( p1->bal >= 0 ) {				/* singla RR rotation */
			p->right = p1->left; 
			p1->left = p;
			if ( p1->bal == 0 ) {
				p->bal = +1;
				p1->bal = -1;
				*h = false;
			}
			else {
				p->bal = 0;
				p1->bal = 0;
			}
			p = p1;
		}
		else {								/* double RL rotation */
			struct tree_node *p2 = p1->left;
			p1->left = p2->right;
			p2->right = p1;
			p->right = p2->left;
			p2->left = p;
			p->bal  = ( p2->bal == +1 ) ? -1 : 0;
			p1->bal = ( p2->bal == -1 ) ? +1 : 0;
			p = p2;
			p2->bal = 0;
		}
	}
	return p;
}

static struct tree_node *
balanceR(struct tree_node *p, bool *h)
{
	if ( p->bal == +1 ) {
		p->bal = 0;
	}
	else if ( p->bal == 0 ) {
		p->bal = -1;
		*h = false;
	}
	else /* p->bal == -1 */ {		/* rebalance */
		struct tree_node *p1 = p->left;
		if ( p1->bal <= 0 ) {		/* single LL rotation */
			p->left = p1->right; 
			p1->right = p;
			if ( p1->bal == 0 ) {
				p->bal = -1;
				p1->bal = +1;
				*h = false;
			}
			else {
				p->bal = 0;
				p1->bal = 0;
			}
			p = p1;
		}
		else {						/* double LR rotation */
			struct tree_node *p2 = p1->right;
			p1->right = p2->left;
			p2->left = p1;
			p->left = p2->right;
			p2->right = p;
			p->bal  = ( p2->bal == -1 ) ? +1 : 0;
			p1->bal = ( p2->bal == +1 ) ? -1 : 0;
			p = p2;
			p2->bal = 0;
		}
	}
	return p;
}

static void
del(struct tree_node **q, struct tree_node **r, bool *h)
{
	if ( (*r)->right != NULL ) {
		del(q, &(*r)->right, h);
		if ( *h ) 
			*r = balanceR(*r, h);
	}
	else {
		/* copy data */
		(*q)->key = (*r)->key;
		(*q)->count = (*r)->count;

		*q = *r;
		*r = (*r)->left;
		*h = true;
	}
}

static struct tree_node *
delete_r(T x, struct tree_node *p, bool *h)
{
	if ( p == NULL ) {
		ERROR("key not found");
	}
	else if ( x < p->key ) {
		p->left = delete_r(x, p->left, h);
		if ( *h )
			p = balanceL(p, h);
	}
	else if ( x > p->key ) {
		p->right = delete_r(x, p->right, h);
		if ( *h )
			p = balanceR(p, h);
	}
	else /* if ( x == p->key ) */ {
		struct tree_node *q = p;
		if ( q->right == NULL ) {
			p = q->left;
			*h = true;
		}
		else if ( q->left == NULL ) {
			p = q->right;
			*h = true;
		}
		else {
			del(&q, &q->left, h);
			if ( *h )
				p = balanceL(p, h);
		}
		free(q);
	}
	return p;
}

struct tree_node *
delete(struct tree_node *tree, T data)
{
	bool h = false;
	return delete_r(data, tree, &h);
}


// aux display and verification routines, helpful but not essential
struct trunk {
	struct trunk *prev;
	char * str;
};
 
void show_trunks(struct trunk *p)
{
	if (!p) return;
	show_trunks(p->prev);
	printf("%s", p->str);
}
 
// this is very haphazzard
void show_tree(struct tree_node *root, struct trunk *prev, int is_left)
{
	if (root == NULL) return;

	struct trunk this_disp = { prev, "    " };
	char *prev_str = this_disp.str;
	show_tree(root->right, &this_disp, 1);

	if (!prev)
		this_disp.str = "---";
	else if (is_left) {
		this_disp.str = ".--";
		prev_str = "   |";
	} else {
		this_disp.str = "`--";
		prev->str = prev_str;
	}

	show_trunks(&this_disp);
	if ( root->key >= 'A' && root->key <= 'Z' )
		printf("%c\n", root->key);
	else
		printf("%d\n", root->key);

	if (prev) prev->str = prev_str;
	this_disp.str = "   |";

	show_tree(root->left, &this_disp, 0);
	if (!prev) puts("");
}

void
print(struct tree_node *tree)
{
	if ( tree ) {
		print(tree->left);
		printf("%d (%d)\n", tree->key, tree->bal);
		print(tree->right);
	}
}

int
main()
{


#if 0	/* 1a/b */
	tree = insert(tree, 20);
	tree = insert(tree,  4);
	show_tree(tree, 0, 0);

	//tree = insert(tree, 15);
	tree = insert(tree,  8);
	show_tree(tree, 0, 0);
#endif

#if 0	/* 2a/b */
	tree = insert(tree, 20);
	tree = insert(tree,  4);
	tree = insert(tree, 26);
	tree = insert(tree,  3);
	tree = insert(tree,  9);
	show_tree(tree, 0, 0);

	//tree = insert(tree, 15);
	tree = insert(tree,  8);
	show_tree(tree, 0, 0);
#endif

#if 0	/* 3a/b */
	tree = insert(tree, 20);
	tree = insert(tree,  4);
	tree = insert(tree, 26);
	tree = insert(tree,  3);
	tree = insert(tree,  9);
	tree = insert(tree, 21);
	tree = insert(tree, 30);
	tree = insert(tree,  2);
	tree = insert(tree,  7);
	tree = insert(tree, 11);
	show_tree(tree, 0, 0);

	//tree = insert(tree, 15);
	tree = insert(tree,  8);
	show_tree(tree, 0, 0);
#endif

#if 0
	tree = insert(tree, 2);
	tree = insert(tree, 1);
	tree = insert(tree, 4);
	tree = insert(tree, 3);
	tree = insert(tree, 5);
	show_tree(tree, 0, 0);

	tree = delete(tree, 1);
	show_tree(tree, 0, 0);
#endif

#if 0
	tree = insert(tree,  6);
	tree = insert(tree,  2);
	tree = insert(tree,  9);
	tree = insert(tree,  1);
	tree = insert(tree,  4);
	tree = insert(tree,  8);
	tree = insert(tree,  'B');
	tree = insert(tree,  3);
	tree = insert(tree,  5);
	tree = insert(tree,  7);
	tree = insert(tree,  'A');
	tree = insert(tree,  'C');
	tree = insert(tree,  'D');
	show_tree(tree, 0, 0);

	tree = delete(tree, 1);
	show_tree(tree, 0, 0);
#endif


#if 0
	tree = insert(tree,  5);
	tree = insert(tree,  2);
	tree = insert(tree,  8);
	tree = insert(tree,  1);
	tree = insert(tree,  3);
	tree = insert(tree,  7);
	tree = insert(tree,  'A');
	tree = insert(tree,  4);
	tree = insert(tree,  6);
	tree = insert(tree,  9);
	tree = insert(tree,  'B');
	tree = insert(tree,  'C');
	show_tree(tree, 0, 0);

	tree = delete(tree, 1);
	show_tree(tree, 0, 0);
#endif


#if 0
	tree = insert(tree,  5);
	tree = insert(tree,  3);
	tree = insert(tree,  8);
	tree = insert(tree,  2);
	tree = insert(tree,  4);
	tree = insert(tree,  7);
	tree = insert(tree, 10);
	tree = insert(tree,  1);
	tree = insert(tree,  6);
	tree = insert(tree,  9);
	tree = insert(tree, 11);

	tree = delete(tree,  4);
	tree = delete(tree,  8);
	tree = delete(tree,  6);
	tree = delete(tree,  5);
	tree = delete(tree,  2);
	tree = delete(tree,  1);
	tree = delete(tree,  7);

	show_tree(tree, 0, 0);
#endif

	struct tree_node *tree = NULL;

	srand(time(NULL));
	for ( int i = 0; i != 300000; ++i )
		tree = insert(tree, rand());

	//show_tree(tree, 0, 0);

	return EXIT_SUCCESS;
}