#include <stdio.h>
#include <stdlib.h>
#include "Profiler.h"
Profiler profiler("DynamicOrderStatistics");
#define max_size 10000

int op_select = 0;
int op_delete = 0;
int op_build = 0;

typedef struct NodeT
{
	int data;
	int size;
	struct NodeT *left, *right, *parent;
} NodeT;

NodeT* initialize_node(int data)
{
	NodeT* new_node = (NodeT*)malloc(sizeof(NodeT));
	op_build++;
	new_node->data = data;
	op_build++;
	new_node->size = 1;
	new_node->left = new_node->right = NULL;
	new_node->parent = NULL;
	return new_node;
}
NodeT* buildPBT(int a[], int first, int last) //build a PBT from an ordered array
{
	NodeT* root = (NodeT*)malloc(sizeof(NodeT));
	op_build++;
	if (first <= last)
	{
		int mid = (first + last + 1) / 2;
		root = initialize_node(a[mid]);
		op_build = op_build + 2;
		root->left = buildPBT(a, first, mid - 1);
		root->right = buildPBT(a, mid + 1, last);

		op_build++;
		if (root->left != NULL)
		{
			op_build++;
			root->size = root->size + root->left->size;
		}
		op_build++;
		if (root->right != NULL)
		{
			op_build++;
			root->size = root->size + root->right->size;
		}

		op_build++;
		if (root->left != NULL)
		{
			op_build++;
			root->left->parent = root;
		}
		op_build++;
		if (root->right != NULL)
		{
			op_build++;
			root->right->parent = root;
		}
		return root;
	}
	else
		return NULL;
}

void show_tree(NodeT* p, int level)
{
	if (p != NULL)
	{
		show_tree(p->right, level + 1);
		for (int i = 0; i <= level; i++)
			printf("       ");
		if(p->parent == NULL)
			printf("%d,%d - NULL\n\n", p->data, p->size);
		else
			printf("%d,%d - %d\n\n", p->data, p->size, p->parent->data);
		show_tree(p->left, level + 1);
	}
}

NodeT* OS_Select(NodeT* root, int i)
{
	int r;
	op_select++;
	if (root != NULL)
	{
		op_select++;
		if (root->left != NULL)
			r = root->left->size + 1;
		else
			r = 1;
		if (i == r)
			return root;
		else
		{
			if (i < r)
				return OS_Select(root->left, i);
			else
				return OS_Select(root->right, i - r);
		}
	}
	else
		return NULL;
}

NodeT* findMin(NodeT* pNode)
{
	op_delete++;
	if (pNode == NULL)
		return NULL;
	op_delete++;
	if (pNode->left != NULL)
		return findMin(pNode->left);
	else
		return pNode;

}

void transplant(NodeT* root, NodeT* u, NodeT* v)
{
	op_delete++;
	if (u->parent == NULL)
	{
		root = v;
		op_delete++;
	}
	else
	{
		op_delete++;
		if (u == u->parent->left)
		{
			u->parent->left = v;
			op_delete++;
		}
		else
		{
			op_delete++;
			u->parent->right = v;
		}
		if (v != NULL)
		{
			v->parent = u->parent;
			op_delete++;
		}
	}
}
void delete_node(NodeT* root, NodeT* z)
{
	op_delete++;
	if (z->left == NULL)
	{
		//	op_delete++;
		NodeT* aux = z;
		op_delete++;
		while (aux->parent != NULL)
		{
			op_delete++;
			aux->parent->size--;
			op_delete++;
			aux = aux->parent;
			op_delete++;
		}
		op_delete++;
		transplant(root, z, z->right);
	}
	else
	{
		NodeT* aux = z;
		op_delete++;
		while (aux->parent != NULL)
		{
			op_delete++;
			aux->parent->size--;
			op_delete++;
			aux = aux->parent;
			op_delete++;
		}
		op_delete++;
		op_delete++;
		if (z->right == NULL)
		{
			NodeT* aux = z;
			op_delete++;
			while (aux->parent != NULL)
			{
				op_delete++;
				aux->parent->size--;
				op_delete++;
				aux = aux->parent;
				op_delete++;
			}
			op_delete++;
			transplant(root, z, z->left);
		}
		else
		{
			op_delete++;
			NodeT* y = findMin(z->right);
			op_delete++;
			NodeT* aux = y;
			while (aux->parent != NULL)
			{
				op_delete++;
				aux->parent->size--;
				op_delete++;
				aux = aux->parent;
				op_delete++;
			}
			op_delete++;
			op_delete++;
			if (y->parent != z)
			{
				transplant(root, y, y->right);
				op_delete++;
				y->right = z->right;
				op_delete++;
				y->right->parent = y;
			}
			transplant(root, z, y);
			op_delete++;
			y->left = z->left;
			op_delete++;
			y->left->parent = y;
			op_delete++;
			y->size = z->size;
		}
	}

}
int main()
{
	///////demo
	NodeT* root = (NodeT*)malloc(sizeof(NodeT));
	int n = 11;
	int a[] = { 5, 10, 20, 27, 30, 31, 32, 35, 40, 45, 70 };
	int i;
	NodeT* y;
	//int a[] = { 1, 2, 3, 4};
	//int n = 4;
	root = NULL;
	root = buildPBT(a, 0, n - 1);
	show_tree(root, 0);

	i = 6;//two children 31, root
	y = OS_Select(root, i);
	if (y != NULL)
		printf("I found the element %d of rank %d\n", y->data, i);
	else
		printf("We don't have rank %d in this tree.", i);
	delete_node(root, y);
	show_tree(root, 0);


	return 0;
}