////// class Huffman ////////////////////

package bitio;

import java.io.*;                               // filbehandling
import java.net.URL;                            // internett
import hjelpeklasser.*;                         // diverse metoder

public class Huffman                            // klasse for komprimering
{
  public static String[] ascii =
  {"NUL","SOH","STX","ETX","EOT","ENQ","ACK","BEL","BS","HT","LF",
   "VT","FF","CR","SO","SI","DLE","DC1","DC2","DC3","DC4","NAK",
   "SYN","ETB","CAN","EM","SUB","ESC","FS","GS","RS","US"};

  private static class Node                     // en basisklasse
  {
    private int frekvens;                       // nodens frekvens
    private Node venstre;                       // pekere til venstre barn
    private Node høyre;                         // pekere til høyre barn

    private Node() {}                           // standardkonstruktør

    private Node(int frekvens, Node v, Node h)  // konstruktør
    {
      this.frekvens = frekvens;
      venstre = v;
      høyre = h;
    }
  }  // class Node

  private static class BladNode extends Node    // en subklasse
  {
    private final char tegn;                    // bladnodens tegn

    private BladNode(char tegn, int frekvens)   // konstruktør
    {
      super(frekvens, null, null);     // basisklassens konstruktør
      this.tegn = tegn;
    }

  }  // class BladNode

  private static Node byggHuffmanTre(int[] frekvens)
  {
    PrioritetsKø<Node> kø =         // bruker et lamda-uttrykk
      new HeapPrioritetsKø<>((p,q) -> p.frekvens - q.frekvens);

    for (int i = 0; i < frekvens.length; i++)
      if (frekvens[i] > 0)          // dette tegnet skal være med
        kø.leggInn(new BladNode((char)i, frekvens[i]));

    if (kø.antall() < 2)            // må ha minst to noder
      throw new IllegalArgumentException("Det er for få tegn!");

    while (kø.antall() > 1)
    {
      Node v = kø.taUt();                  // blir venstre barn
      Node h = kø.taUt();                  // blir høyre barn
      int sum = v.frekvens + h.frekvens;   // summen av frekvensene

      kø.leggInn(new Node(sum, v, h));     // legger noden inn i køen
    }

    return kø.taUt();                      // roten i treet
  }

  private static void finnBitkoder(Node p, String kode, String[] koder)
  {
    if (p instanceof BladNode) koder[((BladNode)p).tegn] = kode;
    else
    {
      finnBitkoder(p.venstre, kode + '0', koder);  // 0 til venstre
      finnBitkoder(p.høyre, kode + '1', koder);    // 1 til høyre
    }
  }

  public static String[] stringBitkoder(int[] frekvens)
  {
    Node rot = byggHuffmanTre(frekvens);               // bygger treet

    String[] bitkoder = new String[frekvens.length];   // en kodetabell
    finnBitkoder(rot,"",bitkoder);                     // lager bitkodene

    return bitkoder;    // returnerer tabellen
  }

  public static int[] stringFrekvens(String tekst)
  {
    int[] frekvens = new int[256];

    for (int i = 0; i < tekst.length(); i++)
      frekvens[tekst.charAt(i)]++;

    return frekvens;
  }

  public static int[] streamFrekvens(InputStream inn) throws IOException
  {
    int[] frekvens = new int[256];

    int tegn;
    while ((tegn = inn.read()) != -1) frekvens[tegn]++;
    inn.close();

    return frekvens;
  }

} // class Huffman