import java.util.StringTokenizer;
import java.util.*;
public class HuffmanTree
{
	//Some class variables.
	Stack Queue=new Stack();
	Stack temp=new Stack();
	int row=0, col=0;
	treeNode root;
	
	
	public HuffmanTree(String sentence){
		
		Freq(sentence, 0);
		Queue=prioritizeQueue(Queue);
		root=buildTree(Queue);
		//System.out.print("This is the root: ");
		//root.printNode();
	} 
	
	//The treeNode innner class.
	public class treeNode
	{
		int frequency;
		String val;
		treeNode r;//child
		treeNode l;//child
		
		public treeNode(String value, int freq, treeNode right, treeNode left)
		{
			this.frequency=freq;
			this.val=value;
			this.r=right;
			this.l=left;
		}
		
		public void printNode(){
			System.out.println("["+val+"|"+frequency+"]");
		}
		
	}
	
	/*****************************************************
	 Name: Freq()
	 Parameters: String, int
	 Declared variables:char current, bool doIt, int freqCount
	 	char fc.
	 Return value: void
	 Purpose: Takes a String argument, calculates the frequencies
	 	of the characters in the String, creates nodes for them
	 	and inserts them into a Queue.
	 
	 Algorithm: (assumes the user puts all the characters in the same case)
	 	Freq(entireString, starting indx 'initialy starts 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. 
	 	
	 		create a new treeNode
	 		push it onto the Queue.	
	 		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 Freq(String s, int stIndx){
		char current;
		boolean doIt=true;
		treeNode node1;
		
		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.
		}
		
		String x = String.valueOf(current);//Converts char-to-String.
		node1=new treeNode(x,freqCount, null, null); 
		Queue.push(node1);
		
		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
			Freq(s, stIndx);//Recurse.
	} 
	
	public void printQueue(Stack q){
		Iterator i=q.iterator();
		
		while(i.hasNext()){
			((treeNode)i.next()).printNode();
		}
	}
	
	/****************************************************
	 Name: prioritizeQueue()
	 Parameters: Stack queue
	 Declared variables:
	 Return value:void
	 Purpose: Takes a queue argument orders that queue and 
	 	sticks it back into the queue in priority order.
	 
	 Algorithm:
	 	prioritizeQueue(Stack q)
	 		if(there is nothing in the Queue)
	 			return.	
	 		
	 		new temporary Stack.
	 		new iterator.
	 		while (Queue has items in it)
	 			find the highest priority node in the Queue
	 				currentNode =highest priority node.
	 		end while
	 		push current node onto the temp stack
	 		remove it from the Queue.
	 	recurse.
	*****************************************************/
	public Stack prioritizeQueue(Stack q){
		
		Iterator i=q.iterator();
		int currentHigh;
		treeNode currentNode, finalNode;
		
		currentNode=(treeNode)i.next();//This is the current node to compare to the currentHigh.
		currentHigh= currentNode.frequency;//This is just the int frequency.
		
		finalNode=currentNode;
		while(i.hasNext()){
			currentNode=(treeNode)i.next();
			if(currentHigh < currentNode.frequency){
				currentHigh=currentNode.frequency;
				finalNode=currentNode;
			}	
		}
 
		temp.push(finalNode);
		q.remove(finalNode);
		
		if(q.isEmpty()){//If I have taken the last thing out.
			q=temp;
			temp=null;
			return q;//Quit the function.
		}
		else{
			
		    return prioritizeQueue(q);
		}
	}
	
	/****************************************************
	 Name: buildTree()
	 Parameters: Stack q
	 Declared variables:
	 Return value:
	 Purpose: To take a Queue in and create a binary tree
	 	from the nodes in the Queue.
	 
	  Algorithm:
	 	buildTree()
	 		get two nodes out of the Queue
	 		add the frequencies and create a parent node. (first from Q is right child)
	 		put new parent node onto the Queue.
	 		
	 		recurse.
	 	end.	
	*****************************************************/
	public treeNode buildTree(Stack q){
		treeNode n1;
		treeNode n2;
		treeNode newParent;
		
		
		if(q.size() == 1){// stop when only one item in tree
			return (treeNode)q.pop();	
		}
		
		n1=(treeNode)Queue.pop();//right node
		System.out.println("node1 pop: ");n1.printNode();
		n2=(treeNode)Queue.pop();//left node
		System.out.println("node2 pop: ");n2.printNode();
		//Creating a parent node, from the two nodes I popped.
		newParent=new treeNode("*", n1.frequency+n2.frequency, n1, n2);
		q.push(newParent);
		q=prioritizeQueue(q);
		return buildTree(q);//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: 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;
   	}
 
	public static void main(String[] args){
		HuffmanTree tree=new HuffmanTree("susie says it is easy");
	}
	
}

q=(Stack)temp.clone();
temp.clear();