#include "BinarySearchTree.h"
#include <cstdlib>
#include <iostream>
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::draw( tree t, bool endline)
{
	if(t!=NULL)
	{
		for(int i = 0 ; i < t->getPos(); i++)
		{
			cout << "\t";
		}

		cout << t->getKey();
		if(endline)
			cout << endl;

		draw(t->left,false);
		draw(t->right,true);
	}
}

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::balanceVector(vector<vector <int> > v, int f, int l)
{
	BinarySearchTree *balancedTree = NULL;
	int n = (f + (l - f ))/2;
	
	if(f - l == 0)
	{

		balancedTree->insert(v[n][0], balancedTree, 0);
		balancedTree->draw(balancedTree,true);
	}
	else
	{
		balancedTree->insert(v[n][0], balancedTree, 0);
		balancedTree->draw(balancedTree,true);

		*balancedTree->left = balanceVector(v, f, n-1);
		*balancedTree->right = balanceVector(v, n+1, l);
	}

	return 	*balancedTree;
}

BinarySearchTree BinarySearchTree::balance(tree t)
{
	BinarySearchTree *balancedTree = NULL;
	t->serialiseInOrder(t);
	*balancedTree = balanceVector(t->inOrder, 0, t->inOrder.size()-1);

	return *balancedTree;
}

vector<int> BinarySearchTree::nextPostOrder()
{
	vector<int> n = *postOrderIterator;
	postOrderIterator++;
	return n;
}

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

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

		postOrderIterator = postOrder.begin();
	}
}
vector<int> BinarySearchTree::nextPreOrder()
{
	vector<int> n = *preOrderIterator;
	preOrderIterator++;
	return n;
}

void BinarySearchTree::serialisePreOrder(tree t)
{
	if(t!=NULL)
	{
		vector<int> a;
		a.push_back(t->getKey());
		a.push_back(t->getDepth());
		a.push_back(t->getPos());
		preOrder.push_back(a);


		serialisePreOrder(t->left);
		serialisePreOrder(t->right);

		preOrderIterator = preOrder.begin();
	}
}
vector<int> BinarySearchTree::nextInOrder()
{
	vector<int> n = *inOrderIterator;
	inOrderIterator++;
	return n;
}

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;
}