/*
Build Tree is a procedure that builds a balanced tree from an ordered set of keys

OS_SELECT
	This procedure returns a pointer to the node containing the i smallest key
in the subtreee rooted at x
- if our node is equal to the key - what are we are looking for, we return it
- it it less than we search in the left subtree and if it is greater we search in the
right subtree

OS_DELETE
 This procedure deletes a node from the tree
There are 3 cases:
1. if the node has no children(it is a leaf) we simply delete ot
2. if the node has one child, we delete the nodeand update the link to its son
3. if the node has two children, we find the smallest successor in the right subtree, we copy
the content to the nodeand we delete the successor(we replace the node to the smallest right successor)

MAINTAINING SUBTREE SIZES
- we increment the size of the node with every node added in the subtree
- when we delete a node, we simply decrement the size of every other node that is traveresed untill that node


*/
#include <iostream>
#include <string>
#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <vector>
#include <iterator>
#include "Profiler.h"
#include <time.h>
#include <iomanip>
#define COUNT 10
Profiler profiler("HashTables");
using namespace std;

typedef struct Node {
	int key;
	int size;
	Node* left;
	Node* right;
} Node;

Node* create_Node(int key, int size) {
	Node* new_Node = (Node*)malloc(sizeof(Node));
	new_Node->key = key;
	new_Node->size = size;
	new_Node->left = NULL;
	new_Node->right = NULL;
	return new_Node;
}
Node* build_tree(int a[], int left, int right) {
	if (left <= right)
	{
		int m = (left + right) / 2;
		Node* root = create_Node(a[m], 1);
		root->right = build_tree(a, m + 1, right);
		root->left = build_tree(a, left, m - 1);
		if(root->right!=NULL)
		root->size = root->size + root->right->size;
		if (root->left!= NULL)
		root->size = root->size + root->left->size;

		return root;
	}
	else return NULL;
}

Node* os_select(Node* root, int i,int n) {
	int r;
	profiler.createOperation("OS-SELECT", n);
	if (root != NULL)
	{
		profiler.countOperation("OS-SELECT", n, 1);
		if (root->left == NULL) r = 1;
		else  r = (root->left)->size + 1;

		if (i == r)
			return root;
		else
		{

			if (i < r)
				return os_select(root->left, i, n);
			else return os_select(root->right, i - r, n);

		}
	}
}
Node* GetMaxValueNode(Node* root) {
	Node* max_node = root;
	while (max_node->right != NULL) {
		max_node = max_node->right;
	}
	return max_node;
}
Node* deleteNode(Node* root, int key, int n)
{
	profiler.createOperation("OS-DELETE", n);
	profiler.countOperation("OS-DELETE", n, 1);
	if (root == NULL) return root;

	root->size--;
	profiler.countOperation("OS-DELETE", n, 1);
	if (key < root->key)
	{
		root->left = deleteNode(root->left, key,n);
	}
	else if (key > root->key)
	{
		profiler.countOperation("OS-DELETE", n, 1);
		root->right = deleteNode(root->right, key, n);
	}
	else
	{
		profiler.countOperation("OS-DELETE", n, 2);
		if (root->left == NULL)
		{
			profiler.countOperation("OS-DELETE", n, 1);
			Node* temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL)
		{
			profiler.countOperation("OS-DELETE", n, 1);
			Node* temp = root->left;
			free(root);
			return temp;
		}

		Node* temp = GetMaxValueNode(root->left);
		profiler.countOperation("OS-DELETE", n, 1);
		root->key = temp->key;


		root->left = deleteNode(root->left, temp->key, n);
	}
	return root;
}

Node* delete_n(Node* root, int i,int n) {
	Node* temp = os_select(root, i, n);
	return deleteNode(root, temp->key, n);
}
void inorder(Node* node)
{
	if (node == NULL)
		return;

	inorder(node->left);


	printf("(%d with size %d)\n", node->key, node->size);


	inorder(node->right);
}

void prettyPrint(Node* root, int space)
{

	if (root == NULL)
		return;

	space += COUNT;

	prettyPrint(root->right, space);
	cout << endl;
	for (int i = COUNT; i < space; i++)
		cout << " ";
	cout << root->key << "\n";

	prettyPrint(root->left, space);
}
void demo()
{
	int k = 11;
	int* a = (int*)malloc(k * sizeof(int));
	FillRandomArray(a, k, 0, k - 1, true, 1);
	printf("Sorted array: ");
	for (int j = 0; j < k; j++) {
		printf("%d ", a[j]);
	}

	printf("\nPretty print: ");
	printf("\n");
	Node* n = build_tree(a, 0, k - 1);

	prettyPrint(n, 0);
	printf("\n");
	inorder(n);
	int index[3];
	FillRandomArray(index, 3, 1, k - 1, true,0);
	for (int i = 0; i < 3; i++) {
		printf("We delete element %d \n", a[index[i]]);
		n = delete_n(n, a[index[i]],i);
		prettyPrint(n, 0);
		printf("\n");
		inorder(n);
	}
	system("pause");
}

void compute()
{
	int r;
	for (int i = 100; i <= 1000; i = i + 100)
	{
		int* a = (int*)malloc(i * sizeof(int));
		int* index_array = (int*)malloc(i * sizeof(int));

		for (int j = 1; j <= 5; j++)
		{
			FillRandomArray(a, i, 0, i-1, true, 1);
			Node* n = build_tree(a, 1, i);

			for (int k = 0; k < i; k++)
			{
				r = rand() % (i-k) + 1;
				n = delete_n(n, a[r], i);
			}
		}
	}
	profiler.divideValues("OS-SELECT", 5);
	profiler.divideValues("OS-DELETE", 5);
	profiler.createGroup("AverageOperations", "OS-SELECT", "OS-DELETE");
	profiler.showReport();
}

int main()
{
	//demo();
	compute();
}