function [n_max, n, m, timeel] = decodeSPIHT(in)
% decodeSPIHT - SPIHT decoder
%
% parameters:      in - compressed data
% output:          m - image, n_max - max steps, n - last step, timeel - time elapsed 


%-----------  initialization  ----------------

disp(' ');
disp('SPIHT decoder engaged...');

% settings
m = zeros(in(1,1));
n_max = in(1,2);
level = in(1,3);
ctr = 4;

%----------- LIP, LSP, LIS init ----------------
temp = [];
timeel = 0;
bandsize = 2.^(log2(in(1,1)) - level + 1);   
temp1 = 1 : bandsize;
for i = 1 : bandsize
    temp = [temp; temp1];
end
LIP(:, 1) = temp(:);
temp = temp';
LIP(:, 2) = temp(:);

LIS(:, 1) = LIP(:, 1);
LIS(:, 2) = LIP(:, 2);
LIS(:, 3) = zeros(length(LIP(:, 1)), 1);
pstart = 1;
pend = bandsize / 2;
for i = 1 : bandsize / 2
    LIS(pstart : pend, :) = [];
    pdel = pend - pstart + 1;
    pstart = pstart + bandsize - pdel;
    pend = pend + bandsize - pdel;
end
LSP = [];

disp('DECODER: header set, initialization finished');

%-----------   decoding   ----------------
n = n_max;
while (ctr <= size(in,2))
    tic;
    ctr_backup=ctr;
    
    %Sorting Pass
    LIPtemp = LIP; temp = 0;
    
    % LIP pass
    for i = 1:size(LIPtemp,1)  
        temp = temp+1;
        
        % bitstream end condition
        if ctr > size(in,2) 
            return
        end
        
        % pixel in LIP is significant
        if in(1,ctr) == 1 
            ctr = ctr + 1;
            if in(1,ctr) > 0
                %sign +, thr + 1/2 to m
                m(LIPtemp(i,1),LIPtemp(i,2)) = 2^n + 2^(n-1);
            else
                %sign -, -thr - 1/2 to m
                m(LIPtemp(i,1),LIPtemp(i,2)) = -2^n  - 2^(n-1);  
            end
            
            %add pixel to LSP, remove from LIP
            LSP = [LSP; LIPtemp(i,:)];  
            LIP(temp,:) = []; temp = temp - 1;
        end
        
        %not significant -> another pixel
        ctr = ctr + 1;
    end
    
    % LIS pass
    LIStemp = LIS; temp = 0; i = 1;
    while ( i <= size(LIStemp,1))
        temp = temp + 1;
        
        if ctr > size(in,2)
            return
        end
        
        % entry type A
        if LIStemp(i,3) == 0
            % entry has significant descendants
            if in(1,ctr) == 1 
                ctr = ctr + 1;
                x = LIStemp(i,1); y = LIStemp(i,2); 
                
                if ctr > size(in,2)
                    return
                end
                
                %top-left significance
                if in(1,ctr) == 1 
                    %send to LSP, value to m
                    LSP = [LSP; 2*x-1 2*y-1];
                    ctr = ctr + 1;
                    if in(1,ctr) == 1
                        m(2*x-1,2*y-1) = 2^n + 2^(n-1);  
                    else
                        m(2*x-1,2*y-1) = -2^n  - 2^(n-1); 
                    end
                    ctr = ctr + 1;
                else
                    %save to LIP
                    LIP = [LIP; 2*x-1 2*y-1];
                    ctr = ctr + 1;
                end
                
                if ctr > size(in,2)
                    return
                end
                
                %top-right significance
                if in(1,ctr) == 1
                    ctr = ctr + 1;
                    LSP = [LSP; 2*x-1 2*y];   
                    if in(1,ctr) == 1;
                        m(2*x-1,2*y) = 2^n + 2^(n-1); 
                    else
                        m(2*x-1,2*y) = -2^n  - 2^(n-1); 
                    end
                    ctr = ctr + 1;
                else
                    LIP = [LIP; 2*x-1 2*y];
                    ctr = ctr + 1;
                end
                
                if ctr > size(in,2)
                    return
                end
                
                %bottom-left significance
                if in(1,ctr) == 1
                    ctr = ctr + 1;
                    LSP = [LSP; 2*x 2*y-1];
                    if in(1,ctr) == 1
                        m(2*x,2*y-1) = 2^n + 2^(n-1); 
                    else
                        m(2*x,2*y-1) = -2^n  - 2^(n-1);
                    end
                    ctr = ctr + 1;
                else
                    LIP = [LIP; 2*x 2*y-1];
                    ctr = ctr + 1;
                end
                
                if ctr > size(in,2)
                    return
                end
                
                %bottom-right significance
                if in(1,ctr) == 1
                    ctr = ctr + 1;
                    LSP = [LSP; 2*x 2*y];
                    if in(1,ctr) == 1
                        m(2*x,2*y) = 2^n + 2^(n-1); 
                    else
                        m(2*x,2*y) = -2^n  - 2^(n-1); 
                    end
                    ctr = ctr + 1;
                else
                    LIP = [LIP; 2*x 2*y];
                    ctr = ctr + 1;
                end   
                
                %has [x,y] room for more descendants?
                if ((2*(2*x)-1) < size(m) & (2*(2*y)-1) < size(m))  
                    %yes --> insert into LIS and LIStemp as [x,y,1] (type B entry)
                    LIS = [LIS; x y 1];           
                    LIStemp = [LIStemp; x y 1];  
                end
                
                %done - remove entry type A [x,y,0] from LIS
                LIS(temp,:) = []; temp = temp-1; 
                
            else
                % no significant descendants - nothing happens
                ctr = ctr + 1;
            end
            
        else 
            % entry type B
            
            % B - significance?
            if in(1,ctr) == 1  
                x = LIStemp(i,1); y = LIStemp(i,2);
                
                % save grandchildren into LIS and LIStemp as type A
                LIS = [LIS; 2*x-1 2*y-1 0; 2*x-1 2*y 0; 2*x 2*y-1 0; 2*x 2*y 0]; 
                LIStemp = [LIStemp; 2*x-1 2*y-1 0; 2*x-1 2*y 0; 2*x 2*y-1 0; 2*x 2*y 0];  
                
                % delete entry type B [x,y,1] from LIS
                LIS(temp,:) = []; temp = temp - 1; 
            end
            ctr = ctr + 1;
        end
        i = i+1;
    end
    
    ctr_backup2 = ctr;
    
    % Refinement Pass
    temp = 1;
    value = m(LSP(temp,1), LSP(temp,2));
    
    % as long as there are items in LSP compliant with the following
    % condition
    while (abs(value) >= 2^(n+1) & (temp <= size(LSP,1)))
        if ctr > size(in,2)
            return
        end

        % add (subtract) according to bit
        value = value + ((-1)^(in(1,ctr) + 1)) * (2^(n-1))*sign(m(LSP(temp,1),LSP(temp,2))); 
        m(LSP(temp,1),LSP(temp,2)) = value;
        ctr = ctr + 1;
        temp = temp + 1;    
        if temp <= size(LSP,1)
            value = m(LSP(temp,1),LSP(temp,2));
        end
    end
    
    time = toc;
    timeel = timeel + time;
    
    disp(['DECODER: STEP ' num2str(n_max-n) ' finished in ' num2str(time) 's. Processed: (S/R): ' num2str(ctr_backup2-ctr_backup) '/' num2str(ctr-ctr_backup2) 'bits.']);
   
    n = n - 1;
end