-module(huffman).
-export([start/1]).
start(String) ->
List = split(String, []),
Sort = sort(List, []),
Tree = buildHTree(Sort),
createHCode(Tree, ""),
encode(String). % uncomment the next line to print the huffman code, don't forget ton drop the previous dot for a comma.
% io:format("~w~n", [get()]).
insertByElem([], X, Acc) ->
lists:reverse([{X, 1}|Acc]);
insertByElem([{X, Nb}|T], X, Acc) ->
lists:concat([Acc, [{X, (Nb+1)}|T]]);
insertByElem([H|T], X, Acc) ->
insertByElem(T, X, [H|Acc]).
insertByOcc(Tree, [], Acc) ->
lists:reverse([Tree|Acc]);
insertByOcc({Tree, Val}, [{X, Occs}|T], Acc) when Val < Occs ->
lists:concat([Acc, [{Tree, Val}, {X, Occs}|T]]);
insertByOcc(Tree, [H|T], Acc) ->
insertByOcc(Tree, T, [H|Acc]).
split([], List) ->
List;
split([X|Xs], List) ->
NewL = insertByElem(List, X, []),
split(Xs, NewL).
comp({_X, NbX}, {_Y, NbY}) when NbX < NbY -> inf;
comp(_X, _Y) -> else.
getMin([], Acc, Min) ->
{Acc, Min};
getMin([X|Xs], Acc, Min) ->
case comp(X, Min) of
inf -> getMin(Xs, [Min|Acc], X);
_Else -> getMin(Xs, [X|Acc], Min)
end.
sort([], Sorted) ->
lists:reverse(Sorted);
sort([H|T], Acc) ->
{List, Min} = getMin(T, [], H),
sort(List, [Min|Acc]).
buildHTree([{X, _Occs}]) ->
X;
buildHTree([{X1, Occ1}, {X2, Occ2}|Tail]) ->
NewO = Occ1 + Occ2,
LittleT = {{X1, X2}, NewO},
NewL = insertByOcc(LittleT, Tail, []),
buildHTree(NewL).
createHCode({X1, X2}, CodeS) ->
Gauche = ["0"|CodeS],
Droite = ["1"|CodeS],
createHCode(X1, Gauche),
createHCode(X2, Droite);
createHCode(Elem, CodeS) ->
Bin = lists:reverse(CodeS),
put(Elem, Bin).
encode([]) ->
io:format("~n");
encode([H|T]) ->
HCode = get(H),
io:format("~s", [HCode]),
encode(T).