import java.io.*;
   import java.util.*;
   public class HuffmanCoding_3_Lay{
      private static HashMap<String, Integer> frequencyMap = new HashMap<String, Integer>();
      private static TreeMap<String, String> huffMap = new TreeMap<String, String>();
      private static PriorityQueue<HuffNode> nodeQueue = new PriorityQueue<HuffNode>();
      private static HuffNode huffRoot = null;
      public static void main(String[] args) throws IOException{
         Scanner sc = new Scanner(System.in);
         System.out.println("Type in something.");
         String message = sc.nextLine();
         File schemeFile = new File("scheme." + message.toLowerCase()+".txt");
         if(!schemeFile.exists())
            schemeFile.createNewFile();
         System.setOut(new PrintStream(new FileOutputStream(schemeFile)));
         huffRoot = makeTree(makeQueue(calcFrequency(message)));
         printScheme(huffRoot, message);
         File messageFile = new File("message."+message.toLowerCase()+".txt");
         if(!messageFile.exists())
            messageFile.createNewFile();
         System.setOut(new PrintStream(new FileOutputStream(messageFile)));
         System.out.println(huffmanCode(message));
      }
      public static void printScheme(HuffNode root, String s){
         HuffNode temp = root;
         printHelper(temp, huffMap, "");
         for(String str : huffMap.keySet())
            System.out.println(str + ":" + huffMap.get(str));
      }
      private static void printHelper(HuffNode temp, TreeMap<String, String> map, String s){
         if(temp == null)
            return;
         else{
            if(!temp.getLetter().equals("*"))
               map.put(temp.getLetter(), s);
            printHelper(temp.getLeft(), map, s+"0");
            printHelper(temp.getRight(), map, s+"1");
         }
      }
      public static HashMap<String, Integer> calcFrequency(String s){
         String letter;
         for(int x = 0; x < s.length(); x++){
            letter = s.substring(x,x+1);
            if(!frequencyMap.containsKey(letter))
               frequencyMap.put(letter, 1);
            else
               frequencyMap.put(letter, frequencyMap.get(letter)+1);
         }
         return frequencyMap;
      }
      public static PriorityQueue<HuffNode> makeQueue(HashMap<String, Integer> map){
         Iterator<String> itr = map.keySet().iterator();
         String current = "";
         while(itr.hasNext()){
            current = itr.next();
            nodeQueue.add(new HuffNode(current, map.get(current), null, null));
         }
         return nodeQueue;
      }
      public static HuffNode makeTree(PriorityQueue<HuffNode> q){
         HuffNode temp1;
         HuffNode temp2;
         int sum;
         while(q.size() > 1){
            temp1 = q.remove();
            temp2 = q.remove();
            int sums = temp1.getFrequency() + temp2.getFrequency();
            q.add(new HuffNode("*", sums, temp1, temp2));
         }
         huffRoot = q.remove();
         return huffRoot;
      }
      public static String huffmanCode(String s){
         String str = "";
         for(int x = 0; x < s.length(); x++)
            str += huffMap.get(s.substring(x, x+1));
         return str;
      }
      static class HuffNode implements Comparable<HuffNode>{
         private int myFrequency;
         private HuffNode myLeft;
         private HuffNode myRight;
         private String myLetter;
         public HuffNode(String letter, int frequency, HuffNode left, HuffNode right){
            myFrequency = frequency;
            myLeft = left;
            myRight = right;
            myLetter = letter;
         }
         public int getFrequency(){
            return myFrequency;
         }
         public HuffNode getLeft(){
            return myLeft;
         }
         public HuffNode getRight(){
            return myRight;
         }
         public String getLetter(){
            return myLetter;
         }
         public void setFrequency(int frequency){
            myFrequency = frequency;
         }
         public void setLeft(HuffNode left){
            myLeft = left;
         }
         public void setRight(HuffNode right){
            myRight = right;
         }
         public void setLetter(String letter){
            myLetter = letter;
         }
         public int compareTo(HuffNode h){
            if(myFrequency > h.getFrequency())
               return 1;
            if(myFrequency < h.getFrequency())
               return -1;
            else
               return 0;
         }
      }
   }