//Huffman.java    
//package huffman.xmu;    
import java.io.*;
import java.util.LinkedHashMap;    
import java.util.ArrayList;    
import java.util.Set;    
import java.util.Iterator;    
public class HuffmanDecoder 
{    
   
  public HuffmanDecoder(LinkedHashMap<Character,Integer> map){    
     
  charTable = map;    
  charset = map.keySet();    
  creatHuffmanTree();    
  creatHuffmanCode();    
      
      
 }    
     
     
 //encode the input string    
 public String enCodeString(String inString){   
      
   StringBuffer temp = new StringBuffer();    
   for(int i=0;i<inString.length();i++){    
         
     int ch = inString.charAt(i);    
     int j=1;    
    for( ;huffmanTree.get(j).charTag!=ch&&j<charset.size()+1;j++){    
        
    }    
    if(j<=charset.size()){    
         
      temp.append(huffmanCode.get(j));    
    } else {    
        
     temp.append(ch);    
    }    
        
   }    
       
   return temp.toString();    
       
       
 }    
     
 //decode the string    
 public String deCodeString(String inString){    
     
   StringBuffer temp = new StringBuffer();    
   int root = charset.size()*2-1;    
   for(int i=0;i<inString.length();i++){    
    char ch=inString.charAt(i);    
        
    if(ch=='0'){    
        
     root=huffmanTree.get(root).lChild;    
    }else if(ch=='1'){    
        
     root=huffmanTree.get(root).rChild;    
    }else {    
        
     temp.append(ch);    
    }    
        
    if(root<=charset.size()){    
        
     temp.append(huffmanTree.get(root).charTag);    
     root=charset.size()*2-1;    
    }    
       
   }    
   return temp.toString();    
     
 }    
     
     
 //creat the huffman tree    
 private void creatHuffmanTree(){    
       
   initTree();    
   int min_child1;    
   int min_child2;    
       
       
   for(int i=charset.size()+1;i<2*charset.size();i++){    
         
     min_child1=0;    
     min_child2=0;    
         
     for(int j=1;j<i;j++){    
           
      
      if(huffmanTree.get(j).parent==0){    
          
       if(huffmanTree.get(j).weight<huffmanTree.get(min_child1).weight||    
          huffmanTree.get(j).weight<huffmanTree.get(min_child2).weight ) {    
             
         if (huffmanTree.get(min_child1).weight < huffmanTree.get(min_child2).weight) {    
                min_child2 = j;    
            }  else {    
                min_child1= j;    
            }                          
          }    
      }    
     }    
         
         
     huffmanTree.get(min_child1).parent=i;    
     huffmanTree.get(min_child2).parent=i;    
         
     if(min_child1<min_child2){    
       huffmanTree.get(i).lChild=min_child1;    
       huffmanTree.get(i).rChild=min_child2;    
     } else{    
       huffmanTree.get(i).rChild=min_child1;    
       huffmanTree.get(i).lChild=min_child2;    
     }    
         
     huffmanTree.get(i).weight=huffmanTree.get(i).weight+huffmanTree.get(i).weight;    
         
        
   }    
     
 }    
     
 private void creatHuffmanCode(){    
      
  huffmanCode = new ArrayList<String>(charset.size()+1);    
  huffmanCode.add(0,null);    
  char [] tempChars = new char[charset.size()+1];     
      
  for(int i=1;i<charset.size()+1;i++){    
       
   int startIndex=charset.size();    
   int parent = huffmanTree.get(i).parent;    
   int ch=i;    
   while(parent!=0){    
       
    if(huffmanTree.get(parent).lChild== ch){    
        
     tempChars[startIndex]='0';    
       
         
    }else {    
        
     tempChars[startIndex]='1';    
       
    }     
        
    startIndex--;    
    ch=parent;    
    parent=huffmanTree.get(parent).parent;    
         
          
   }    
       
   //System.out.println(String.valueOf(tempChars,startIndex+1,charset.size()-startIndex));    
   huffmanCode.add(i, String.valueOf(tempChars,startIndex+1,charset.size()-startIndex));    
       
       
  }//end for    
      
     
      
 }//end method    
   
     
 private void initTree(){    
       
   huffmanTree = new ArrayList<Node>();    
       
   Iterator<Character>  charIter = charset.iterator();    
       
   int i=1;    
       
       
   huffmanTree.add(0,new Node((char) 0, Integer.MAX_VALUE, 0, 0, 0));    
  while(charIter.hasNext()){    
        
    Character ch=charIter.next();    
   huffmanTree.add(i,new Node(ch,charTable.get(ch),0,0,0));    
       
      
   i++;    
      
  }    
      
      
  for(int j=charset.size()+1;j<2*charset.size();j++){    
      
   huffmanTree.add(j,new Node((char)0,0,0,0,0));    
  }    
      
      
 }    
     
 //character table with the frequency of each character    
 private LinkedHashMap<Character,Integer>  charTable;    
     
 private Set<Character >  charset;    
     
 //store the huffman tree with the ArrayList    
 private ArrayList<Node> huffmanTree ;    
     
 //store the huffman code with the ArrayList    
 private ArrayList<String> huffmanCode;    
     
     
 class Node{    
     
  char charTag;    
  int weight;    
  int parent;    
  int lChild;    
  int rChild;    
      
  public Node(char c,int w, int p,int l, int r){    
      
   charTag = c;    
   weight = w;    
   lChild = l;    
   rChild = r;    
  }    
      
 }//end Node    
     
     
     
 public static void main(String [] args)  throws Exception
 {    
     
  LinkedHashMap<Character,Integer> hasmap = new LinkedHashMap<Character,Integer>();    
  hasmap.put('a',509); 
  hasmap.put('A',5); 
  hasmap.put('b',90);  
  hasmap.put('B',5);   
  hasmap.put('c',187);  
  hasmap.put('C',11); 
  hasmap.put('d',259);  
  hasmap.put('D',5); 
  hasmap.put('e',897);  
  hasmap.put('E',1); 
  hasmap.put('f',173);  
  hasmap.put('F',8); 
  hasmap.put('g',128);  
  hasmap.put('G',8); 
  hasmap.put('h',345);  
  hasmap.put('H',20); 
  hasmap.put('i',470);  
  hasmap.put('I',7); 
  hasmap.put('j',15);  
  hasmap.put('J',3); 
  hasmap.put('k',15);  
  hasmap.put('K',1); 
  hasmap.put('l',239);  
  hasmap.put('L',1); 
  hasmap.put('m',146);  
  hasmap.put('M',4); 
  hasmap.put('n',510);  
  hasmap.put('N',9); 
  hasmap.put('o',527);  
  hasmap.put('O',2); 
  hasmap.put('p',137);  
  hasmap.put('P',5); 
  hasmap.put('q',5);  
  hasmap.put('Q',0); 
  hasmap.put('r',443);  
  hasmap.put('R',3); 
  hasmap.put('s',486);  
  hasmap.put('S',13); 
  hasmap.put('t',653);  
  hasmap.put('T',7); 
  hasmap.put('u',213);  
  hasmap.put('U',3); 
  hasmap.put('v',77);  
  hasmap.put('V',2); 
  hasmap.put('w',97);  
  hasmap.put('W',8); 
  hasmap.put('x',9);  
  hasmap.put('X',0); 
  hasmap.put('y',88);  
  hasmap.put('Y',2); 
  hasmap.put('z',4);  
  hasmap.put('Z',0); 

  
  char Comma=(char)44;    
  hasmap.put(Comma,121); 
  
  char FullStop=(char)46;
  hasmap.put(FullStop,40);
  
  char Colonis=(char)58;
  hasmap.put(Colonis,8);
 
  char Semicolon=(char)59;
  hasmap.put(Semicolon,9); 
  
  char Space=(char)32;
  hasmap.put(Space,1390);
  
  char LeftParenthesis=(char)40;
  hasmap.put(LeftParenthesis,1);
  
  char RightParenthesis=(char)41;
  hasmap.put(RightParenthesis,1); 
  
  char SingleQuotes=(char)39;
  hasmap.put(SingleQuotes,1);
  
  char LeftSquareBrackets=(char)91; 
  hasmap.put(LeftSquareBrackets,1);
  
  char RightSquareBrackets=(char)93; 
  hasmap.put(RightSquareBrackets,1);
   
  char dh=(char)45; 
  hasmap.put(dh,1);   
  
  char Enter=(char)13; 
  hasmap.put(Enter,30);
 
  char UK=(char)10; 
  hasmap.put(UK,30); 
       			
  //String str="dasdsdad";
						BufferedReader re=new BufferedReader(new FileReader("DecOfInd.huf"));   
						StringBuffer buffer=new StringBuffer();   
 					  String line;   
  					while ((line=re.readLine())!=null)   
  					{   
         		buffer.append(line); 
         		  
        	  buffer.append("\r");
        	  buffer.append("\n");   
            }   
  re.close();   
  String last=buffer.toString();
  

  HuffmanDecoder huffman = new HuffmanDecoder(hasmap);    
  String temp = huffman.deCodeString(last);    
  

  
   FileOutputStream outFile=null;
	 outFile=new FileOutputStream("DecOfInd-1.txt");
   outFile.write(temp.getBytes("US-ASCII"));
   outFile.close();
  
  /*char[] a=new char[temp.length()];
  for(int cd=0;cd<temp.length();cd++)
  {
  			a[cd]=temp.charAt(cd);
  }  
  for(int cd=0;cd<temp.length();cd++)
  {
  			if(a[cd]==(char)10)
  }*/
  
  
	 /*FileOutputStream outFile=null;
	 outFile=new FileOutputStream("DecOfInd-1.txt");
   outFile.write(temp.getBytes());*/
   
   /*FileWriter te=new FileWriter("ss.txt");
   te.write(a);
   te.close();*/
   
 }    
     
}