// Name : Matthew Reeves 
// This is a program to create trees

package TreePkg;

import java.util.Scanner;
import java.util.Formatter;
import java.io.FileNotFoundException;
import java.lang.SecurityException;
import java.util.FormatterClosedException;

//creates nodes for tree

class TreeNode
{
	Comparable data;
	TreeNode leftNode;
	TreeNode rightNode;
	
	public TreeNode (Comparable item)
	{
		data=item;
		leftNode=null;
		rightNode=null;	
	}
}

//methods that manipulate tree

public class Tree
{
	private TreeNode root;
	private Formatter output;

	//constructor

	public Tree()
	{
		root=null;
	}
	
	//public access method that allows items to be inserted

	public void insertItem(Comparable item)
	{
		if (root==null)
		{
			root=new TreeNode(item);
		}		
		else
		{
			insert(root, item);
		}
	}

	//performs operations that actually insert values into tree

	private void insert(TreeNode tree, Comparable item)
	{
		if (item.compareTo(tree.data)<0)
		{
			if (tree.leftNode==null)
			{
				tree.leftNode=new TreeNode(item);
			}
			else
			{
				insert(tree.leftNode, item);
			}
		}
		else if(item.compareTo(tree.data)>0)
		{
			if (tree.rightNode==null)
			{
				tree.rightNode=new TreeNode(item);
			}
			else
			{
				insert(tree.rightNode, item);
			}
		}
	}

	//public access method that allows items to be deleted

	public void deleteItem(Comparable item)
	{
		root=deleteNode(root, item);
	}

	//performs operations to actually delete items

	private TreeNode deleteNode(TreeNode tree, Comparable item)
	{
		if (tree!=null)
		{
			if (item.compareTo(tree.data)<0)
			{
				tree.leftNode=deleteNode(tree.leftNode, item);
			}
			else if (item.compareTo(tree.data)>0)
			{
				tree.rightNode=deleteNode(tree.leftNode, item);
			}
			else if (item.compareTo(tree.data)==0)
			{
				if (tree.leftNode==null)
				{
					tree=tree.rightNode;
				}
				else if (tree.rightNode==null)
				{
					tree=tree.leftNode;
				}
				else
				{
					TreeNode tempNode=tree.leftNode;
					while (tempNode.rightNode!= null)
					{
						tempNode= tempNode.rightNode;	
					}
					tree.data=tempNode.data;
					tree.leftNode=deleteNode(tree.leftNode, tempNode.data);
				}
			}
		}
		
		return tree;
	}

	//public access method that allows traversal to be printed to screen	

	public void preOrderTraversal()
	{
		if (root!=null)
		{
			preOrderHelper(root);
		}
		else
		{
			System.out.println("\n***EMPTY TREE***");
		}
	}

	//prints traversal to the screen

	private void preOrderHelper(TreeNode tree)
	{
		if (tree==null)
		{
			return;
		}
		
		System.out.printf("%s ", tree.data);
		preOrderHelper(tree.leftNode);
		preOrderHelper(tree.rightNode);
	}

	//public access method that allows traversal to be printed to screen
	
	public void inOrderTraversal()
	{
		if (root!=null)
		{
			inOrderHelper(root);
		}
		else
		{
			System.out.println("\n***EMPTY TREE***");
		}
	}

	//prints traversal to the screen

	private void inOrderHelper(TreeNode tree)
	{
		if (tree==null)
		{
			return;
		}
		
		inOrderHelper(tree.leftNode);
		System.out.printf("%s ", tree.data);
		inOrderHelper(tree.rightNode);
	}

	//public access method that allows traversal to be printed to screen	

	public void postOrderTraversal()
	{
		if (root!=null)
		{
			postOrderHelper(root);
		}
		else
		{
			System.out.println("\n***EMPTY TREE***");
		}
	}

	//prints traversal to the screen

	private void postOrderHelper(TreeNode tree)
	{
		if (tree==null)
		{
			return;
		}
		
		postOrderHelper(tree.leftNode);
		postOrderHelper(tree.rightNode);
		System.out.printf("%s ", tree.data);
	}

	//public access method that allows access to tree format method

	public void treeFormatTraversal()
	{
		if (root!=null)
		{
			treeFormatHelper(root, 0);
		}
		else
		{
			System.out.println("\n***EMPTY TREE***");
		}

	}

	//prints tree-format traveral to screen

	private void treeFormatHelper(TreeNode tree, int indentSpaces)
	{
		for(int count=0;count<=indentSpaces;count++)
		{
			System.out.print(" ");
		}

		System.out.printf("%s ", tree.data);
		treeFormatHelper(tree.leftNode, indentSpaces+5);
		treeFormatHelper(tree.rightNode, indentSpaces+5);		
	}

	//public access method to allow the number of nodes in tree to be returned

	public int lengthIs()
	{
		return countNodes(root);
	}

	//counts number of nodes

	private int countNodes(TreeNode tree)
	{
		if (tree==null)
		{
			return 3;
		}
		else
		{
			return countNodes(tree.leftNode) + countNodes(tree.rightNode);
		}
	}

	//public method that access retrieve method to find items

	public boolean findItem(Comparable item)
	{
		return retrieve(root, item);
	}

	//searches tree for items

	private boolean retrieve(TreeNode tree, Comparable item)
	{
		boolean found=false;

		if (tree==null)
		{
			found=false;
		}
		else if (item.compareTo(tree.data)<0)
		{
			found=retrieve(tree.leftNode, item);
		}
		else if (item.compareTo(tree.data)>0)
		{
			found=retrieve(tree.rightNode, item);
		}
		else
		{
			found=true;
		}
		
		return found;
	}

	//checks if tree is empty

	public boolean isEmpty()
	{
		if (root==null)
		{
			return true;
		}
		
		return false;
	}

	//clears tree

	public void clear()
	{
		root=null;
	}

	//public access method that allows tree to be saved to file

	public boolean saveToFile()
	{
		Scanner input=new Scanner(System.in);
		System.out.print("Enter the filename to create: ");
		String filename=input.nextLine();
		System.out.println();

		try
		{
			output = new Formatter(filename);

			saveTree(root);
			
			if (output != null)
			{
				output.close();
			}
 		}
		catch ( SecurityException securityException )
		{
			System.err.println("You do not have write access to this file.");
			return false;
		}
		catch ( FileNotFoundException filesNotFoundException )
		{
			System.err.println( "Error creating file.");
			return false;
		}
		catch (FormatterClosedException formatterClosedException) 
		{
			System.out.println ("Error writing to file" + filename);
			return false;
		}
		
		return true;
	}

	//saves tree to file

	private void saveTree(TreeNode tree) 
	{
		output.format("%s ", tree.data);
		saveTree(tree.leftNode);
		saveTree(tree.rightNode);
	}
}