//******************************************************************
// Main.C
//******************************************************************
#include "Tree.h"
#include <iostream>
using namespace std;

// ----Main Class----
//
// Calls the appropriate method based on user input.
// a = add
// r = remove
// s = size
// c = contains
// p = print
// q = quit
//

int main ( )
{
BSTree mytree; // creates new tree

// Creates a buffer array for the input line to be stored on
char buffer[200];
while ( !cin.eof() )
{

cin.getline ( buffer, 200 );

// Scans the input line for a certain character predefined
// in the assignment. Input is set as the location of the
// found character + 2 to increment position to the parameter
// variable. Subtracting '0' gives the value of the character.
for (int i = 0 ; buffer[i] != '\0' ; i++ )
{
//------ADD------
if ( buffer[i] == 'a' )
{
int * input = new int;
int k;
for (k = i ; buffer[k+2] != '\0' ; k++)
*input = (*input*10) + (buffer[k+2] - '0');

if(mytree.add( input ))
cout << *input << " successfully added to tree" << endl;
i = k+1;
}

//------REMOVE------
else if ( buffer[i] == 'r' )
{
int * input = new int;
for (int k = i ; buffer[k+2] != '\0' ; k++)
*input = (*input*10) + (buffer[k+2] - '0');

if (mytree.contains ( *input ) == 1)
{
mytree.remove( *input );
}
else
cout << *input << " is not located in the tree" << endl;
}

//------CONTAINS------(done)
else if ( buffer[i] == 'c' )
{
int * input = new int;
for (int k = i ; buffer[k+2] != '\0' ; k++)
*input = (*input*10) + (buffer[k+2] - '0');

if (mytree.contains( *input ) == 1)
cout << *input << " is in the tree" << endl;
else
cout << *input << " is not in the tree" << endl;
}

//------SIZE------
else if ( buffer[i] == 's' )
{
cout << "The tree contains " << mytree.size() << " elements" << endl;
}

//------PRINT------
else if ( buffer[i] == 'p' )
{
mytree.print( );
cout << "Tree done." << endl;
}

//------QUIT------
else if ( buffer[i] == 'q' )
{
~BSTree() { delete [] mytree; }
return 0;
}
}
}
}

//******************************************************************
// Node.h
//
//
//******************************************************************

#ifndef NODE_H
#define NODE_H

#include "Tree.h"
#include <iostream>
using namespace std;

//******************************************************************
// class NODE
//
// The layout of each node. Stores a left and right child pointer
// as well as the data of the current node.
//******************************************************************
class NODE
{
public:
NODE* left;
NODE* right;
int *data;
} ;

#endif

//******************************************************************
// Tree.C
//
//
//******************************************************************

#include "Tree.h"
#include <iostream>
using namespace std;

//******************************************************************
// BSTree()
// Creates a new tree
//
// Initially null
//******************************************************************
BSTree::BSTree()
{
root = 0;
}


//******************************************************************
// ~BSTree()
// Destroys the tree
//
// Seals any memory leaks upon exit
//******************************************************************
BSTree::~BSTree()
{
delete root;
}


//******************************************************************
// add(int)
// Adds a new node to the tree
// int <data> - the value being inserted
// Return - true or false, depending on if the node was inserted
// Calls a recursive method to do tree traversals
//******************************************************************
bool BSTree::add ( int * data )
{
if (root == 0)
{
NODE* newnode = new NODE;
newnode->data = data;
newnode->left = 0;
newnode->right = 0;
root = newnode;
return 1;
}
else
return (findNode(root, data) != NULL );
}


//******************************************************************
// findNode(NODE*, int)
// Recursive method called by add(int) to traverse the tree, searching
// for the correct location to add a node.
// NODE* <root> - the root pointer, int <data> - the value to be added
// Return - node pointer to be evaluated by add(int)
//******************************************************************
NODE* BSTree::findNode(NODE *root, int *data)
{
if (root == 0)
{
NODE* newnode = new NODE;
newnode->data = data;
newnode->left = 0;
newnode->right = 0;
root = newnode;
return root;
}
else if (*data < *(root->data))
root->left = this->findNode(root->left, data);
else if (*data > *(root->data))
root->right = this->findNode(root->right, data);
else // data already in tree
{
cout << *data << " is already in the tree" << endl;
return 0;
}
return root;
}


//******************************************************************
// print()
// Prints the tree on its side, with correct indentation.
//
//
// Calls a recursive method to print the tree during traversal
//******************************************************************
void BSTree::print( )
{
printTree( root, 1 );
}


//******************************************************************
// printTree(NODE*, int)
// Recursive method called by print() to traverse the tree and print
// the node values with correct indentation.
// NODE* <root> - the root pointer, int <level> - the current level
//******************************************************************
void BSTree::printTree( NODE *root, int level )
{
if ( root != 0 )
{
printTree(root->right, level+1);
for(int i=0 ; i<3*level ; i++)
cout << " ";
cout << *(root->data) << endl;
printTree(root->left, level+1);
}
}


//******************************************************************
// contains(int)
// Evaluates whether or not a given value is present in the tree
// int <target> - the value to be compared with each node in the tree
// Return - True if the value is found in the tree, false otherwise
// Calls a recursive method to do tree traversals and comparisons
//******************************************************************
bool BSTree::contains ( int target)
{
return hasValue(root, target);
}


//******************************************************************
// hasValue(NODE*, int)
// Recursive method called by contains(int) to traverse the tree and
// compare each apprpriate node with the given target value.
// NODE* <root> - the root pointer, int <target> - the target value
// Return - True is the value is found, false otherwise
//******************************************************************
bool BSTree::hasValue ( NODE *root, int target )
{
if ( root == 0 ) return 0;
else
{
if ( target == *(root->data)) return 1;
else
{
if ( target < *(root->data) )
return ( this->hasValue ( root->left, target ) );
else
return ( this->hasValue ( root->right, target ) );
}
}
}


//******************************************************************
// size()
// Method that returns the numbers of elements in the tree
//
// Return - number of elements in the tree
// Calls a recursive method to traverse the tree and count each node
//******************************************************************
int BSTree::size ( )
{
return hasSize( root);
}


//******************************************************************
// hasSize(NODE*)
// Recursive function called by size() to traverse the tree and count each
// node.
// NODE* < root> - the root pointer
// Return - number of elements in the tree
//******************************************************************
int BSTree::hasSize(NODE* root)
{
if (root==0)
return(0);
else
return(this->hasSize(root->left) + 1 + this->hasSize(root->right));
}


//******************************************************************
// Remove(int)
// Removes a value-specific node from the tree and organizes the result
// to maintain an ordered inorder print (ascending).
// int <target> - the value to be removed
// Return - the node pointer
// Calls two recursive methods. One to do the actual deleting, and the
// other to find the target node.
//******************************************************************
int* BSTree::remove( int target )
{
NODE* location = findIt(root, target);
DeleteNode( location );
}


//******************************************************************
// DeleteNode(NODE*)
// Recursive method called by the remove(int) method to delete the
// given node and organize the tree
// NODE* <root> - the root pointer
//
//******************************************************************
void BSTree::DeleteNode(NODE* root) {
NODE* temp = root;
if (root->left == NULL && root->right == NULL)
{
delete temp;
}
else if (root->left != NULL && root->right == NULL)
{
root = root->left;
delete temp;
}
else if (root->left == NULL && root->right != NULL)
{
root = root->right;
delete temp;
}
else {
temp = root->left;
while (temp->right != NULL)
temp = temp->right;

root->data = temp->data;
DeleteNode(temp);
}
}


//******************************************************************
// findIt(NODE*, int)
// Recursive method called by the remove(int) method to seek out and
// return the location of the target node.
// NODE* <root> - the root pointer, int <target> - the value to seek out
// Return - the node location
//******************************************************************
NODE* BSTree::findIt(NODE *root, int target)
{
if (root == 0)
{
cout << "** ERROR: NOT FOUND **" << endl;
return 0;
}
else if (target < *(root->data))
root->left = this->findIt(root->left, target);
else if (target > *(root->data))
root->right = this->findIt(root->right, target);
else // 'target data' = 'root data'
return root;

return root;

}
/*
~BSTree()
{
if(root->left)
delete root->left[0];
if(Childs[1])
delete Childs[1];
}
// ...
delete Tree.Root;
}

void BSTree::clear()
{
deleteAll(root);
}
void BSTree::deleteAll(NODE* root)
{
delete BSTree();

}*/

//******************************************************************
// Tree.h
//
//******************************************************************

#ifndef TREE_H
#define TREE_H

#include "Node.h"
#include <iostream>
using namespace std;

//******************************************************************
// class BSTree
//
// Defines the methods to be used by the program.
// add - adds a new node to the tree in the correct locale
// contains - is the given value in the tree?
// print - prints the tree on its side
// size - returns the number of elements in the tree
// remove - removes a node and sorts it again
//******************************************************************
class BSTree
{

public:
BSTree();
~BSTree();
void clear ( );
bool add ( int * data );
NODE* findNode ( NODE *root, int * data);
bool contains ( int target );
void print ( );
int size ( );
int *remove(int k);


private:
NODE* root;

void deleteAll( NODE *root );
bool hasValue ( NODE *root, int target );
void printTree ( NODE *root, int level );
int hasSize ( NODE *root );
NODE* findIt ( NODE *root, int target );
void DeleteNode(NODE* root);
};

#endif