import java.util.*;

class Driver {
	
	//Create the two trees we care about
	//-----------------------------------
	static DianeTree diane;
	static LinkedBinaryIntTree student;
			
	//Create the array of string tokenizers we will use
	static StringTokenizer [] trees;

	//Error and test number counters for each test
	static int count1,count2,count3,count4,count5;
	static int testNum1, testNum2,testNum3,testNum4,testNum5;
	static int total1,total2,total3;

	
	public static void main (String [] args) {
		
	try {			
		//Create the two trees we care about
		//-----------------------------------
		diane = new DianeTree();
		student = new LinkedBinaryIntTree();
			
		//Create the array of string tokenizers we will use
		trees = new StringTokenizer [30];
	
		//-----------------------------------
		//Test contains()
		//-----------------------------------
		
		System.out.println ("============================");
		System.out.println ("contains () Testing");
		System.out.println ("============================");
		System.out.print ("\n");

		createTrees(trees);
		
		//A: Empty Test
		testNum1++;
		buildBuild(diane,student,trees[0],trees[1],0);
		testContains(diane,student,100);
		
		//B: One node tree
		//Match
		testNum1++;
		buildBuild(diane,student,trees[2],trees[3],1);
		testContains(diane,student,100);
		
		//NoMatch
		testNum1++;
		testContains(diane,student,0);
		
		//C: Non-BST +/-
		
		//No Match
		testNum1++;
		buildBuild(diane,student,trees[4],trees[5],10);
		testContains(diane,student,1001);

		//1 Match
		testNum1++;
		testContains(diane,student,-24);
		
		//2 Matches
		testNum1++;
		testContains(diane,student,-9);
		
		//D:  BST +
		
		//No Match
		testNum1++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testContains(diane,student,43);
		
		//1 Match
		testNum1++;
		testContains(diane,student,53);
		
		//2 Match
		testNum1++;
		testContains(diane,student,55);
		
		//E: BST -
		testNum1++;
		buildBuild(diane,student,trees[10], trees[11],10);
		testContains(diane,student,-23);
		
		//Summary
		System.out.println ("=======================================> Contains: " + count1 + " tests out of " + testNum1 + " failed.");
		System.out.print("\n");

		destroyTrees(trees);
		
		
		
		
		//-----------------------------------
		//Test numOccurences()
		//-----------------------------------
		
		System.out.println ("============================");
		System.out.println ("numOccurences () Testing");
		System.out.println ("============================");
		System.out.print ("\n");

		createTrees(trees);
		
		//A: Empty Test
		testNum2++;
		buildBuild(diane,student,trees[0],trees[1],0);
		testNumOccurences(diane,student,100);
		
		//B: One node tree
		//Match
		testNum2++;
		buildBuild(diane,student,trees[2],trees[3],1);
		testNumOccurences(diane,student,100);
		
		//NoMatch
		testNum2++;
		testNumOccurences(diane,student,0);
		
		//C: Non-BST
		
		//No matches
		testNum2++;
		buildBuild(diane,student,trees[4],trees[5],10);
		testNumOccurences(diane,student,10000);
		
		//All matches
		testNum2++;
		buildBuild (diane,student,trees[12],trees[13],5);
		testNumOccurences(diane,student,3);
		
		//Some matches
		testNum2++;
		buildBuild(diane,student,trees[14],trees[15],10);
		testNumOccurences(diane,student,3);
		
		//Some matches
		testNum2++;
		testNumOccurences(diane,student,6);
		
		//Some matches
		testNum2++;
		testNumOccurences(diane,student,2);
		
		//D:  BST
		
		//no match
		testNum2++;
		buildBuild(diane,student,trees[10],trees[11],10);
		testNumOccurences(diane,student,-300);
	
		//match -interesting position
		testNum2++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testNumOccurences(diane,student,28);

		//Summary
		System.out.println ("=======================================> NumOccurences: " + count2 + " tests out of " + testNum2 + " failed.");
		System.out.print("\n");
		destroyTrees(trees);
	
	
	
		//-----------------------------------
		//Test biggest()
		//-----------------------------------

		System.out.println ("============================");
		System.out.println ("biggest () Testing");
		System.out.println ("============================");
		System.out.print ("\n");


		createTrees(trees);
		
		//A: One node tree
		testNum3++;
		buildBuild(diane,student,trees[2],trees[3],1);
		testBiggest(diane,student);
		
		//B:  Non-BST
		
		//At root
		testNum3++;
		buildBuild(diane,student,trees[16],trees[17],6);
		testBiggest(diane,student);
		
		//In Middle
		testNum3++;
		buildBuild(diane,student,trees[18],trees[19],6);
		testBiggest(diane,student);		
	
		//In Middle
		testNum3++;		
		buildBuild(diane,student,trees[20],trees[21],10);
		testBiggest(diane,student);		
		
		//At leaf
		testNum3++;
		buildBuild(diane,student,trees[22],trees[23],7);
		testBiggest(diane,student);
		
		//Normal BST
		testNum3++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testBiggest(diane,student);
			
		//All negative BST
		testNum3++;
		buildBuild(diane,student,trees[10],trees[11],10);
		testBiggest(diane,student);
		
		//All negative nonBST
		testNum3++;
		buildBuild(diane,student,trees[8],trees[9],8);
		testBiggest(diane,student);
		
		//All duplicate tree
		testNum3++;
		buildBuild(diane,student,trees[12],trees[13],5);
		testBiggest(diane,student);
		
		//some duplicate tree
		testNum3++;
		buildBuild(diane,student,trees[14],trees[15],10);
		testBiggest(diane,student);

		//Summary
		System.out.println ("=======================================> Biggest: " + count3 + " tests out of " + testNum3 + " failed.");
		System.out.print("\n");
		destroyTrees(trees);





		//-----------------------------------
		//Test replace()
		//-----------------------------------
		createTrees(trees);

		System.out.println ("============================");
		System.out.println ("replace () Testing");
		System.out.println ("============================");
		System.out.print ("\n");


		//A: Empty tree
		testNum4++;
		buildBuild(diane,student,trees[0],trees[1],0);
		testReplace(diane,student,100,0);
	
		//B: One node tree
		//-------------
		
		//Match
		testNum4++;
		buildBuild(diane,student,trees[2],trees[3],1);
		testReplace(diane,student,100,3);
		
		destroyTrees(trees);
		createTrees(trees);
		
		//NO match
		testNum4++;
		buildBuild(diane,student,trees[2],trees[3],1);
		testReplace(diane,student,101,1);

		//BST
		//---------
		//no match
		testNum4++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testReplace(diane,student,36,37);
	
		destroyTrees(trees);
		createTrees(trees);
		
		//1 match
		testNum4++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testReplace(diane,student,20,3000);

		destroyTrees(trees);
		createTrees(trees);
	
		//2 match
		testNum4++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testReplace(diane,student,55,2000);
		
		
		//Non-BST
		//--------
		destroyTrees(trees);
		createTrees(trees);

		
		//No match
		testNum4++;
		buildBuild(diane,student,trees[4],trees[5],10);
		testReplace(diane,student,-10,10);

		destroyTrees(trees);
		createTrees(trees);
	
		//1 match
		testNum4++;
		buildBuild(diane,student,trees[4],trees[5],10);
		testReplace(diane,student,80,1001);
	
		//all match
		testNum4++;
		buildBuild(diane,student,trees[12],trees[13],5);
		testReplace(diane,student,3,-3);
	
		//some matches
		testNum4++;
		buildBuild(diane,student,trees[14],trees[15],5);
		testReplace(diane,student,2,-1000);
		
		//Summary
		System.out.println ("=======================================> Replace: " + count4 + " tests out of " + testNum4 + " failed.");
		System.out.print("\n");
		destroyTrees(trees);



		//-----------------------------------
		//Test flip()
		//-----------------------------------

		System.out.println ("============================");
		System.out.println ("flip () Testing");
		System.out.println ("============================");
		System.out.print ("\n");

		createTrees(trees);

		//A: empty tree
		testNum5++;
		buildBuild(diane,student,trees[0],trees[1],0);
		testFlip(diane,student);
		
		//B:  1 node
		testNum5++;
		buildBuild(diane,student,trees[2],trees[3],1);
		testFlip(diane,student);
		
		//C:  Bst +
		testNum5++;
		buildBuild(diane,student,trees[6],trees[7],11);
		testFlip(diane,student);
		
		//D:  Bst -
		testNum5++;
		buildBuild(diane,student,trees[10],trees[11],10);
		testFlip(diane,student);
		
		//E:  NonBST +/-
		testNum5++;
		buildBuild(diane,student,trees[4],trees[5],10);
		testFlip(diane,student);
		
		//E:  NonBST -
		testNum5++;
		buildBuild(diane,student,trees[8],trees[9],8);
		testFlip(diane,student);
		
		//F: some duplicates
		testNum5++;
		buildBuild(diane,student,trees[14],trees[15],10);
		testFlip(diane,student);
		
		//G:  2 - level tree
		testNum5++;
		buildBuild(diane,student,trees[24],trees[25],3);
		testFlip(diane,student);
		
		//H:  all duplicates
		testNum5++;
		buildBuild(diane,student,trees[12],trees[13],5);
		testFlip(diane,student);
		
		//I:  leaf-level max tree
		testNum5++;
		buildBuild(diane,student,trees[22],trees[23],7);
		testFlip(diane,student);
		
		//Summary
		System.out.println ("=======================================> Flip: " + count5 + " tests out of " + testNum5 + " failed.");
		System.out.print("\n");
		destroyTrees(trees);

		total1 = count1 + count2 + count3 + count4 + count5;
		total2 = testNum1 +testNum2 + testNum3 + testNum4 + testNum5;
		
		total3 = total2 - total1;
		
		//Total Summary
		//----------------------------------------------------
		System.out.println (" ");
		System.out.println (" ");
		System.out.println ("--------------------------------------------------------------------");
		System.out.println ("Total Testing Summary: " + total3 + " tests out of " + 
					total2 + " passed.");
		System.out.println ("--------------------------------------------------------------------");
		System.out.println (" ");
		System.out.println (" ");
	
	}
	catch (Exception e){
		System.out.println ("Student's code caused an exception in our main: Test fails");
	}
	
	}
	
	
	
	
	
	//-------------------------------------------------------------------	
	// HELPERS
	//-------------------------------------------------------------------
	
	public static void testContains(DianeTree diane, LinkedBinaryIntTree student, int key){
		try {
			if (diane.contains(key) != student.contains(key)){
				System.out.println ("contains: test " + testNum1 + " failed");
				count1++;
			}
		}
		catch (Exception e){
			System.out.println ("contains: test " + testNum1 + " causes exception");
			count1++;
		}
	}
	
	public static void testNumOccurences(DianeTree diane, LinkedBinaryIntTree student, int key){
		try {
			if (diane.numOccurrences(key) != student.numOccurrences(key)){
				System.out.println ("numOccurences: test " + testNum2 + " failed");
				count2++;
			}
		}
		catch (Exception e){
			System.out.println ("numOccurences: test " + testNum2 + " causes exception");
			count2++;
		}
	}
	
	public static void testBiggest(DianeTree diane, LinkedBinaryIntTree student){
		try {
			if (diane.biggest() != student.biggest()){
				System.out.println ("biggest: test " + testNum3 + " failed");
				count3++;
			}
		}
		catch (Exception e){
			System.out.println ("biggest: test " + testNum3 + " causes exception");
			count3++;
		}
	}
	
	public static void testReplace(DianeTree diane, LinkedBinaryIntTree student, int old,int key){
		try {
			diane.replace(old,key);
			student.replace(old,key);
			if (!((diane.toString()).equals(student.toString()))){
				System.out.println ("replace: test " + testNum4 + " failed");
				count4++;
			}
		}
		catch (Exception e){
			System.out.println ("replace: test " + testNum4 + " causes exception");
			count4++;
		}
	}
	
	public static void testFlip(DianeTree diane, LinkedBinaryIntTree student){
		try {
			diane.flip();
			student.flip();
			if (!((diane.toString()).equals(student.toString()))){
				System.out.println ("flip: test " + testNum5 + " failed");
				count5++;
			}
		}
		catch (Exception e){
			System.out.println ("flip: test " + testNum5 + " causes exception");
			count5++;
		}
	}
	
	public static void createTrees(StringTokenizer [] trees){
	
		//Insert some string tokenizers
		trees[0] = null;				//Empty Tree
		trees[1] = null;				//Empty Tree
		trees[2] = new StringTokenizer ("100");  	//Single node tree	(1)
		trees[3] = new StringTokenizer ("100");  	//Single node tree
		trees[4] = new StringTokenizer ("-9 3 80 1 323 55 -9 -54 1000 -24");  	//Non BST +/- (10)
		trees[5] = new StringTokenizer ("-9 3 80 1 323 55 -9 -54 1000 -24");  	//Non BST +/-
		trees[6] = new StringTokenizer ("1 11 20 28 35 41 46 50 53 55 55");   	//BST + (11)
		trees[7] = new StringTokenizer ("1 11 20 28 35 41 46 50 53 55 55");   	//BST +
		trees[8] = new StringTokenizer ("-5 -3 -7 -9 -1 -90 -4 -2");		//Non BST - (8)
		trees[9] = new StringTokenizer ("-5 -3 -7 -9 -1 -90 -4 -2");		//Non BST -
		trees[10] = new StringTokenizer("-100 -50 -33 -23 -22 -15 -11 -8 -5 -3"); //BST - (10)
		trees[11] = new StringTokenizer("-100 -50 -33 -23 -22 -15 -11 -8 -5 -3"); //BST -
		trees[12] = new StringTokenizer("3 3 3 3 3 ");		//Numoccurence -all match (5)
		trees[13] = new StringTokenizer("3 3 3 3 3 ");		//Numoccurence -all match 
		trees[14] = new StringTokenizer ("3 2 6 4 3 2 3 6 2 2"); //Numoccurence - some matches (10)
		trees[15] = new StringTokenizer ("3 2 6 4 3 2 3 6 2 2"); //Numoccurence - some matches
		trees[16] = new StringTokenizer (" 3 5 6 4 3 3"); //biggest (at root) (6)
		trees[17] = new StringTokenizer (" 3 5 6 4 3 3"); //biggest (at root)
		trees[18] = new StringTokenizer("5 6 10 3 11 0"); //biggest (in middle) (6)
		trees[19] = new StringTokenizer("5 6 10 3 11 0"); //biggest (in middle) 
		trees[20] = new StringTokenizer("5 6 101 15 20 3 95 32 10 0"); //biggest (in middle) (10)
		trees[21] = new StringTokenizer("5 6 101 15 20 3 95 32 10 0"); //biggest (in middle)
		trees[22] = new StringTokenizer("100 3 5 7 9 10 101"); //biggest (at leaf) (7)
		trees[23] = new StringTokenizer("100 3 5 7 9 10 101"); //biggest (at leaf)
		trees[24] = new StringTokenizer ("50 100 150");	//double level tree(3)
		trees[25] = new StringTokenizer ("50 100 150"); //double level tree
	}
	
	public static void destroyTrees(StringTokenizer [] trees){
	
		for (int i=0; i < 26; i++){
			trees[i] = null;
		}
	}
	
	public static void buildBuild (DianeTree diane, LinkedBinaryIntTree student,
					StringTokenizer a, StringTokenizer b, int length){
	
		diane.build(a,length);
		student.build(b,length);
	}

}