#include <iostream>
#include <string>
using namespace std;
// #include "lista_polje.h"
#include "lista_pokazivac.h"
 
 
 
int dodaj(int sifra, Lista *zivotinje){
    zivotinja nova;
    nova.sifra = sifra;
    cout << "Unesi naziv zivotinje: ";
    cin >> nova.naziv;
    cout << "Unesi vrstu: ";
    cin >> nova.vrsta;
    cout << "Unesi cijenu: ";   
    cin >> nova.cijena;
    cout << "Unesi datum: ";
    cin >> nova.datum;
    // buduci da InsertL vraca 0 ili 1, mi to samo proslijedimo
    // tamo odakle je pozvan dodaj()
    return InsertL(nova, EndL(zivotinje), zivotinje);
}
 
 
void ispis(Lista *zivotinje) {
    element temp;
    zivotinja tmp;
    cout << endl;
    cout << "sifra\t naziv\t vrsta \t cijena \t datum" << endl;
    cout << "_________________________________________________________________" << endl;
 
    temp = EndL(zivotinje);
    do {    
        temp = PreviousL(temp, zivotinje);
        tmp = RetrieveL(temp, zivotinje);
 
        cout << tmp.sifra << "\t" << tmp.naziv << "\t" << tmp.vrsta << "\t" << tmp.cijena << "\t" << tmp.datum << endl;
    } while (temp != FirstL(zivotinje));
}
 
 
void pretrazi(Lista *zivotinje) {
     cout << endl;
    cout << "Pretrazujemo listu za novijim zivotinjama." << endl;
    element temp;
    zivotinja tmp;
 
    temp = FirstL(zivotinje);
 
    do {
        tmp = RetrieveL(temp, zivotinje);        
        if (tmp.datum > 20120923) {
            cout << "Naziv: " << tmp.naziv << ", datum: ";
            cout << tmp.datum << endl;
        }
        temp = NextL(temp, zivotinje);
    } while(temp != EndL(zivotinje));
}
 
 
 
int brisi_naziv(string naziv, Lista *zivotinje) {
    element temp, prethodni;
    zivotinja tmp;
 
    int brisanje = 0;
 
    temp = FirstL(zivotinje);
    do {
        tmp = RetrieveL(temp, zivotinje);
        if (tmp.naziv == naziv) {
            prethodni = PreviousL(temp, zivotinje);
            DeleteL(temp, zivotinje);
            brisanje = 1;
            temp = prethodni;
        }
        temp = NextL(temp, zivotinje);
 
    } while(temp != EndL(zivotinje));
 
    return brisanje;
} 
 
int brisi_vrsta(string vrsta, Lista *zivotinje) {
    element temp, prethodni;
    zivotinja tmp;
 
    int brisanje = 0;
 
    temp = FirstL(zivotinje);
    do {
        tmp = RetrieveL(temp, zivotinje);
        if (tmp.vrsta == vrsta) {
            prethodni = PreviousL(temp, zivotinje);
            DeleteL(temp, zivotinje);
            brisanje = 1;
            temp = prethodni;
        }
        temp = NextL(temp, zivotinje);
 
    } while(temp != EndL(zivotinje));
 
    return brisanje;
} 
 
 
 
void merge_2(zivotinja polje[], int lijevi, int desni) {
    int sredina = (lijevi + desni) / 2;
    zivotinja temp;
 
    if (desni - lijevi == 1) { // polje od 2 elem
        if (polje[desni].cijena > polje[lijevi].cijena) {
            temp = polje[desni];
            polje[desni] = polje[lijevi];
            polje[lijevi] = temp;
            return;
        }
    }    
    else if (desni == lijevi) { // polje od 1 el
        return;
    }
    else { 
        // rekurzija
        merge_2(polje, lijevi, sredina);
        merge_2(polje, sredina +1, desni);
        // spajanje dijelova
        int size_pomocno = desni-lijevi +1;
        zivotinja *polje_pomocno = new zivotinja[size_pomocno];
        int l = lijevi;
        int s = sredina +1;
 
        for (int i = 0; i < size_pomocno; i++) {
            if (l == sredina+1) { // sad samo s vadi
                polje_pomocno[i] = polje[s]; s++;
                continue;
            }
            if (s == desni +1) { // samo l vadi)
                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++;
            }
        } 
        // iz pomocnog iskopiraj u glavno, obrisi pomocno
        int j = 0;
        for (int i = lijevi; i <= desni; i++) {
            polje[i] = polje_pomocno[j]; j++;
        }
        // delete polje_pomocno; // kvar!
 
    }
 
}
 
 
void merge_1(zivotinja polje[], int lijevi, int desni) {
    int sredina = (lijevi + desni) / 2;
    zivotinja temp;
    if (desni - lijevi == 1) { // polje od 2 elem
        if (polje[desni].naziv > polje[lijevi].naziv) {
            temp = polje[desni];
            polje[desni] = polje[lijevi];
            polje[lijevi] = temp;
            return;
        }
    }    
    else if (desni == lijevi) { // polje od 1 el
        return;
    }
    else { 
        // rekurzija
        merge_1(polje, lijevi, sredina);
        merge_1(polje, sredina +1, desni);
        // spajanje dijelova
        int size_pomocno = desni-lijevi +1;
        zivotinja *polje_pomocno = new zivotinja[size_pomocno];
 
        int l = lijevi;
        int s = sredina +1;
 
        for (int i = 0; i < size_pomocno; i++) {
            if (l == sredina+1) { // sad samo s vadi
                polje_pomocno[i] = polje[s]; s++;
                continue;
            }
            if (s == desni +1) { // samo l vadi)
                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++;
            }
        } 
        // iz pomocnog iskopiraj u glavno, obrisi pomocno
        int j = 0;
        for (int i = lijevi; i <= desni; i++) {
            polje[i] = polje_pomocno[j]; j++;
        }
 
    }
}
 
int main() {
 
    zivotinja prva, druga, treca, cetvrta, peta;
    prva.cijena = 100;
    prva.sifra = 1;
    prva.naziv = "Newfoundler";
    prva.vrsta = "pas";
    prva.datum = 20121010;  // YYYYMMDD
 
    Lista zivotinje;
    InitL(&zivotinje);
 
    InsertL(prva, EndL(&zivotinje), &zivotinje);
 
    druga.cijena = 5000000;
    druga.sifra = 2;
    druga.naziv = "Lav";
    druga.vrsta = "divlja macka";
    druga.datum = 20100505; 
 
    InsertL(druga, EndL(&zivotinje), &zivotinje);
 
    treca.cijena = 50000;
    treca.sifra = 3;
    treca.naziv = "Pangolin";
    treca.vrsta = "mravojed";
    treca.datum = 20121105; 
 
    InsertL(treca, EndL(&zivotinje), &zivotinje);
 
    cetvrta.cijena = 123;
    cetvrta.sifra = 4;
    cetvrta.naziv = "Russian blue";
    cetvrta.vrsta = "macka";
    cetvrta.datum = 20121511; 
 
    InsertL(cetvrta, EndL(&zivotinje), &zivotinje);
 
    peta.cijena = 21;
    peta.sifra = 5;
    peta.naziv = "Tigar";
    peta.vrsta = "divlja macka";
    peta.datum = 20110105; 
 
    InsertL(peta, EndL(&zivotinje), &zivotinje);
 
    int sifra = 6;
 
    int rezultat = dodaj(sifra, &zivotinje);
    if (rezultat == 1) {
        cout << "Zivotinja uspjesno dodana." << endl;
        sifra++;
    }
    else {
        cout << "Neuspjelo dodavanje." << endl;
    }
 
    // druga funkcija: ispis liste unatrag
    ispis(&zivotinje);
    // treca funkcija: pretrazivanje za datumom > 23.09.2012.
    pretrazi(&zivotinje);
 
    // cetvrta funkcija: brisanje po nazivu
    cout << endl;
    cout << "Naziv zivotinje koju zelite obrisati: ";
    string naziv;
    cin >> naziv;
    if (brisi_naziv(naziv, &zivotinje) == 0) {
        cout << "Brisanje nije uspjelo (nepostojeca zivotinja?)" << endl << endl;
    }
    // ispisemo listu da vidimo radi li brisanje
    ispis(&zivotinje);
    cout << endl;
 
    // peta funkcija: brisanje po vrsti
    cout << endl;
    cout << "Vrstu zivotinje koju zelite obrisati: ";
    string vrsta;
    cin >> vrsta;
    if (brisi_vrsta(vrsta, &zivotinje) == 0) {
        cout << "Brisanje nije uspjelo (nepostojeca zivotinja?)" << endl << endl;
    }
    // ispisemo listu da vidimo radi li brisanje
    ispis(&zivotinje);
    cout << endl;
 
    // sortiranje
    // prvo ucitamo cijelu listu u jedno polje.
    // da bismo to mogli, moramo prebrojati koliko je el. u listi.
    element temp;
    zivotinja tmp;
    temp = FirstL(&zivotinje);
    int broj = 0;
    while (temp != EndL(&zivotinje)) {
        temp = NextL(temp, &zivotinje);
        ++broj;
    }
 
    // stvorimo polje!
    zivotinja *polje_zivotinje = new zivotinja[broj];
 
    // citamo iz liste, spremamo u polje
    temp = FirstL(&zivotinje);
    for (int i = 0; i < broj; ++i) {
        tmp = RetrieveL(temp, &zivotinje);
        temp = NextL(temp, &zivotinje);
        polje_zivotinje[i] = tmp;
    }
    // sad mozemo sortirati polje!
 
    merge_1(polje_zivotinje, 0, broj-1); // sort po nazivu
    cout << endl;
    cout << endl << "Ispisujemo sortirani sadrzaj liste (po nazivu)." << endl;
    for (int i = 0; i < broj; i++) {
        cout << polje_zivotinje[i].naziv << endl;
    }
 
    merge_2(polje_zivotinje, 0, broj-1); // po cijeni
    cout << endl;
    cout << endl << "Ispisujemo sortirani sadrzaj liste (po cijeni)." << endl;
    for (int i = 0; i < broj; i++) {
        cout << polje_zivotinje[i].naziv << " " << polje_zivotinje[i].cijena << endl;
    }   
 
    system("pause");
    return 0;
}