go =>
  huffman("this is an example for huffman encoding").

huffman(LA) :-
   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([FG,FD], Code, CF) :-
   CodeR = reverse(Code),
   CF = [[FG, FD, CodeR]] .

is_node([_V, _FG, _FD]).

print_code([N, Car, Code]) :-
   printf("%w:\t%w\t", Car, N),
   foreach(V in Code) print(V) end,
   nl.

packList([], []).
packList([X],[[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, [V|LRest], [N1,V], RRest) :-
   run(V, LRest, [N, V], RRest),
   N1 = N + 1.
run(V, [Other|RRest], [1,V], [Other|RRest]) :-
   different_terms(V, Other).