function [KRold,P]=Hafmen(P)
%Realizuje Huffman-ov statisticki koder.
%
%Reci=Hafmen(P)
%   P je vektor verovatnoca poruka izvora. Zbir elemenata vektora P mora biti 1.
%      Vektor verovatnoca P treba da bude uredjen po nerastucem poretku. U suprotnom,
%      vektor P ce biti automatski preuredjen da zadovolji ovaj uslov.
%   Reci je niz celija koji sadrzi kodne reci. Svaka celija je niz znakova (string)
%      koji definise jednu kodnu rec. Redosled kodnih reci odgovara sortiranom 
%      vektoru verovarnoca po nerastucem poretku.
%
%[Reci,Psort]=Hafmen(P)
%   Psort je sortirani vektor verovatnoca P po nerastucen poretku.

% provera
s=sum(P);
if s<1-1e-6 | s>1+1e-6
    disp('Greska: Zbir elemenata vektora P mora biti 1.')
    return
end

% sortiranje
n=length(P);
P=sort(P);
P=P(n:-1:1);

%DEMO Q{1}=P; %Q je niz celija u kome se pamte nizovi verovatnoca pri svim redukcijama. Q{i+1} je niz verotnoca i-te redukcije

% PROCES REDUKCIJE POLAZNOG SKUPA VEROVATNOCA
p=P;
for redukcija=1:n-2 %Broj redukcija je n-2
%obradjuje se vektor verovatnoca prethodne redukcije i dobija vektor verovatnoca tekuce redukcije
   
    a=p(n-redukcija)+p(n-redukcija+1); %zbir poslednje dve verovatnoce
    
    %formira se novi sortirani vektor verivatnoca q sa elementom a na odgovarajucoj poziciji koja se pamti u redBr
    i=1; q=0;
    while i<=n-redukcija-1
        if p(i)<a, break, end
        q(i)=p(i);
        i=i+1;
    end
    redBr(redukcija)=i; %pamti se lokacija zbira a u vektoru verovatnoca tekuce redukcije
    q(i)=a;
    while i<=n-redukcija-1
        q(i+1)=p(i);
        i=i+1;
    end
    
%DEMO    Q{redukcija+1}=q; %novi vektor verovatnoca se smesta u niz celija
    p=q; % priprema za novu iteraciju
end

% FORMIRANJE KODNIH RECI
KRold={'0' '1'}; % pocetni skup kodnih reci u poslednjoj redukciji
for redukcija=n-2:-1:1 % krecemo se unazad kroz redukcije i formiramo kodne reci
    duzina=n-redukcija; %duzina vektora verovatnoca iz prethodne redukcije
    k=redBr(redukcija); %pozicija zbirnog elementa u vektoru verovatnoca iz prethodne redukcije
    % kopiranje svih kodnih reci ispred k-te jer se ne menjaju u tekucoj redukciji
    for i=1:k-1
        KRnew(i)=KRold(i);
    end
    % kopiranje svih kodnih reci iza k-te jer se ne menjaju u tekucoj redukciji
    for i=k+1:duzina
        KRnew(i-1)=KRold(i);
    end
    % poslednje dve kodne reci nastaju od k-te kada se doda 0/1 na kraj reci
    KRnew{duzina}=[KRold{k} '0'];
    KRnew{duzina+1}=[KRold{k} '1'];
    
    KRold=KRnew; % priprema za novu iteraciju
    KRnew={}; % nije neophodno
end

KRold=KRold'; % bolja preglednost pri prikazivanju na ekran