/*      Author:         R.P. Patillo
        Instructor:     Dr. Ames
        Due Date:       Now. 13, 2008
        Complilation:   g++ stutreeclient.cpp -o stutreeclient.out
        Execution:      ./stutreeclient.out
*/

// stutree.cpp - implementation file for tree.h

#include <iostream>
using namespace std;

// ------------------- Public Gradetree members ----------------------
//
// These can be called from clients.
// Each has a corresponding recursive private member
// 
// -------------------------------------------------------------------

// default constructor
Gradetree::Gradetree ()
{
root = NULL;
}

// copy constructor - for deep copies
Gradetree::Gradetree (const Gradetree& othergradetree)
{
	root = copytree (othergradetree.root);
}

// destructor
Gradetree::~Gradetree ()
{
	destroytree (root);
}

// overload assignment for deep copies
void Gradetree::operator= (const Gradetree& othergradetree)
{
	root = copytree (othergradetree.root);
}

// visit inorder and display grades
void Gradetree::Inorder ()
{
	Inorder (root);
}

// visit preorder and display grades
void Gradetree::Preorder ()
{
	Preorder (root);
}

// visit postorder and display grades
void Gradetree::Postorder ()
{
	Postorder (root);
}

// display a sideways "picture" of the tree
void Gradetree::TreePicture ()
{
	Treepicture (root, 1);
}

// add a new grade to the tree
void Gradetree::Insert (int newgrade)
{
	Insert (root, newgrade);
}

// delete one occurrence of a grade from the tree
void Gradetree::Delete (int delgrade)
{
        Delete (root, delgrade);
}

// sum of grades within tree 
int Gradetree::SumGrades()
{
	SumGrades(root);
}

// number of grades within tree
int Gradetree::NumGrades()
{
	NumGrades(root);
}

// calculates the avg. of grades in tree
float Gradetree::AvgGrade()
{
        return SumGrades(root)/ NumGrades(root);
}

// number of nodes within tree
int Gradetree::NodeCount()
{
	return NodeCount(root);
}

// the number of leaves in the tree
int Gradetree::LeafCount()
{
	return LeafCount(root);
}

// the number of nodes that aren't nodes within tree
int Gradetree::NonLeafCount()
{
	return NonLeafCount(root);
}

// checks if the two trees have the same shape
bool Gradetree::SimilarTrees(Gradetree othertree)
{
	return SimilarTrees(root, othertree);
}


// the height of the tree
int Gradetree::Height()
{
	return Height(root);
}
	
// ------------------- Private Gradetree members ----------------------
// 
// These are used by the public members.
// They are necessary to facilitate the recursion.
//
// --------------------------------------------------------------------

// used by copy constructor and operator=
Treenode* Gradetree::copytree (Treenode* t)
{
    Treenode* tmp = NULL;  // for building copy of t

    if (t != NULL)
    {
	tmp = new Treenode;
	tmp->grade = t->grade;
	tmp->count = t->count;
	tmp->left = copytree (t->left);
	tmp->right = copytree (t->right);
    }

    return tmp;
}

// used by destructor
void Gradetree::destroytree (Treenode* t)
{
    if (t != NULL)
    {
	destroytree (t->left);
	destroytree (t->right);
	delete t;
    }
}

void Gradetree::Inorder (Treenode* t)
{
    if (t != NULL)
    {
	Inorder (t->left);
	cout << t->grade << " ";
	Inorder (t->right);
    }
}

void Gradetree::Preorder (Treenode* t)
{
    if (t != NULL)
    {
	cout << t->grade << " ";
	Preorder (t->left);
	Preorder (t->right);
    }
}

void Gradetree::Postorder (Treenode* t)
{
    if (t != NULL)
    {
	Postorder (t->left);
	Postorder (t->right);
	cout << t->grade << " ";
    }
}

void Gradetree::Treepicture (Treenode* t, int level)  // start w/ level == 1
{
    if (t != NULL)
    {
	Treepicture (t->right, level+1);
	for (int i = 1; i < level; i++)  // spacing to "drop" to correct level
		cout << "     ";
	cout << t->grade << "\n";
	Treepicture (t->left, level+1);
    }
}

void Gradetree::Insert (Treenode* &t, int newgrade)
{
    if (t == NULL)  // this is spot where grade belongs
    {
	t = new Treenode;
	t->grade = newgrade;
	t->count = 1;
	t->left = NULL;
	t->right = NULL;
    }
    else  if (newgrade > t->grade)
	Insert (t->right, newgrade);
    else  if (newgrade < t->grade)
	Insert (t->left, newgrade);
    else
	t->count++;
}

void Gradetree::Delete (Treenode* &t, int delgrade) 
{
    if (t == NULL) // grade is not in tree - abort!
        return;
    else if (delgrade < t->grade)
	Delete (t->left, delgrade);
    else if (delgrade > t->grade)
	Delete (t->right, delgrade);
    else  // match found
	if (t->count > 1)  // just subtract if >1 of this grade
	    t->count--;
	else               // need to delete grade node
	{
	    Treenode* temp = t;  // note t is actually parent link to node!
	    if (t->left == NULL && t->right == NULL)  // case 1: delete leaf
	    {
		t = NULL;
		delete temp;
	    }
	    else if (t->left == NULL)  // case 2: no left child, connect to right
	    {
		t = t->right;
		delete temp;
	    }
	    else if (t->right == NULL)  // case 2: no right child, connect to left
	    {
		t = t->left;
		delete temp;
	    }
	    else // yikes - it's a case 3 node!
	    {
		temp = t->left;                // once to left ...
		while (temp->right != NULL)    // ... all the way down right
		    temp = temp->right;    //     to immediate pred.
	        t->grade = temp->grade;        // copy pred to this node
		Delete (t->left, temp->grade); // now delete pred
	    }
	}
}

int Gradetree::SumGrades(Treenode* t)
{
	if (t != NULL)
	{
	    return (SumGrades(t->left) + SumGrades(t->right) + t->grade * t->count);
	}

	else
	    return 0;
}

int Gradetree::NumGrades(Treenode* t)
{
	if (t != NULL)
	{
	    return (NumGrades(t->left) + NumGrades(t->right) + t->count);
	}

	else
	    return 0;
}


int Gradetree::NodeCount(Treenode* t)
{
	if (t != NULL)
	{
	    return (NodeCount(t->left) + NodeCount(t->right) + 1);
	}

	else
	    return 0;
}

int Gradetree::LeafCount(Treenode* t)
{
	if (t!= NULL)
	{
	    if (t->left == NULL && t->right == NULL)
		return 1;
	
	    else
		return (LeafCount(t->left) + LeafCount(t->right));
	}
	else
	    return 0;
}

int Gradetree::NonLeafCount(Treenode* t)
{
	if (t!= NULL)
	{
	    if (t->left != NULL || t->right != NULL)
		return (NonLeafCount(t->left) + NonLeafCount(t->right) + 1);
	
	    else
		return 0;
	}

	else 
	    return 0;
}

bool Gradetree::SimilarTrees(Treenode* t, Gradetree othertree)
{
	if (t!=NULL)
	{
	    if(NodeCount(t) == othertree.NodeCount())
	    {
		if(LeafCount(t) == othertree.LeafCount())
		{
		    if(NonLeafCount(t) == othertree.NonLeafCount())
			return true;
		}
	    }
	    else
		return false;
	}

	else
	    return false;
}

int Gradetree::Height(Treenode* t)
{
	if (t!=NULL)
	{
 	    if (Height(t->right) > Height(t->left))
		return Height(t->right) + 1;
	    else
		return Height(t->left) + 1;
	}	
	else
	    return 0;
}