#include<iostream>
using namespace std;
 
struct tzivotinja{
    int sifra, god, mj, dan;
	float cijena;
	char vrsta[40], ime[40];             
};
typedef int element;
struct zapis{
       tzivotinja zivotinja[100];
       int kursor;
};
typedef struct zapis lista;
bool brisiime=0;
element LastL(lista *L){
    return (L->kursor);
}
 
element EndL(lista *L){
    return (L->kursor);
}
element FirstL(lista *L){
          if(L->kursor==0) 
                  return EndL(L); 
           else 
                return 0;      
}
tzivotinja RetreiveL(element p, lista *L){
        return L->zivotinja[p];
}
element InsertL(tzivotinja x,element p,lista *L){
          if(p>L->kursor || p<0) return 0;
              else{
                 for( int q=L->kursor;q>=p;q--)
                      L->zivotinja[q+1]=L->zivotinja[q];
                 L->kursor++;
                 L->zivotinja[p]=x;
                 return 1;  }  
}
element NextL(element p, lista *L){
        if(p==EndL(L)-1) return EndL(L);
        if(p==EndL(L)) return 0;
        else 
             return p+1;
}
element PreviousL(element p, lista *L){
        if(p==FirstL(L)) return -1;
        if(p==EndL(L)) return p-1;
        return p-1;       
}
element LocateL(tzivotinja trazi, lista *L){
        element pozicija=EndL(L);
        pozicija=PreviousL(pozicija,L);
 
        if(brisiime==1){
            if(FirstL(L)!=EndL(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(FirstL(L)!=EndL(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);
}
element DeleteL(element p, lista *L){
    if((L->kursor==0))
         return 0;
     if((p>=L->kursor)||(p<0))
         return 0;
       if(p==EndL(L))
                      return 0;   
       if(p==FirstL(L)){
          L->kursor--;
         for( int i=p; i<L->kursor; i++)
              L->zivotinja[i]=L->zivotinja[i+1];
         return 1;
                        }
    else{
         L->kursor--;
         for( int i=p; i<L->kursor; i++)
              L->zivotinja[i]=L->zivotinja[i+1];
         }
     return 1;    
}
lista *InitL(lista *L){
      L=new lista;
      L->kursor=0;
      return L;
}
void VratiL(tzivotinja x,int p,lista *L) {
     L->zivotinja[p]=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=RetreiveL(I,L);
                B=RetreiveL(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=RetreiveL(J++,L);
             POM[K++] = B;
             }
 
     else while(I<=k) {
          A=RetreiveL(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,EndL(L)-1);
     return 1;
     }