function [out_bitstream, time_coder]= SPIHT_coder (wav_matrica1, n_razl1, bpp) 
% SPIHT_coder
% Ulazi: wav_matrica1 - matrica nastala DWT dekompozicijom
%        n_razl1 - broj razina razlaganja DWT-om
%        bpp - broj bita po pikselu
% Izlazi: out_bitstream - niz bitova koji se tijekom alogoritma formiraju kao
%                         odgovori na postavljenja pitanja
%         time_coder - vrijeme potrebno funkciji da kodira sliku
%
% NMDOS projekt, 15.1.2009.
% Autor: Vana Jelièiæ

global n_razl
global wav_matrica

wav_matrica=wav_matrica1;
n_razl=n_razl1;

LIS = [];  %LIS - D-ovi od Root-ova
LIP= [];
LSP = [];

cont=0;

time_coder=0;

% matrice korištene za uhodavanje i testiranje rada algoritma
% M=[18 3 2 2;
%     6 -5 1 -2;
%     8 13 -6 4;
%     -7 1 3 -2];
%
% M= [26 6 13 10;
%     -7 7 6 4;
%     4 -4 4 -3;
%     2 -2 -2 0];

% M=[26 15 13 10 -9 5 5 3;
%     20 18 -14 9 8 4 2 1;
%     16 -12 10 4 3 -3 2 2;
%     15 13 11 -7 5 4 3 2;
%     14 14 -11 9 6 5 3 2;
%     10 7 5 -4 3 3 2  1;
%     6 5 -4 4 3 2 2 1 ;
%     4 3 3 2 1 -1 0 0 ];
%
% wav_matrica = M;
% [sizey sizex]= size (M);

polje_nMSB=[];

[sizey sizex] = size (wav_matrica); % sizey-broj redaka, sizex-broj stupaca

number_of_bits_max = bpp*sizex*sizey;

max_pix= max(max(wav_matrica));
n_max = floor(log2(max_pix)) 
n=n_max;

%podruèje aproksimacije (LL)
H_sizex = sizex/(2^n_razl);
H_sizey = sizey/(2^n_razl);


k=1;
for i= 1:H_sizey
    for j=1:H_sizex
        LIP (k,1)=i;
        LIP (k,2)=j;
        k=k+1;
    end
end

indeks =[];

%HEADER U BITSTREAMU 
out_bitstream = [n, n_razl, sizey, sizex]; 
sizeb2 = size(out_bitstream,2);
number_of_bits=sizeb2*8; %? svaka od 4 varijable sastoji se od 8 bitova


%dakle, 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(1)=1;
    LIS(2)=1;
    LIS(3)=1; % type A

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 (k,1)=i;
                LIS (k,2)=j;
                LIS (k,3)=1;  % A
                k=k+1;
            end
        end
    end
end

disp('Inicijalizacija zavrsena.')


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

while (n>0) 
    tic; %starts a stopwatch timer
    treshold=2^n;
   % n
    size1LSP=size(LSP,1);
    
    % pretrazujemo LIP -> Sorting Pass
    size1LIP = size (LIP,1);
    %l=1;
    k=1;
    while (k<=size1LIP) 
        if number_of_bits>=number_of_bits_max
           % disp('izlaz1')
            time_coder=toc;
            return
        end
        
        [root_significance postoji_D_L] = S_n (LIP(k,:),treshold, 1); %indeks (i,j) predajemo
        % root_significance
        number_of_bits=number_of_bits+1;
        out_bitstream(number_of_bits)=root_significance;

        if root_significance == 1
            sign_wav_koef = wav_matrica(LIP(k,1), LIP(k,2))>=0;
            number_of_bits=number_of_bits+1;
            out_bitstream(number_of_bits)=sign_wav_koef;

            LSP=[LSP; LIP(k,1:2),sign_wav_koef]; % u principu je nepotrebno sign_wav_koef zapisivati u LIP

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

    % obradjujemo LIS
    size1LIS = size(LIS,1);

    i=1;
    count=0; % zajedno s cont kontrolira indekse LIS-a pri premještanju
    while (i>0 & i<=size1LIS)
        i=i-count;
        if cont==1
            %disp ('i na ul')
            i=i+1-count;
            if i<=0  %
                i=1;
            end
            cont=0;
        end
        count=0;
        if LIS (i,3)==1
           % disp('if1 A')
            %LIS(i,1:2)
            if number_of_bits>=number_of_bits_max
               % disp('izlaz2')
                time_coder=toc;
                return
            end
            [are_D_significant postoji_D] = S_n (LIS(i,1:2), treshold, 2);
            number_of_bits=number_of_bits+1;
            out_bitstream(number_of_bits)=are_D_significant;

            if postoji_D==1
                if are_D_significant == 1 
                    [O ind_offsp postoji_offsp] = racunamo_offspringe (LIS(i,1:2));
                    for m=1:4  
                        if not(ind_offsp(m,1)==0 & ind_offsp(m,2)==0)
                            [offspring_significant postoji_D_L] = S_n( ind_offsp(m,:), treshold,1);

                            number_of_bits=number_of_bits+1;
                            out_bitstream(number_of_bits)=offspring_significant; 

                            if offspring_significant == 1 
                                sign_of_offsp = wav_matrica (ind_offsp(m,1),ind_offsp(m,2)) >= 0;
                                number_of_bits=number_of_bits+1;
                                out_bitstream(number_of_bits)=sign_of_offsp;
                                
                                LSP  = [ LSP; ind_offsp(m,1), ind_offsp(m,2), sign_of_offsp ];
                                
                            else
                                LIP = [ LIP; ind_offsp(m,1), ind_offsp(m,2) ];
                                
                            end
                        end
                    end
                    size1LIS = size(LIS,1);
                    
                    [L postoji_L] = racunamo_L (LIS(i,1:2));  
                    v=zeros(1,2);
                    if postoji_L==1
                        
                        v=LIS(i,1:2);
                        if(i==1)
                            if size1LIS==1
                                LIS=[];
                               
                            else
                                LIS=[LIS(2:size1LIS,:)];
                               
                            end
                        elseif (i>1)&&(i<size1LIS)
                            LIS=[LIS(1:(i-1),:); LIS((i+1):size1LIS,:)];
                           
                        elseif (i==size1LIS)
                            LIS=[LIS(1:(size1LIS-1),:)];
                           
                        end
                        count = count +1; 
                       
                        LIS= [LIS; v, 2]; 
                       % disp('micemo na kraj LISa ko B')
                        cont=1;
                        continue;

                    else  
                        
                        if(i==1)
                           if size1LIS==1
                                LIS=[];
                           else
                                LIS=[LIS(2:size1LIS,:)];
                           end
                        elseif (i>1)&&(i<size1LIS)
                            LIS=[LIS(1:(i-1),:); LIS((i+1):size1LIS,:)];
                        elseif (i==size1LIS)
                            LIS=[LIS(1:(size1LIS-1),:)];
                        end
                        count=count+1;

                    end
                  
                end
           end
        end

        size1LIS =size (LIS,1);
        if(i>0 & i<=size1LIS)
            if any(LIS)==1
               
                if number_of_bits>=number_of_bits_max
                   % disp('izlaz3')
                    time_coder=toc;
                    return
                end
                
                size1LIS = size(LIS,1);
                if LIS (i,3)==2 %   type B
                    %disp('if B')
                    [are_L_significant, postoji_L]= S_n (LIS (i,1:2), treshold, 3);
                    number_of_bits=number_of_bits+1;
                    out_bitstream(number_of_bits)=are_L_significant; 

                    if postoji_L==1 
                       if are_L_significant ==1
                            [O, ind_offsp]= racunamo_offspringe(LIS(i,1:2));
                            
                            if(i==1)
                                
                                if size1LIS==1
                                    LIS=[];
                                 
                                else
                                    LIS=[LIS(2:size1LIS,:)];

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

                            elseif (i==size1LIS)
                                LIS=[LIS(1:(size1LIS-1),:)];
                            end
                            
                            count=count+1;

                            for m=1:4
                                if not (ind_offsp(m,1)==0 & ind_offsp(m,2)==0)
                                    LIS = [LIS; ind_offsp(m,:), 1]; %'A'
                                    
                                    size1LIS = size(LIS,1);
                                    
                                end
                            end
                            cont=1;
                            continue;
                          
                        end
                    end
                end
                
                size1LIS = size(LIS,1);
                
                i=(i+1)-count; 
                count=0;
                if i<=1  
                    i=1;
                end
            end
        end
        if not (any(LIS)==1)
            i=0;
        end
    end


    % Refinement pass-
    % for each entry in the LSP, except those included in the
    % last sorting pass (with same n), output the n-th most significant bit of
    % abs(c_ij)  
    
    %disp('prije ref')
    for b=1: size1LSP
        if number_of_bits>=number_of_bits_max
           % disp('izlaz4')
            time_coder=toc;
            return
        end
        if uint16(abs(wav_matrica ( LSP (b,1), LSP (b,2)))) >= 2^(n+1) % nisam sigurna da li ide > ili >=
            if (n>=0 & n<n_max)
                nMSB = bitget (uint16(abs(wav_matrica (LSP(b,1), LSP(b,2)))),(n+1));  %(1<<n);
                polje_nMSB=[polje_nMSB, nMSB];

                number_of_bits=number_of_bits+1;
                out_bitstream(number_of_bits)=nMSB;
                
            end
        end
        b=b+1;

    end
    
    % quantization-step update
    n=n-1;
    
end

time_coder=toc;   %read the stopwatch timer

