import java.util.StringTokenizer;
import java.util.*;
public class HuffmanTree
{
	//Some class variables.
	Hashtable freqTable;//For the frequencies.
	Stack queue;
	int row=0, col=0;
	
	
	public HuffmanTree(String sentence){
		
		freqTable= new Hashtable();
		getFreq(sentence, 0);
	} 
	/*****************************************************
	 Name: getFreq()
	 Parameters: String, int
	 Declared variables:char current, bool doIt, int freqCount
	 	char fc.
	 Return value: void
	 
	 Algorithm: (assumes the user puts all the characters in the same case)
	 	getFreq(entireString, starting indx 'initialy at 0')
	 		
	 		remove white spaces if flag alows.
	 		frequent count=0
	 		current=char @ stIndx
	 		
	 		for(compare every char in the entire string to char @ stIndx)
	 			every true comparison to the char @ stIndx  add one to a 
	 			counter for that char.
	 		end for. 
	 	
	 		add the current char and the counter to the hashTable	
	 		remove every instance of the current char.
	 		set white space flag to true
	 		if(startIndx is not at the end of the string)				
	 			recurse.
	 	end.
	 				
	 ****************************************************/
	public void getFreq(String s, int stIndx){
		char current;
		boolean doIt=true;
		
		if(doIt){
			s=removeWhiteSpaces(s);
			doIt=false;
		}
		
		int freqCount=0;
		current=s.charAt(stIndx);
			
		for(int i=0; i<s.length(); ++i){
			if(current==s.charAt(i))
				freqCount++;//Number of character accurances.
		}
		freqTable.put(""+current,new Integer(freqCount));
		s=removeChar(s,current);//Removes every instance of the current char from sentence.
		doIt=true;//Remove all the white spaces again.
	
		if(stIndx < s.length())//If not at the end
			getFreq(s, stIndx);//Recurse.
			
		
	} 
	
	/*****************************************************
	 Name: removeWhiteSpaces()
	 Parameters: String s
	 Declared variables: StringTokenizer, StringBuffer
	 Return value: String
	 Purpose: Takes all the white spaces out of the specified
	 	String object.
	 ****************************************************/
	public String removeWhiteSpaces(String s){
		StringTokenizer sToken=new StringTokenizer(s," ",false);
		StringBuffer sbuff=new StringBuffer();
		while(sToken.hasMoreTokens()){
			sbuff.append(sToken.nextToken());
		}
		s=sbuff.toString();//Converts the StringBuffer sbuff into a regular String.
		return s;
	}
	
	/*****************************************************
	 Name: display()
	 Parameters: HashTable ht
	 Declared variables: Iterator, Set, String
	 Return value: void
	 Purpose: Creates an iterator which it uses, and goes 
	 	through the entire HashTable and prints each of the 
	 		items.
	 ****************************************************/
	public void display(Hashtable ht){
		Set st = ht.keySet();//Creates a new set for all the keys that are in the hashTable.		
		Iterator i = st.iterator();//Creates a new iterator for the set.
		String temp;
		
		//Iterates through the hashTable set.		
		while (i.hasNext())
		{			
			temp = (String)i.next();			
			System.out.println(temp+" = "+ (Integer)ht.get(temp));		
		}
	}
	
	/*****************************************************
	 Name: displayFreqTable()
	 Parameters: none.
	 Declared variables: none
	 Return value: void
	 Purpose: Makes a call to display to display the 
	 	frequency table.
	 ****************************************************/
	public void displayFreqTable(){
		System.out.println("Frequency Table");
		display(freqTable);
	}
	
   	
   	/*****************************************************
	 Name: removeChar()
	 Parameters: String s, char c
	 Declared variables: String
	 Return value: String
	 Purpose: Removes all the characters that match the 
	 	specified 'char c' from the specified 'String s'.
	 ****************************************************/
   	public String removeChar(String s, char c) {
   		String r = "";
   		for (int i = 0; i <s.length(); i ++) {
      		if (s.charAt(i) != c) r += s.charAt(i);
      	}
   		return r;
   	}
	/****************************************************
	 Name: buildTree()
	 Parameters: HashTable ht
	 Declared variables:
	 Return value:
	 Purpose: To take a HashTable in and create a binary tree
	 	from the frequencies located in the HashTable.
	 
	 Algorithm:
	 	
	*****************************************************/
	public void buildTree(Hashtable ht){
	}
	
	/****************************************************
	 Name: insertIntoQueue()
	 Parameters: HashTable ht
	 Declared variables: Stack queue, Enumerator e, String temp
	 	Set s, Integer currentLow, currentItem.
	 Return value: void
	 Purpose: Takes a HashTable argument, remove the frequencies and 
	 	insert them into a priority queue;
	 
	 Algorithm:
	 	
	 	insertIntoQueue(hashTable h)
	 		currentHigh=temp(current);
	 		
	 		while(theres something in the Hashtable)
	 			if(currentHigh is greaterthan the current position)
	 				make the currentHigh equal the current position.
	 			else
	 				move on.
	 		end while.
	 			if (nothing was bigger than the current High) 
	 				add the current high to the stack and remove it from
	 					the Hashtable.
				end if.	 			
	 				
	 	end.
	*****************************************************/
	public void insertIntoQueue(Hashtable ht){
		
		//Function variables.
		queue=new Stack();
		Set s=ht.keySet();
		Iterator i = s.iterator();
		String currentPos, highItem="";
		Integer currentHigh;
		
		currentPos=(String)i.next();//Equals current item we are looking at.
		currentHigh=((Integer)ht.get(currentPos));//currentHigh= the next items value.
		
		while(i.hasNext()){
			
			currentPos=(String)i.next();//Equals current item we are looking at.
			
			//If there is something bigger make it equal to the current
			if(currentHigh.intValue() <= ((Integer)ht.get(currentPos)).intValue()){
				currentHigh=(Integer)ht.get(currentPos);//CurrentHigh=currentPos.
				highItem=currentPos;
 
			}
			
		}
		System.out.println("Current high: "+currentHigh);
		//currentPos=last char in the Hashtable.
		//If nothing was bigger then add itself.
		System.out.println("Removed: "+highItem);
		ht.remove(highItem);//Remove item from the table.
		queue.push(currentHigh);
	}
	
	public void fuck(){
		insertIntoQueue(freqTable);
	}
	
	/****************************************************
	 Name: createNode()
	 Parameters: Stack s
	 Declared variables:
	 Return value: Node
	 Purpose: Pop two frequencies off the queue and create
	 	a new Node with them, then return it. 
	 
	 Algorithm:
	 	
	 	createNode(Stack s)
	 		
	 	end.
	*****************************************************/
	//public Node createNode(Stack s){
		
	//}
	
	
	//The treeNode innner class.
	public class treeNode
	{
		int frequency;//This becomes the sum of the two leafs freqs under it.
		char code='0';
		boolean isRoot;
		treeLeaf r;
		treeLeaf l;
		
		public treeNode(int freq, boolean isR, treeLeaf right, treeLeaf left)
		{
			this.frequency=freq;
			this.isRoot=isR;//Set this flag to true if node is root of tree.
			//These are the two leafs under this node.
			this.r=right;
			this.l=left;
		}
	}	
	
	//The treeLeaf inner class.
	public class treeLeaf
	{
		int frequency;
		char value;
		char code='1';
		
		public treeLeaf(int freq, char val)
		{
			this.frequency=freq;
			this.value=val;
		}
	}
 
	public static void main(String[] args){
		HuffmanTree tree=new HuffmanTree("susie says it is easy");
		tree.displayFreqTable();
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
		tree.fuck();
		System.out.println("-----------------------------");
		tree.displayFreqTable();
		
	}
	
}