#include <iostream>
 
#include "lista_pokazivaci.h"
//#include "lista_polje.h"
 
using namespace std;
 
int sifra = 1;
 
int dodaj(Lista *lis) {
    animal nova_zivotinja;
    cout << "Unesi ime zivotinje (pocnite velikim slovom): ";
    cin >> nova_zivotinja.naziv;
    cout << "Unesi vrstu: ";
    cin >> nova_zivotinja.vrsta;
    cout << "Unesi datum: ";
    cin >> nova_zivotinja.datum;
    cout << "Unesi cijenu: ";
    cin >> nova_zivotinja.cijena;
    nova_zivotinja.sifra = sifra;
    ++sifra;
 
    return InsertL(nova_zivotinja, EndL(lis), lis);
}
 
void ispis_po_sifri_od_najnovije(Lista *lis) {
    animal zadnja_zivotinja;
    element tekuci = EndL(lis);
 
    if (FirstL(lis) == EndL(lis)) {
        cout << "Lista je prazna. " << endl;
        return;
    }
 
    do {
        tekuci = PreviousL(tekuci, lis);
        zadnja_zivotinja = RetrieveL(tekuci, lis);
 
        cout << "Sifra zivotinje: ";
        cout << zadnja_zivotinja.sifra << endl;
        cout << "Ime zivotinje: ";
        cout <<  zadnja_zivotinja.naziv << endl;
        cout << "Vrsta: ";
        cout <<  zadnja_zivotinja.vrsta << endl;
        cout << "Datum: ";
        cout <<  zadnja_zivotinja.datum << endl;
        cout << "Cijena: ";
        cout <<  zadnja_zivotinja.cijena << endl;
        cout << "================================" << endl;
    } while (zadnja_zivotinja.sifra != RetrieveL(FirstL(lis), lis).sifra);
}
 
void b(Lista *lis) {
    int ukupan_broj = 0;
    if (FirstL(lis) == EndL(lis)) {
        cout << "Lista je prazna." << endl;
        return;
    }
    cout << "================================" << endl;
    animal zivotinja;
    element tekuci = FirstL(lis);  
 
    while (tekuci != EndL(lis)) {
          zivotinja = RetrieveL(tekuci, lis);
        if (zivotinja.datum > "20120923") {
            ukupan_broj++;
            cout << "Sifra zivotinje: ";
            cout << zivotinja.sifra << endl;
            cout << "Ime zivotinje: ";
            cout <<  zivotinja.naziv << endl;
            cout << "Vrsta: ";
            cout <<  zivotinja.vrsta << endl;
            cout << "Datum: ";
            cout <<  zivotinja.datum << endl;
            cout << "Cijena: ";
            cout <<  zivotinja.cijena << endl;
            cout << "================================" << endl;
 
        }       
 
        tekuci = NextL(tekuci, lis);
    }  
    cout << "Ukupno je " << ukupan_broj << " dodanih tada.";
    cout << endl;
}
 
int c_po_nazivu(Lista *lis) {
    if (FirstL(lis) == EndL(lis)) {
        cout << "Lista je prazna " << endl;
        return 0;
    }
 
    string naziv;
    cout << "Naziv zivotinje za brisanje: ";
    cin >> naziv;
 
    animal zivotinja;
    element tekuci = FirstL(lis);  
 
    while (tekuci != EndL(lis)) {
         zivotinja = RetrieveL(tekuci, lis);
        if (zivotinja.naziv == naziv) {
 
            DeleteL(LocateL(zivotinja, lis), lis);  
            tekuci = FirstL(lis);        
        }
        else { 
            tekuci = NextL(tekuci, lis);
        }
    }
    return 1;
}
 
int c_po_vrsti(Lista *lis) {
    if (FirstL(lis) == EndL(lis)) {
        cout << "Lista je prazna " << endl;
        return 0;
    }
 
    string naziv;
    cout << "Vrsta zivotinje za brisanje: ";
    cin >> naziv;
 
    animal zivotinja;
    element tekuci = FirstL(lis);  
    element za_brisanje;
 
    while (tekuci != EndL(lis)) {
         zivotinja = RetrieveL(tekuci, lis);
        if (zivotinja.vrsta == naziv) {
            za_brisanje = tekuci;
            DeleteL(za_brisanje, lis);   
            tekuci = FirstL(lis);          
        }
        else { 
            tekuci = NextL(tekuci, lis);
        }
    }
    return 1;
 
}
 
void mergesort_po_nazivu(animal polje[], int left, int right) {
    int middle = (left + right) / 2;
    animal temp;
    if (right - left == 1) { 
        if (polje[right].naziv > polje[left].naziv) {
            temp = polje[right];
            polje[right] = polje[left];
            polje[left] = temp;
            return;
        }
    }    
    else if (right == left) { 
        return;
    }
    else { 
        mergesort_po_nazivu(polje, left, middle);
        mergesort_po_nazivu(polje, middle +1, right);
 
        int size_pomocno = right-left +1;
        animal *polje_pomocno = new animal[size_pomocno];
        int l = left;
        int s = middle +1;
 
        for (int i = 0; i < size_pomocno; i++) {
            if (l == middle+1) { 
                polje_pomocno[i] = polje[s]; s++;
                continue;
            }
            if (s == right +1) { 
                polje_pomocno[i] = polje[l]; l++;
                continue;
            }
 
            if (polje[l].naziv > polje[s].naziv) {
                polje_pomocno[i] = polje[l];
                l++;
            }
            else {
                polje_pomocno[i] = polje[s];
                s++;
            }
        } 
 
        int j = 0;
        for (int i = left; i <= right; i++) {
            polje[i] = polje_pomocno[j]; j++;
        }
    }
}
 
 
void mergesort_po_cijeni(animal polje[], int left, int right) {
    int middle = (left + right) / 2;
    animal temp;
    if (right - left == 1) { 
        if (polje[right].cijena > polje[left].cijena) {
            temp = polje[right];
            polje[right] = polje[left];
            polje[left] = temp;
            return;
        }
    }    
    else if (right == left) { 
        return;
    }
    else { 
        mergesort_po_cijeni(polje, left, middle);
        mergesort_po_cijeni(polje, middle +1, right);
 
        int size_pomocno = right-left +1;
        animal *polje_pomocno = new animal[size_pomocno];
        int l = left;
        int s = middle +1;
 
        for (int i = 0; i < size_pomocno; i++) {
            if (l == middle+1) { 
                polje_pomocno[i] = polje[s]; s++;
                continue;
            }
            if (s == right +1) { 
                polje_pomocno[i] = polje[l]; l++;
                continue;
            }
 
            if (polje[l].cijena > polje[s].cijena) {
                polje_pomocno[i] = polje[l];
                l++;
            }
            else {
                polje_pomocno[i] = polje[s];
                s++;
            }
        } 
 
        int j = 0;
        for (int i = left; i <= right; i++) {
            polje[i] = polje_pomocno[j]; j++;
        }
    }
}
 
void d(Lista *lis) {
    int n = 0;
    element temp = FirstL(lis);
    while (temp != EndL(lis)) {
        ++n;
        temp = NextL(temp, lis);
    }
 
    animal *polje = new animal[n];
 
    temp = FirstL(lis);
    for (int i = 0; temp != EndL(lis); i++) {
        polje[i] = RetrieveL(temp, lis);
        temp = NextL(temp, lis);
    }
    cout << "Sortiramo po nazivu." << endl;
    cout << endl;
    mergesort_po_nazivu(polje, 0, n-1);
    for (int i = 0; i < n; i++) {
 
        cout << "Sifra zivotinje: ";
        cout << polje[i].sifra << endl;
        cout << "Ime zivotinje: ";
        cout <<  polje[i].naziv << endl;
        cout << "Vrsta: ";
        cout <<  polje[i].vrsta << endl;
        cout << "Datum: ";
        cout <<  polje[i].datum << endl;
        cout << "Cijena: ";
        cout <<  polje[i].cijena << endl;
        cout << "================================" << endl;
    }
    cout << endl;
 
    DeleteAll(lis);
    for (int i = 0; i < n; i++) {
        InsertL(polje[i], EndL(lis), lis);
    }
 
    cout << "Lista sortirana po cijeni zivotinje: " << endl;
    cout << endl;
    mergesort_po_cijeni(polje, 0, n-1);
    for (int i = 0; i < n; i++) {
 
        cout << "Sifra zivotinje: ";
        cout << polje[i].sifra << endl;
        cout << "Ime zivotinje: ";
        cout <<  polje[i].naziv << endl;
        cout << "Vrsta: ";
        cout <<  polje[i].vrsta << endl;
        cout << "Datum: ";
        cout <<  polje[i].datum << endl;
        cout << "Cijena: ";
        cout <<  polje[i].cijena << endl;
        cout << "================================" << endl;
    }
    cout << endl;
 
    DeleteAll(lis);
    for (int i = 0; i < n; i++) {
        InsertL(polje[i], EndL(lis), lis);
    }
 
}
 
int main() {
 
    animal a;
    a.sifra = sifra; sifra++;
    a.naziv = "Kodi";
    a.vrsta = "pas";
    a.datum = "20111005"; 
    a.cijena = 7000;
 
    Lista popis;
    InitL(&popis);
 
    InsertL(a, EndL(&popis), &popis);
 
    a.sifra = sifra; sifra++;
    a.naziv = "Friki";
    a.vrsta = "macka";
    a.datum = "20121023";
    a.cijena = 300;
 
    InsertL(a, EndL(&popis) , &popis);
 
    a.sifra = sifra; sifra++;
    a.naziv = "Dona";
    a.vrsta = "pas";
    a.datum = "19990214";
    a.cijena = 9543;
    InsertL(a, EndL(&popis) , &popis);
 
    a.sifra = sifra; sifra++;
    a.naziv = "Mrvica";
    a.vrsta = "zec";
    a.datum = "20040313";
    a.cijena = 574;
    InsertL(a, EndL(&popis) , &popis);
 
    a.sifra = sifra; sifra++;
    a.naziv = "Brza";
    a.vrsta = "kornjaca";
    a.datum = "20130414";
    a.cijena = 378;
    InsertL(a, EndL(&popis) , &popis);
 
    ispis_po_sifri_od_najnovije(&popis);
 
    dodaj(&popis);
    cout << "================================" << endl;
    dodaj(&popis);
    cout << "================================" << endl;
 
    ispis_po_sifri_od_najnovije(&popis);
    cout << "===== Slijedi ispis zivotinja dodanih nakon 23.9.2012. =====";
    cout << endl;
 
    b(&popis);
 
    cout << endl;
    c_po_nazivu(&popis);
    cout << "===== Ispis nakon brisanja po nazivu =====" << endl;
    cout << endl;
    ispis_po_sifri_od_najnovije(&popis);
 
    cout << endl;
    c_po_vrsti(&popis);
    cout << "===== Ispis nakon brisanja po vrsti =====" << endl;
    cout << endl;
    ispis_po_sifri_od_najnovije(&popis);
 
    cout << endl;
    cout << "===== Merge sort. =====" << endl;
    d(&popis);
 
 
    system ("pause");
    return 0;
}