import java.util.Scanner;

public class HuffmanCode {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Podaj tekst: ");
    String text = input.nextLine();
    
    int[] counts = getCharacterFrequency(text); // Zliczanie wystąpień

    System.out.printf("%-15s%-15s%-15s%-15s\n",
      "Kod ASCII", "Znak", "Wystąpienia", "Kod");
    
    Tree tree = getHuffmanTree(counts); // Tworzenie drzewa Huffmana
    String[] codes = getCode(tree.root); // Wyznaczanie kodów
        
    for (int i = 0; i < codes.length; i++)
      if (counts[i] != 0) // Jeśli counts[i] to 0, (char)i nie występuje w tekście
        System.out.printf("%-15d%-15s%-15d%-15s\n", 
          i, (char)i + "", counts[i], codes[i]);
  }
  
  /** Wyznaczanie kodów Huffmana dla znaków.
    * Ta metoda jest wywoływana raz po utworzeniu drzewa Huffmana
   */
  public static String[] getCode(Tree.Node root) {
    if (root == null) return null;    
    String[] codes = new String[128];
    assignCode(root, codes);
    return codes;
  }
  
  /* Rekurencyjne pobieranie kodów dla liści */
  private static void assignCode(Tree.Node root, String[] codes) {
    if (root.left != null) {
      root.left.code = root.code + "0";
      assignCode(root.left, codes);
      
      root.right.code = root.code + "1";
      assignCode(root.right, codes);
    }
    else {
      codes[(int)root.element] = root.code;
    }
  }
  
  /** Tworzenie drzewa Huffmana na podstawie kodów */
  public static Tree getHuffmanTree(int[] counts) {
    // Tworzenie kopca do przechowywania drzew
    Heap<Tree> heap = new Heap<>(); // Zdefiniowana na listingu 23.9
    for (int i = 0; i < counts.length; i++) {
      if (counts[i] > 0)
        heap.add(new Tree(counts[i], (char)i)); // Drzewo w postaci liścia
    }
    
    while (heap.getSize() > 1) { 
      Tree t1 = heap.remove(); // Usuwanie drzewa o najmniejszej wadze
      Tree t2 = heap.remove(); // Usuwanie drzewa o następnej najmniejszej wadze
      heap.add(new Tree(t1, t2)); // Łączenie dwóch drzew
    }

    return heap.remove(); // Drzewo jest gotowe
  }
  
  /** Wyznaczanie liczby wystąpień znaków */
  public static int[] getCharacterFrequency(String text) {
    int[] counts = new int[128]; // 128 znaków ASCII
    
    for (int i = 0; i < text.length(); i++)
      counts[(int)text.charAt(i)]++; // Zliczanie znaków w tekście
    
    return counts;
  }
  
  /** Definicja drzewa Huffmana */
  public static class Tree implements Comparable<Tree> {
    Node root; // Korzeń drzewa

    /** Tworzenie drzewa z dwoma poddrzewami */
    public Tree(Tree t1, Tree t2) {
      root = new Node();
      root.left = t1.root;
      root.right = t2.root;
      root.weight = t1.root.weight + t2.root.weight;
    }
    
    /** Tworzenie drzewa zawierającego liść */
    public Tree(int weight, char element) {
      root = new Node(weight, element);
    }
    
    @Override /** Porównywanie drzew na podstawie wag */
    public int compareTo(Tree t) {
      if (root.weight < t.root.weight) // Celowe odwrócenie kolejności
        return 1;
      else if (root.weight == t.root.weight)
        return 0;
      else
        return -1;
    }

    public class Node {
      char element; // Przechowuje znak zapisany w liściu
      int weight; // Waga poddrzewa, którego korzeniem jest dany węzeł
      Node left; // Wskaźnik do lewego poddrzewa
      Node right; // Wskaźnik do prawego poddrzewa
      String code = ""; // Kod danego węzła (wyznaczany od korzenia)

      /** Tworzy pusty węzeł */
      public Node() {
      }
      
      /** Tworzy węzeł z podaną wagą i określonym znakiem */
      public Node(int weight, char element) {
        this.weight = weight;
        this.element = element;
      }
    }
  }  
}