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

	#define _path_left	0
	#define _path_right	1

	#define _balance_lh	-1
	#define _balance_rh	1
	#define _balance_eh	0

	typedef struct avl_node_def avl_node_t;
	
	struct avl_node_def {
		avl_node_t *paths[2];
		unsigned int key;
		char balance;
	};

	avl_node_t *tree = 0;

	#define _stack_max	0x0100
	#define _stack_min	0x0000

	avl_node_t *route_stack[_stack_max];
	unsigned int route_index = (_stack_max-1);

	#define _ret_success	1
	#define _ret_failure	0

	inline void init_routestack() {
		route_index = (_stack_max-1);

		for(unsigned int init_c = 0; init_c < _stack_max; init_c++)
			route_stack[init_c] = 0;
	}

	inline char push_node(avl_node_t *node) {
		if(route_index > _stack_min) {
			route_stack[route_index--] = node;
			return _ret_success;
		} else return _ret_failure;
	}

	inline avl_node_t *pop_node() {
		if(route_index < _stack_max) {
			avl_node_t *retnode = route_stack[++route_index];
			route_stack[route_index] = 0;
			return retnode;
		} else return (avl_node_t*)_ret_failure;
	}

	void dump_routestack() {
		for(unsigned int dump_c = 0; dump_c < _stack_max; dump_c++) {
			printf(" [ %d ] -> ", dump_c);
			if(route_stack[dump_c]) printf("Node %d\r\n", route_stack[dump_c]->key); 
			else printf("NULL.\r\n");
		}
	}	

	avl_node_t *rotate_left(avl_node_t *node) {
		avl_node_t *new_root = node->paths[_path_right];
		node->paths[_path_right] = new_root->paths[_path_left];
		new_root->paths[_path_left] = node;
		return new_root;
	}

	avl_node_t *rotate_right(avl_node_t *node) {
		avl_node_t *new_root = node->paths[_path_left];
		node->paths[_path_left] = new_root->paths[_path_right];
		new_root->paths[_path_right] = node;
		return new_root;
	}
 
	avl_node_t *rebalance_left(avl_node_t *node, char mode) {
		avl_node_t *xnode = node->paths[_path_left];
		avl_node_t *ynode = xnode->paths[_path_right];

		if(xnode->balance > _balance_eh) {
			if(ynode->balance < _balance_eh) {
				xnode->balance = _balance_eh;
				ynode->balance = _balance_eh;
				node->balance = _balance_rh;
			} else if(ynode->balance > _balance_eh) {
				xnode->balance = _balance_lh;
				ynode->balance = _balance_eh;
				node->balance = _balance_eh;
			} else if(ynode->balance == _balance_eh) {
				xnode->balance = _balance_eh;
				ynode->balance = _balance_eh;
				node->balance = _balance_eh;
			}
			node->paths[_path_left] = rotate_left(xnode);
		} else {
/*			if((mode == 1) && \
			   (xnode->paths[_path_left] != 0) && \
			   (xnode->paths[_path_right] != 0)) {
				xnode->balance = _balance_rh;
				node->balance = _balance_lh;
*/
			if((mode == 1) && \
			   (xnode->balance == 0)) {
				xnode->balance = _balance_rh;
				node->balance = _balance_lh;
			} else {
				node->balance = _balance_eh;
				xnode->balance = _balance_eh;
			}
		}
		return rotate_right(node);
	}

	avl_node_t *rebalance_right(avl_node_t *node, char mode) {
		avl_node_t *xnode = node->paths[_path_right];
		avl_node_t *ynode = xnode->paths[_path_left];

		if(xnode->balance < _balance_eh) {
			if(ynode->balance > _balance_eh) {
				xnode->balance = _balance_eh;
				ynode->balance = _balance_eh;
				node->balance = _balance_lh;
			} else if(ynode->balance < _balance_eh) {
				xnode->balance = _balance_rh;
				ynode->balance = _balance_eh;
				node->balance = _balance_eh;
			} else if(ynode->balance == _balance_eh) {
				xnode->balance = _balance_eh;
				ynode->balance = _balance_eh;
				node->balance = _balance_eh;
			}
			node->paths[_path_right] = rotate_right(xnode);
		} else {
			/*
			if((mode == 1) && \
			   (xnode->paths[_path_left] != 0) && \
			   (xnode->paths[_path_right] != 0)) {
			*/
			if((mode == 1) && \
			   (xnode->balance == 0)) {
				xnode->balance = _balance_lh;
				node->balance = _balance_rh;
			} else {
				node->balance = _balance_eh;
				xnode->balance = _balance_eh;
			}
		}
		return rotate_left(node);
	}

	avl_node_t *create_node(unsigned int key) {
		avl_node_t *new_node = (avl_node_t*)malloc(sizeof(avl_node_t));
		if(new_node == 0) return (avl_node_t*)_ret_failure;

		new_node->key = key;
		new_node->paths[_path_left] = 0;
		new_node->paths[_path_right] = 0;
		new_node->balance = 0;

		return new_node;
	}

	void showtree(avl_node_t *node) {
		if(node != 0) {
			showtree(node->paths[_path_left]);
		
			printf(" : Node %d [ %d ] : L= 0x", node->key, node->balance);
			if(node->paths[_path_left]) printf("%X : U= 0x%x : ", node->paths[_path_left], node);
			else printf("000000 : U= 0x%x : ", node);
			if(node->paths[_path_right]) printf("R= 0x%X >", node->paths[_path_right]);
			else printf("R= 0x000000 >", node);
			
			if(tree == node) printf("[ Root ]\r\n");
			else if((node->paths[_path_right]!=0) && (node->paths[_path_left]!=0)) printf("[ Subtree ]\r\n");
			else if(node->paths[_path_left]!=0) printf("[ Left branch ]\r\n");
			else if(node->paths[_path_right]!=0) printf("[ Right branch ]\r\n");
			else printf("[ Leaf ]\r\n");

			showtree(node->paths[_path_right]);
		}
	}

	avl_node_t *insert_node(avl_node_t *node) {
		if(node == 0) return (avl_node_t*)_ret_failure;
		
		//printf(" - Insert(%d):\r\n", node->key);
		if(tree == 0) {
			tree = node;
			return node;
		} else {
			avl_node_t *iterator = tree;
			unsigned int director = (_stack_max-1);
			route_index = (_stack_max-1);

			while(1) {
				//director = (tree->key < node->key);
				if(node->key < iterator->key) director = _path_left;
				else director = _path_right;

				if(node->key == iterator->key) {
					free(node);
					return (avl_node_t*)_ret_failure;
				} else if(iterator->paths[director] != 0) {
					if(push_node(iterator)==_ret_failure) {
						free(node);
						return (avl_node_t*)_ret_failure;
					}
					iterator = iterator->paths[director];
				} else {
					if(push_node(iterator)==_ret_failure) {
						free(node);
						return (avl_node_t*)_ret_failure;
					}
					iterator->paths[director] = node;
					break;
				}
			}

			while(1) {
				iterator = pop_node();
				if(iterator == _ret_failure) return (avl_node_t*)_ret_failure;

				director = (iterator->key < node->key);
				if(director) iterator->balance += 1;
				else iterator->balance -= 1;

				if(iterator->balance < _balance_lh) {
					if(tree == iterator) {
						tree = rebalance_left(iterator, 0);
						break;
					} else {
						avl_node_t *iterator_parent = pop_node();
						if(iterator_parent == _ret_failure) return (avl_node_t*)_ret_failure;
						iterator_parent->paths[(iterator_parent->key < iterator->key)] = rebalance_left(iterator, 0);
						break;
					}
				} else if(iterator->balance > _balance_rh) {
					if(tree == iterator) {
						tree = rebalance_right(iterator, 0);
						break;
					} else {
						avl_node_t *iterator_parent = pop_node();
						if(iterator_parent == _ret_failure) return (avl_node_t*)_ret_failure;
						iterator_parent->paths[(iterator_parent->key < iterator->key)] = rebalance_right(iterator, 0);
						break;
					}
				} else if(iterator->balance == _balance_eh) break;	
				//else if(iterator == tree) break;
			}
			return node;
		}
	}

	char checktree(avl_node_t *node) {
		if(node == 0) return 0;
		else {
			if(checktree(node->paths[_path_left])==1) return 1;

			if((node->paths[0]==0) && (node->balance < 0)) {
				printf(" > Node %d Left Heavy but has no Left children!\r\n", node->key);
				return 1;
			} else if((node->paths[1]==0) && (node->balance > 0)) {
				printf(" > Node %d Right Heavy but has no Right children!\r\n", node->key);
				return -1;
			} 

			if(node->paths[0])
				if(node->paths[0]->key > node->key) {
					printf(" > Node %d is greater than its Left child!\r\n", node->key);
					return 1;
				}
			if(node->paths[1])
				if(node->paths[1]->key < node->key) {
					printf(" > Node %d is smaller than its Right child!\r\n", node->key);
					return 1;
				}

			if((node->paths[0]==0) && (node->paths[1]!=0) && (node->balance == 0)) {
				printf(" > Node %d is balanced, but only has a Right child!\r\n", node->key);
				return 1;
			}

			if((node->paths[1]==0) && (node->paths[0]!=0) && (node->balance == 0)) {
				printf(" > Node %d is balanced, but only has a Left child!\r\n", node->key);
				return 1;
			}

			if((node->paths[0]==0) && (node->paths[1]==0) && (node->balance != 0)) {
				printf(" > Node %d is a Leaf but its balance contradicts this!\r\n", node->key);
				return 1;
			}

			if(checktree(node->paths[_path_right])==1) return 1;;
			return 0;
		}
	}

	avl_node_t *find_node(unsigned int key) {
		if(tree == 0) return (avl_node_t*)_ret_failure;
		else {
			avl_node_t *iterator = tree;
			unsigned int director = 0;
			route_index = (_stack_max-1);

			while(iterator != 0) {
				if(key == iterator->key) return iterator;

				if(key < iterator->key) director = 0;
				else if(key > iterator->key) director = 1;

				if(push_node(iterator)!=_ret_success) return (avl_node_t*)_ret_failure;
				iterator = iterator->paths[director];
			}
			return (avl_node_t*)_ret_failure;
		}
	}

	void delete_node(avl_node_t *node) {
		if(tree == 0) return;
		else if(node == 0) return;
		else {
			avl_node_t *iterator = 0;
			unsigned int key_storage = node->key, director = 0;

			if((node->paths[_path_left]!=0) && (node->paths[_path_right]!=0)) {
				//printf(" ~ Subtree deletion\r\n");
				// We need to find this Nodes replacement
				iterator = node->paths[_path_left];
				while(iterator->paths[_path_right]!=0) iterator = iterator->paths[_path_right];

				// Buffer its keyword.
				key_storage = iterator->key;

				// Remove the Replacement Node.
				delete_node(find_node(iterator->key));

				// Copy the Key to the Subtree node!
				node->key = key_storage;

				// Refresh the Stack! (If this fails, we know that our Replacement caused
				// a rebalancing operation. Believe it or not, the Tree is in balance.
				if(find_node(node->key)) {
					return;
				}

				// Okay, Now all we have to do is propogate this change up the Tree!
				// (We changed something, somewhere!)
				iterator = pop_node();

				if((iterator->balance == _balance_lh) || \
				   (iterator->balance == _balance_rh)) {
					//printf("itret\r\n");
					return;
				} else if((node->balance == _balance_lh) || \
					  (node->balance == _balance_rh)) {
					//printf("ndret\r\n");
					return;
				} else if(iterator == tree) return;
			} else if(node->paths[_path_left]!=0) {
				//printf(" ~ L/Branch deletion\r\n");
				if(node == tree) {
					tree = node->paths[_path_left];
					free(node);
					return;
				}
				iterator = pop_node();

				if(key_storage < iterator->key) director = 0;
				else director = 1;
	
				iterator->paths[director] = node->paths[_path_left];
				free(node);					
			} else if(node->paths[_path_right]!=0) {
				//printf(" ~ R/Branch deletion\r\n");
				if(node == tree) {
					tree = node->paths[_path_right];
					free(node);
					return;
				}
				iterator = pop_node();

				if(key_storage < iterator->key) director = 0;
				else director = 1;
	
				iterator->paths[director] = node->paths[_path_right];
				free(node);					
			} else {
				//printf(" ~ Leaf deletion\r\n");
				if(node == tree) {
					tree = 0;
					free(node);
					return;
				}
				iterator = pop_node();

				if(key_storage < iterator->key) director = 0;
				else director = 1;

				iterator->paths[director] = 0;
				free(node);
			}

			while(1) {
				if(iterator == _ret_failure) break;
				if(key_storage < iterator->key) director = 0;
				else director = 1;

				iterator->balance += (director ? -1 : 1);
		
				if(iterator->balance < _balance_lh) {
					if(iterator == tree) {
						tree = rebalance_left(iterator, 1);
						break;
					} else {
						if(iterator->key < route_stack[route_index+1]->key) director = 0;
						else director = 1;

						route_stack[route_index+1]->paths[director] = \
							rebalance_left(iterator, 1);

						iterator = route_stack[route_index+1]->paths[director];
					}
				} else if(iterator->balance > _balance_rh) {
					//printf("r.crit\r\n");
					if(iterator == tree) {
						tree = rebalance_right(iterator, 1);
						break;
					} else {
						if(iterator->key < route_stack[route_index+1]->key) director = 0;
						else director = 1;

						route_stack[route_index+1]->paths[director] = \
							rebalance_right(iterator, 1);

						iterator = route_stack[route_index+1]->paths[director];
					}
				}
				if(iterator->balance != _balance_eh) {
					break;
				}

				key_storage = iterator->key;
				iterator = pop_node();
			}
		}
	}

	#define _test_range	0x8000

	//#define _dbg_seq_ascending
	//#define _dbg_seq_descending
	#define _dbg_random

	int main(void) {
		#ifdef _dbg_seq_ascending
			for(unsigned int a = 0; a < _test_range; a++) {
				insert_node(create_node(a));
			} 
		#endif

		#ifdef _dbg_seq_descending
			for(unsigned int a = _test_range; a > 0; a--) {
				insert_node(create_node(a));
			} 
		#endif

		#ifdef _dbg_random
			srand(time(NULL));
			unsigned int a = 0;

			while(a < _test_range) {
				if(insert_node(create_node((rand()%(_test_range*2))))!=_ret_failure) {
					a++;
					if(checktree(tree)!=0) break;
				}
			}
		#endif

//		dump_routestack();	

		unsigned int c = 0;

		while(tree != 0) {
			delete_node(find_node(tree->key));
			if(checktree(tree)!=0) break;
			else printf(" %d OK!\r\n", c);
			c++;
		}

		printf("feep\r\n");
		showtree(tree);
		printf("%d\r\n", checktree(tree));

		system("PAUSE");
		return 0;
	}