#include<string>
#include <fstream>
#include<iostream>
#include <cstring>
#include"BST.h"

using namespace std;

Node*null = NULL;

BST::BST(){
	Root = null;
}

BST::~BST(){
	if (Root != null){
		DeleteAll(Root);
	}
}

//An in order traversal for printing to file.
void BST::InOrder(Node* root){
	if (root != null)
	{
		InOrder(root->left);
		Process(root);
		InOrder(root->right);
	}
}

//post order traversal for searching for the item to delete.
void BST::PostOrderDelete(Node* root, Node*trail, TreeType itemToDelete){
	if (root != null)
	{
		PostOrderDelete(root->left, root, itemToDelete);
		PostOrderDelete(root->right, root, itemToDelete);
		if (root->word == itemToDelete){
			if (root->left == NULL && root->left == NULL && trail == NULL){
				delete root;
				Root = NULL;
			}
			else if (root->left == NULL && root->left == NULL){
				delete root;
				if (trail->left == root)
				{
					trail->left = NULL;
				}
				else{
					trail->right = NULL;
				}
			}
			else if (root->left != NULL && root->right != NULL){
				if (root->left != NULL && root->left->right != NULL){
					Node*trail = root->left;
					Node*temp = root->left->right;
					while (temp->right != NULL)
					{
						trail = temp;
						temp = temp->right;
					}
					if (temp->left == NULL){
						root = temp;
						trail->right = null;
					}
					else
					{
						trail->right = temp->left;
						root = temp;
					}
				}
				else if (root->left != NULL){
					if (root->right != NULL)
						root->left->right = root->right;
					Node*move = root->left;
					delete root;
					root = move;
				}
			}
		}
	}
}

void BST::write(){
	InOrder(Root);
}

//
//void BST::PostOrder(Node*root, string processType){
//	if (root != null)
//	{
//		PostOrder(root->left, processType);
//		PostOrder(root->right, processType);
//		Process(root, processType);
//	}
//}
//
//void BST::PreOrder(Node*root, string processType){
//	if (root != null)
//	{
//		Process(root, processType);
//		PreOrder(root->left, processType);
//		PreOrder(root->right, processType);
//	}
//}

//writes to file.  Used by the in order traversal for file writing.
void BST::Process(Node* nodeToProcess){
	if (OutputFile.good())
		OutputFile << nodeToProcess->word << '\t' << nodeToProcess->count << endl;
	else
		cout << "Output file not created...\n";
}

//checks if empty since head is private.
bool BST::Empty(){
	return (Root == null);
}

//inserts a word into the BST
bool BST::Insert(TreeType itemToInsert){
	// check if the tree is empty
	if (Root == null)
	{
		Root = new Node;
		// Rrrrrrrobustness
		if (!Root)
		{
			return false;
			cout << "Unable to allocate memory.\n";
		}
		//set the branches to null
		Root->left = null;
		Root->right = null;
		// insert word and set count to 1
		Root->word = itemToInsert;
		Root->count = 1;
	}
	else
	{
		Node*temp = Root;
		//create temp Node ptr to traverse the tree to find an insertion point
		// Bool for the loop
		bool tempBool = false;
		// loop to traverse the tree to find an insertion point.
		while (!tempBool)
		{
			if (temp == null)
			{
				temp = new Node;
				//more Rrrrrrrobustness
				if (!temp)
				{
					return false;
					cout << "Unable to allocate memory.\n";
				}
				//more setting to null
				temp->left = null;
				temp->right = null;
				temp->word = itemToInsert;
				temp->count = 1;
				//end the loop
				tempBool = true;
			}
			//if the word is already in the tree
			else if (temp->word == itemToInsert){
				temp->count++;
				tempBool = true;
			}
			else if (temp->word < itemToInsert)
				temp = temp->right;
			else
				temp = temp->left;
		}
	}
	return true;
}

int BST::NodeTotal(){
	return NodeTotalRecursive(Root);
}

//My own concoction >:D
//It totals it all up recursively by returning the sum of the returns of the next calls if it's not null,
//then adding on as it goes.
int BST::NodeTotalRecursive(Node* merp){
	if (merp != NULL) { return NodeTotalRecursive(merp->left) + NodeTotalRecursive(merp->right); }
	return 1;
}

int BST::findMax() {
	return height(Root);
}

//I'm ashamed to say I didn't figure this out myself... I found it on StackOverflow.
//But dang it, I can't do it better...
//It recursively loops through and returns 1 when it hits a valid node and 0 when the node is null.
//in order to find the max height, it chooses the larger of the two return values to pass to the
//next call.  Pretty elogant if you ask me.  If only I had come up with it myself...
int BST::height(Node*root){
		if (root == null) return 1;
		else return 1 + max(height(root->left), height(root->right));
	}

//finds the max.  Pretty straight forward.
int BST::max(int x, int y){
	if (x > y) return x;
	else return y;
}

//calls the post order deleting function to find the item to delete.
void BST::Delete(TreeType itemToDelete){
	PostOrderDelete(Root, NULL, itemToDelete);
}

//literally just deletes everything.  Can't recursively call the deconstructor so I needed this.
void BST::DeleteAll(Node* root)
{
	if (root != null)
	{
		DeleteAll(root->left);
		DeleteAll(root->right);
		delete root;
	}
}