function [wav_koef_rek, time_dec]= SPIHT_decoder (bitstream)
% SPIHT_decoder
% Ulazi: bitstream - niz bitova nastao kodiranjem slike (u funkciji
%                    SPIHT_coder
% Izlazi: wav_koef_rek - rekonstruirana DWT matrica, predaje se dalje
%                        funkciji DWT_reconstruction da bi se rekonstruirala originalna slika
%         time_dec - vrijeme potrebno funkciji da rekonstruira matricu 

% NMDOS projekt, 15.1.2009.
% Autor: Vana Jelièiæ


global n_razl
global sizey
global sizex

cont=0;
time_dec= 0;

%primanje header-a
n_max=bitstream(1);
n_razl=bitstream(2);
sizey=bitstream(3);
sizex=bitstream(4);

size_bs=size(bitstream,2);
bitstream_indeks=4*8;

%nakon toga dolaze 'bitovi slike'


%---------------------------------------


LIS_rek = [];
LIP_rek= [];
LSP_rek = [];

wav_koef_rek=zeros(sizey,sizex);

n=n_max;

H_sizex = sizex/(2^n_razl);
H_sizey = sizey/(2^n_razl);

%inicijalizacija LIP-a
%svi roots

k=1;
for i= 1: H_sizey
    for j=1:H_sizex

        LIP_rek(k,:)=[i,j];
        k=k+1;

    end
end

%u LIS su na pocetku svi roots osim onih kojima su obje koordinate (i,j)
%NEPARNE!
k=1;
if (H_sizex==1)&(H_sizey==1)
    LIS_rek(1)=1;
    LIS_rek(2)=1;
    LIS_rek(3)=1;

else
    for i= 1 : H_sizey
        for j= 1: H_sizex
            if not(mod(i,2)==1 & mod(j,2)==1) % ako nisu i,j neparni
                LIS_rek (k,1)=i;
                LIS_rek (k,2)=j;
                LIS_rek (k,3)=1;
                k=k+1;
            end
        end
    end
end
% ZAVRSILA INICIJALIZACIJA

% while (any(LIS_rek))==1
%while n>=1

while (bitstream_indeks<size_bs)
    tic;
%    n

    treshold=2^n;
    size1LSP = size (LSP_rek,1);

    size1LSP=size(LSP_rek,1);

    %Sorting pass - LIP
    k=1;
    size1LIP = size (LIP_rek,1);
    while (k<=size1LIP)
        if(bitstream_indeks>=size_bs)
            %disp('izlaz1')
            time_dec=toc;
            return
        end
        bitstream_indeks=bitstream_indeks+1;
        root_significance=bitstream(bitstream_indeks);

        if root_significance==1
            wav_koef_rek(LIP_rek(k,1),LIP_rek(k,2))=1.5*treshold;
            bitstream_indeks=bitstream_indeks+1;
            sign_wav_koef=bitstream(bitstream_indeks);

            if sign_wav_koef==0
                wav_koef_rek(LIP_rek(k,1),LIP_rek(k,2))=-wav_koef_rek(LIP_rek(k,1),LIP_rek(k,2));
            end

            LSP_rek=[LSP_rek; LIP_rek(k,1:2),sign_wav_koef];

            %mièemo iz LIP-a
            if(k==1)
                LIP_rek=[LIP_rek(2:size1LIP,:)];
            elseif (k>1)&&(k<size1LIP)
                LIP_rek=[LIP_rek(1:(k-1),:); LIP_rek((k+1):size1LIP,:)]; %micemo znacajni koeficijent iz LIP u LSP
            elseif (k==size1LIP)
                LIP_rek=[LIP_rek(1:(size1LIP-1),:)];
            end
        end

        size1LIP = size (LIP_rek,1);

        if not (root_significance == 1)
            k=k+1;
        end

    end


    %Sorting pass - LIS
    size1LIS = size(LIS_rek,1);

    i=1;
    count=0;
    while (i>0 & i<=size1LIS)

        i=i-count;
        if cont==1

            i=i+1-count;
            if i<=0
                i=1;
            end
            cont=0;
        end
        count=0;
        if LIS_rek (i,3)==1

            if bitstream_indeks>=size_bs
                %disp('izlaz2')
                time_dec=toc;
                return
            end

            bitstream_indeks=bitstream_indeks+1;
            D_significant=bitstream(bitstream_indeks);
            [ind_offsp, postoji_offsp ] = racunamo_offspringe_dec (LIS_rek(i,1:2));

            if postoji_offsp==1

                if D_significant == 1
                    for m=1:4
                        if (H_sizey==1)
                            if (LIS_rek(i,1)==1 & LIS_rek (i,2)==1)
                                if m==4
                                    break;
                                end
                            end
                        end

                        bitstream_indeks=bitstream_indeks+1;
                        offspring_significant=bitstream(bitstream_indeks);

                        if offspring_significant == 1
                            if not(ind_offsp(m,1)==0 & ind_offsp(m,2)==0)
                                wav_koef_rek(ind_offsp(m,1),ind_offsp(m,2))=1.5*treshold;
                                bitstream_indeks=bitstream_indeks+1;
                                sign_wav_koef=bitstream(bitstream_indeks);

                                if sign_wav_koef==0
                                    wav_koef_rek(ind_offsp(m,1),ind_offsp(m,2))=-wav_koef_rek(ind_offsp(m,1),ind_offsp(m,2));
                                end
                            end %

                            LSP_rek  = [ LSP_rek; ind_offsp(m,1), ind_offsp(m,2), sign_wav_koef ];

                        else
                            LIP_rek = [ LIP_rek; ind_offsp(m,1), ind_offsp(m,2) ];

                        end
                    end
                    size1LIS = size(LIS_rek,1);

                    [postoji_L] = racunamo_L_dec (LIS_rek(i,1:2));

                    v=zeros(1,2);
                    if postoji_L==1
                        v=LIS_rek(i,1:2);
                        if(i==1)
                            if size1LIS==1
                                LIS_rek=[];
                            else
                                LIS_rek=[LIS_rek(2:size1LIS,:)];
                            end

                        elseif (i>1)&&(i<size1LIS)
                            LIS_rek=[LIS_rek(1:(i-1),:); LIS_rek((i+1):size1LIS,:)];
                        elseif (i==size1LIS)
                            LIS_rek=[LIS_rek(1:(size1LIS-1),:)];
                        end
                        count = count +1;

                        LIS_rek= [LIS_rek; v,2];
                        %disp('micemo na kraj LISa ko B')
                        cont=1;
                        continue;
                    else
                        if(i==1)
                            if size1LIS==1
                                LIS_rek=[];
                            else
                                LIS_rek=[LIS_rek(2:size1LIS,:)];
                            end
                        elseif (i>1)&&(i<size1LIS)
                            LIS_rek=[LIS_rek(1:(i-1),:); LIS_rek((i+1):size1LIS,:)];
                        elseif (i==size1LIS)
                            LIS_rek=[LIS_rek(1:(size1LIS-1),:)];
                        end
                        count=count+1;

                    end

                end
            end
        end
        size1LIS =size (LIS_rek,1);
        if(i>0 & i<=size1LIS)
            if any(LIS_rek)==1

                if bitstream_indeks>=size_bs
                   % disp('izlaz3')
                    time_dec=toc;
                    return
                end

                size1LIS=size (LIS_rek,1);

                if LIS_rek (i,3)==2
                    size1LIS=size (LIS_rek,1);
                    [postoji_L] = racunamo_L_dec (LIS_rek(i,1:2));
                    bitstream_indeks=bitstream_indeks+1;
                    L_significant=bitstream(bitstream_indeks);
                    if postoji_L==1
                        if L_significant ==1
                            [ind_offsp, postoji_offsp ] = racunamo_offspringe_dec (LIS_rek(i,1:2));

                            if(i==1)

                                if size1LIS==1
                                    LIS_rek=[];

                                else
                                    LIS_rek=[LIS_rek(2:size1LIS,:)];
                                end

                            elseif (i>1)&&(i<size1LIS)
                                LIS_rek=[LIS_rek(1:(i-1),:); LIS_rek((i+1):size1LIS,:)];
                            elseif (i==size1LIS)
                                LIS_rek=[LIS_rek(1:(size1LIS-1),:)];
                            end
                            count=count+1;

                            for m=1:4
                                if not (ind_offsp(m,1)==0 & ind_offsp(m,2)==0)
                                    LIS_rek = [LIS_rek; ind_offsp(m,:), 1];
                                    size1LIS = size(LIS_rek,1);
                                end
                            end
                            cont=1;
                            continue;

                        end
                    end
                end
                size1LIS = size(LIS_rek,1);

                i=i+1-count;
                count=0;

            end
        end
        if i<=1
            i=1;
        end

        if not (any(LIS_rek)==1)
            i=0;
        end
    end

    for b=1: size1LSP

        if bitstream_indeks>=size_bs
           % disp('izlaz4')
            time_dec=toc;
            return
        end
        bitstream_indeks=bitstream_indeks+1;
        nMSB_rek=bitstream(bitstream_indeks);
        if n>=0 & n<n_max
            if nMSB_rek==1
                if wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))>=0
                    wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))= wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))+2^(n-1);
                else
                    wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))= -(abs(wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2)))+2^(n-1));
                end

            else
                if wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))>=0
                    wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))= wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))-2^(n-1);
                else
                    wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2))= -(abs(wav_koef_rek(LSP_rek(b,1),LSP_rek(b,2)))-2^(n-1));
                end
            end
        end
       
    end
    
    % quantization-step update
    n=n-1;
    
end
%
time_dec=toc;
