/* 

  Huffman coding in Picat.

  From Rosetta Code
  http://rosettacode.org/wiki/Huffman_coding
  """
  Using the characters and their frequency from the string "this is an example 
  for huffman encoding", create a program to generate a Huffman encoding for each character as a table. 
  """

  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.

go => 
  huffman.

% Translated from 
% http://rosettacode.org/wiki/Huffman_coding#Prolog
huffman =>
   LA = "this is an example for huffman encoding",
   LS=sort(LA),
   packList(LS,PL),
   PLS=sort(PL).remove_dups(),
   build_tree(PLS, A),
   coding(A, [], C),
   SC=sort(C).remove_dups(),
   println("Symbol\tWeight\tCode"),
   foreach(SS in SC) print_code(SS) end.
 
build_tree([[V1|R1], [V2|R2]|T], AF) => 
   V = V1 + V2, 
   A = [V, [V1|R1], [V2|R2]],
   (   T=[] -> AF=A ;  NT=sort([A|T]), build_tree(NT, AF) ).
 
coding([_A,FG,FD], Code, CF) =>
   (   is_node(FG) ->  coding(FG, [0 | Code], C1)
          ;  leaf_coding(FG, [0 | Code], C1) ),
   (   is_node(FD) ->  coding(FD, [1 | Code], C2)
          ;  leaf_coding(FD, [1 | Code], C2) ),
   append(C1, C2, CF).
 
leaf_coding(FGFD, Code, CF) =>
        FGFD=[FG,FD],
   CodeR = reverse(Code),
   CF = [[FG, FD, CodeR]] .
 
is_node([_V, _FG, _FD]) => true.
 
print_code([N, Car, Code]) =>
   printf("%w:\t%w\t%8s", Car, N,""),
   foreach(V in Code) write(V) end,
   nl.
 
packList([], []) ?=> true.
packList([X],XX ) ?=> XX=[[1,X]].
packList([X|Rest], XRunPacked)?=>
   XRunPacked = [XRun|Packed],
   run(X, Rest, XRun, RRest),
   packList(RRest, Packed).
 
run(V, [], VV, [])  ?=> VV=[1,V].
run(V, VLRest, N1V, RRest) ?=>
   VLRest = [V|LRest],
   N1V=[N1,V],
   run(V, LRest, [N, V], RRest),
   N1 = N + 1.
run(V, OtherRRest, VV, OtherRRest2) =>
   OtherRRest = [Other|RRest],
   VV=[1,V],
   OtherRRest2 = [Other|RRest],
   different_terms(V, Other).