////////////////// class AdHuffman //////////////////////////////
package bitio;

import java.io.*;
import java.net.URL;
import java.util.Arrays;

public class AdHuffman     // adaptiv Huffman
{
  private static final int EOC = 256;   // End of Compression

  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 final static class Node          // en indre nodeklasse
  {
    private int frekvens;                  // nodens frekvens
    private int c;                         // nodens tegn
    private int nummer;                    // nodens nummer
    private Node forelder;                 // peker til forelder
    private Node venstre = null;           // peker til venstre barn
    private Node høyre = null;             // peker til høyre barn

    private Node(int frekvens, int c, int nummer, Node forelder)
    {
      this.frekvens = frekvens;
      this.c = c;
      this.nummer = nummer;
      this.forelder = forelder;
    }

    @Override
    public String toString()
    {
      String s = "(" + nummer + "," + frekvens;
      if (c >= 0)  // bladnoder har c = -1
      {
        if (c < 32) s += "," + ascii[32];
        else s += "," + (char)c;
      }
      return s + ")";
    }

  }  // Node

  private Node rot, NULL;         // pekere til rotnoden og nullnoden
  private Node[] noder;           // nodetabell for nodene
  private Node[] tegn;            // nodetabell for tegn
  int antall = 0;                 // antall noder i treet

  public AdHuffman()              // kontruktør - lager et tomt tre
  {
    rot = NULL = new Node(0, -1, 0, null);   // rotnoden er lik nullnoden
    noder = new Node[2 * 8 + 1];             // plass til 17 noder (8 tegn)
    noder[antall++] = rot;                   // roten legges i posisjon 0
    tegn = new Node[257];                    // alle ascii-verdier + EOC
  }

  private static void bytt(Node p, Node q, Node[] noder)
  {
    Node f = p.forelder, g = q.forelder;  // finner foreldrene

    if (p == f.venstre) f.venstre = q;    // f får q som barn
    else f.høyre = q;

    if (q == g.høyre) g.høyre = p;        // g får p som barn
    else g.venstre = p;

    p.forelder = g;                // p får g som forelder
    q.forelder = f;                // q får f som forelder

    noder[q.nummer] = p;           // p flyttes til plassen til q
    noder[p.nummer] = q;           // q flyttes til plasen til p

    int nummer = p.nummer;         // p og q bytter nummer
    p.nummer = q.nummer;
    q.nummer = nummer;
  }

  private Node nyttTegn(int c)                    // et nytt tegn
  {
    if (antall == noder.length)                   // er tabellen full?
    {
      noder = Arrays.copyOf(noder,2*antall - 1);  // dobler
    }

    Node p = NULL;                          // p settes lik nullnoden

    p.høyre = new Node(1,c,antall,p);       // ny node som høyre barn
    tegn[c] = p.høyre;                      // noden inn i tegn-tabellen
    noder[antall++] = p.høyre;              // noden inn i nodetabellen

    p.venstre = new Node(0,-1,antall,p);    // ny node som venstre barn
    noder[antall++] = p.venstre;            // noden inn i nodetabellen

    NULL = p.venstre;                       // ny nullnode

    if (p == rot) return p;                 // returnerer roten

    p.frekvens = 1;                         // frekvens lik 1
    return p.forelder;
  }

  private void oppdater(int c)
  {
    Node p = tegn[c];                  // slår opp i tegntabellen
    if (p == null) p = nyttTegn(c);    // er det et nytt tegn?

    while (p != rot)                   // går fra p og opp mot roten
    {
      // sammenligner p med noden rett foran
      if (noder[p.nummer - 1].frekvens == p.frekvens)
      {
        int k = p.nummer - 1;          // leter videre mot venstre
        while (noder[k-1].frekvens == p.frekvens) k--;

        Node q = noder[k];                      // q er minst
        if (q != p.forelder) bytt(p,q,noder);   // p og q bytter plass
      }

      p.frekvens++;                             // øker frekvensen
      p = p.forelder;                           // går til forelderen
    }
  }

  public static void skrivTre(String melding)
  {
    AdHuffman h = new AdHuffman();             // lager et tomt tre

    char[] tegn = melding.toCharArray();       // gjør om til en tegntabell
    for (char c : tegn) h.oppdater(c);         // bygger opp treet

    for (int i = 0; i < h.antall; i++)         // skriver ut nodene
      System.out.print(h.noder[i] + " ");
  }

} // class AdHuffman