#include<iostream>
using namespace std;
 
struct tzivotinja{
    int sifra, god, mj, dan;
	float cijena;
	char vrsta[40], ime[40];             
};
 
struct zapis{
       tzivotinja zivotinja;
       zapis *sljedeci;
};
typedef zapis *element;
typedef zapis lista;
bool brisiime=0;
element EndL(lista *L){
      return 0;
}
element FirstL(lista *L){
      if(L->sljedeci==NULL) return EndL(L);
      else
          return L->sljedeci;
}
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;
}
 
tzivotinja RetreiveL(element p, lista *L){
        return p->zivotinja;       
}
 
int InsertL(tzivotinja 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->zivotinja=x;  
                      return 1;
                      }  
               else{
                    p=PreviousL(p,L);
                    novi=new lista;
                    novi->sljedeci=L->sljedeci;
                    p->sljedeci=novi;
                    novi->zivotinja=x;
                    return 1;
                    }
}
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(tzivotinja trazi, lista *L){
        element pozicija=EndL(L);
        pozicija=PreviousL(pozicija,L);
 
        if(brisiime==1){
            if(EndL(L)!=FirstL(L)){
                while(true){
                         tzivotinja tmp=RetreiveL(pozicija,L);
                         if(strcmp(trazi.ime,tmp.ime)==0)
                                return pozicija;
                         if(pozicija==FirstL(L))break;
                         pozicija=PreviousL(pozicija,L);
                         }
            }
        }
        if(brisiime==0){                               
            if(EndL(L)!=FirstL(L)){
                while(true){
                         tzivotinja tmp=RetreiveL(pozicija,L);
                         if(strcmp(trazi.vrsta,tmp.vrsta)==0)
                                return pozicija;
                         if(pozicija==FirstL(L))break;
                         pozicija=PreviousL(pozicija,L);
                         }
                }
        }
        return EndL(L);
}
 
tzivotinja RetreiveINT(int p, lista *L){
        lista *tekuci = L->sljedeci; 
        for(int i=0;i<p;i++) tekuci=tekuci->sljedeci;
        return tekuci->zivotinja;        
}
int EndINT(lista *L) {
    lista *tekuci=L;
    int p=0;
    while(tekuci->sljedeci) {
                            tekuci=tekuci->sljedeci;
                            p++;
                            }
    return p;
    }
 
lista *InitL(lista *L){
      L=new lista;
      L->sljedeci=NULL;
      return L;
}
void VratiL(tzivotinja x,int p,lista *L) {
     lista* tekuci=L->sljedeci;
     for(int i=0;i<p;i++) tekuci=tekuci->sljedeci;
     tekuci->zivotinja=x;
     }
 
void Spoji(lista *L,int i, int k, int j) {
     int I=i, J=k+1, K=0;
     tzivotinja  A,B,*POM = new tzivotinja [j-i+1];
 
     while(I<=k && J<=j){
                A=RetreiveINT(I,L);
                B=RetreiveINT(J,L);
 
                if(A.cijena < B.cijena) {
                POM[K++]=A;
                I++; 
                }
 
                else if(A.cijena > B.cijena){
                     POM[K++]=B;
                     J++;
                     }
                else if(strcmp(A.ime,B.ime)==1) {
                     POM[K++]=B;
                     J++;
                     }
                else {
                     POM[K++]=A;
                     I++;
                     }
                }
 
     if(I>k) while(J<=j) { 
             B=RetreiveINT(J++,L);
             POM[K++] = B;
             }
 
     else while(I<=k) {
          A=RetreiveINT(I++,L);
          POM[K++] = A;
          }
 
     for(int I=0;I<=j-i;I++) VratiL(POM[I],i+I,L);
     delete [] POM;
     }
 void Sortiraj(lista *L, int i, int j) {
     if(i<j) {
             int k=(i+j)/2;
             Sortiraj(L,i,k);
             Sortiraj(L,k+1,j);
             Spoji(L,i,k,j);
             }
     }
int MSort(lista *L) {
     Sortiraj(L,0,EndINT(L)-1);
     return 1;
     }