/**
 ******************************************************************************
 *                    HOMEWORK     15-211      COMPRESSION
 ******************************************************************************
 *
 *   This implements the Huffman encoding algorithm
 *
 *
 * @author
 * @date
 *****************************************************************************/
 /*****************************************************************************

                         IMPLEMENT THIS CLASS

 *****************************************************************************/

import java.io.*;
import java.util.*;


public class HuffmanEncode
{
	/** Code bit for a leaf node in file-based tree representation */
	private static final int LEAF = 0;

	/** Code bit for a parent node in file-based tree representation */
	private static final int PARENT = 1;

	/** Code bit for the left child in the file-based tree representation */
	private static final int LEFT = 0;

	/** Code bit for the right child in the file-based tree representation */
	private static final int RIGHT = 1;

	/** the root of the Huffman tree    */
	private HuffmanNode root; 

	/** it stores chars and their frequences    */
	private Map<Byte, Integer> freqMap;

	/** it stores bytes and the encoding */
	private Map<Byte, int[]> encoding;

	/**
	*  Reads-in the input file, compresses it and writes to the output file
	*/
	public void encode(BitReader reader, BitWriter writer)
	{
		int fileBytes = reader.length();
		if (fileBytes == 0) return;

		countFrequencies(reader);
		HuffmanTree(freqMap);
		try{ writeHeader(writer); } catch(IOException e) {}
		writer.writeInt(fileBytes);

		reader.reset();

		for (int i = 0; i < fileBytes; i++)
			encode((byte) reader.readByte(), writer);

		writer.flush();
	}


	/**
	* This method takes a item and writes the corresponding codeword.
	* The bits <tt>LEFT</tt> and <tt>RIGHT</tt> are written so that
	* if one takes that path in the Huffman tree they will get to the
	* leaf node representing <tt>item</tt>.
	*/
	public void encode(Byte item, BitWriter writer)
	{
		throw new RuntimeException("You must implement this method");
	}


	/**
	*  Calculates frequences of each character from the ASCII table
	*/
	public Map<Byte, Integer> countFrequencies(BitReader reader)
	{
		throw new RuntimeException("You must implement this method");
	}

	/**
	* Takes a list of (Byte, Frequency) pairs (here represented as a map)
	* and builds a tree for encoding the data items using the Huffman
	* algorithm.
	*/
	public void HuffmanTree (Map<Byte, Integer> map)
	{		
		throw new RuntimeException("You must implement this method");
	}
	
	/**
	* Writes the Huffman tree into a compressed file.
	*
	* The format for the tree is defined recursively. To write
	* the entire tree, you start with the root. When the node
	* is a leaf node, you write the bit <tt>LEAF</tt>
	* and then call the <tt>writeByte</tt> to write the node value.
	* Otherwise, you write the bit <tt>PARENT</tt>, then
	* go to the left and right nodes.
	*/
	public void writeHeader(BitWriter writer) throws IOException
	{
		throw new RuntimeException("You must implement this method");
	}
		
	/**
	 * For testing purposes
	 * DO NOT REMOVE!
	 */
	public HuffmanNode getCodeTreeRoot()
	{
		return root;
	}

}