//********************************************************************************
// Louis Gliozzi		2/19/08		To Do List
// This program will create a to do list and associate an estimated time it will
// take to complete each task. This holds the variables for that list.
//*********************************************************************************

public class StudentTree
{
	StudentNode root;

	public StudentTree()
	{
		root = null;
	}

	//check if a child is a leaf or not
	public boolean isLeaf(StudentNode x)
	{
		if((x.lchild == null) && (x.rchild == null))
			return true;
		else
			return false;
	}

	//check if the tree is empty
	public boolean isEmpty()
	{
		if (root == null)
			return true;
		else
			return false;
	}

	//add a StudentNode
	public void add(String name, double GPA)
	{
		StudentNode ptr;

		//case for an empty tree
		if(isEmpty())
		{
			StudentRecord studentFile = new StudentRecord(name, GPA);
			root = new StudentNode(studentFile, null, null);
			return;
		}

		ptr = root;
		while (true)
		{
			if(name.compareToIgnoreCase(ptr.record.name) < 0)
			{
				//goes on left side
				if (ptr.lchild == null)
				{
					ptr.lchild = new StudentNode(new StudentRecord(name, GPA), null, null);
					return;
				}
				else
				{
					ptr = ptr.lchild;
				}
			}
			else
			{
				//goes on right side
				if (ptr.rchild == null)
				{
					ptr.rchild = new StudentNode(new StudentRecord(name, GPA), null, null);
					return;
				}
				else
				{
					ptr = ptr.rchild;
				}
			}
		}
	}

	//find GPA
	public String find(String name)
	{
		StudentNode ptr;
		final String notfound = "GPA not found";

		if(isEmpty())
		{
			return notfound;
		}
		ptr = root;
		while (ptr != null)
		{
			if(name.equalsIgnoreCase(ptr.record.name))
			{
				return Double.toString(ptr.record.GPA);
			}
			else if (name.compareToIgnoreCase(ptr.record.name) < 0)
			{
				ptr = ptr.lchild;
			}
			else
			{
				ptr = ptr.rchild;
			}
		}
		return notfound;
	}

	//print all students in alphabetical order
	public String printAlphabetical()
	{
		if (isEmpty())
		{
			return "No students on file";
		}
		else
		{
			return recursivePrint(root);
		}
	}
	public String recursivePrint(StudentNode ptr)
	{
		String retString = "";

		//print lchild
		if (ptr.lchild != null)
		{
			retString = recursivePrint(ptr.lchild);
		}
		//print me
		retString = retString + ptr.record.name + "\t" + ptr.record.GPA;
		//print rchild
		if (ptr.rchild != null)
		{
			retString = recursivePrint(ptr.rchild);
		}
		return retString;
	}
	//print all students in reverse alphabetical order
	public String printReverseAlphabetical()
	{
		if (isEmpty())
		{
			return "No students on file";
		}
		else
		{
			return reverseRecursivePrint(root);
		}
	}
	public String reverseRecursivePrint(StudentNode ptr)
	{
		String retString = "";

		//print rchild
		if (ptr.rchild != null)
		{
			retString = recursivePrint(ptr.rchild);
		}
		//print me
		retString = retString + ptr.record.name + "\t" + ptr.record.GPA;
		//print lchild
		if (ptr.lchild != null)
		{
			retString = recursivePrint(ptr.lchild);
		}

		return retString;
	}

	//change GPA
	public void changeGPA(String name, double GPA)
	{
		StudentNode ptr;
		final String notfound = "Student not found";

		if(isEmpty())
		{
			add(name, GPA);
			return;
		}
		ptr = root;
		while (ptr != null)
		{
			if(name.equalsIgnoreCase(ptr.record.name))
			{
				ptr.record.GPA = GPA;
			}
			else if (name.compareToIgnoreCase(ptr.record.name) < 0)
			{
				ptr = ptr.lchild;
			}
			else
			{
				ptr = ptr.rchild;
			}
		}
		return;
	}

	//average GPA
	public String average()
	{
		if (isEmpty())
		{
			return "No students on file";
		}
		else
		{
			return Double.toString(recursiveGPA(root));
		}
	}

	public double recursiveGPA(StudentNode ptr)
	{
		double totalGPA	= 0;
		int iterations	= 0;

		//add lchild
		if (ptr.lchild != null)
		{
			totalGPA = recursiveGPA(ptr.lchild);
		}
		//add me
		totalGPA = totalGPA + ptr.record.GPA;
		iterations++;
		//add rchild
		if (ptr.rchild != null)
		{
			totalGPA = recursiveGPA(ptr.rchild);
		}
		return totalGPA/iterations;
	}
}