/***
Saeteurn, San
ect_sfs@ecst.csuchico.edu
15b Program 7: Train Schedule
***/
#include "stree.h"
STree::~STree()
{
	remove(m_root);
}
bool STree::insert(string oCity,string desCity,Node *root)
{
	if(m_root == NULL)
	{
		m_root = new Node(oCity);
		m_root->m_left = new Node(desCity);
		return true;
	}
	else if(lookUp(desCity,m_root) != NULL)
	{
		return false;
	}
	else if(m_root->m_city == oCity)
	{
		if(m_root->m_left == NULL)
		{
			m_root->m_left = new Node(desCity);
			return true;
		}
		else if(m_root->m_right == NULL)
		{
			m_root->m_right = new Node(desCity);
			return true;
		}
		else
		{
			return false;
		}
	}
	else
	{
		Node *targ = lookUp(oCity,root);
		if(targ == NULL)
		{
			return false;
		}
		else
		{
			if(targ->m_left == NULL)
			{
				targ->m_left = new Node(desCity);
				return true;
			}
			else if(targ->m_right == NULL)
			{
				targ->m_right = new Node(desCity);
				return true;
			}
			else
			{
				return false;
			}
		}
	}
}
STree::Node* STree::findParent(string target,Node *root)
{
	if(root == NULL || (root->m_left == NULL && root->m_right == NULL))
        {
                return NULL;
        }
        else if(root->m_city == target)
        {
                return NULL;
        }
        else if(root->m_left != NULL && root->m_left->m_city == target)
        {
		return root;
        }
        else if(root->m_right != NULL && root->m_right->m_city == target)
        {
		return root;
        }
	else
	{
		if(root->m_left != NULL)
		{
			Node *tmp = findParent(target,root->m_left);
			if(tmp == NULL)
			{
				return findParent(target,root->m_right);
			}
			else
			{
				return tmp; 
			}
		}
	}
}
bool STree::remove(string city)
{
	if(m_root == NULL)
	{
		return false;
	}
	else if(m_root->m_city == city)
	{
		return remove(m_root);
	}
	Node *parent = findParent(city,m_root);
	if(parent == NULL)
	{
		return false;
	}
	else
	{
		if(parent->m_left != NULL && parent->m_left->m_city == city)
		{
			return remove(parent->m_left);
		}
		else if(parent->m_right != NULL && parent->m_right->m_city == city)
		{
			return remove(parent->m_right);
		}
	}
}
bool STree::remove(Node *&root)
{
	if(root == NULL)
	{
		return false;
	}
	if(root->m_left == NULL)
	{
		if(root->m_right == NULL)
		{
			delete root;
			root = NULL;
			return true;
		}
		else
		{
			remove(root->m_right);
		}
	}
	else
	{
		remove(root->m_left);
		remove(root->m_right);
		delete root;
		root = NULL;
		return true;
	}
}
bool STree::print(string oCity,string &desCity,string &desCity2)
{
	Node *theCity = lookUp(oCity,m_root);
	if(theCity == NULL)
	{
		return false;
	}
	else
	{
		if(theCity->m_left == NULL)
		{
			desCity = "none";
		}
		else
		{
			desCity = theCity->m_left->m_city;
		}
		if(theCity->m_right == NULL)
		{
			desCity2 = "none";
		}
		else
		{
			desCity2 = theCity->m_right->m_city;
		}
		return true;
	}
}
STree::Node* STree::lookUp(string city,Node *root)
{
	if(root == NULL)
	{
		return NULL;
	}
	else if(root->m_city == city)
	{
		return root;
	}
	else if(root->m_left != NULL)
	{
		Node *tmp = lookUp(city,root->m_left);
		if(root->m_right != NULL && tmp == NULL)
		{
			return lookUp(city,root->m_right);
		}
		else
		{
			return tmp;
		}
	}
	else if(root->m_right != NULL)
	{
		return lookUp(city,root->m_right);
	}
	else
	{
		return NULL;
	}
}
bool STree::distance(string oCity,string desCity,int &dis)
{
	Node *start = lookUp(oCity,m_root);
	Node *end = NULL;
	if(start != NULL)
	{
		end = lookUp(desCity,start);
	}
	else
	{
		return false;
	}
	if(end == NULL)
	{
		return false;
	}
	else
	{
		assert(start != NULL && end != NULL);
		return distance(start,desCity,dis);
	}
}
bool STree::distance(Node *root,string desCity,int &dis)
{
	if(root == NULL)
	{
		return false;
	}
	else if(root->m_city == desCity)
	{
		return true;
	}
	else if(root->m_left != NULL)
	{
		if(distance(root->m_left,desCity,dis) == false)
		{
			if(distance(root->m_right,desCity,dis) == false)
			{
				return false;
			}
			else
			{
				dis++;
				return true;
			}
		}
		else
		{
			dis++;
			return true;
		}
	}
	else if(root->m_right != NULL)
	{
		if(distance(root->m_right,desCity,dis) == false)
		{
			return false;
		}
		else
		{
			dis++;
			return true;
		}
	}
	else
	{
		return false;
	}
}