/*

	CORRECTNESS:
	partial correctness : OS_select finds the element
						  OS_delete deletes it
						  BuildTree builds PBT
	total correctness : above  + program terminates



	OS_select -> cormen -> finds the i'th smallest element

	OS_delete -> dsa -> deletes a node.
	case1 : no sons -> delete
	case2 : 1 son -> delete node and update links to son
	case3 : 2 sons -> find min in the right subtree, swap keys and delete that min

	OBS: height is log(n) - perfectly balanced tree


*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include "Profiler.h"

Profiler profiler("OS_Trees");

int nbOp_sel = 0;
int nbOp_del = 0;
int nbOp_bld = 0;
struct Node
{
	int info;
	Node *pLeft;
	Node *pRight;
	int size;
};

Node* buildTree(int l, int r)
{
	struct Node *pNew = (struct Node*)malloc(sizeof(struct Node));
	nbOp_bld++;
	if (l <= r)
	{
		int mid = (l + r) / 2;

		nbOp_bld += 2;
		pNew->info = mid;
		pNew->size = 1;

		nbOp_bld += 2;
		pNew->pLeft = buildTree(l, mid - 1);
		pNew->pRight = buildTree(mid + 1, r);


		nbOp_bld++;
		if (pNew->pLeft != NULL)
		{
			nbOp_bld++;
			pNew->size = pNew->size + pNew->pLeft->size;
		}

		nbOp_bld++;
		if (pNew->pRight != NULL)
		{
			nbOp_bld++;
			pNew->size = pNew->size + pNew->pRight->size;
		}

		return pNew;
	}
	else return NULL;
}

void showTree_in(struct Node* pWalker, int level)
{
	if (pWalker == NULL) return;

	showTree_in(pWalker->pRight, level + 1);
	printf("%*s(%d,%d)\n\n", 7 * level, "", pWalker->info, pWalker->size);
	showTree_in(pWalker->pLeft, level + 1);

}

Node * OS_Select(struct Node* root, int i)
{
	nbOp_sel++;
	if (root != NULL)
	{
		int r;
		nbOp_sel++;
		if (root->pLeft != NULL)  r = root->pLeft->size + 1;
		else r = 1;
		if (i == r) return root;
		else
		{
			if (i < r) return OS_Select(root->pLeft, i);
			else return OS_Select(root->pRight, i - r);
		}
	}
	else return NULL;

}

struct Node* findMin(struct Node* pNode)
{
	nbOp_del++;
	if (pNode == NULL) return NULL;
	nbOp_del++;
	if (pNode->pLeft != NULL) return findMin(pNode->pLeft);
	else
		return pNode;

}

struct Node* OS_delete_node(struct Node* pNode, int x)
{
	nbOp_del++;
	if (pNode == NULL)
	{
		printf("\nElement %c not found.\n", x);
	}
	else
	{
		nbOp_del++;
		if (x < pNode->info)
		{
			pNode->pLeft = OS_delete_node(pNode->pLeft, x);
			pNode->size--;
			nbOp_del++;
		}
		else
		{
			nbOp_del++;
			if (x > pNode->info)
			{
				pNode->pRight = OS_delete_node(pNode->pRight, x);
				pNode->size--;
				nbOp_del++;
			}
			else
			{
				nbOp_del +=2;
				if (pNode->pRight != NULL && pNode->pLeft != NULL)
				{
					pNode->size--;
					nbOp_del++;
					struct Node* temp = findMin(pNode->pRight);
					pNode->info = temp->info;
					nbOp_del++;
					pNode->pRight = OS_delete_node(pNode->pRight, temp->info);
				}
				else
				{
					struct Node* temp = pNode;
					nbOp_del++;
					if (pNode->pLeft == NULL)
					{
						pNode = pNode->pRight;
					}
					else
					{
						nbOp_del++;

						if (pNode->pRight == NULL)
						{
							pNode = pNode->pLeft;
						}
					}
					free(temp);
				}
			}
		}
	}
	return pNode;
}

int main()
{

	printf("For demo press 1 , for actual stuff press 2 .\n");
	int demo;
	scanf("%d", &demo);

	if (demo == 1)
	{
		struct Node *root = NULL;
		int n = 11;
		root = buildTree(1, n);
		printf("TREE : \n");
		showTree_in(root, 0);

		printf("\n");
		srand(time(NULL));



		// random select & delete
		int a = 2;// rand() % (n) + 1;
		printf("FIND the %d-th smallest ! \n", a);
		if (OS_Select(root, a) != NULL) printf("Found %d , now we will DELETE IT ! \n", OS_Select(root, a)->info);
		root = OS_delete_node(root, OS_Select(root, a)->info);
		showTree_in(root, 0);
		n--;

		int b = 3; //rand() % (n - 1) + 1;
		printf("\nFIND the %d-th smallest ! \n", b);
		if (OS_Select(root, b) != NULL) printf("Found %d , now we will DELETE IT ! \n", OS_Select(root, b)->info);
		root = OS_delete_node(root, OS_Select(root, b)->info);
		showTree_in(root, 0);
		n--;

		int c = 4; //rand() % (n - 1) + 1;
		printf("\nFIND the %d-th smallest ! \n", c);
		if (OS_Select(root, c) != NULL) printf("Found %d , now we will DELETE IT ! \n", OS_Select(root, c)->info);
		root = OS_delete_node(root, OS_Select(root, c)->info);
		showTree_in(root, 0);
		n--;


	}
	else
	{
		int n;
		for (n = 100; n <= 10000; n += 100)
		{

			nbOp_sel = 0;
			nbOp_del = 0;
			nbOp_bld = 0;
			struct Node *root = NULL;
			root = buildTree(1, n);

			int i;
			srand(time(NULL));
			int nnn = n;
			for (i = 0; i < n; i++)
			{
				int xth_smallest = rand() % (nnn)+1;
				struct Node *val = OS_Select(root, xth_smallest);

				root = OS_delete_node(root, val->info);
				nnn--;
			}

			profiler.countOperation("nbOp_SEL", n, nbOp_sel);
			profiler.countOperation("nbOp_DEL", n, nbOp_del);
			profiler.countOperation("nbOp_BLD", n, nbOp_bld);
			profiler.countOperation("sumOps", n, nbOp_sel+nbOp_del+nbOp_bld);

			profiler.createGroup("ops", "nbOp_SEL", "nbOp_DEL","nbOp_BLD", "sumOps");
		}
		profiler.showReport();
	}
	printf("gata");



	_getch();
	return 0;
}