////////////////// class LZW //////////////////////////////

package bitio;

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

public class LZW
{
  private static final int LZW_GRENSE = 16;               // maks antall biter
  private static final int MAKS = (1 << LZW_GRENSE) - 1;  // maks tallkode

  private static final int NYTT_BITFORMAT = 256;          // et flagg
  private static final int FØRSTE_KODE = 257;             // første ledige kode

  public static List<Integer> komprimer(String melding)
  {
    char c = melding.charAt(0);     // første tegn i meldingen
    String s = String.valueOf(c);   // tegnstrengen med c som innhold
    int kode = c;                   // tallkoden til c
    int nestekode = 256;            // første ledige tallkode

    Map<String,Integer> ordbok = new HashMap<>();  // en ordbok
    List<Integer> resultat = new ArrayList<>();    // resultatliste

    for (int i = 1; i < melding.length(); i++)  // resten av meldingen
    {
      c = melding.charAt(i);                    // neste tegn i meldingen
      Integer ordkode = ordbok.get(s + c);       // søker etter s + c

      if (ordkode == null)                      // s + c er ikke i ordboken
      {
        ordbok.put(s + c, nestekode++);         // legger s + c i ordboken
        s = String.valueOf(c);                  // setter s = c
        resultat.add(kode);
        kode = c;                               // kode blir tallkoden til c
      }
      else                                      // s + c er i ordboken
      {
        kode = ordkode;                         // kode = ordkoden til s + c
        s = s + c;                              // setter s = s + c
      }
    }
    resultat.add(kode);                         // alle tegn er behandlet

    return resultat;
  }

  public static String dekomprimer(List<Integer> koder)
  {
    int kode = koder.get(0);                        // første tallkode er < 256
    String t;                                       // foreløpig udefinert
    String s = String.valueOf((char)kode);          // ord med ett tegn
    char c;                                         // foreløpig udefinert
    StringBuilder resultat = new StringBuilder(s);  // til å lagre resultatet
    int nestekode = 256;                            // nestekode lik 256

    Map<Integer,String> ordbok = new TreeMap<>();   // en ordbok

    for (int i = 1; i < koder.size(); i++)          // resten av tallene
    {
      kode = koder.get(i);                          // neste tall
      t = s;                                        // t settes lik s

      if (kode < nestekode)                         // kode er i ordboken
      {
        s = kode < 256 ? String.valueOf((char)kode) // ny verdi på s 
                       : ordbok.get(kode);
        c = s.charAt(0);                            // c lik første tegn i s
      }
      else                                          // kode er ikke i ordboken
      {
        c = t.charAt(0);                            // c lik første tegn i t
        s = t + c;                                  // s lik t + c
      }

      resultat.append(s);                           // lagrer s
      ordbok.put(nestekode, t + c);                 // legger inn i ordboken 
      nestekode++;                                  // øker nestekode med 1
    }

    return resultat.toString();
  }

  public static int komprimer0(InputStream inn, BitOutputStream ut)
    throws IOException
  {
    int bitformat = 9, bitGrense = 512;            // starter med 9 biter

    int c = inn.read();                            // leser inn første byte
    if (c == -1) return;                           // inn er tom
    int antallInnlesteTegn = 1;                    // første tegn

    Map<String,Integer> ordbok = new HashMap<>();  // ordboken
    String s = String.valueOf((char)c);            // må bruke char her
    int kode = c;                                  // setter kode = c
    int nesteKode = FØRSTE_KODE;                   // første ledige tallkode

    while ((c = inn.read()) != -1)                 // slutt hvis c er -1
    {
      antallInnlesteTegn++;                        // et nytt tegn
      Integer ordkode = ordbok.get(s + (char)c);   // søker etter s + c

      if (ordkode == null)                         // fant ikke s + c
      {
        while (kode >= bitGrense)                  // sjekker størrelsen
        {
          ut.writeBits(NYTT_BITFORMAT,bitformat);  // setter inn flagget
          bitformat++;                             // øker bitformat med 1
          bitGrense <<= 1;                         // dobler bitGrense
        }

        ut.writeBits(kode, bitformat);             // skriver ut koden

        if (nesteKode < MAKS)                      // sjekker størelsen
        {
          ordbok.put(s + (char)c, nesteKode);      // nytt ord i ordboken
          nesteKode++;                             // øker nesteKode med 1
        }

        s = String.valueOf((char)c);               // setter s = c
        kode = c;                                  // setter kode = c
      }
      else                                         // fant s + c i ordboken
      {
        kode = ordkode;                            // tallkoden til s + c
        s += (char)c;                              // legger c bakerst i s
      }
    }

    while (kode >= bitGrense)                      // sjekker før utskrift
    {
      ut.writeBits(NYTT_BITFORMAT,bitformat);      // setter inn flagget
      bitformat++;                                 // øker bitformat med 1
      bitGrense <<= 1;                             // dobler bitGrense
    }
    ut.writeBits(kode,bitformat);                  // skriver ut siste kode
    return antallInnlesteTegn;                     // returnerer antallet
  }

  public static void dekomprimer0(BitInputStream inn, OutputStream ut)
    throws IOException
  {
    int bitformat = 9;                             // starter med 9 biter

    int kode = inn.readBits(bitformat);            // leser først tallkode
    if (kode == -1) return;                        // inn er tom

    Map<Integer,String> ordbok = new HashMap<>();  // oppretter ordboken

    int nesteKode = FØRSTE_KODE;                   // første ledige tall

    String s  = String.valueOf((char)kode);        // første kode
    String t;                                      // hjelpevariabel
    char c;                                        // hjelpevariabel

    ut.write(kode);                                // skriver ut

    while ((kode = inn.readBits(bitformat)) != -1) // resten av kodene
    {
      while (kode == NYTT_BITFORMAT)               // skifter bitformat
      {
        bitformat++;                               // øker bitformat med 1       
        kode = inn.readBits(bitformat);            // leser neste kode
      }

      t = s;                                       // setter t = s

      if (kode < nesteKode)                        // kode er i ordboken
      {
        s = kode < 256 ? String.valueOf((char)kode) : ordbok.get(kode);
        c = s.charAt(0);                           // c = første tegn i s
      }
      else                                         // ukjent kode
      {
        c = t.charAt(0);                           // c = første tegn i t
        s = t + c;                                 // setter s = t + c
      }

      ut.write(s.getBytes());                      // skriver ut s
      ordbok.put(nesteKode++, t + c);              // nytt ord i ordboken
    }
  }

  public static int komprimer(InputStream inn, BitOutputStream ut)  // Ny versjon
  throws IOException
  {
    int bitformat = 9, bitGrense = 512;            // starter med 9 biter

    int c = inn.read();                            // leser inn første tegn
    if (c == -1) return 0;                         // inn er tom
    int antallInnlesteTegn = 1;                    // første tegn

    record Node(byte tegn, int forelder) {}        // nodedefinisjon
    Map<Node,Integer> ordbok = new HashMap<>();    // ordboken som trestruktur

    int kode = c;
    int nesteKode = FØRSTE_KODE;                   // første ledige tall

    while ((c = inn.read()) != -1)                 // slutt hvis c er -1
    {
      antallInnlesteTegn++;                        // et nytt tegn

      Node node = new Node((byte)c,kode);          // lager en node
      Integer ordkode = ordbok.get(node);          // søker etter noden

      if (ordkode == null)                         // fant ikke noden
      {
        if (kode >= bitGrense)                     // sjekker størelsen
        {
          ut.writeBits(NYTT_BITFORMAT,bitformat);  // setter inn flagget
          bitformat++;                             // øker bitformat med 1
          bitGrense *= 2;                          // dobler bitGrense
        }

        ut.writeBits(kode,bitformat);              // skriver ut koden

        if (nesteKode < MAKS)                      // sjekker størelsen
        {
          ordbok.put(node,nesteKode);              // legges i trestrukturen
          nesteKode++;                             // øker nesteKode med 1
        }
        kode = c;                                  // setter kode = c
      }
      else                                         // vi fant noden
      {
        kode = ordkode;                            // tallkoden til noden
      }
    }

    if (kode >= bitGrense)                         // siste utskrift
    {
      ut.writeBits(NYTT_BITFORMAT,bitformat);      // setter inn flagget
      bitformat++;                                 // øker bitformat med 1
    }

    ut.writeBits(kode,bitformat);                  // siste kode
    return antallInnlesteTegn;                     // returnerer
  }

  public static int komprimer(String fraUrl, String tilFil) throws IOException
  {
    InputStream fra = new BufferedInputStream((new URL(fraUrl)).openStream());
    BitOutputStream til = new BitOutputStream(new FileOutputStream(tilFil));

    int antallInnlesteTegn = LZW.komprimer(fra, til);

    fra.close(); til.close();

    return antallInnlesteTegn;
  }

  public static void dekomprimer(BitInputStream inn, OutputStream ut)  // Ny versjon
  throws IOException
  {
    int bitformat = 9;                             // starter med 9 biter
    int kode = inn.readBits(bitformat);            // første tallkode
    if (kode == -1) return;                        // inn er tom

    record Node(byte tegn, int forelder) {}        // en nodedefinisjon
    List<Node> ordbok = new ArrayList<>();         // en tabell

    // De 256 første nodene med -1 som forelder, 256 "nulles" vekk
    for (int i = 0; i < FØRSTE_KODE; i++) ordbok.add(new Node((byte)i,-1));

    Deque<Integer> stakk = new ArrayDeque<>();     // en stakk

    int forelder = 0, forrige = kode;

    int c = kode;
    ut.write(c);                                   // det første tegnet

    while ((kode = inn.readBits(bitformat)) != -1)
    {
      while (kode == NYTT_BITFORMAT)               // er det et flagg?
      {
        bitformat++;                               // øker bitlengden
        kode = inn.readBits(bitformat);            // leser med ny bitlengde
      }

      if (kode < ordbok.size()) forelder = kode;
      else
      {
        forelder = forrige;
        stakk.push(c);                             // legger på stakken
      }

      while (forelder != -1)
      {
        Node node = ordbok.get(forelder);          // henter fra ordboken
        stakk.push((int)node.tegn);                // legger på stakken
        forelder = node.forelder;                  // fortsetter oppover
      }

      c = stakk.peek();                            // tar vare på toppen

      while (!stakk.isEmpty()) ut.write(stakk.pop());

      ordbok.add(new Node((byte)c,forrige));
      forrige = kode;
    }
  }

  public static void dekomprimer(String fraUrl, String tilFil) throws IOException
  {
    BitInputStream fra = new BitInputStream((new URL(fraUrl)).openStream());
    OutputStream til = new BufferedOutputStream(new FileOutputStream(tilFil));

    dekomprimer(fra, til);

    fra.close(); til.close();
  }

} // LZW