function huffstream = adaptivehuffman(stream,type)
%
%==========================================================================
%                    Matt Clarkson - University of Bath
%
%                             Copyleft 2008
%==========================================================================
%
% huffstream = adaptivehuffman(stream,type)
%
% Adaptively encodes or decodes an integer stream.  If type is not defined
% the program inspects the input stream and failing to find a suitable
% adaptively encoded huffman stream the program defaults to compression.
%
% The stream has a two bit header containing the bit depth of the symbols.
% This is easily removed if a constant bit depth is always going to be
% used.
%
% To help visualise the huffman tree a function "treedetails" can be called
% at any point to display the values of each node.
% 
% Examples:
%
% huffstream = adaptivehuffman(stream) returns a adaptively huffman encoded
% stream or a decompressed string depending on the input.  For compression 
% the input must be a one dimensional horizontal unsigned integer  
% array.  8 and 16 bit depths are accepted.  For decompression the
% input must be a previously encoded string
%
% huffstream = adaptivehuffman(stream,'enc') returns compressed stream.
% Also the compression percentage is printed.
%
% huffstream  = adaptivehuffman(stream,'dec') returns the result of
% decompressing a previously compressed huffman stream.
%
%==========================================================================

%==========================================================================
%Insect input stream
%==========================================================================
if nargin < 2;    %Inspects input stream
    if isinteger(stream)...    %If integer...
       && (size((unique(stream)),2) == 2)...     %and has two symbols...
       && isa(stream,'uint8')...    %and a usigned 8 bit integer stream...
       && ~(size(size(stream),2)~=2)...     %and is 2D...
       && (size(stream,1) == 1 && size(stream,2) > 0)...    %and is 1D horizontal...
       && sum(unique(stream)) == 1     %and is binary stream   
        type = 'dec';
    else
        type = 'enc';
    end
end
if ~strcmp(type,'dec')     %If not decoding, encode
    
%==========================================================================
%Adaptive Huffman Encoding
%==========================================================================
clear type
%--------------------------------------------------------------------------
%Check stream structure
%--------------------------------------------------------------------------
    if ~isinteger(stream);error('Input must be unsigned integer stream');end
    for i = 3:6;if isa(stream, num2str(2^i,'int%i'));error('Input must be unsigned integer stream');end;end
    if size(size(stream),2)~=2 || ~(size(stream,1) == 1 && size(stream,2) > 0)
        error('Input must be a one dimensional horizontal stream');
    end
%--------------------------------------------------------------------------
%Find bit depth of stream and check for accepted bit depths
%--------------------------------------------------------------------------
    for i = 3:6
        if isa(stream, num2str(2^i,'uint%i'));bitdepth = 2^i;end;
    end
    if ~exist('bitdepth','var');error('Input stream must be a unsigned integer');end;
    if bitdepth == 64 || bitdepth == 32;error('Bit depth must be 8 or 16');end;
%--------------------------------------------------------------------------
%Set up the Not Yet Transmitted (NYT) Node and Tree Structure
%--------------------------------------------------------------------------
    huffstream = uint8([]);     %Initialise outputstream
    NYT = unique(stream);     %Find unique symbols and create NYT list
    NYTlocation = double(max(NYT))+2;     %Set the NYT location
    n = length(stream);     %Find length of stream
    nodenumber = (2*n);     %Find the amount of nodes
    tree(1).number = nodenumber;     %Total number of nodes
    tree(1).parent = 0;     %Node parent
    tree(1).left = 0;     %Node left child
    tree(1).right = 0;     %Node right child
    tree(1).symbol = NYTlocation;     %Node symbol
    tree(1).weight = 0;     %Node Weight
    location = zeros(1,NYTlocation);     %Location of the symbols in the tree
    location(NYTlocation) = 1;     %Location of the NYT node
%--------------------------------------------------------------------------
%Add a one bit header to the huffman stream where 0 and 1 represent
%8 and 16 bit depths respectively.  If the function is going to be used
%with only one bit depth the following line can be commented out.  Make
%sure, the bit depth in the decoding section is changed accordingly
%--------------------------------------------------------------------------
    huffstream = [huffstream uint8(bitget((log2(bitdepth)-3),1))];
%--------------------------------------------------------------------------
%Huffman Tree loop
%--------------------------------------------------------------------------
    wb = waitbar(0,'Please Wait...','Name','Encoding');     %Creates progress bar
    for index = 1:n     %For whole stream
        symbol = stream(index);     %Read in symbol
        if sum(NYT == symbol)     %Symbol seen before?
            nodecode(NYTlocation-1)     %Add NYT code to the output stream
            treeloop(symbol);      %Start the huffman tree loop for symbol
            huffstream(length(huffstream)+1:length(huffstream)+bitdepth) = uint8(bitget(symbol,bitdepth:-1:1));     %Output symbol
        else        
            nodecode(symbol);     %Add NYT code to the output stream
            treeloop(symbol);      %Start the huffman tree loop for symbol
        end
        waitbar(index/n,wb);     %Update progress bar
    end
    close(wb)     %Close progress bar
    if nargin==2;fprintf(['Compressed: ' num2str((length(huffstream)/(length(stream)*bitdepth))*100,'%6.2f') '%%\n']);end;
else
    
%==========================================================================
%Adaptive Huffman Decoding
%==========================================================================
clear type
%--------------------------------------------------------------------------
%Finds bitdepth.  If the function is going to be used with only one bit
%depth alter the commenting of the following three assignments.  Make sure
%that, if a constant bit rate is going to be used, the header assignment in
%the encoding part of the function is commented out.
%--------------------------------------------------------------------------
    bitdepth = 2^((bits2dec(stream(1)))+3);stream(1)=[];
    %bitdepth = 8;
    %bitdepth = 16;
%--------------------------------------------------------------------------
%Set up the Not Yet Transmitted (NYT) Node and Tree Structure
%--------------------------------------------------------------------------
    huffstream = eval(num2str(bitdepth,'uint%i([])'));     %Initialise outputstream
    NYT = 0:(2^bitdepth)-1;     %Find unique symbols and create NYT list
    NYTlocation = max(NYT)+2;     %Set the NYT location
    n = length(stream);     %Find length of stream
    nodenumber = max(2*NYT)+1;     %Find the amount of nodes
    tree(1).number = nodenumber;     %Total number of nodes
    tree(1).parent = 0;     %Node parent
    tree(1).left = 0;     %Node left child
    tree(1).right = 0;     %Node right child
    tree(1).symbol = NYTlocation;     %Node symbol
    tree(1).weight = 0;     %Node Weight
    location = zeros(1,NYTlocation);     %Location of the symbols in the tree
    location(NYTlocation) = 1;     %Location of the NYT node
%--------------------------------------------------------------------------
%Perform Decoding
%--------------------------------------------------------------------------
    wb = waitbar(0,'Please Wait...','Name','Decoding');     %Creates progress bar
    progress = length(stream);     %Value to update progress bar
    while ~isempty(stream);     %While stream is not empty
        position = 1;      %Go to root node
        while isempty(tree(position).symbol);     %If position is not a leaf
            if stream(1)     %If bit is 1
                position = tree(position).right;     %Go right
                stream(1) = [];     %Remove bit from stream
            else     %If bit is 0
                position = tree(position).left;     %Go left
                stream(1) = [];     %Remove bit from stream
            end                
        end
        if tree(position).symbol == NYTlocation     %If node is NYT
            symbol = bits2dec(stream(1:bitdepth));     %Finds first symbol
            stream(1:bitdepth) = [];     %Removes symbol from bit stream
            huffstream = [huffstream symbol];    %Adds to output stream
        else
            symbol = tree(position).symbol;     %Output known symbol
            huffstream = [huffstream symbol];    %Adds to output stream
        end
        treeloop(symbol)    %Updates the tree
        waitbar((progress-length(stream))/progress,wb);     %Update progress bar