// *****************************************************************
// Author:			Zhixiang Chen
// Class:			CSCI/CMPE 3333, Fall 2014
// Lab 2:			AVL tree
// Date:			08/2014
// Comment:			The code here is meant to be revised.
//-----------------------------------------------------------------
// Description: This program is to implement the binary search tree 
// class template
// *****************************************************************
#include <iostream>
#include <cassert>
#include <string> 
#include <cstdlib>
#include <ctime>

#include "lab3333_2_head.h"	


using namespace std; 

int main()
{
	/**********************************************************
	 Part A: Some practice
	 **********************************************************/
	//var decarations
	unsigned int seed;					//a random seed
	int num;							//to hold an int value
	AVLTree<int> tree;					//create a list of int type
	char tag; 
	
	
	tree.insert(4); 
	tree.insert(2); 
	tree.insert(5);
	tree.insert(1); 
	tree.insert(3);
	//tree.insert(6);
	cout<<"inorder traversal ..... "<<endl; 
	tree.inOrderTraversal(); 
	cout<<"preorder traversal ..... "<<endl; 
	tree.preOrderTraversal(); 
	cout<<"postorder traversal ..... "<<endl; 
	tree.postOrderTraversal(); 

	tree.remove(4); 
	//tree.remove(5);
	//tree.remove(1); 
	
	cout<<" **************************" <<endl;
	
	cout<<"inorder traversal ..... "<<endl; 
	tree.inOrderTraversal(); 
	cout<<"preorder traversal ..... "<<endl; 
	tree.preOrderTraversal(); 
	cout<<"postorder traversal ..... "<<endl; 
	tree.postOrderTraversal(); 

	//tree.insert(16);
	//tree.insert(15);
	
	/*
	tree.insert(5); 
	tree.insert(2); 
	tree.insert(8); 
	tree.insert(1);
	tree.insert(4); 
	tree.insert(7); 
	tree.insert(3); 
	tree.insert(6);
	*/
	/*
	srand(time(0));						//set the randon seed

	for (int i=0; i <10 ; i++)			//insert 50 random numbers into the list
	{
		num = rand()%31; 
		cout<<num<<"  ";
		tree.insert(num);
	}
	cout<<endl; 
	

	cout<<"inorder traversal ..... "<<endl; 
	tree.inOrderTraversal(); 
	cout<<"preorder traversal ..... "<<endl; 
	tree.preOrderTraversal(); 
	cout<<"postorder traversal ..... "<<endl; 
	tree.postOrderTraversal(); 
	cout<<"tree height is "<< tree.treeHeight()<<endl; 
	cout<<"tree node count is "<< tree.treeNodeCount()<<endl; 
	cout<<"tree leave count is "<< tree.treeLeaveCount()<<endl; 

	cout<<endl; 
	*/

	//test delete and search
	while (true)
	{
		cout<<"Want to play with searching or deletion(s/d)? "<<endl; 
		cout<<"Enter q to stop "; 
		cin>>tag; 
		switch (tag)
		{
		case 'd':
		case 'D':
				cout<<"What to be deleted? "; 
				cin>> num; 
				tree.remove(num); 
				tree.inOrderTraversal(); 
				cout<<endl; 
				break; 
		case 's': 
		case 'S':
				cout<<"What to be searched for? "; 
				cin>>num; 
				if(tree.find(num))
					cout<<"found "<< num <<" in the tree "<<endl; 
				else 
					cout<<"failed to find " <<num<<" in the tree "<<endl; 
		default: 
				break;
		}
		if (tag == 'q' || tag == 'Q')
			break; 
	}

	/**********************************************************************
	 Part B: Try to create a AVL tree of strings and practice 
	 basic tree operations such as insertion, deletion, search, etc.
	 **********************************************************************/
	
	//Write your code here

	/**********************************************************************
	 Part C: First define a personType class with three data members 
	 (string name, int ID, and double grade). Second, create an AVL
	 tree of personType. Third, practice basic tree operations such as 
	 insertion, deletion, search, etc.
	 ***********************************************************************/
	
	//Write your code here
	
	/******************************************************************************************
	 Part D: Use an AVL tree to sort a list of 1,000,000 random integers.
	 (1) Use a random number generator to generate a list of 1,000,000 random integers 
		 and save them into a file "data.txt"
	 (2) Create an AVL tree of int type 
		 and use this tree to sort those integers in "data.txt". Record the time of the sorting. 
	 (3) Use insertionSort, selectionSort, bubbleSort, megerSort, and quickSort to sort
		 the same list of the integers, and record the times of those sorting algorithms
	 (4) Prepare a table to report the time performance of those sorting algorithms. 
	 *******************************************************************************************/
	//Write your code here


	//complete the program
	return 0; 
}