function [reci,P]=SenonFano(P)
%SenonFano  Generise kodne reci Shannon-Fano-ovog statistickog kodera.
%Reci=SenonFano(P) generise kodne reci koje smesta u niz celija (cell array) X.
%   Svaka kodna rec je niz karaktera (string) koji je smesten u jednu celiju niza X.
%   Parametar P je vektor verovatnoca pojavljivanja odgovarajucih kodnih reci.
%   Broj kodnih reci koje je potrebno generisati odredjuje se duzinim vektora P.
%   Pre poziva funkcije neophodno je vektor P urediti po nerastucim vrednostima.
%
%[Reci,Psort]=SenonFano(P)
%   Psort je sortirani vektor verovatnoca P po nerastucen poretku.

n=length(P);    %broj kodnih reci se utvrdjuje na osnovu dimenzije vektora verovatnoce
% sortiranje
P=sort(P);
P=P(n:-1:1);

for i=1:n
    reci{i}=''; %incijalizacija niza celija 'praznim' kodnim recima
end
tind=[1 n];     %niz tekucih indeksa. U ovaj niz se smestaju PAROVI indeksa koji
                %definisu podnizove, u osnovnom nizu verovatnoca P, koje je
                %potrebno dalje deliti u smislu Shannon-Fano-ovog metoda. Svaki
                %par indeksa je jedan podnniz vektora P.
while length(tind) > 0  %ako nema podnizova koje je potrebno dalje deliti, onda je kraj
    nind=[];    %niz novih indeksa. U ovaj niz se smestaju tekuci indeksi za narednu podelu
                %u smislu Shannon-Fano-ovog metoda.
    m=1;        %tekuca (prazna) lokacija za upus u niz nind.
    
    %ovom petljom se prolazi kroz sve podnizove definisane u tind i vrsi njihovo dalje deljenje na
    %dva dela, ako je to potrebno.
    for k=1:2:length(tind)  %obradi sve podnizove definisane nizom tind
        %ako je podniz, definisan parom indeksa u tind, duzi od 2 onda ga treba dalje deliti na 2 dela
        if tind(k+1)-tind(k) >= 2   
            gr=sum(P(tind(k):tind(k+1)))/2; %granicna vrednost verovatnoce za podelu podniza na 2 dela
            s=0;    %promenljiva za sumiranje verovatnoca 
            for i=tind(k):tind(k+1) %ovom petljom se krece kroz elemente podniza od P
                s=s+P(i);           %i vrsi njihovo sabiranje (sabiraju se verovatnoce)
                %sledecim uslovom se vrsi podela tekuceg podniza na dva dela. Svaki deo mora da
                %sadrzi bar po jedan element i verovatnoce prvog i drugog dela treba da budu
                %priblizno jednake.
                if (i==tind(k)) | (s<=gr) | ((i>tind(k))&(s>gr)&((s-gr)<=abs(s-P(i)-gr)))
                    %prvi deo podniza verovatnoca P
                    ind=i;  %na ovom indeksu se podniz deli na dva dela. Promenljiva ind 'pamti'
                            %poslednji indeks koji pripada prvom delu
                    reci{i}=strcat(reci{i},'0'); %dodaj '0' na kraj kodne reci prve polovine podniza
                else
                    %drugi deo podniza
                    reci{i}=strcat(reci{i},'1'); %dodaj '1' na kraj kodne reci druge polovine podniza
                end
            end
            %sada se formiraju novi indeksi za podnizove P koje treba dalje deliti
            nind(m:m+3)=[tind(k) ind ind+1 tind(k+1)];
            m=m+4;  %m ukazuje na sledecu slobodnu lokaciju u nizu nind
        elseif tind(k+1)-tind(k) == 1   %ako podniz ima tacno 2 clana onda se
            reci{tind(k)}=strcat(reci{tind(k)},'0');    %prvom dodaje '0'
            reci{tind(k+1)}=strcat(reci{tind(k+1)},'1');%a drugom '1' na kraj kodne reci
            %i ne vrsi dalja podela na dva dela
        end
        %ko je podniz duzine 1 onda ne treba raditi nista
    end
    tind=nind; 
end
        
reci=reci'; % bolja preglednost pri prikazivanju na ekran