function codebook=compactcodeP(Kraft_vector)
%compactcodeP designs a compression codebook.
%Given a proper Kraft vector L,  command y=compactcodeP(L)
%designs a vector y of indices of bitstrings in
%a prefix set having kraft vector L.
%
% Usage:
%   plaintext = [7 7 7 7 4 4 3 3 2 1]
%   the_histogram =  histo( plaintext(:) );
%   Kraft_vector =  unsorted_kraft( the_histogram );
%   codebook = compactcodeP( Kraft_vector );
%   print_bitstrings( codebook )
% returns
%   01
%   10
%   11
%   000
%   001
% Given that Kraft vector, this is the unique
% "canonical" Huffman code -- see 
%   http://www.compressconsult.com/huffman/#canonical
%   http://www.rdrop.com/~cary/html/data_compression.html#huffman
% for details.
% See HUFFMANCODE, PRINT_BITSTRINGS, HUFFMANLENGTH, COMPACTCODEI, FREQUENCY, INDEX_TO_BITSTRING.

% huffcode.m in huffman.zip
% at   
% ftp://ftp.mathworks.com/pub/contrib/v5/misc/huffman/
% http://www.mathworks.com/ftp/miscv5.shtml
% does exactly the same thing as
% compactcodeP.m
% (perhaps it is faster).

% Change log:
% 1999-06-25:DAV:
%   Given the Kraft lengths of each symbol from a to z,
%   in order from a to z,
%   now generates output codes directly in that order
%   (no need to re-sort further).
% 1999-06-24:DAV: Completely re-written
%   to generate the "canonical" Huffman code.
% 1999-06-24:DAV: David Cary wrote more documentation
% ???:JCK: originally by John C. Kieffer
%   by John C. Kieffer
%   http://www.ee.umn.edu/users/kieffer/programs.html
%   documented in
%   ftp://oz.ee.umn.edu/users/kieffer/slides/slide20.ps

Kraft_vector = double(Kraft_vector);
longest_code_length = max(Kraft_vector);
% initialize the current code
% for each possible code length.
% This ensures that shorter codes are
% never prefixes of longer codes.
%
% The all zeros code is the longest code.
% 00...0000
% The all ones code (or "1") is the shortest code.

% start at longest length and work down
value = 0;
for current_length = longest_code_length:-1:1,
   current_code(current_length) = binary_to_index(current_length, value);
   % How many codes (n) have length i ?
   n = length(find(Kraft_vector == current_length));
   % ASSERT( ~odd(value + n) );
   value = fix((value + n)/2);
end;
% ASSERT( isequal(1, value) );

% reserve space for each item in the alphabet of source symbols.
codebook = zeros(size(Kraft_vector));

x = 1:length(Kraft_vector);

for i = 1:length(Kraft_vector)
   code_length = Kraft_vector(i);
   if(code_length < 1)
      % Give the bogus code (-1) to items that never occur.
      codebook(i) = -1;
   else,
      codebook(i) = current_code(code_length);
      % make sure all codes of a given length
      % are unique
      current_code(code_length) = current_code(code_length) + 1;
   end;
end;

% end compactcodeP.m