#include<iostream>
using namespace std;
struct zivotinja{
    int sifra;
    char vrsta[35];
    char naziv[35];
    float cijena;
    int datum[3];        
};
struct Lista_zapis{
       zivotinja vrijednost;
       Lista_zapis *sljedeci;
};
typedef Lista_zapis *element;
typedef Lista_zapis lista;
element EndL(lista *L){
      return 0;
}
element FirstL(lista *L){
      if(L->sljedeci==NULL) return EndL(L);
      else
          return L->sljedeci;
}
lista *InitL(lista *L){
      L=new lista;
      L->sljedeci=NULL;
      return L;
}
element PreviousL(element p, lista *L){
               if(p==FirstL(L)) return 0;
               if(p==EndL(L)){  
                     while(L->sljedeci)
                         L=L->sljedeci;
                         }
               else{
                    while(p!=L->sljedeci)
                       L=L->sljedeci;
                    }
               return L;
}
zivotinja RetreiveL(element p, lista *L){
        return p->vrijednost;       
}
int InsertL(zivotinja x, lista *p, lista *L){
               lista *novi;
               if(p>L->sljedeci || p<0) return 0;
               if(p==EndL(L)){
                              while(L->sljedeci)
                                  L=L->sljedeci;
                              novi=new lista;
                              L->sljedeci=novi;
                              novi->sljedeci=NULL;
                              novi->vrijednost=x;  
                              return 1;
                              }  
               else{
                    p=PreviousL(p,L);
                    novi=new lista;
                    novi->sljedeci=L->sljedeci;
                    p->sljedeci=novi;
                    novi->vrijednost=x;
                    return 1;
                    }
}
element NextL(element p, lista *L){
        if(p->sljedeci==NULL) return EndL(L);
        if(p==EndL(L)) return 0;
        else{
             return p->sljedeci;             
             }
}
int DeleteL(element p, lista *L){
    element prethodni, tekuci;
    tekuci=p;
    if(tekuci==EndL(L))return 0;
    if(p==FirstL(L)){
                     L->sljedeci=tekuci->sljedeci;
                     delete tekuci;
                     return 1;
                     }
    else{
         prethodni=PreviousL(tekuci,L);
         prethodni->sljedeci=tekuci->sljedeci;
         delete tekuci;
         return 1;
         }
    return 0;
}
 
 
element LocateL(zivotinja x, lista *L){
        element pozicija=EndL(L);
        pozicija=PreviousL(pozicija,L);
        if(strlen(x.naziv)>0){
        if(EndL(L)!=FirstL(L)){
        while(5){
                 zivotinja sad=RetreiveL(pozicija,L);
                 if(strcmp(x.naziv,sad.naziv)==0)
                        return pozicija;
                 if(pozicija==FirstL(L))break;
                 pozicija=PreviousL(pozicija,L);
                 }
                 }}
        if(strlen(x.vrsta)>0){
        if(EndL(L)!=FirstL(L)){
        while(5){
                 zivotinja sad=RetreiveL(pozicija,L);
                 if(strcmp(x.vrsta,sad.vrsta)==0)
                        return pozicija;
                 if(pozicija==FirstL(L))break;
                 pozicija=PreviousL(pozicija,L);
                 }
                 }}
        return EndL(L);
}
element DeleteAll(lista *L){
        element sad,prijasnji;
        prijasnji=L;
        sad=L->sljedeci;
        while(sad){
                        delete prijasnji;
                        prijasnji=sad;
                        sad=sad->sljedeci;
                        }
        delete prijasnji;
        L=NULL;
        return NULL;
}
void Merge(zivotinja polje[],int i, int k, int j){
   int beg=i, sec=k+1, br=0, vel=j-i+1;
   zivotinja *pomocno=new zivotinja[j-i+1];
   while(beg<=k && sec<=j){
                if(polje[beg].cijena>polje[sec].cijena)
                         pomocno[br++]=polje[beg++];
                else if(polje[beg].cijena<polje[sec].cijena)
                     pomocno[br++]=polje[sec++];
                if(polje[beg].cijena==polje[sec].cijena){
                if(strcmp(polje[beg].naziv,polje[sec].naziv)==1)
                       pomocno[br++]=polje[beg++];
                else
                    pomocno[br++]=polje[sec++];
 
                }
                }
   while(beg<=k)
           pomocno[br++]=polje[beg++];
   while(sec<=j)
                pomocno[br++]=polje[sec++];
   for(int I=0;I<vel;I++)
           polje[i+I]=pomocno[I];
   delete []pomocno;
 
}
void Rec(zivotinja polje[],int i, int j){
     int middle;
     if(i<j){
             middle=(i+j)/2;
             Rec(polje,i,middle);
             Rec(polje,middle+1,j);
            Merge(polje,i,middle,j);
            }    
 
}
void copy(zivotinja polje[],int velicina){
 element sortirana=InitL(sortirana);
 element novi,zadnji;
 zadnji=sortirana;
 for(int i=0; i<velicina;i++){
                      while(zadnji->sljedeci)
                                             zadnji=zadnji->sljedeci;
                      novi=new lista;
                      zadnji->sljedeci=novi;
                      novi->sljedeci=NULL;    
                      novi->vrijednost.sifra=polje[i].sifra;
                      strcpy(novi->vrijednost.naziv,polje[i].naziv);
                      novi->vrijednost.datum[0]=polje[i].datum[0];
                      novi->vrijednost.datum[1]=polje[i].datum[1];
                      novi->vrijednost.datum[2]=polje[i].datum[2];
                      strcpy(novi->vrijednost.vrsta,polje[i].vrsta);
                      novi->vrijednost.cijena=polje[i].cijena;
                      cout<<"Sifra "<<novi->vrijednost.sifra<<endl;
                      cout<<"Naziv "<<novi->vrijednost.naziv<<endl;
                      cout<<"Cijena "<<novi->vrijednost.cijena<<endl;
                      cout<<"Vrsta "<<novi->vrijednost.vrsta<<endl;
                      cout<<"Datum "<<novi->vrijednost.datum[0]<<"."<<novi->vrijednost.datum[1]<<"."<<novi->vrijednost.datum[2]<<"."<<endl;
                      cout<<endl;
 
}
}
void MSort(lista *L,element i, element j){
   if(FirstL(L)!=EndL(L)){
         int velicina=0,br=0;                  
    element zadnji;
    zadnji=L;
    while(zadnji->sljedeci){
                            zadnji=zadnji->sljedeci;   
                           velicina++;                        
                           }
    zivotinja *pomocno=new zivotinja[velicina];
    element lokacija=L->sljedeci;
    while(lokacija){
                              pomocno[br++]=RetreiveL(lokacija,L);
                              lokacija=lokacija->sljedeci;  
 
                                                        }
     Rec(pomocno,0,velicina-1);                                                   
     copy(pomocno,velicina);
    }
   else
     cout<<"Lista ne postoji ili je prazna "<<endl;  
}