/* 

  LZW Compression (Rosetta Code) in Picat.

  http://rosettacode.org/wiki/LZW_compression
  """
  The Lempel-Ziv-Welch (LZW) algorithm provides lossless data compression. 
  You can read a complete description of it in the Wikipedia article 
  [http://en.wikipedia.org/wiki/Lempel-Ziv-Welch ] on the subject. 
  It was patented, but it fell in the public domain in 2004. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.

% inspired by the Python solution

go =>

  S = "TOBEORNOTTOBEORTOBEORNOT",
  % S = "This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/",
  % S = read_file_chars("lzw_compression.pi"),
  println(s=S),
  println(len=S.length),

  Compressed = compress(S),
  println(compressed=Compressed),
  println(len=Compressed.length),
  
  Uncompressed = uncompress(Compressed),
  println(uncompressed=Uncompressed),
  
  printf("compressed to %3.3f%%\n", 100*(Compressed.length / S.length)),

  if S = Uncompressed then
    println("Same!")
  else
    println("Error: S != Uncompressed!"),
    printf("S.length: %d  Uncompressed.length: %d\n", S.length, Uncompressed.length),
    edit(S,Uncompressed,Distance,Diffs),
    println(distance=Distance),
    println(diffs=Diffs)
  end,
  nl.

compress(Uncompressed) = Compressed =>
  DictSize = 256,
  % Note: chr(I) converts I to ASCII, 
  % but it don't handle chr(0) 
  Dict = new_map([C=C : I in 1..DictSize-1, C=chr(I).to_string()]),
  W = "",
  Result = [],
  foreach(C in Uncompressed) 
    C := C.to_string(),
    WC = W ++ C,
    if Dict.has_key(WC) then
      W := WC
    else 
      Result := Result ++ [Dict.get(W)],
      Dict.put(WC, DictSize),
      DictSize := DictSize + 1,
      W := C
    end
  end,

  if W.length > 0 then
     Result := Result ++ [Dict.get(W)]
  end,
  
  Compressed = Result.


uncompress(Compressed) = Uncompressed => 
  DictSize = 256,
  Dict = new_map([ C=C : I in 1..DictSize-1, C=chr(I).to_string()]),
  W = Compressed.first(),
  Compressed := Compressed.tail(),
  Result = W,

  Entry = "",
  foreach(K in Compressed) 
    if Dict.has_key(K) then
      Entry := Dict.get(K)
    elseif K == DictSize then
      Entry := W ++ W[1].to_string()
    else
      printf("Bad compressed K: %w\n", K)
    end,
    Result := Result ++ Entry,   
    Dict.put(DictSize,(W ++ Entry[1].to_string())),
    DictSize := DictSize + 1,

    W := Entry

  end,
  Uncompressed = Result.flatten().


% from exs.pi
% computing the minimal editing distance of two given lists
table(+,+,min,-)
edit([],[],D,Diffs) => D=0, Diffs=[].
edit([X|Xs],[X|Ys],D,Diffs) =>   % copy
    edit(Xs,Ys,D,Diffs).
edit(Xs,[Y|Ys],D,Diffs) ?=>      % insert
    edit(Xs,Ys,D1,Diffs1),
    D=D1+1,
    Diffs = [insert=Y,xPos=Xs.length,yPos=Ys.length|Diffs1].
edit([X|Xs],Ys,D,Diffs) =>       % delete
    edit(Xs,Ys,D1,Diffs1),
    D=D1+1,
    Diffs = [[delete=X,xPos=Xs.length,yPos=Ys.length]|Diffs1].