import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Hashtable;
import java.util.Set;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.util.Scanner;
import java.io.FileNotFoundException;

public class PA2{

	//PA #2 TODO: finds the smallest tree in a given forest, allowing for a single skip
	//Finds the smallest tree (by weight) in the supplied forest.
	//Note that this function accepts a second optional parameter of an index to skip.
	//Use this index to allow your function to also find the 2nd smallest tree in the
	//forest.
	public static int findSmallestTree(List<HuffmanTree<Character>> forest)
	{
		return findSmallestTree(forest, -1); //find the real smallest
	}
	public static int findSmallestTree(List<HuffmanTree<Character>> forest, int index_to_ignore)
	{
		//iterate through every character , each tree in forest, look at weight
		//smallest weight, record it, if you hit weight smaller
		//record index number, if smaller
		//current index, smallest index, weight
		//Then loop if I!= index to ignore && list (i).getweight < smallest weight
				//then smallest index = I and smallest weight = list (i).get weight
				//Then when the loop is done return smallest index

		int smallest_weight = Integer.MAX_VALUE;
		int smallest_index = -1;
		for(int i = 0; i <forest.size(); i ++)
		{
			if(i!= index_to_ignore && forest.get(i).getWeight() < smallest_weight)
			{
				smallest_index = i;
				smallest_weight = forest.get(i).getWeight();
			}
		}
		return smallest_index;


		 //find the smallest except the index to ignore.
	}

	//PA #2 TODO: Generates a Huffman character tree from the supplied text
	//Builds a Huffman Tree from the supplied list of strings.
	//This function implement's Huffman's Algorithm as specified in page
	//435 of the book.
	public static HuffmanTree<Character> huffmanTreeFromText(List<String> data) {
		//In order for your tree to be the same as mine, you must take care
		//to do the following:
		//1.	When merging the two smallest subtrees, make sure to place the
		//      smallest tree on the left side!
		//2.	Have the newly created tree take the spot of the smallest
		//		tree in the forest(e.g. list.set(smallest_index, merged_tree) ).
		//3.	Use list.remove(second_smallest_index) to remove
		//      the other tree from the forest.
		//HuffmanTree<Character> some_tree = new HuffmanTree<Character>('a', 5);
		//HuffmanNode<Character> root = some_tree.getRoot();
		//hashtable<character, int>
		Hashtable<Character, Integer> dict = new Hashtable<Character, Integer>();

		for(String line: data)
		{
			for(Character c: line.toCharArray())
			{
				if( dict.contains(c))
				{
					dict.put(c, dict.get(c)+1);
				}
				else
				{
					dict.put(c, 1);
				}
			}
		}
		List<HuffmanTree<Character>> forest = new ArrayList<HuffmanTree<Character>>();
		Set<Character> keys = dict.keySet();
		for(Character key: keys)
		{
			HuffmanTree<Character> tree = new HuffmanTree<Character>(key, dict.get(key));
			forest.add(tree);
		}
		int smallestIndex = -1;
		int secondIndex = -1;
		HuffmanTree<Character> tree = null;
		while(forest.size() >1)
		{
			//1.	When merging the two smallest subtrees, make sure to place the
			//      smallest tree on the left side!
			//2.	Have the newly created tree take the spot of the smallest
			//		tree in the forest(e.g. list.set(smallest_index, merged_tree) ).
			//3.	Use list.remove(second_smallest_index) to remove
			//      the other tree from the forest.
			smallestIndex = findSmallestTree(forest);
			secondIndex = findSmallestTree(forest, smallestIndex);
			HuffmanTree<Character> smallest = forest.get(smallestIndex);
			HuffmanTree<Character> secondSmallest = forest.get(secondIndex);
			tree = new HuffmanTree<>(smallest, secondSmallest);
			forest.set(smallestIndex, tree);
			forest.remove(secondIndex);
		}

		//note that root is a HuffmanNode instance. This type cast would only work
		//if you are sure that root is not a leaf node.
		//Vice versa, for this assignment, you might need to force type cast a HuffmanNode
		//to a HuffmanLeafNode when you are sure that what you are getting is a HuffmanLeafNode.
		//HuffmanInternalNode<Character> i_root = (HuffmanInternalNode<Character>)root;
		return tree;
	}


	//PA #2 TODO: Generates a Huffman character tree from the supplied encoding map
	//NOTE: I used a recursive helper function to solve this!
	public static HuffmanTree<Character> huffmanTreeFromMap(Map<Character, String> huffmanMap) {
		//Generates a Huffman Tree based on the supplied Huffman Map.Recall that a
		//Huffman Map contains a series of codes(e.g. 'a' = > 001).Each digit(0, 1)
		//in a given code corresponds to a left branch for 0 and right branch for 1.

		//reccursion while something is still in the string
		//if 1 get the right child
		//create node, split value up, and take eah part in till done.
		HuffmanTree tree = new HuffmanTree(new HuffmanInternalNode(null, null));
		for(Character key: huffmanMap.keySet())
		{
			helper(tree.getRoot(), huffmanMap.get(key),key);
		}


		return tree;

	}

	//PA #2 TODO: Generates a Huffman encoding map from the supplied Huffman tree
	//NOTE: I used a recursive helper function to solve this!
	public static Map<Character, String> huffmanEncodingMapFromTree(HuffmanTree<Character> tree) {
		//Generates a Huffman Map based on the supplied Huffman Tree.  Again, recall
		//that a Huffman Map contains a series of codes(e.g. 'a' = > 001).Each digit(0, 1)
		//in a given code corresponds to a left branch for 0 and right branch for 1.
		//As such, a given code represents a pre-order traversal of that bit of the
		//tree.  I used recursion to solve this problem.


		Map<Character, String> result = new HashMap<>();
		helper2(tree.getRoot(), "", result);
		return result;
	}

	//PA #2 TODO: Writes an encoding map to file.  Needed for decompression.
	public static void writeEncodingMapToFile(Map<Character, String> huffmanMap, String file_name) {
		//Writes the supplied encoding map to a file.  My map file has one
		//association per line (e.g. 'a' and 001).  Each association is separated by
		//a sentinel value.  In my case, I went with a double pipe (||).
		String newline = System.getProperty("line.separator");
		File file = new File(file_name);
		FileWriter fWriter = null;
		BufferedWriter bWriter = null;
		try
		{
			fWriter = new FileWriter(file);
			bWriter = new BufferedWriter(fWriter);
			for(Map.Entry<Character,String> entry: huffmanMap.entrySet())
			{
				Character key = entry.getKey();
				String value = entry.getValue();
				bWriter.write(key + "||" + value + newline);
			}
		}catch(IOException e) {
			e.printStackTrace();
		}finally {
			try {
				if(bWriter != null)
				{
					bWriter.close();
				}
				if(fWriter != null)
				{
					fWriter.close();
				}
			}catch(IOException e) {
				e.printStackTrace();
			}
		}
	}

	//PA #2 TODO: Reads an encoding map from a file.  Needed for decompression.
	public static Map<Character, String> readEncodingMapFromFile(String file_name) throws FileNotFoundException {
		//Creates a Huffman Map from the supplied file.Essentially, this is the
		//inverse of writeEncodingMapToFile. Use String.split() function - note that
		//the split() function takes a Regular Expression as an input, not a "string" itself.
		//To separate based on "||", the argument for the function should be: split("\\|\\|")
		String newline = System.getProperty("line.separator");
		Map<Character, String> result = new HashMap<>();
		File file = new File(file_name);
		FileReader fReader = new FileReader(file);
		BufferedReader bReader = new BufferedReader(fReader);
		try
		{
		String line = "";
		while((line = bReader.readLine()) != null)
				{
					String parts[] = line.split("\\|\\|");
					result.put(parts[0].charAt(0), parts[1]);
				}
		}catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				if (bReader != null) {
					bReader.close();
				}
				if(fReader != null)
				{
					fReader.close();
				}
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return result;
	}