// Stephen Bassoli
// CSE 124 Section 01
// Lab 7

#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "TreeNode.h"

template <class T>
class BinTree
{
	private:
		TreeNode<T>* root;
		TreeNode<T>* curr;
		int size;
		TreeNode<T>* GetTreeNode(const T& item);
		//	Input:		Data value of node
		//	Precond:	None
		//	Process:	Returns node
		//	Output:		Returns node
		//	Postcond:	None

		void FreeNode(TreeNode<T>* t);
		//	Input:		Node to be deleted
		//	Precond:	None
		//	Process:	Deletes node
		//	Output:		None
		//	Postcond:	None

		void DeleteTree(TreeNode<T>* t);
		//	Input:		Root of tree to be deleted
		//	Precond:	None
		//	Process:	Deletes tree
		//	Output:		None
		//	Postcond:	None

		void IndentBlanks(int num);
		//	Input:		Number of level
		//	Precond:	None
		//	Process:	Formats text of PrintTree method
		//	Output:		None
		//	Postcond:	None

		bool SameTree(TreeNode<T>* t1, TreeNode<T>* t2);
		//	Input:		Two trees with same root
		//	Precond:	None
		//	Process:	Compares trees
		//	Output:		Returns true if trees are the same
		//	Postcond:	None

		char* PostOrderString(TreeNode<T>* t);
		char* PostOrderString(TreeNode<T>* t, char* string);
		//	Input:		Node to be scanned
		//	Precond:	None
		//	Process:	Creates string in PostOrder
		//	Output:		Returns string in PostOrder
		//	Postcond:	None

		void Simplify(TreeNode<T>* t);
		//	Input:		Node to be simplified
		//	Precond:	None
		//	Process:	Simplifies two duplicate trees
		//	Output:		None
		//	Postcond:	None

		void SimplifyZero(TreeNode<T>* t);
		//	Input:		Node to be simplified
		//	Precond:	None
		//	Process:	Simplifies tree that has a zero attached to it
		//	Output:		None
		//	Postcond:	None

		void SimplifyOne(TreeNode<T>* t);
		//	Input:		Node to be simplified
		//	Precond:	None
		//	Process:	Simplifies tree that has a one attached to it
		//	Output:		None
		//	Postcond:	None

	public:
		BinTree(void);
		//	Input:		None
		//	Precond:	None
		//	Process:	Constructor
		//	Output:		None
		//	Postcond:	None

		BinTree(const BinTree<T>& rhs);
		//	Input:		None
		//	Precond:	None
		//	Process:	Copy Constructor
		//	Output:		None
		//	Postcond:	None

		~BinTree(void);
		//	Input:		None
		//	Precond:	None
		//	Process:	Destructor
		//	Output:		None
		//	Postcond:	None

		BinTree<T>& operator= (const BinTree& rhs);
		//	Input:		None
		//	Precond:	None
		//	Process:	Assignment operator
		//	Output:		None
		//	Postcond:	None

		void ClearTree(TreeNode<T>* t = NULL);
		//	Input:		None (argument is used for recursive use)
		//	Precond:	None
		//	Process:	Deletes entire tree
		//	Output:		None
		//	Postcond:	None

		void Insert(const T& item);
		//	Input:		Data of item
		//	Precond:	None
		//	Process:	Inserts item into the tree
		//	Output:		None
		//	Postcond:	None

		void PrintTree(int level = 0);
		void PrintTree(TreeNode<T>* t, int level = 0);
		//	Input:		None (arguments are for recursive use)
		//	Precond:	None
		//	Process:	Prints the tree
		//	Output:		None
		//	Postcond:	None

		void PreOrder(void);
		void PreOrder(TreeNode<T>* t);
		//	Input:		None (arguments are for recursive use)
		//	Precond:	None
		//	Process:	Prints the tree in PreOrder
		//	Output:		None
		//	Postcond:	None

		void InOrder(void);
		void InOrder(TreeNode<T>* t);
		//	Input:		None (arguments are for recursive use)
		//	Precond:	None
		//	Process:	Prints the tree in InOrder
		//	Output:		None
		//	Postcond:	None

		void PostOrder(void);
		void PostOrder(TreeNode<T>* t);
		//	Input:		None (arguments are for recursive use)
		//	Precond:	None
		//	Process:	Prints the tree in PostOrder
		//	Output:		None
		//	Postcond:	None

		void FindDouble(void);
		void FindDouble(TreeNode<T>* t);
		//	Input:		None (arguments are for recursive use)
		//	Precond:	None
		//	Process:	Finds a node with two of them same children
		//	Output:		None
		//	Postcond:	None

		void PostOrderFind(void);
		void PostOrderFind(TreeNode<T>* t);
		//	Input:		None (arguments are for recursive use)
		//	Precond:	None
		//	Process:	Finds 1s or 0s in the tree then simplifies them
		//	Output:		None
		//	Postcond:	None

};

template <class T>
BinTree<T>::BinTree(void)
{
	root = curr = NULL;
	size = 0;
}

template <class T>
BinTree<T>::~BinTree(void)
{
	ClearTree();
}

template <class T>
BinTree<T>::BinTree(const BinTree<T>& rhs)
{
	int index, length;
	char* string;
	string = new char[100];
	strcpy(string, PostOrderString(rhs.root));
	length = strlen(string);
	index = length - 1;
	for (index ; index >= 0 ; index--)
	{
		Insert(string[index]);
	}
	delete [] string;
}

template <class T>
BinTree<T>& BinTree<T>::operator= (const BinTree& rhs)
{
	int index, length;
	char* string;
	string = new char[100];
	strcpy(string, PostOrderString(rhs.root));
	length = strlen(string);
	index = length - 1;
	for (index ; index >= 0 ; index--)
	{
		Insert(string[index]);
	}
	delete [] string;
	return *this;
}

template <class T>
void BinTree<T>::ClearTree(TreeNode<T>* t)
{
	t = root;
	DeleteTree(t);
	t = curr = root = NULL;
	size = 0;
}


template <class T>
TreeNode<T>* BinTree<T>::GetTreeNode(const T& item)
{
	TreeNode<T>* NewTreeNode;
	NewTreeNode = new TreeNode<T>(item);
	if (NewTreeNode == NULL)
	{
		cerr << "Memory allocation failure!\n";
		exit(1);
	}
	return NewTreeNode;
}

template <class T>
void BinTree<T>::FreeNode(TreeNode<T> *t)
{
	delete t;
}

template <class T>
void BinTree<T>::Insert(const T& item)
{
	static bool locked = false;
	if (size == 0)
	{
		root = GetTreeNode(item);
		curr = root;
		if (isalnum(item))
			locked = true;
		size++;
	}
	else
	{
		if (isalnum(item) && curr->LookRight())
		{
			curr->SetRight(GetTreeNode(item)); 
			size++;
		}
		else if (isalnum(item) && curr->LookLeft())
		{
			curr->SetLeft(GetTreeNode(item));
			size++;
		}
		else if (curr->LookRight())
		{
			curr->SetRight(GetTreeNode(item));
			curr = curr->Right();
			size++;
		}
		else if (curr->LookLeft())
		{
			curr->SetLeft(GetTreeNode(item));
			curr = curr->Left();
			size++;
		}
		else
		{
			curr = curr->Up();
			Insert(item);
		}
	}
}

template <class T>
void BinTree<T>::DeleteTree(TreeNode<T>* t)
{	
	if (t != NULL)
	{
		DeleteTree(t->Left());
		DeleteTree(t->Right());
		FreeNode(t);
	}
}

template <class T>
void BinTree<T>::IndentBlanks(int num)
{
	for (int i = 0 ; i < num ; i++)
		cout << " ";
}

template <class T>
void BinTree<T>::PrintTree(int level)
{
	if (size == 0)
	{
		cout << "Empty Tree\n";
		return;
	}
	TreeNode<T>* t;
	t = root;
	if (t != NULL)
	{
		PrintTree(t->Right(),level+1);
		IndentBlanks(6*level);
		cout << t->Data() << endl;
		PrintTree(t->Left(), level+1);
	}
}

template <class T>
void BinTree<T>::PrintTree(TreeNode<T>* t, int level)
{
	if (t != NULL)
	{
		PrintTree(t->Right(),level+1);
		IndentBlanks(6*level);
		cout << t->Data() << endl;
		PrintTree(t->Left(), level+1);
	}
}

template <class T>
void BinTree<T>::PreOrder(void)
{
	TreeNode<T>* t;
	t = root;
	if (t != NULL)
	{	
		cout << t->Data() << " ";
		PreOrder(t->Left());
		PreOrder(t->Right());
	}
	cout << endl;
}

template <class T>
void BinTree<T>::PreOrder(TreeNode<T>* t)
{
	if (t != NULL)
	{	
		cout << t->Data() << " ";
		PreOrder(t->Left());
		PreOrder(t->Right());
	}
}

template <class T>
void BinTree<T>::InOrder(void)
{
	TreeNode<T>* t;
	t = root;
	if (t != NULL)
	{
		InOrder(t->Left());
		cout << t->Data() << " ";
		InOrder(t->Right());
	}
	cout << endl;
}

template <class T>
void BinTree<T>::InOrder(TreeNode<T>* t)
{
	if (t != NULL)
	{
		if (!(t->LookLeft()&&t->LookRight()))
			cout << "( ";
		InOrder(t->Left());
		cout << t->Data() << " ";
		InOrder(t->Right());
		if (!(t->LookLeft()&&t->LookRight()))
			cout << ") ";
	}
}

template <class T>
void BinTree<T>::PostOrder(void)
{
	TreeNode<T>* t;
	t = root;
	if (t != NULL)
	{
		PostOrder(t->Left());
		PostOrder(t->Right());
		cout << t->Data() << " ";
	}
	cout << endl;
}

template <class T>
void BinTree<T>::PostOrder(TreeNode<T>* t)
{
	if (t != NULL)
	{
		PostOrder(t->Left());
		PostOrder(t->Right());
		cout << t->Data() << " ";
	}
}

template <class T>
char* BinTree<T>::PostOrderString(TreeNode<T> *t)
{
	char *string;
	string = new char[30];
	char holder[2];
	string[0] = '\0';
	if (t != NULL)
	{
		strcpy(string,PostOrderString(t->Left(),string));
		strcpy(string,PostOrderString(t->Right(),string));
		holder[0] = t->Data();
		holder[1] = '\0';
		strcat(string, holder);
	}
	return string;
}

template <class T>
char* BinTree<T>::PostOrderString(TreeNode<T> *t, char* string)
{
	char holder[2];
	if (t != NULL)
	{
		strcpy(string,PostOrderString(t->Left(),string));
		strcpy(string,PostOrderString(t->Right(),string));
		holder[0] = t->Data();
		holder[1] = '\0';
		strcat(string, holder);
	}
	return string;
}

template <class T>
void BinTree<T>::FindDouble(void)
{
	TreeNode<T> *t;
	t = root;
	if (!(t->LookLeft() && t->LookRight()))
	{
		if (t->WhatLeft() == t->WhatRight())
		{
			if (SameTree(t->Left(),t->Right()))
			{
				Simplify(t);
			}
			else
			{
				FindDouble(t->Left());
				FindDouble(t->Right());
			}

		}
		else if (t != NULL)
		{
			FindDouble(t->Left());
			FindDouble(t->Right());
		}
	}
	else if (t->LookLeft() && t->LookRight())
		return;
}

template <class T>
void BinTree<T>::FindDouble(TreeNode<T>* t)
{
	if (!(t->LookLeft() && t->LookRight()))
	{
		if (t->WhatLeft() == t->WhatRight())
		{
			if (SameTree(t->Left(),t->Right()))
			{
				Simplify(t);
			}
			else
			{
				FindDouble(t->Left());
				FindDouble(t->Right());
			}
		}
		else if (t != NULL)
		{
			FindDouble(t->Left());
			FindDouble(t->Right());
		}
	}
	else if (t->LookLeft() && t->LookRight())
		return;
}

template <class T>
bool BinTree<T>::SameTree(TreeNode<T>* t1, TreeNode<T>* t2)
{
	if (strcmp(PostOrderString(t1),PostOrderString(t2)) == 0)
		return true;
	else return false;
}

template <class T>
void BinTree<T>::Simplify(TreeNode<T>* t)
{
	char op = t->Data();
	if (op == '+')
	{
		if (isdigit(t->WhatLeft())&&isdigit(t->WhatRight()))
			return;
		else
		{
			DeleteTree(t->Right());
			t->RemoveRight();
			t->SetRight(GetTreeNode('2'));
			t->ChangeData('*');
		}
	}
	else if (op == '-')
	{
		if (t == root)
		{
			ClearTree();
		}
		else
		{
			DeleteTree(t->Right());
			t->RemoveRight();
			DeleteTree(t->Left());
			t->RemoveLeft();
			t->ChangeData('0');
		}
	}
	else if (op == '/')
	{
		DeleteTree(t->Right());
		t->RemoveRight();
		DeleteTree(t->Left());
		t->RemoveLeft();
		t->ChangeData('1');
	}

}

template <class T>
void BinTree<T>::PostOrderFind(void)
{
	TreeNode<T>* t;
	t = root;
	if (t != NULL)
	{
		PostOrderFind(t->Left());
		PostOrderFind(t->Right());
		if (t->Data() == '0')
			SimplifyZero(t);
		else if (t->Data() == '1')
			SimplifyOne(t);
	}
}

template <class T>
void BinTree<T>::PostOrderFind(TreeNode<T>* t)
{ 
	if (t != NULL)
	{
		PostOrderFind(t->Left());
		PostOrderFind(t->Right());
		if (t->Data() == '0')
			SimplifyZero(t);
		else if (t->Data() == '1')
			SimplifyOne(t);
	}
}

template <class T>
void BinTree<T>::SimplifyZero(TreeNode<T>* t)
{
	TreeNode<T>* store;
	if ((t->WhatUp() == '+')||(t->WhatUp() == '-'))
	{
		TreeNode<T>* initial = t;
		t = t->Up();
		store = t->Up();
		if (t == root)
		{
			if (root->WhatLeft() != '0')
			{
				root->RemoveRight();
				root = root->Left();
			}
			else if (root->WhatRight() != '0')
			{
				root->RemoveLeft();
				root = root->Right();
			}
		}	

		else
		{		
			t->RemoveSelfFromUp();
			if (t->Left() == initial)
			{
				if (store->Left() == NULL)
					store->SetLeft(t->Right());
				else if (store->Right() == NULL)
					store->SetRight(t->Right());
			}
			else if (t->Right() == initial)
			{
				if (store->Left() == NULL)
					store->SetLeft(t->Left());
				else if (store->Right() == NULL)
					store->SetRight(t->Left());
			}
		}
	}

	else if (t->WhatUp() == '*')
	{
		TreeNode<T>* zero;
		TreeNode<T>* initial = t;
		t = t->Up();
		store = t->Up();

		if (t == root)
		{
			root = curr = GetTreeNode('0');
			size = 1;
		}
		else 
		{
			t->RemoveSelfFromUp();
			zero = GetTreeNode('0');
			if (store->Right() == NULL)
				store->SetRight(zero);
			else if (store->Left() == NULL)
				store->SetLeft(zero);
			SimplifyZero(zero);
		}

	}
}

template <class T>
void BinTree<T>::SimplifyOne(TreeNode<T>* t)
{
	TreeNode<T>* store;
	if (t->WhatUp() == '*')
	{
		TreeNode<T>* initial = t;
		t = t->Up();
		store = t->Up();
		if (t == root)
		{
			if (root->WhatLeft() != '1')
			{
				root->RemoveRight();
				root = root->Left();
			}
			else if (root->WhatRight() != '1')
			{
				root->RemoveLeft();
				root = root->Right();
			}
		}	
		else
		{		
			t->RemoveSelfFromUp();
			if (t->Left() == initial)
			{
				if (store->Left() == NULL)
					store->SetLeft(t->Right());
				else if (store->Right() == NULL)
					store->SetRight(t->Right());
			}
			else if (t->Right() == initial)
			{
				if (store->Left() == NULL)
					store->SetLeft(t->Left());
				else if (store->Right() == NULL)
					store->SetRight(t->Left());
			}
		}
	}
}