#include<iostream>
#include<cstring>
using namespace std;
 
struct lista{
       int sifra;
       char vrsta[20], naziv[30];
       int dan, mj, god;
       float cijena;
       };
 
lista L[100]; 
int sif=1;      
 
//1. Dodavanje zapisa u listu
int InsertL(int c, lista L[]){
    L[c].sifra=sif++;
    if(c!=0) cin.ignore();
    cout<<"Unesi vrstu zivotinje: ";
    cin.getline(L[c].vrsta, 20);
    cout<<"Unesi naziv zivotinje: ";
    cin.getline(L[c].naziv, 30);
    cout<<"Unesi cijenu zivotinje: ";
    cin>>L[c].cijena;
    cout<<"Unesi datum dostave:"<<endl;
    cout<<"Dan: "; cin>>L[c].dan;
    cout<<"Mjesec: "; cin>>L[c].mj;
    cout<<"Godina: "; cin>>L[c].god;
    if(L[c].dan>31 || L[c].dan<1 || L[c].mj<1 || L[c].mj>12 || L[c].god<1993) return 0;
    return 1;
    }
 
//2. Ispis zapisa liste  
void IspisL(int c, lista L[]){
     for(int x=c-1; x>=0; x--){
           cout<<"Sifra: ";
           if(L[x].sifra<10) cout<<"00";
           else if(L[x].sifra<100)cout<<"0";
           cout<<L[x].sifra<<endl; 
           cout<<"Vrsta: "<<L[x].vrsta<<endl; 
           cout<<"Naziv: "<<L[x].naziv<<endl; 
           cout<<"Cijena: "<<L[x].cijena<<endl; 
           cout<<"Datum: "<<L[x].dan<<"."<<L[x].mj<<"."<<L[x].god<<endl; 
           cout<<"---------------------" << endl;
           }  
     }
 
//3. Pretrazivaje liste
int LocateL(int c, lista L[]){
        int bz=0; 
        for(int x=0; x<c; x++){
               if(L[x].god<2012) continue;
               if(L[x].god==2012 && L[x].mj<9) continue;
               if(L[x].mj==9 && L[x].god==2012 && L[x].dan<=23) continue;
               cout<<"Sifra: ";
               if(L[x].sifra<10) cout<<"00";
               else if(L[x].sifra<100)cout<<"0";
               cout<<L[x].sifra<<endl;
               cout<<"Vrsta: "<<L[x].vrsta<<endl;
               cout<<"Naziv: "<<L[x].naziv<<endl;
               cout<<"Cijena: "<<L[x].cijena<<endl;
               cout<<"Datum dostave: "<<L[x].dan<<"."<<L[x].mj<<"."<<L[x].god<<endl;
               cout<<"-----------------------"<<endl;
               bz++;    
               }
        return bz;
     }
 
//4. Brisanje prema nazivu   
int DeleteL(int c, char naziv[], lista L[]){
     int x;
     for(x=0; x<c; x++){
        if(!strcmp(naziv, L[x].naziv)) break;
     }
     if(x==c) return 0;
     for(int i=x; i<c; i++){
        L[i].sifra=L[i+1].sifra;
        strcpy(L[i].vrsta,L[i+1].vrsta);
        strcpy(L[i].naziv,L[i+1].naziv);
        L[i].cijena=L[i+1].cijena;
        L[i].dan=L[i+1].dan;
        L[i].mj=L[i+1].mj;
        L[i].god=L[i+1].god;
     }
     return 1;
}
 
//5. Brisanje prema vrsti  
int DeleteVrstaL(int c, char vrsta[], lista L[]){
     int x;
     for(x=0; x<c; x++){
        if(!strcmp(vrsta, L[x].vrsta)) break;
     }
     if(x==c) return 0;
     for(int i=x; i<c; i++){
        L[i].sifra=L[i+1].sifra;
        strcpy(L[i].vrsta,L[i+1].vrsta);
        strcpy(L[i].naziv,L[i+1].naziv);
        L[i].cijena=L[i+1].cijena;
        L[i].dan=L[i+1].dan;
        L[i].mj=L[i+1].mj;
        L[i].god=L[i+1].god;
     }
     return 1;
}
 
 
//6. Sortiranje merge sort
void Spajanje(lista *L, int i, int k, int j){
     int I=i, J=k+1, K=0;
     lista *A=new lista [j-i+1];
     while(I<=k && J<=j){
                if(L[I].cijena<=L[J].cijena){
                   A[K++]=L[I++];
                   }
                else {
                     A[K++]=L[J++];
                     }
                }//while
     if(I>k) while(J<=j) {
             A[K++]=L[J++];
             }//while
     else while(I<=k) {
             A[K++]=L[I++];
             }//while
     for(int I=0; I<=j-i; I++){
             L[i+I]=A[I];
             }
     }//spajanje
 
void MSort(lista *L, int i, int j){
     if(i<j){
             int k=(i+j)/2;
             MSort(L,i,k);
             MSort(L,k+1,j);
             Spajanje(L,i,k,j);
             }
     }
 
void SortL(int c, lista *L){
     MSort(L,0,c-1);
     cout<<"Lista je uspjesno sortirana!!!"<<endl;
     }