function table=huff_tbl(fre)
% Usage: table=huff_tbl(fre)
% generating huffman table to be used by huffman.m
% Using tree search method
%
% fre: p x 1 vector, consists of frequency counts of each 
%    symbol.  sum(fre) = 1. 
%
% ptr: a p by 3 pointer matrix.
%  In ptr, postive integers (1 to p) are leaf nodes, each corresponds
%  to the original code words.  Negative 
%  integers are parent nodes of a tree with -p being the root node.

% table: p by dmax+1 matrix. First column consists of length of code
%    2nd column and on is the actual code (by row)
%
% (c) Copyright 1996-7 by Yu Hen Hu
% Last revision: 2/7/96
% Comment added: 11/11/97
%

% Initiation
ptr=[];  % pointer matrix
p= length(fre); 
tmp=[fre [1:p]']; % fre must be column vector

% Create the tree represented by the matrix ptr
% each alphabet is given a positive integer from 1 to p
% after combining the code word probability of an alphabet,
% a negative integer, whose absolute value represents the level
% of the tree is used as the symbol of the newly combined node
% for example, if five code words with their code word prob. are
%   1/4   1/4    1/5    .15   .15
%    1     2      3      4     5
% the transpose of above table is called the tmp matrix.
% First, tmp matrix will be sorted so that code word prob. is 
% in ascending order.  Then,
% node 4 and 5 will be combined, and a new node -1 will be
% created which has a code word probability .15 + .15 = .3
% In the first row of ptr, it will be recorded as  -1  4   5
% Now tmp' =
%  .3  1/4  1/4  1/5
%  -1   1    2    3
% After sorting, it is called sf.  sf' =
%  1/5 1/4  1/4  .3
%   3   1    2   -1
% the parent node of 3 and 1 will be denoted by -2. Hence the 2nd
% row of ptr is -2  3  1  the updated tmp, and then after sorting, sf' =
%  1/4  .3   .45
%   2   -1    -2
% this leads to the third row of ptr = -3  2  -1

for i = 1:p-1, % p-1 level tree building

   % sort current code word prob from small to large
   [xf,xi]=sort(tmp(:,1));
   sf=tmp(xi,:);   

   ptr=[ptr;-i sf(1:2,2)'];
   if i < p-1,
      tmp=[sf(1,1)+sf(2,1) ptr(i,1);sf(3:p-i+1,:)];
   elseif i==p-1,
      tmp=[sf(1,1)+sf(2,1) ptr(i,1)];
   end
end

% Here is the tree:
ptr

% from the ptr (tree) generate code for each node
%  including intermediate nodes. Note that -(p-1) is
%  the root node of the tree

% np is a 2(p-1) by 3 matrix with first column contains all leaf nodes
% and all parent nodes except the root.
% the second column points to the parent node of that particular
% node. It should contain only negative integers form -1 to -p
% each appear exactly twice.
% the third column assigns 0 or 1 of the corresponding branch
% between that node and its parent
% for example, for for alphabet 4, its entry in np is 4 -1 0
% and for alphabet 5, its entry is 5 -1 1.

p2=p+p-2;
% first create a node-to-parent node matrix.
np=[[[1:p]';[-1:-1:-p+2]'] zeros(p2,2)];
for i=1:p-1, % total p-1 nodes
   for j=2:3,
      for k=1:p2,
        if np(k,1)==ptr(i,j),
              np(k,2) = ptr(i,1);
              np(k,3) = 1-rem(j,2); % if j=2, 1, j=3, 0
        end
      end
   end
end

np

% initilize extended code table from the ptr table
code=[np(:,3) zeros(p2,p-2)]; depth=ones(p2,1);
for i= p2:-1:p+1,  % start from root search all parent nodes
                   % level by level
   % for each parent node, append its own code to prefix the 
   % child node code, and increment the depth of child node by 1
   for k=1:i-1, 
      if np(k,2)==np(i,1),  % if node k is a child of node i
                            % exactly two such k's will be found
         depth(k) = depth(i) + 1; % child code length is 
             % sum of child code length + parent code length
             % since each node can be the child of only one parent
             % depth(k) has a depth equal to the parent depth + 1
         % append parent code to prefix child code
         code(k,1:depth(k))=[code(i,1:depth(i)) code(k,1)];
       end
   end
end

dmax=max(depth(1:p));
table=[code(1:p,1:dmax) depth(1:p)];table=[code(1:p,1:dmax) depth(1:p)];