#include <iostream>
#include <fstream> // for files in C++ 
#include <stdlib.h> //to be able to use system("cls");
#include <cassert> // used to detect file errors 


using namespace std;


template <class Entry>
struct Binary_node
{
	Entry data;
	Binary_node<Entry> *left;
	Binary_node<Entry> *right;
	Binary_node(); //constructors
	Binary_node(const Entry &x);
};

template <class Entry>
class Binary_tree
{
   public:
		   Binary_tree();
		   void insert(const Entry & );
		   void recursive_insert (Binary_node<Entry>*& sub_root, const Entry & data);
		   void fill_tree();
		   //void inorder() const;
		   //void preorder() const;
		   //void descending() const;
		   //void postorder() const;
		   //int size() const;
		   //float average() const;
		   //void search (int target_key, Binary_node<Entry> * & target_pointer);
		   //bool remove (int target);
   private:
	       Binary_node<Entry> *root;
};

template <class Entry>
Binary_node<Entry>::Binary_node()
{ left=right=NULL;}



struct datanode
{	int key;
	float gpa;
};

void holdscreen() //holds the screen until enter is pressed
{
	cin.ignore();
	cin.ignore();
}

int menu( );

int main()
{	
	Binary_tree<datanode> tree;
	datanode data;
//	Binary_node<datanode> *pointer;
	int choice, key;
	float gpa;

	do
	{	
		system("cls");
		choice = menu();
		switch(choice)
		{	
			case 1:	 tree.fill_tree(); break;
			case 2:  {  cout<<"Enter key and gpa: ";
				        cin>>key>>gpa;
						data.key = key;
						data.gpa = gpa;
						tree.insert(data);
					 }  break;
		/*	case 3:  tree.inorder(); holdscreen(); break;
			case 4:  tree.preorder(); holdscreen(); break;
			case 5:  tree.postorder(); holdscreen(); break;
			case 6:  tree.descending(); holdscreen(); break;
			case 7:  {  cout<<"Size= "<<tree.size()<<endl; holdscreen(); } break;
			case 8:  {  cout<<"Average= "<<tree.average()<<endl;
						holdscreen(); } break;
			case 9:  {  cout<<"Enter key to search for: ";
						cin>>key;
						tree.search(key, pointer);
						if (pointer == NULL)  cout<<"NOT FOUND\n";
						else cout<<"key= "<<pointer->data.key<<" gpa= "<<pointer->data.gpa<<endl;
					 }  holdscreen(); break;
			case 10: {  cout<<"Enter key of node to delete: ";
						cin>>key;
						if ( ! tree.remove(key) )
						{
							cout<<"NOT FOUND\n";
							holdscreen();
						}   break;
					 }
			case 11: break; 
			default: {cout<<"Invalid Choice\n"; holdscreen();}*/
		}
	} while (choice != 11);

  return 0;
}


int menu( )
{ //pre: there is no menu on screen
  //post: user menu on screen

int choice;
system("cls");
cout<<"	LAB5 MENU"<<endl;
cout<<" 1.  Fill tree from file lab5.in"<<endl;
cout<<" 2.  Insert a node into the tree"<<endl;
cout<<" 3.  Print KEYS ONLY in ascending order"<<endl;
cout<<" 4.  Print KEYS with GPAs in preoder"<<endl;
cout<<" 5.  Print KEYS with GPAs in postorder"<<endl;
cout<<" 6.  Print KEYS with GPAs in descending order"<<endl;
cout<<" 7.  Count nodes in tree"<<endl;
cout<<" 8.  Calculate average of GPAs in tree"<<endl;
cout<<" 9.  Search for a KEY in the tree"<<endl;
cout<<" 10. Delete a node from the tree."<<endl;
cout<<" 11. Quit"<<endl;
cout<<" Enter choice: ";
cin>>choice;
return choice;
}

template <class Entry>
void Binary_tree<Entry>::insert (const Entry &data)
{  
	recursive_insert(root,data);
}
					 
template<class Entry>
void Binary_tree<Entry>::recursive_insert (Binary_node<Entry>*& sub_root, const Entry & data)
{
	if (sub_root==NULL) sub_root=new Binary_node<Entry> (data);
	else if (data.key<sub_root->data.key)
		     recursive_insert(sub_root->left,data);
		 else recursive_insert(sub_root->right,data);
}
	
template<class Entry>
void Binary_tree<Entry>::fill_tree()	
{
	datanode fileData;
	int fileKey;
	float fileGpa;

	ifstream infile ("c:\\temp\\LAB5.IN", ios::in);
	assert (!infile.fail()); //stops program if file doesn't open

	while (infile>>fileKey)
	{
		infile>>fileKey;
		infile>>fileGpa;
		fileData.key = fileKey;
		fileData.gpa = fileGpa;
		insert(fileData);
	}
	infile.close(); // done with infile so we close it here
}