#include <cstdlib>
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

BinarySearchTree::BinarySearchTree()
{
	left = NULL;
	right = NULL;
	key = -1;
	depth = -1;
	pos = -1;
}
BinarySearchTree::BinarySearchTree(int k)
{
	left = NULL;
	right = NULL;
	key = k;
	depth = 0;
	pos = 0;
}

BinarySearchTree::~BinarySearchTree()
{
	delete this->left;
	delete this->right;
}

void BinarySearchTree::setInOrderPos(tree t, int &count)
{
	if(t != NULL )
	{
		setInOrderPos(t->left, count);
		t->setPos(++count);
		setInOrderPos(t->right, ++count);
	}
}

void BinarySearchTree::insert(int k, tree &t, int depth)
{
	if( t == NULL )
	{
		t = new BinarySearchTree(k);
		t->setDepth(depth);
		t->left = NULL;
		t->right = NULL;
	}
	else if( k < t->getKey() )
	{
		insert(k, t->left, t->getDepth()+1);
	}
	else if( k > t->getKey() )
	{
		insert(k, t->right, t->getDepth()+1);
	}
	else
	{
		cout << "Duplicate key" << endl;
	}

}
BinarySearchTree* BinarySearchTree::balanceArray(int a[], int f, int l)
{
	int n = (f + (l - f ))/2;
	BinarySearchTree *root = NULL;

	if(n == 0)
	{
		BinarySearchTree *root = new BinarySearchTree(a[n]);
		root->left=NULL;
		root->right=NULL;
	}
	if(n>0)
	{
		BinarySearchTree *root = new BinarySearchTree(a[n]);
		//cout << "n:" << n << " k:" << root->getKey() << " f:" << f << " l: " << l << endl;


		root->left = balanceArray(a, f, n-1);

		root->right = balanceArray(a, n+2, l);
	}

	return root;
	
}

BinarySearchTree* BinarySearchTree::balance(tree t)
{
	BinarySearchTree *balancedTree = NULL;
	t->serialiseInOrder(t);

	int a[t->inOrder.size()];

	for(int i=0; i < t->getSize(t); i++)
	{
		a[i] = t->inOrder[i][0];
	}

	balancedTree = balanceArray(a, 0, t->inOrder.size()-1);

	return balancedTree;
}

void BinarySearchTree::serialiseInOrder(tree t)
{
	if(t!=NULL)
	{
		serialiseInOrder(t->left);

		vector<int> a;
		a.push_back(t->getKey());
		a.push_back(t->getDepth());
		a.push_back(t->getPos());
		inOrder.push_back(a);

		serialiseInOrder(t->right);

		inOrderIterator = inOrder.begin();
	}
}

int BinarySearchTree::getSize(tree t)
{
	if(t == NULL)
		return 0;
	else
		return 1+getSize(t->left)+getSize(t->right);
}

int BinarySearchTree::getKey()
{
	return key;
}

int BinarySearchTree::getPos()
{
	return pos;
}

int BinarySearchTree::getDepth()
{
	return depth;
}

void BinarySearchTree::setPos(int p)
{
	pos = p;
}

void BinarySearchTree::setDepth(int d)
{
	depth = d;
}