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

typedef struct tree_node AVL_tree_node;

typedef struct tree_data
{
	unsigned char value;
	char* text;
}AVL_tree_data;

typedef struct tree_key
{
	unsigned int address;
}AVL_tree_key;

struct tree_node
{
	AVL_tree_node* left;
	AVL_tree_node* right;

	int depth_left;
	int depth_right;

	AVL_tree_key key;
	AVL_tree_data data;
};

typedef struct
{
	AVL_tree_node* root;
}AVL_tree;

typedef enum
{
	AVL_ROT_NONE,
	AVL_ROT_RIGHT,
	AVL_ROT_LEFT,
	AVL_ROT_RIGHT_LEFT,
	AVL_ROT_LEFT_RIGHT
} AVL_tree_rotation;

/* initialize tree structure */
void AVL_init(AVL_tree* tree);

/* destroys tree structure */
void AVL_free(AVL_tree* tree);
/* adds node into the tree (only if tree with same address does not exist) */
void AVL_add(AVL_tree* tree, AVL_tree_key key, AVL_tree_data inputData);
/* find node in tree with given address */
AVL_tree_node* AVL_find(AVL_tree* tree, AVL_tree_key key);

/* prints tree */
void AVL_printTree(AVL_tree* tree);
/* prints node */
void AVL_printNode(AVL_tree_node* node, int spaces);
/* prints data of node */
void AVL_printNodeData(AVL_tree_key key, AVL_tree_data data);


static void AVL_nodeInit(AVL_tree_node* node);
static void AVL_nodeFree(AVL_tree_node* node);
static AVL_tree_rotation AVL_nodeAdd(AVL_tree_node** node, AVL_tree_key key, AVL_tree_data data);
static AVL_tree_node* AVL_findNode(AVL_tree_node* node, AVL_tree_key key);
static AVL_tree_rotation AVL_checkIfParentRotates(AVL_tree_node* node);
static void AVL_rotate(AVL_tree_node* node, AVL_tree_rotation type, char rotateLeftChild);
static void AVL_rotateLeft(AVL_tree_node* node, char rotateLeftChild);
static void AVL_rotateRight(AVL_tree_node* node, char rotateLeftChild);


static void AVL_nodeCopyKey(AVL_tree_key source, AVL_tree_key* destination);
static void AVL_nodeCopyData(AVL_tree_data source, AVL_tree_data* destination);
static void AVL_nodeFreeKey(AVL_tree_key key);
static void AVL_nodeFreeData(AVL_tree_data data);
static char compareNodes(AVL_tree_key a, AVL_tree_key b);


void AVL_init(AVL_tree* const tree)
{
	tree->root = NULL;
}

void AVL_free(AVL_tree* const tree)
{
	if(tree->root != NULL)
	{
		if(tree->root->left != NULL)
		{
			AVL_nodeFree(tree->root->left);
		}
		if(tree->root->right != NULL)
		{
			AVL_nodeFree(tree->root->right);
		}
		AVL_nodeFreeKey(tree->root->key);
		AVL_nodeFreeData(tree->root->data);
		free(tree->root);
		tree->root = NULL;
	}
}

void AVL_add(AVL_tree* tree, AVL_tree_key key, AVL_tree_data inputData)
{
//	AVL_tree_data inputData = {.address = address, .value = value};
	AVL_tree_rotation rotation = AVL_nodeAdd(&(tree->root), key, inputData);

	if(rotation != AVL_ROT_NONE)
	{
		AVL_tree_node* tmp = (AVL_tree_node*) malloc (sizeof(AVL_tree_node));
		tmp->left = tree->root;
		/* rotate left subtree */
		AVL_rotate(tmp, rotation, 1);

		/* in tmp->left is new root of the tree */
		tree->root = tmp->left;
		tmp->left = NULL;
		free(tmp);
	}
}

AVL_tree_node* AVL_find(AVL_tree* tree, AVL_tree_key key)
{
	return AVL_findNode(tree->root, key);
}



static void AVL_nodeInit(AVL_tree_node* node)
{
	node->left = node->right = NULL;
}

static void AVL_nodeFree(AVL_tree_node* node)
{
	if(node->left != NULL)
	{
		AVL_nodeFree(node->left);
	}
	if(node->right != NULL)
	{
		AVL_nodeFree(node->right);
	}
	AVL_nodeFreeKey(node->key);
	AVL_nodeFreeData(node->data);
	free(node);
}

static AVL_tree_rotation AVL_nodeAdd(AVL_tree_node** node, AVL_tree_key key, AVL_tree_data data)
{
	AVL_tree_rotation returnRot = AVL_ROT_NONE;

	/* if *node is NULL, create new node */
	if((*node) == NULL)
	{
		*node = (AVL_tree_node*) malloc (sizeof(AVL_tree_node));

		AVL_nodeInit((*node));
		AVL_nodeCopyData(data, &((*node)->data));
		AVL_nodeCopyKey(key, &((*node)->key));
		(*node)->depth_left = (*node)->depth_right = 0;
	}
	/*else find if new node should be created in left or right subtree */
	else
	{
		char ret = 0;
		char rotateLeftChild = 0;
		AVL_tree_node* left, *right;

		ret = compareNodes(key, (*node)->key);
		/* if new node is considered less than actual node, work in left subtree */
		if(ret == -1)
		{
			/* add node in left subtree 
			*  returns type of rotation needed
			*/
			returnRot = AVL_nodeAdd(&((*node)->left), key, data);
			left = (*node)->left;
			/* flag indicating that left subtree will be rotated (if needed) */
			rotateLeftChild = 1;
			/* updated depth of left subtree */
			(*node)->depth_left = 1 + (((left->depth_right) > (left->depth_left)) ? left->depth_right : left->depth_left);
		}
		/* if new node is considered more than actual node, work in right subtree */
		else if(ret == 1)
		{
			/* add node in left subtree 
			*  returns type of rotation needed
			*/
			returnRot = AVL_nodeAdd(&((*node)->right), key, data);
			right = (*node)->right;
			/* updated depth of right subtree */
			(*node)->depth_right = 1 + (((right->depth_right) > (right->depth_left)) ? right->depth_right : right->depth_left);
		}

		/* check if rotation is supposed to happen */
		if(returnRot != AVL_ROT_NONE)
		{
			AVL_rotate(*node, returnRot, rotateLeftChild);
		}

		/* calculate if parent should rotate */
		returnRot = AVL_checkIfParentRotates(*node);
	}
	return returnRot;
}

static AVL_tree_rotation AVL_checkIfParentRotates(AVL_tree_node* node)
{
	int depthDiff = 0, depthDiffChild = 0;
	AVL_tree_rotation returnRot = AVL_ROT_NONE;

	depthDiff = node->depth_left - node->depth_right;
	/* if depth of left subtree is higher than depth of right subtree by more than 1, right rotation is needed */
	if(depthDiff > 1)
	{
		depthDiffChild = node->left->depth_left - node->left->depth_right;
		/* if depth of child's left subtree is higher than right subtree, only right rotation is needed */
		if(depthDiffChild > 0)
		{
			returnRot = AVL_ROT_RIGHT;
		}
		/* if depth of child's left subtree is lower than right subtree, only left->right rotation is needed */
		else if (depthDiffChild < 0)
		{
			returnRot = AVL_ROT_LEFT_RIGHT;
		}
	}
	/* if depth of left subtree is less than depth of right subtree by more than 1, left rotation is needed */
	else if(depthDiff < -1)
	{
		depthDiffChild = node->right->depth_left - node->right->depth_right;
		/* if depth of child's left subtree is lower than right subtree, only left rotation is needed */
		if(depthDiffChild < 0)
		{
			returnRot = AVL_ROT_LEFT;
		}
		/* if depth of child's left subtree is higher than right subtree, only right->left rotation is needed */
		else if (depthDiffChild > 0)
		{
			returnRot = AVL_ROT_RIGHT_LEFT;
		}
	}

	return returnRot;
}

static void AVL_rotate(AVL_tree_node* node, AVL_tree_rotation type, char rotateLeftChild)
{
	char rotateLeftSubChild = 0;
	AVL_tree_node* nodeToRotate = node->right;
	if(rotateLeftChild == 1)
		nodeToRotate = node->left;

	if(nodeToRotate->depth_left - nodeToRotate->depth_right > 0)
		rotateLeftSubChild = 1;

	switch(type)
	{
		case AVL_ROT_LEFT:
			// rotate to left
			AVL_rotateLeft(node, rotateLeftChild);
			break;
		case AVL_ROT_RIGHT:
			// rotate to right
			AVL_rotateRight(node, rotateLeftChild);
			break;
		case AVL_ROT_LEFT_RIGHT:
			// rotate child to left
			AVL_rotateLeft(nodeToRotate, rotateLeftSubChild);
			// then rotate to right
			AVL_rotateRight(node, rotateLeftChild);
			break;
		case AVL_ROT_RIGHT_LEFT:
			// rotate child to right
			AVL_rotateRight(nodeToRotate, rotateLeftSubChild);
			// then rotate to left
			AVL_rotateLeft(node, rotateLeftChild);
			break;
		default:
			break;
	}
}


static void AVL_rotateLeft(AVL_tree_node* node, char rotateLeftChild)
{
	AVL_tree_node** newRoot;
	AVL_tree_node* oldRoot;
	int* newRootDepth;

	/* set newRoot to actual root of rotated subtree */
	newRoot = &(node->right);
	newRootDepth = &(node->depth_right);
	if(rotateLeftChild == 1)
	{
		newRoot = &(node->left);
		newRootDepth = &(node->depth_left);
	}

	/* store aside actual root */
	oldRoot = *newRoot;
	/* new root will be right child of actual root */
	*newRoot = (*newRoot)->right;
	/* new root's left subtree will now be old root's right subtree */
	oldRoot->right = (*newRoot)->left;
	/* new roots left subtree is old root */
	(*newRoot)->left = oldRoot;

	/* depths of nodes has to be updated */
	/* old roots right subtree was new roots left subtree */
	oldRoot->depth_right = (*newRoot)->depth_left;
	/* new roots left subtree was old root */
	(*newRoot)->depth_left = oldRoot->depth_left + 1;
	/*new depth of parent node is 1 + maximum of new roots left subtree depths and right subtree depth*/
	(*newRootDepth) = 1 + (((*newRoot)->depth_left > (*newRoot)->depth_right) ? (*newRoot)->depth_left : (*newRoot)->depth_right);

}

static void AVL_rotateRight(AVL_tree_node* node, char rotateLeftChild)
{
	AVL_tree_node** newRoot;
	AVL_tree_node* oldRoot;
	int* newRootDepth;

	/* set newRoot to actual root of rotated subtree */
	newRoot = &(node->right);
	newRootDepth = &(node->depth_right);
	if(rotateLeftChild ==  1)
	{
		newRoot = &(node->left);
		newRootDepth = &(node->depth_left);
	}

	/* store aside actual root */
	oldRoot = *newRoot;
	/* new root will be left child of actual root */
	*newRoot = (*newRoot)->left;
	/* new root's right subtree will now be old root's left subtree */
	oldRoot->left = (*newRoot)->right;
	/* new roots right subtree is old root */
	(*newRoot)->right = oldRoot;

	/* depths of nodes has to be updated */
	/* old roots left subtree was new roots right subtree */
	oldRoot->depth_left = (*newRoot)->depth_right;
	/* new roots right subtree was old root */
	(*newRoot)->depth_right = oldRoot->depth_right + 1;
	/*new depth of parent node is 1 + maximum of new roots left subtree depths and right subtree depth*/
	(*newRootDepth) = 1 + (((*newRoot)->depth_left > (*newRoot)->depth_right) ? (*newRoot)->depth_left : (*newRoot)->depth_right);

}


static AVL_tree_node* AVL_findNode(AVL_tree_node* node, AVL_tree_key key)
{
	if(node == NULL)
		return NULL;

	if(compareNodes(node->key, key) == 0)
		return node;
	else if(node->left != NULL && compareNodes(node->key, key) == 1)
		return AVL_findNode(node->left, key);
	else if(node->right != NULL && compareNodes(node->key, key) == -1)
		return AVL_findNode(node->right, key);
	else
		return NULL;
}

void AVL_printTree(AVL_tree* tree)
{
	AVL_printNode(tree->root, 0);
}

void AVL_printNode(AVL_tree_node* node, int spaces)
{
	const int spaceIndent = 10;

	if(node == NULL)
		return;

	// print right
	AVL_printNode(node->right, spaces + spaceIndent);

	// print root
	for(int i = 0; i < spaces; ++i)
		printf("%c", ' ');
	printf("%d:%d:", node->depth_right, node->depth_left);
	AVL_printNodeData(node->key, node->data);

	// print left
	AVL_printNode(node->left, spaces + spaceIndent);
}


void AVL_printNodeData(AVL_tree_key key, AVL_tree_data data)
{
	printf("(%d;%d;%s)\n", key.address, data.value, data.text);
}


static void AVL_nodeCopyKey(AVL_tree_key source, AVL_tree_key* destination)
{
//	printf("%d <- %d\n", destination->address, source.address);
	destination->address = source.address;
}

static void AVL_nodeCopyData(AVL_tree_data source, AVL_tree_data* destination)
{
	int textLenCnt = 0;
	char* txtIt = source.text;

	while(*(txtIt++) != 0)
	{
		textLenCnt++;
	}

	destination->text = (char*) calloc (textLenCnt + 1, sizeof(char));
	memcpy(destination->text, source.text, textLenCnt);
	//destination->text[0] ^= 0x20;

	destination->value = source.value;

}

static void AVL_nodeFreeKey(AVL_tree_key key)
{

}

static void AVL_nodeFreeData(AVL_tree_data data)
{
	free(data.text);
}


static char compareNodes(AVL_tree_key a, AVL_tree_key b)
{
	/* 1 means a is more than b */
	if(a.address > b.address)
		return 1;
	/* -1 means a is less than b */
	else if (a.address < b.address)
		return -1;
	/* 0 means a equals b */
	else
		return 0;
}


int main(void)
{
//	learnMonths();
//	learnConjugation();

	srand(time(NULL));
	AVL_tree tree;
	AVL_tree_node* foundNode;
	AVL_tree testLeft, testRight, testRL;
	AVL_tree randomTree;

	AVL_init(&tree);
	AVL_init(&testLeft);
	AVL_init(&testRight);
	AVL_init(&testRL);
	AVL_init(&randomTree);

	char* dd = (char*) malloc (5);
	memcpy(dd, "abcd", 4);
	dd[4] = 0;



	// test of add functionality
	AVL_add(&tree, (AVL_tree_key){10}, (AVL_tree_data){20, dd});
	AVL_printTree(&tree);
	printf("-----------------------------------------------------\n");
	AVL_add(&tree, (AVL_tree_key){30}, (AVL_tree_data){40, "qwe"});
	AVL_printTree(&tree);
	printf("-----------------------------------------------------\n");
	AVL_add(&tree, (AVL_tree_key){50}, (AVL_tree_data){80, "rty"});
	AVL_printTree(&tree);
	printf("-----------------------------------------------------\n");
	AVL_add(&tree, (AVL_tree_key){20}, (AVL_tree_data){100, "fgh"});
	AVL_printTree(&tree);
	printf("-----------------------------------------------------\n");
	AVL_add(&tree, (AVL_tree_key){84}, (AVL_tree_data){1, "zxc"});
	AVL_printTree(&tree);
	printf("-----------------------------------------------------\n");
	AVL_add(&tree, (AVL_tree_key){12}, (AVL_tree_data){77, "vbn"});
	AVL_printTree(&tree);
	printf("-----------------------------------------------------\n");

	dd[0] = 'Q';

//	// test of find functionality
//	foundNode = AVL_find(&tree, (AVL_tree_key){88});
//	if(foundNode != NULL)
//		AVL_printNodeData(foundNode->key, foundNode->data);
//	else
//		printf("NODE NOT FOUND\n");
//
//	foundNode = AVL_find(&tree, (AVL_tree_key){84});
//	if(foundNode != NULL)
//		AVL_printNodeData(foundNode->key, foundNode->data);
//	else
//		printf("NODE NOT FOUND\n");
//
//	foundNode = AVL_find(&tree, (AVL_tree_key){30});
//	if(foundNode != NULL)
//		AVL_printNodeData(foundNode->key, foundNode->data);
//	else
//		printf("NODE NOT FOUND\n");
//	printf("-----------------------------------------------------\n");
//
//	// change value of found address
//	foundNode->data.text = "ppp";
//	AVL_printTree(&tree);

//	AVL_add(&testLeft, 10, 10);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 20, 20);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 30, 30);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 40, 40);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 50, 50);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 60, 60);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 70, 70);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testLeft, 80, 80);
//	AVL_printTree(&testLeft);
//	printf("-----------------------------------------------------\n");
//
//	printf("-----------------------------------------\n");
//
//	AVL_add(&testRight, 80, 80);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 70, 70);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 60, 60);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 50, 50);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 40, 40);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 30, 30);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 20, 20);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//	AVL_add(&testRight, 10, 10);
//	AVL_printTree(&testRight);
//	printf("-----------------------------------------------------\n");
//
//	printf("-----------------------------------------\n");
//
//	AVL_add(&testRL, 20, 20);
//	AVL_printTree(&testRL);
//	printf("-----------------------------------------\n");
//	AVL_add(&testRL, 40, 40);
//	AVL_printTree(&testRL);
//	printf("-----------------------------------------\n");
//	AVL_add(&testRL, 30, 30);
//	AVL_printTree(&testRL);
//	printf("-----------------------------------------\n");
//	AVL_printTree(&testRL);
//	printf("-----------------------------------------\n");
//
////	/* random adds into tree */
////	for(int i = 0; i < 10000; ++i)
////	{
////		AVL_add(&randomTree, rand()%(1<<20), i);
////	}
////	AVL_printTree(&randomTree);
////	printf("-----------------------------------------\n");
////
////	for(int j = 0; j < 20; ++j)
////	{
////		printf("%d. tree\n", j+1);
////		AVL_free(&randomTree);
////		for(int i = 0; i < 100000; ++i)
////		{
////			AVL_add(&randomTree, rand()%(1<<26), i);
////		}
////	}


//	AVL_free(&tree);
//	AVL_free(&tree);
//	AVL_free(&testLeft);
//	AVL_free(&testRight);
//	AVL_free(&testRL);
//	AVL_free(&randomTree);

//	system("pause");
    return 0;
}