RunProgLab3

gistfile1.txt

package huffmanTree;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.time.Instant;
import java.util.Scanner;

public class RunProgLab3 
{
		public static void main(String [] args)
		{
			
			Boolean runtimeParamCorrect = false;
		
			//Check to make sure user has correctly entered the 3 required runtime parameters 
			while (runtimeParamCorrect != true)
			{
				//if (args != null && args.length == 5)
				{
				
					runtimeParamCorrect = true;
					//Runtime parameters:
					
					//Update this at the end; for now, these 2 lines are commented out
//					String inputFilePath = args[0];
//					String outputFilePath = args[1];
					//String outputFilePath2 = args[2];
//					//String outputFilePath3 = args[2];
				
					String inputFilePath = "/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/InputLab3.txt";
					String outputFilePath = "/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3.txt";
					String outputFilePath2 = "/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3_2.txt";
					String outputFilePath3 = "/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3_3.txt";
					String outputFilePath4 = "/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3_FINAL.txt";
			
					Instant start = Instant.now();
					
					//For testing; later change to args[0] b/c it will be runtime param		
					//final long startTime = System.currentTimeMillis();
					final long startTime = System.nanoTime();
					readInput(inputFilePath, outputFilePath);
					readInput2(inputFilePath, outputFilePath2);
					readInput3(inputFilePath, outputFilePath3);
					combineOutput(outputFilePath, outputFilePath2, outputFilePath3, outputFilePath4);
					final long duration = System.nanoTime() - startTime;

				}
				
				
				//If runtime parameters are entered incorrectly, give error message and break so user can re-enter from terminal 
/*					else if (args == null || args.length < 5||args.length > 5)
					{
						System.out.println("\n"+ "5 runtime parameters are required." + "\n" + "To run this program, use the following command line prompt: " + "\n" + "java RunProgLab3 /Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/InputLab3.txt 
						/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3.txt 
						 /Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3_2.txt
						 /Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3_3.txt 
						/Users/christine/Documents/workspace2/Data_Structures_Lab3_Fall_2015/src/OutputLab3_FINAL.txt");
						break;
					

					}	//close else if	
*/	
			}	//close while
		}	//close main
		
		
		/**
	 * @method readInput reads in an input txt file containing (a) character 
	 * frequency table; (b) strings to encode; (c) strings to decode 
	 * <dt><b>Precondition:</b><dd>
	 * Input path is correctly specified as the first runtime parameter; 
	 * 	the input file is not empty, and contains valid input 
	 * @param String inputFilePath: the path of the input txt file; 
	 * 	String outputFilePath 
	 * @returns String [] the output array 
	 * <dt><b>Postconditions:</b><dd>
	 * The input file is read in so that other operations can be performed
	 * @author Christine Herlihy
	 */
	public static void  readInput(String inputFilePath, String outputFilePath)
	{
	//For natural merge
	String [][] freqIn = new String[26][26];
	int [] freqInNumeric = new int [26];
	String[][] treeBuilder = new String[26][26];
	Node [] builtTree = new Node[110];
	Node [] builtTree2 = new Node[110];
	LinkedHuffmanStack tempStackA = new LinkedHuffmanStack();
	int charCounter =0;
	int treeCounter = 0;
	int decodeCounter =0;
	
	//Read in the input file 
	try(BufferedReader buffer = new BufferedReader(new FileReader(inputFilePath)))
	{
	//For input
	String line= new String();
	Scanner input = new Scanner(System.in);
	
	//For output
	BufferedWriter outputFile = new BufferedWriter(new FileWriter(outputFilePath));
	
	//Read each line of the input file in; store each char and int 
	while((line=buffer.readLine()) != null)
	{

	String tempFirst = new String(line);	//the first line in the input file will = the order of the first matrix 
	tempFirst = tempFirst.replaceAll("[-–]","");	//regex checks for two types of dashes used in the input file
	//System.out.println("tempfirst is " + tempFirst);	//TESTING
	input = new Scanner(tempFirst).useDelimiter("\\s+");	//after that, for each line, want to parse the line, using white space as a delimiter, and grabbing all of the integer values 

	//Read each letter and its frequency value into the 
	//freqIn array; delimiter= whitespace
	while(input.hasNext() & charCounter < 26)
	{
	
	freqIn[charCounter][0] = input.next();
	String temp= input.next();
	
	freqIn[charCounter][1] = temp;
	freqInNumeric[charCounter] = Integer.parseInt(temp);
	charCounter  ++;	//Keep track of how many rows are in the array
	}	
	}	//close while((line=buffer.readLine()) != null)
	

	//Conduct 2-way merge sort on frequency values; put in ascending order
	freqInNumeric= sortFreqValsNumeric(freqInNumeric);
	
	//Pair up numeric values with their alphabetic counterparts from input array 
	for(int i = 0; i<freqInNumeric.length; i++)
	{
	int temp = (freqInNumeric[i]);
	int next = 0;
	
	if(i+1 < freqInNumeric.length)
	{
	next = (freqInNumeric[i+1]);
	}
	
	for(int j = 0; j<freqIn.length; j++)
	{
	if(Integer.parseInt(freqIn[j][1]) == temp)
	{
	if(temp != next)
	{
	treeBuilder[i][0]= freqIn[j][0];
	treeBuilder[i][1]= String.valueOf(temp);
	}
	
	//There is a duplicate value. 
	//In this input file, the max # of dups is 2
	else if(temp == next)
	{
	treeBuilder[i][0]= freqIn[j][0];
	treeBuilder[i][1]= String.valueOf(temp);
	
	//Get the second instance of same freq. value 
	for(int k = j+1; k<freqIn.length; k++)
	{
	if(Integer.parseInt(freqIn[k][1]) == temp)
	{
	treeBuilder[i+1][0]= freqIn[k][0];
	treeBuilder[i+1][1]= String.valueOf(temp);
	i++;	//increase treeBuilder index by 1
	}
	}	
	}	//close else if(temp == next)
	}	//close if(Integer.parseInt(freqIn[j][1]) == temp)
	}	//close for(int j = 0; j<freqIn.length; j++)
	}//close for(int j = 0; j<freqIn.length; j++)

	//Push letters onto stack in order of decreasing frequency
	//TOP after loop runs will be node represented by the LEAST FREQUENT LETTER
	for(int i=treeBuilder.length-1; i> -1; i--)
	{
	//System.out.print(i + "  ");
	Node tempNode = new Node(treeBuilder[i][0], Integer.parseInt(treeBuilder[i][1]));
	//System.out.println("tempNode freq " + tempNode.getFreqVal());	//TESTING
	if(tempNode.getElement() !=null)
	{
		tempStackA.push(tempNode);
	}
	//System.out.println(tempStackA.peek());	//TESTING 
	}
	
//	Node [] temp = build(treeBuilder, builtTree);
//	
//	for(int i=0; i <temp.length; i++)
//	{
//	if(temp[i] !=null)
//	{
//	
//	System.out.println(temp[i].toString());
//	}
//	}
	
	//builtTree = build(treeBuilder, builtTree);
	

	/*//Builds the Huffman tree for later use in traversal/encoding/decoding
	builtTree = build(treeBuilder, builtTree);
	

	//Set index value of each node object for later searching
	for(int i = 0; i<builtTree.length; i++)
	{
	if(builtTree[i]!=null)
	{
	builtTree[i].setIndex(i);
	//System.out.println(builtTree[i].index);	//FOR TESTING
	}
	}
	
	for(int i = 0; i<builtTree.length; i++)
	{
	if(builtTree[i]!=null)
	{
	String temp = builtTree[i].getElement();
	
	int j= Node.getIndex(temp, builtTree);
	//System.out.println(j);
	}
	}
	
	HuffmanTree.printTree(builtTree);
	
	//Conduct pre-order traversal to assign Huffman code values 
	HuffmanTree.assignHuffman(builtTree);*/
	Node [] treeOut = new Node[100];

	treeOut = build2(tempStackA, builtTree);

	for(int i =0; i<treeOut.length; i++)
	{
		if(treeOut[i]!=null)
		{
			//System.out.println(treeOut[i].toString());
			System.out.println(i);
		}
	}
	
	//System.out.println(treeOut.length);

	String [][] outTraversal = HuffmanTree.printTreePreorderTraversal(treeOut);
	
	for(int j=0; j<outTraversal.length; j++)
	{
		
		//System.out.println(outTraversal[j][0] + " :" + outTraversal[j][1] );
		
	}
	
	for(int i = treeOut.length-2; i> -1; i--)
	{
		HuffmanTree.preOrder(treeOut[i]);
		
	}
	
	
	//HuffmanTree.preOrder(treeOut[24]);
	
//	for(int i = 0; i<builtTree2.length; i++)
//	{
//	if(builtTree2[i]!=null)
//	{
//	String temp = builtTree2[i].getElement();
//	
//	//int j= Node.getIndex(temp, builtTree);
//	System.out.println("temp" + temp);
//	}
//	}
	
	
	
	/*	
	for(int g=0; g<matrixCounter; g++)
	{
	Matrix dummyMatrix = matrixOutArray[g];
	Instant start = Instant.now();	
	final long startTime = System.currentTimeMillis();
	double det = dummyMatrix.determinantCalc(dummyMatrix.newMatrix);
	final long duration = System.currentTimeMillis() - startTime;
	
	outputFile.write("Input Matrix #" + (g+1) +  ":"+ "\n\n");
	tempMatrix.matrixOut(outputFile, dummyMatrix);
	outputFile.write("\n");
	outputFile.write("Order: " + dummyMatrix.getSize()+ "\n");
	outputFile.write("The determinant is: " + det+ "\n"); 
	outputFile.write("It took "+ duration + " nanoseconds to calculate this determinant");
	outputFile.write("\n" + "#----------------------------------------------------#");
	outputFile.write("\n\n");
	}*/
	//outputFile.close();
	
	//Project Requirement #1: Print the tree in preorder traversal; print the Huffman code 
	outputFile.write("The tree in preorder traversal is: " + "\n");
	
	//Print out (string representation) of tree in pre-order traversal 
	for(int i =0; i<builtTree.length;i++)
	{
	if(builtTree[i] != null & i<52){
	outputFile.write(builtTree[i].toString()+ "; "+ "\n");	
	}

	else if(builtTree[i] != null & i==52){
	outputFile.write(builtTree[i].toString()+ "\n");	
	}
	
	}
	
	outputFile.write("\n" + "#----------------------------------------------------#" + "\n" );
	
	outputFile.write("The code is: " + "\n");
	for(int i=0; i< builtTree.length; i++)
	{
	if(builtTree[i] != null & i < 51 & i%2==1)
	{
	outputFile.write(builtTree[i].toStringHuffman()+ "; " + "\n");	
	}
	else if(builtTree[i] != null & i==52)
	{
	outputFile.write(builtTree[i].toStringHuffman()+ "\n");	
	}
	}
	
	outputFile.write("\n" + "#----------------------------------------------------#"  + "\n" );
	
	outputFile.close();
	
	}	//close try 

	catch (FileNotFoundException e)
	{
	System.out.println("Database file not found.");
	
	}
	
	catch (IOException e) 
	{
	System.out.println("An I/O Error occured.");
	
	}
	}
	
	
	/**
	 * @method readInput2 reads in an input txt file containing (a) character 
	 * frequency table; (b) strings to encode; (c) strings to decode 
	 * <dt><b>Precondition:</b><dd>
	 * Input path is correctly specified as the first runtime parameter; 
	 * 	the input file is not empty, and contains valid input 
	 * @param String inputFilePath: the path of the input txt file; 
	 * 	String outputFilePath 
	 * @returns String [] the output array 
	 * <dt><b>Postconditions:</b><dd>
	 * The input file is read in so that other operations can be performed
	 * @author Christine Herlihy
	 */
	public static void  readInput2(String inputFilePath, String outputFilePath2)
	{
	
	//Read in the input file 
	try(BufferedReader buffer2 = new BufferedReader(new FileReader(inputFilePath)))
	{
	//For input
	String line2= new String();
	Scanner input2 = new Scanner(System.in);
	int encodeCounter = 0;
	String [][] encodeIn= new String [15][15];
	String tempSecond = new String();
	String tempSecondB = new String();
	
	//For output
	BufferedWriter outputFile2 = new BufferedWriter(new FileWriter(outputFilePath2));
	
	//Read each line of the input file in; store each char and int 
	while((line2=buffer2.readLine()) != null)
	{
	tempSecond = new String(line2);	//the first line in the input file will = the order of the first matrix 
	tempSecondB = tempSecond.replaceAll("[,\\s+]","");	//regex checks for two types of dashes used in the input file

	encodeCounter++;
	
	if(encodeCounter >26 & encodeCounter <41)
	{
	//Deal with sentences that are broken across multiple lines 
	if(tempSecondB.endsWith(".")| tempSecondB.endsWith("?"))
	{
	//System.out.println("endswith");	//FOR TESTING
	String tempA = tempSecondB.replaceAll("[.?]", "");
	encodeIn[encodeCounter-26][0] = tempSecond;
	encodeIn[encodeCounter-26][1] = tempA;

	}
	
	else
	{
	String tempB= tempSecond + buffer2.readLine();
	String tempBC= tempB.replaceAll("[.?\\s+]", "");
	encodeIn[encodeCounter-26][0] = tempB;
	encodeIn[encodeCounter-26][1] = tempBC;
	encodeCounter++;
	}
	}
	}

	/*	//FOR TESTING 
	for(int i=0; i<encodeIn.length; i++)
	{
	System.out.println(i+ encodeIn[i]);
	}*/
	

	for(int i=0; i< encodeIn.length; i++)
	{
	if(encodeIn[i][0] !=null)
	{
	
	int charCount = encodeIn[i][1].toCharArray().length;
	
	
	//System.out.println("length" + charCount);	//TESTING
	
	outputFile2.write("\n" + "#----------------------------------------------------#"  + "\n" );
	outputFile2.write("Original string to encode: " + encodeIn[i][0] + "\n" );
	outputFile2.write("Trimmed form: " + encodeIn[i][1]+ "\n" );
	outputFile2.write("The trimmed form of this string has " + charCount + " letters, which would require 8*" + charCount + " = "  + 8*charCount + " bits to represent using ASCII" + "\n" );
	outputFile2.write("\n" + "#----------------------------------------------------#"  + "\n" );
	}
	
	
	}
	
	outputFile2.write("\n" + "#----------------------------------------------------#"  + "\n" );
	
	outputFile2.close();
	
	
	}	//close try 2

	catch (FileNotFoundException e)
	{
	System.out.println("Database file not found.");
	
	}
	
	catch (IOException e) 
	{
	System.out.println("An I/O Error occured.");
	
	}
	
	}
	
	/**
	 * @method readInput2 reads in an input txt file containing (a) character 
	 * frequency table; (b) strings to encode; (c) strings to decode 
	 * <dt><b>Precondition:</b><dd>
	 * Input path is correctly specified as the first runtime parameter; 
	 * 	the input file is not empty, and contains valid input 
	 * @param String inputFilePath: the path of the input txt file; 
	 * 	String outputFilePath 
	 * @returns String [] the output array 
	 * <dt><b>Postconditions:</b><dd>
	 * The input file is read in so that other operations can be performed
	 * @author Christine Herlihy
	 */
	public static void  readInput3(String inputFilePath, String outputFilePath3)
	{
	
	//Read in the input file 
	try(BufferedReader buffer3 = new BufferedReader(new FileReader(inputFilePath)))
	{
	//For input
	String line3= new String();
	Scanner input3 = new Scanner(System.in);
	int decodeCounter = 0;
	String [] decodeIn= new String[4];
	
	//For output
	BufferedWriter outputFile3 = new BufferedWriter(new FileWriter(outputFilePath3));
	
	//Read each line of the input file in; store each char and int 
	while((line3=buffer3.readLine()) != null)
	{
	String tempThird = new String(line3);	//the first line in the input file will = the order of the first matrix 
	decodeCounter++;
	
	if(decodeCounter >40 & decodeCounter <45)
	{

	String tempB= tempThird;
	decodeIn[decodeCounter-41] = tempB;
	//decodeCounter++;
	
	}
	}


	for(int i=0; i< decodeIn.length; i++)
	{
	if(decodeIn[i] !=null)
	{
	outputFile3.write(decodeIn[i]+ "\n" );
	}
	
	
	}
	
	outputFile3.write("\n" + "#----------------------------------------------------#"  + "\n" );
	
	outputFile3.close();
	
	
	}	//close try 2

	catch (FileNotFoundException e)
	{
	System.out.println("Database file not found.");
	
	}
	
	catch (IOException e) 
	{
	System.out.println("An I/O Error occured.");
	
	}
	}


	
	/**
	 * @method sortFreqValsNumeric takes an unsorted int array and returns 
	 * the same array sorted in ascending order 
	 * <dt><b>Precondition:</b><dd>
	 * The input array has at least one element
	 * @param int [] input: the array to be sorted 
	 * @returns int []: the input array sorted in ascending order 
	 * <dt><b>Postconditions:</b><dd>
	 * None (sorted input array is returned to caller of function) 
	 * @author Christine Herlihy
	 */
	public static int [] sortFreqValsNumeric(int[] input)
	{

	int temp = input.length;
	
	//If the array has at least 2 elements, need to separate and sort them
	if(temp > 1)
	{
	
	int sizeA = input.length/2;
	int sizeB = sizeA;
	
	//If the input array length is not even, the second sub-array
	//will contain one additional element	
	if(input.length%2 != 0)	
	{
	sizeB +=1;
	}
	
	//Partition input array into two sub arrays
	int [] myArrayA = new int[sizeA];
	int [] myArrayB = new int[sizeB];
	
	//Fill sub array 1 with the first half of the input array contents
	for(int m=0; m <sizeA; m++)
	{
	myArrayA[m] = input[m];
	}
	
	//Fill sub array 2 with the second half of the input array contents
	for(int n =sizeA; n <sizeA + sizeB; n++)
	{
	myArrayB[n-sizeA] = input[n];
	}

	//Recursively call function so that each sub-array will be sorted 
	//and can later be inserted (sorted) into output array
	myArrayA = sortFreqValsNumeric(myArrayA);
	myArrayB = sortFreqValsNumeric(myArrayB);
	
	//Initialize variables to use for looping through each array	
	int a = 0;
	int b= 0;
	int c = 0;
	
	//Conduct 2-way merge: compare first element of each array	
	while(myArrayA.length != a && myArrayB.length != b)
	{
	if(myArrayA[a] <= myArrayB[b])
	{
	input[c] = myArrayA[a];
	//Increase index placeholder in final array
	c++;
	//Increase index in freqInA to compare next value 
	a++;
	
	}
	else
	{
	input[c] = myArrayB[b];
	//Increase index placeholder in final array
	c++;
	//Increase index in freqInA to compare next value 
	b++;
	
	}
	}
	
	/* At this point, either sub array A or B has been exhausted, and
	*  the remaining array's contents have already been sorted via a 
	*  recursive method call; thus, the remaining contents can be inserted
	*  into the output array */
	
	while(myArrayA.length != a)
	{
	input[c] = myArrayA[a];
	c++;
	a++;
	}
	while(myArrayB.length != b)
	{
	input[c] = myArrayB[b];

	c++;
	b++;
	}
	}
	//If the length of the input array is < 1, return input array 
	else{};

	return input;
	}	//close sortFreqVals method 



	/**
	 * @method build takes a sorted (ascending order) array and returns
	 * a Node-array based Huffman tree  
	 * <dt><b>Precondition:</b><dd>
	 * Input array is sorted in ascending order 
	 * @param String[][] input array; Node [] array to store output 
	 * @returns Node[] output array containing tree implemented as Node [] 
	 * <dt><b>Postconditions:</b><dd>
	 * Node [] now contains the Huffman tree nodes 
	 * @author Christine Herlihy
	 */
	public static Node [] build(String[][] array, Node[] nodes)	
	{

	Node tempRoot= new Node(" ", -1); 
	Node updatedRoot= new Node(" ", -1);
	Node tempLeft= new Node(" ", -1); 
	Node tempRight= new Node(" ", -1);	
	Node updatedLeft = new Node(" ", -1);

	int nodesAndRoot = array.length*2; //#of nodes to store in nodes[] (all nodes + root) 
	int counter = 3;

	
	for(int i =0; i<array.length; i++)
	{
	
	if(i < 2)
	{
	//Make a tree with a placeholder root
	tempRoot = HuffmanTree.MakeTree("root", -1);
	
	//Get the alphabetic chars & freqVals for the first 2 nodes
	//(i.e., lowest frequency letters)	
	String alphaA = array[i][0];
	String alphaB = array[i+1][0];
	
	int freqA = Integer.parseInt(array[i][1]);
	int freqB = Integer.parseInt(array[i+1][1]);
	
	//Set the first node as left child of tempRoot
	//Set the second node as the right child of tempRoot	
	tempLeft = new Node(alphaA, freqA);
	tempLeft.setHuffman("0");	//because it's the left child
	
	tempRight= new Node(alphaB, freqB);
	tempRight.setHuffman("1");	//because right child
	
	tempRoot.setLeft(tempLeft);
	tempRoot.setRight(tempRight);
	
	//Set tempRoot's element to the combination of alphaA and alphaB
	tempRoot.setElement(alphaA + alphaB);
	
	//Set tempRoot's freqVal to the sum of freqA and freqB
	tempRoot.setFreqVal(freqA + freqB);	
	
	
	
	nodes[nodesAndRoot -i - 2]= tempRoot;
	nodes[nodesAndRoot -i - 1] = tempRoot.getLeft();
	nodes[nodesAndRoot -i]= tempRoot.getRight();
	i++;
	
	
	}
	
	else if(i >= 2& i <array.length)
	{
	//Make a new node and set its right child equal to tempRoot 
	updatedRoot = HuffmanTree.MakeTree("root", -1);	
	
	System.out.println(tempRoot.toString());

	String alphaC = array[i][0];
	int freqC= Integer.parseInt(array[i][1]);
	
	updatedLeft = new Node(alphaC, freqC);
	updatedRoot.setLeft(updatedLeft);
	updatedLeft.setHuffman("0"); //because left child
	
	
	updatedRoot.setRight(tempRoot);
	tempRoot.setHuffman("1");	//because right child
	
	String temp = alphaC + tempRoot.getElement();
	updatedRoot.setElement(temp);
	updatedRoot.setFreqVal(freqC + tempRoot.getFreqVal());
	
	nodes[nodesAndRoot -counter]= updatedRoot.getLeft();
	counter++;
	nodes[nodesAndRoot -counter]= updatedRoot;
	counter++;

	tempRoot = updatedRoot;
	}
	}
	nodes[2].setHuffman("");	//because root node 
	return nodes;
	}

	
	/**
	 * @method build takes a sorted (ascending order) array and returns
	 * a Node-array based Huffman tree  
	 * <dt><b>Precondition:</b><dd>
	 * Input array is sorted in ascending order 
	 * @param String[][] input array; Node [] array to store output 
	 * @returns Node[] output array containing tree implemented as Node [] 
	 * <dt><b>Postconditions:</b><dd>
	 * Node [] now contains the Huffman tree nodes 
	 * @author Christine Herlihy
	 */
	public static Node [] build2(LinkedHuffmanStack tempStack, Node[] nodes)	
	{
	
	Node tempRoot= new Node(" ", -1); 
	Node updatedRoot= new Node(" ", -1);
	Node tempLeft= new Node(" ", -1); 
	Node tempRight= new Node(" ", -1);	
	Node updatedLeft = new Node(" ", -1);
	boolean terminate = false;
	Node tree = new Node();
	int counterStore = 0; 
	LinkedHuffmanStack dummyStack = new LinkedHuffmanStack();
	int tempInt = 0;
	int nodesAndRoot = tempStack.getSize()*2;
	
	//System.out.println("size" + tempStack.getSize());	//FOR TESTING 

	while(tempStack.getSize() >=2)
	{
	
	
	//System.out.println(tempStack.getSize());
	//Make a tree with a placeholder root
	tempRoot = HuffmanTree.MakeTree("root", 0);
	
	String pop1Name = tempStack.peek();
	int pop1Val = tempStack.peekFreqVal();
	
	//tempStack.pop();
	tempLeft = new Node(pop1Name, pop1Val);
	tempLeft.setHuffman("0");	//because it's the left child
	tempStack.pop();
	
	
	String pop2Name = tempStack.peek();
	int pop2Val = tempStack.peekFreqVal();
	
	tempRight= new Node(pop2Name,pop2Val);
	tempRight.setHuffman("1");	//because right child
	tempStack.pop();
	
	//System.out.println(tempStack.getSize());
	
	tempRoot.setLeft(tempLeft);
	tempRoot.setRight(tempRight);
	
	//Set tempRoot's element to the combination of alphaA and alphaB
	String tempRootName = tempLeft.getElement() + tempRight.getElement();
	tempRoot.setElement(tempRootName);
	
	
	//Set tempRoot's freqVal to the sum of freqA and freqB
	tempRoot.setFreqVal(tempLeft.getFreqVal() + tempRight.getFreqVal());
	
	nodes[counterStore] = tempRoot;
	counterStore++;
	
	//NEED TO FIX THIS PART ??? 
	
	
//	nodes[nodesAndRoot -counterStore - 2]= tempRoot;
//	nodes[nodesAndRoot -counterStore - 1] = tempRoot.getLeft();
//	nodes[nodesAndRoot -counterStore]= tempRoot.getRight();
//	counterStore++;
	
/*	if(counterStore <2)
	{
	nodes[nodesAndRoot -counterStore - 2]= tempRoot;
	nodes[nodesAndRoot -counterStore - 1] = tempRoot.getLeft();
	nodes[nodesAndRoot -counterStore]= tempRoot.getRight();
	counterStore+=2;
	}
	
	else if(counterStore > 2)
	{
	nodes[nodesAndRoot -counterStore]= tempRoot.getLeft();
	counterStore++;
	nodes[nodesAndRoot -counterStore]= tempRoot;
	counterStore++;
	}*/
	
	
	
//	else if(counterStore >2  )
//	{
//	nodes[nodesAndRoot -counterStore]= tempRoot.getLeft();
//	counterStore++;
//	nodes[nodesAndRoot -counterStore]= tempRoot;
//	counterStore++;
//	}

	
	
	if(tempStack.isEmpty() !=true)
	{
	tempInt = tempStack.peekFreqVal();
	
	int test = tempRoot.getFreqVal() - tempInt;
	
	
	int switchController =0;
	
	if(test < 0)
	{
	switchController = 1;
	}
	else if(test == 0)
	{
	switchController =2;
	}
	else if(test > 0)
	{
	switchController =3;
	}
	
	
	switch(switchController)
	{
	case (1): //tempRoot's frequency value is LESS THAN the item on top of the stack; can simply push tempRoot onto stack 
	{
	
	tempStack.push(tempRoot);
	//System.out.println("tempstack top is now " + tempStack.peek());
	break;
	}
	case (2)://tempRoot's frequency value is EQUAL to the item on the top of the stack; need to compare the length of their strings and (if necessary) alphabetical values
	{	
	
	int lengthRoot = tempRoot.getElement().length();
	int lengthOther = tempStack.peek().length();
	String nameOther = tempStack.peek();
	
	
	//the tempRoot's string is longer, so we need to pop the stack, insert it, and then push on the value that was popped off the stack
	if(lengthOther < lengthRoot) 
	{
	
	String peek1Name = tempStack.peek();
	int peek1Val= tempStack.peekFreqVal();
	Node dummyNode = new Node(peek1Name, peek1Val);
	tempStack.pop();

	
	dummyStack.push(dummyNode);	
	tempStack.push(tempRoot);
	
	String peek2Name = dummyStack.peek();
	int peek2Val= dummyStack.peekFreqVal();
	Node dummyNode2 = new Node(peek2Name, peek2Val);
	dummyStack.pop();
	
	tempStack.push(dummyNode2);
	//System.out.println("tempstack top is now " + tempStack.peek());
	//System.out.println("tempstack size is A " + tempStack.getSize());
	break;
	
	}
	
	//the tempRoot's string is shorter, so we can insert it onto the stack first 
	else if(lengthRoot < lengthOther)
	{
	
	tempStack.push(tempRoot);
	//System.out.println("tempstack top is now " + tempStack.peek());
	//System.out.println("tempstack size is B " + tempStack.getSize());
	break;

	}
	
	else if(lengthRoot == lengthOther)
	{
	int a = tempRoot.getElement().compareTo(nameOther);
	
	if(a < 0)
	{
	tempStack.push(tempRoot);
	//System.out.println("tempstack top is now " + tempStack.peek());
	//System.out.println("tempstack size is C " + tempStack.getSize());
	break;
	}
	
	else //temp Root comes after the top node in ABC order 
	{
	String peek1Name = tempStack.peek();
	int peek1Val= tempStack.peekFreqVal();
	Node dummyNode3 = new Node(peek1Name, peek1Val);
	tempStack.pop();

	
	dummyStack.push(dummyNode3);	
	tempStack.push(tempRoot);
	
	String peek2Name = dummyStack.peek();
	int peek2Val= dummyStack.peekFreqVal();
	Node dummyNode4 = new Node(peek2Name, peek2Val);
	dummyStack.pop();
	
	tempStack.push(dummyNode4);
	//System.out.println("tempstack top is now " + tempStack.peek());
	//System.out.println("tempstack size is D " + tempStack.getSize());
	break;
	}
	}

	}
	case (3): //tempRoot's frequency value is GREATER THAN the item on top of the stack; need to reorder 
	{
	
	int difference = test;
	boolean proceed = false;
	String peek1Name = new String();
	int peek1Val =0;
	Node originalTop = new Node();
	
	while(proceed != true & tempStack.peek() !=null)
	{

	//Pop off the top node from the stack that we originally compared the tempRoot value to
	peek1Name = tempStack.peek();
	peek1Val= tempStack.peekFreqVal();
	originalTop = new Node(peek1Name, peek1Val);
	tempStack.pop();
	dummyStack.push(originalTop);
	difference = tempRoot.getFreqVal() - tempStack.peekFreqVal();

	if(difference < 0 | difference == 0) { proceed = true; }
	
	
	if(tempStack.isEmpty() == true & proceed !=true)
	{
	difference = 1-2;
	}
	
	}
	
	if(difference < 0)
	{
	
	tempStack.push(tempRoot);
	
	while(dummyStack.isEmpty() ==false)
	{
	String peek2Name = dummyStack.peek();
	int peek2Val= dummyStack.peekFreqVal();
	Node dummyNode5 = new Node(peek2Name, peek2Val);
	tempStack.push(dummyNode5);
	dummyStack.pop();
	}
	
	//System.out.println("tempstack size is B " + tempStack.getSize());
	//System.out.println("tempstack top is now " + tempStack.peek());
	break;
	}
	
	else if(difference ==0)
	{
	int lengthRoot = tempRoot.getElement().length();
	int lengthOther = tempStack.peek().length();
	String nameOther = tempStack.peek();
	
	
	//the tempRoot's string is longer, so we need to pop the stack, insert it, and then push on the value that was popped off the stack
	if(lengthOther < lengthRoot) 
	{
	
	String peekNameX = tempStack.peek();
	int peekValX= tempStack.peekFreqVal();
	Node dummyNode = new Node(peekNameX, peekValX);
	tempStack.pop();

	
	dummyStack.push(dummyNode);	
	tempStack.push(tempRoot);
	
	while(dummyStack.isEmpty() ==false)
	{
	String peek2Name = dummyStack.peek();
	int peek2Val= dummyStack.peekFreqVal();
	Node dummyNode6 = new Node(peek2Name, peek2Val);
	tempStack.push(dummyNode6);
	dummyStack.pop();
	}
	//System.out.println("tempstack size is C " + tempStack.getSize());
	//System.out.println("tempstack top is now " + tempStack.peek());
	break;
	}
	
	//the tempRoot's string is shorter, so we can insert it onto the stack first 
	else if(lengthRoot < lengthOther)
	{
	
	tempStack.push(tempRoot);
	
	while(dummyStack.isEmpty() ==false)
	{
	String peek2Name = dummyStack.peek();
	int peek2Val= dummyStack.peekFreqVal();
	Node dummyNode2 = new Node(peek2Name, peek2Val);
	tempStack.push(dummyNode2);
	dummyStack.pop();
	}
	//System.out.println("tempstack top is now " + tempStack.peek());
	//System.out.println("tempstack size is D " + tempStack.getSize());
	break;
	}
	
	else if(lengthRoot == lengthOther)
	{
	int a = tempRoot.getElement().compareTo(nameOther);
	
	if(a < 0)
	{
	tempStack.push(tempRoot);
	
	}
	
	else //temp Root comes after the top node in ABC order 
	{
	String peekNameA = tempStack.peek();
	int peekValA= tempStack.peekFreqVal();
	Node dummyNode = new Node(peekNameA, peekValA);
	tempStack.pop();

	
	dummyStack.push(dummyNode);	
	tempStack.push(tempRoot);
	}
	
	while(dummyStack.isEmpty() ==false)
	{
	String peek2Name = dummyStack.peek();
	int peek2Val= dummyStack.peekFreqVal();
	Node dummyNode2 = new Node(peek2Name, peek2Val);
	tempStack.push(dummyNode2);
	dummyStack.pop();
	}
	//System.out.println("tempstack top is now " + tempStack.peek());
	//System.out.println("tempstack size is E " + tempStack.getSize());
	break;
	}
	}	//close else if(difference ==0)
	}	//close case 3
	}	//close switch 
	}
	}
	
	
	if(tempStack.getSize()==0)
	{
	
	tree = new Node(tempRoot.getElement(), tempRoot.getFreqVal());
	//System.out.println(tree.getElement());
	tree.setHuffman("");	//because root node 
	//System.out.println("OUT");
	//terminate = true;
	}
	return nodes;
	}//close build2
	

	
	/**
	 * @method combine output takes multiple output files and combines them into one
	 * <dt><b>Precondition:</b><dd>
	 * All file paths are correctly specified and contain content
	 * @param Four strings: first 3=output paths to combine; last = target path 
	 * @returns None 
	 * <dt><b>Postconditions:</b><dd>
	 * All ouptut is contained in path specified by final parameter
	 * @author Christine Herlihy
	 */
	public static void combineOutput(String out1, String out2, String out3, String out4)
	{
	String [] outputArray = new String[500];
	int counter =0;
	//For output
	
	try(BufferedReader bufferFinal = new BufferedReader(new FileReader(out1)))
	{
	//For input
	String line= new String();
	Scanner input= new Scanner(System.in);
	
	//Read each line of the input file in; store each char and int 
	while((line=bufferFinal.readLine()) != null)
	{
	outputArray[counter]= line;
	counter++;
	}
	
	}	//close try 2

	catch (FileNotFoundException e)
	{
	System.out.println("Database file not found.");
	
	}

	catch (IOException e) 
	{
	System.out.println("An I/O Error occured.");
	
	}
	
	
	try(BufferedReader bufferFinal2 = new BufferedReader(new FileReader(out2)))
	{
	//For input
	String line= new String();
	Scanner input= new Scanner(System.in);	

	//Read each line of the input file in; store each char and int 
	while((line=bufferFinal2.readLine()) != null)
	{
	outputArray[counter]= line;
	counter++;
	}
	
	}	//close try 

	catch (FileNotFoundException e)
	{
	System.out.println("Database file not found.");
	
	}

	catch (IOException e) 
	{
	System.out.println("An I/O Error occured.");
	}
	
	try(BufferedReader bufferFinal3 = new BufferedReader(new FileReader(out3)))
	{
	
	//For input
	String line= new String();
	Scanner input= new Scanner(System.in);
	
	//For output
	BufferedWriter outputFile4 = new BufferedWriter(new FileWriter(out4));

	//Read each line of the input file in; store each char and int 
	while((line=bufferFinal3.readLine()) != null)
	{
	outputArray[counter]= line;
	counter++;
	}
	
	
	for(int i=0; i<outputArray.length; i++)
	{
	if(outputArray[i] !=null)
	{
	outputFile4.write(outputArray[i] + "\n");
	}
	}
	
	outputFile4.close();
	
	}	//close try 
	catch (FileNotFoundException e)
	{
	System.out.println("Database file not found.");
	
	}

	catch (IOException e) 
	{
	System.out.println("An I/O Error occured.");
	}
	}

	}	//close class RunProgLab3