#include <iostream>
 
using namespace std;
 
struct ljubimci_pok{
	int sifra, cijena;
	string naziv, vrsta, datum_dostave;
 
	ljubimci_pok *slijedeci;
};
 
int unos(ljubimci_pok *glv,     //potrebna glava liste
	int zifra, int cijena, 
	string datum_dostave, 
	string naziv, 
	string vrsta)
{
 
	ljubimci_pok *novi=new ljubimci_pok;
 
	novi->cijena=cijena;		//pridru�¾ujemo unesene podatke podatkovnom dijlu ��vora
	novi->sifra = zifra;
	novi->vrsta=vrsta;
	novi->naziv=naziv;
	novi->datum_dostave=datum_dostave;
 
	if(glv->slijedeci==NULL)	//ako je lista prazna dodaj novi zapis na prvo mjesto
	{
		glv->slijedeci=novi;
		novi->slijedeci=NULL;
	}
 
	else
	{	//ako lista nije prazna dodaj novi zapis na pocetak liste
		novi->slijedeci=glv->slijedeci;
		glv->slijedeci=novi;
	}
 
	ljubimci_pok *trenutni=glv->slijedeci;
	while(trenutni->slijedeci!=NULL && trenutni->sifra!=zifra)
		trenutni=trenutni->slijedeci;
 
	if (trenutni->slijedeci==NULL && trenutni->sifra!=zifra)		//ako ova funkcija ne mo�¾e na��i zapis onda stvarno ne znam tko mo�¾e
	{
		return 0;
	}
 
	else
	{
		return 1;
	}
}
 
void ispis(ljubimci_pok *glv)   
{
	if(glv->slijedeci == NULL)		//ako je lista prazna
	{
		cout << "\nNema ljubimaca u listi, prvo dodaj neke.\n";
		return;
	}
 
	ljubimci_pok *trenutni=glv->slijedeci;
 
	cout << "\nUneseni su sljedeci ljubimci:\n\n";
 
	while(trenutni!=NULL){	
		cout << "\nSifra: " << trenutni->sifra;
		cout << "\nVrsta: " << trenutni->vrsta;
		cout << "\nNaziv: " << trenutni->naziv;
		cout << "\nCijena: " << trenutni->cijena;
		cout << "\nDatum dostave: " << trenutni->datum_dostave << "\n-----------------------\n\n";
		trenutni=trenutni->slijedeci; //pomicanje kroz listu
	}
}
 
void trazi(ljubimci_pok *glv)
{
	int dan, mjesec, godina, brojalo=0;
	string temp;
 
	ljubimci_pok *trenutni=glv->slijedeci;
 
	if(trenutni == NULL)		//ako je lista prazna
	{
		cout << "\nNema ljubimaca listi, prvo dodaj neke.\n";
		return;
	}
 
	while(trenutni!=NULL)
	{
		temp=trenutni->datum_dostave.substr(0,2);
		dan=atoi(temp.c_str());
		temp=trenutni->datum_dostave.substr(3,2);
		mjesec=atoi(temp.c_str());
		temp=trenutni->datum_dostave.substr(6,4);
		godina=atoi(temp.c_str());
 
		if((dan>=23 && mjesec>=9 && godina>=2012) || (mjesec>9 && godina>=2012)) //provjera da li je ljubimac dostavljen nakon 23.rujna 2012
		{
			cout << "\nSifra: " << trenutni->sifra;
			cout << "\nVrsta: " << trenutni->vrsta;
			cout << "\nNaziv: " << trenutni->naziv;
			cout << "\nCijena: " << trenutni->cijena;
			cout << "\nDatum dostave: " << trenutni->datum_dostave << "\n------------------------\n\n";
			brojalo++;
		}
		trenutni=trenutni->slijedeci;
	}
 
	cout << "Postoji u bazi podataka " << brojalo << " zivotinja koje su dostavljene nakon 23.rujna 2012.\n\n";
}
 
int brisi_naziv(ljubimci_pok *glv, string ime)
{
	ljubimci_pok *prethodni=glv;
	ljubimci_pok *trenutni=glv->slijedeci;
	int brojalo=0;
 
	while (trenutni->slijedeci!=NULL)
	{
		if(trenutni->naziv==ime)
		{
			prethodni->slijedeci=trenutni->slijedeci;
			free(trenutni);
			brojalo++;
			break;
		}
		prethodni=trenutni;
		trenutni=trenutni->slijedeci;
	}
 
	if (brojalo==0)
	{
		cout << "\nTrazeni zapis nije nadjen u listi.\n";
		return 3;	//nema smisla traziti da li je "brisanje" uspjesno ako nista ne brise (dio ispod return 1 ili 0)
	}
 
	trenutni=glv->slijedeci;
	while(trenutni->slijedeci!=NULL && trenutni->naziv!=ime)
		trenutni=trenutni->slijedeci;
 
	if(trenutni->slijedeci==NULL && trenutni->naziv!=ime)
		return 1;
 
	else
		return 0;
}
 
int brisi_vrstu(ljubimci_pok *glv, string ime)
{
	ljubimci_pok *prethodni=glv;
	ljubimci_pok *trenutni=glv->slijedeci;
	int brojalo=0;
 
	while (trenutni->slijedeci!=NULL)
	{
		if(trenutni->vrsta==ime)
		{
			prethodni->slijedeci=trenutni->slijedeci;
			free(trenutni);
			brojalo++;
			trenutni=glv;
		}
		prethodni=trenutni;
		trenutni=trenutni->slijedeci;
	}
 
	if (brojalo==0)
	{
		cout << "\nTrazeni zapis nije nadjen u listi.\n";
		return 3;	//nema smisla traziti da li je "brisanje" uspjesno ako nista ne brise (dio ispod - return 1 ili 0)
	}
 
	trenutni=glv->slijedeci;
	while(trenutni->slijedeci!=NULL && trenutni->vrsta!=ime)
		trenutni=trenutni->slijedeci;
 
	if (trenutni->slijedeci==NULL && trenutni->vrsta!=ime)
		return 1;
	else
		return 0;
}
 
int cmp(ljubimci_pok *a, ljubimci_pok *b)
{
	return a->cijena - b->cijena;
}
 
ljubimci_pok *m_sort(ljubimci_pok *lista) 
{
	ljubimci_pok *p, *q, *e, *rep;
	int psize, insize, nmerges, qsize, i;
 
	insize=1;
 
	while(1) 
	{
		p=lista;
		lista=NULL;
		rep=NULL;
 
		nmerges=0;
 
		while (p)
		{
			nmerges++;
			q=p;
			psize=0;
			for (i=0; i<insize; i++)
			{
				psize++;
				q=q->slijedeci;
				if (!q) break;
			}
			qsize=insize;
 
			while (psize>0 || (qsize>0 && q))
			{
				if (psize==0)
				{
					e=q; q=q->slijedeci; qsize--;
				}
				else if (qsize==0 || !q)
				{
					e=p; p=p->slijedeci; psize--;
				}
				else if (cmp(p,q) <=0)
				{
					e=p; p=p->slijedeci; psize--;
				}
				else
				{
					e=q; q=q->slijedeci; qsize--;
				}
 
				if (rep)
				{
					rep->slijedeci=e;
				}
				else
				{
					lista=e;
				}
				rep=e;
			}
			p=q;
		}
		rep->slijedeci=NULL;
 
		if (nmerges<=1)
		{
			return lista;
		}
		insize *= 2;
	}
}