function HuffSeq = huffman(Symbols,Probabilities,SymbSeq)
% Function huffman builds a variable-lenth Huffman code using the Symbols and Probabilities matrixes.
% Returns a sequenece of huffman encoded symbols after utilizating the Huffman procedure on symbol sequence SymbSeq.

global HuffCodes

HuffCodes = cell(length(Probabilities),1);
HuffSeq=[];

if length(Probabilities)>1
    s = hufftree(Probabilities);
    makecode(s,[]); 
else
    HuffCodes={'1'};
end

disp(HuffCodes);

for i=1:length(SymbSeq)
    iter2=1;
    while (SymbSeq(i)~=Symbols(iter2))
        iter2=iter2+1;   
    end
    HuffSeq=cat(2,HuffSeq,char(HuffCodes(iter2)));
end

%----------------------------------------------------------------------
function s = hufftree(p);
% Create a Huffamn source reduction tree in a Matlab cell structure
% by performing source symbol reductions until there re only two reduced
% symbols remaining

s = cell(length(p),1);

% Generate a starting tree with symbol nodes 1,2,3, ... to reference 
% the symbol probabilities
for i=1:length(p)
    s{i} = i;
end

while numel(s)>2
    [p, i] = sort(p);       % Sort the symbol probabilities
    
    p(2) = p(1) + p(2);     % Merge the 2 lowest probabilities 
    p(1) = [];              % prune the lowest one
    
    s = s(i);               % Reorder tree for new probabilities 
    s{2} = {s{1}, s{2}};     % and merge & prune its nodes
    s(1) = [];              % to match the probabilities
end


%------------------------------------------------------------------------
function makecode(sc, codeword)
% Scan the codes of a Huffman source reduction tree recursively to generate
% the indicated variable length code words

% Global variable surviving all recursive calls
global HuffCodes

if isa(sc, 'cell')                      % For cell array nodes,
    makecode(sc{1}, [codeword 0]);      % add a 0 if the first element 
    makecode(sc{2}, [codeword 1]);      % or 1 if the second element
else                                    % For leaf (numeric) nodes,
    HuffCodes{sc} = char('0' + codeword);
end