//lista pokazivac
#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)) || (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;
	}
}