package compression;

import java.util.HashMap;
import java.util.Vector;

public class HuffmanTree implements Comparable 
{
	protected Node root;
	protected HashMap<Integer, Node> codeTable;
	
	HuffmanTree()
	{
		root = null;
	}
	
	HuffmanTree(int _val, int _weight) 
	{
		codeTable = new HashMap<Integer, Node> (256);
		root = new Node(_val, _weight);
		codeTable.put(_val, root);
	}

	HuffmanTree(HuffmanTree left, HuffmanTree right) 
	{
		int weight = left.GetWeight() + right.GetWeight();
		root = new Node(left.root.data, weight);
		root.left = left.root;
		root.right = right.root;
		root.left = root.right = root;
		codeTable.putAll(left.codeTable);
		codeTable.putAll(right.codeTable);
	}

	public int GetWeight() 
	{
		return root.GetWeight();
	}

	protected static class Node 
	{
		Node left, right, parent;
		int data;
		int weight;
		private Vector<Boolean> encodValue;

		Node(int newData, int weight, Node _parent) 
		{
			left = null;
			right = null;
			data = newData;
			parent = _parent;
		}
		
		Node(int newData, int weight) 
		{
			this(newData, weight, null);
		}
		
		
		Node(int newData) 
		{
			this(newData, 0); 
		}
		
		int GetWeight()
		{
			return weight;
		}
		

		Vector<Boolean> GetEncodValue()
		{
			return encodValue;
		}
		
		
		void print(String prefix)
		{
			if (left == null && right == null)
				System.out.printf(prefix + "[%c]\n", this.data);
			
			if (left != null)
				left.print(prefix + "-");
			
			if (right != null)
				right.print(prefix + "-");
		}
		
		void computeEncodValue(Vector<Boolean> prefix)
		{
			if (prefix.size() >= 8 || (prefix == null))
				System.out.println("ERREUR");
			
			if (left == null && right == null)
				encodValue = prefix;
			else
				encodValue = null;
			
			if (left != null)
			{
				Vector<Boolean> leftPrefix = (Vector<Boolean>) prefix.clone();
				leftPrefix.add(false);
				left.computeEncodValue(leftPrefix);
			}
			
			if (right != null)
			{
				Vector<Boolean> leftPrefix = (Vector<Boolean>) prefix.clone();
				leftPrefix.add(true);
				left.computeEncodValue(leftPrefix);
			}
		}
		
		public void incWeight()
		{
			weight++;
		}
	}

	public int compareTo(Object o) 
	{
		 int ow = ((HuffmanTree) o).GetWeight();
		 if (ow > this.GetWeight())
			 return -1;
		 else if (ow < this.GetWeight())
		 	return 1;
		 else // Si les poids sont egaux, on utilise la valeur de l'etiquette
		{
			 int oVal = ((HuffmanTree) o).root.data;
			 if (oVal > this.root.data)
				 return -1;
			 else if (oVal < this.root.data)
				 return 1;
			 
			return 0;
		}
		

	}
	
	public void ComputeEncodValues()
	{
		this.root.computeEncodValue(new Vector<Boolean> ());
	}
	
	
	public void printTree()
	{
		root.print("");
	}

}