#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
3. (25p) Napisati program koji učitava podatke o broju rođenih beba, dečaka i devojčica po
mesecima u jednom gradu i smešta ih u listu. podaci se u fajlu nalaze u obliku: mesec godina broj
rođenih dečaka i broj rođenih devojčica, svi podaci su razdvojeni spejsom. Primer: 2 2018 120 150 (u
februaru 2018. rođeno je 120 dečaka i 150 devojčica).
Napraviti meni sa interakciju preko konzole sa slededim opcijama.
a) (7p) učitavanje podataka, unosi se naziv fajla koji sadrži opisane podatke i učitava se u listu
uređenu nerastuce po godini i mesecu,
b) (8p) ispis broja meseci u kome je rođeno više od određenog broja dece, unosi se broj i treba
ispisati koliko ima meseci u kojima je ukupan broj rođenih vedi od unetog broja, ovu funkcionalnost
je potrebno implementirati na dva načina, iterativno i rekurzivno,
c) (10p) ispis broja rođenih dečaka i devojčica u jednoj godini sortirano po ukupnom broju rođenih,
posmatra se broj rođenih u jednoj godini i ispisuje se broj rođenih dečaka, broj rođenih devojčica i
godina sortirano po ukupnom broju rođenih u godini (dozvoljeno je praviti nove strukture podataka).
*/

typedef struct Beba Beba;

struct Beba {
    int mesec, godina, brm, brz;
    Beba *sl;
};

char buffer[1000];  // privremeni spremnik za citanje sa standardnog ulaza

int meni() {
    int op = 0;
    printf("Meni: \n");
    printf("1: Ucitavanje podataka\n");
    printf("2: Ispis broja meseci limitirano\n");
    printf("3: Ispis broja rodjenih sortirano\n");
    printf("4: Izlaz\n");

    while(op < 1 || op > 4) {
        printf("Unesite opciju: ");
        gets(buffer);
        op = atoi(buffer);
    }

    return op;
}

Beba *napravi(int mesec, int godina, int brm, int brz) {
    Beba *t = calloc(1, sizeof *t);
    t->mesec = mesec;
    t->godina = godina;
    t->brm = brm;
    t->brz = brz;
    return t;
}

Beba *ucitavanje() {
    FILE *f;
    printf("Unesite naziv datoteke: ");
    gets(buffer);
    f = fopen(buffer, "r");

    // Ako je f NULL, ne mozemo da citamo
    if(!f) {
        printf("Datoteka sa unetim nazivom ne moze biti otvorena za citanje.\n");
        return NULL;
    }
    else {
        Beba *l = NULL;  // pocetak liste
        int m, g, brm, brz;  // mesec, godina, broj muske i broj zenske dece

        while(fscanf(f, "%d%d%d%d", &m, &g, &brm, &brz) == 4) {
            Beba *n = napravi(m, g, brm, brz);
            // Ako je lista prazna, dodajemo novi element na pocetak
            if(!l) {
                l = n;
            }
            else {
                // Provera da li treba da se doda na pocetak (po godini i mesecu)
                if(l->godina < n->godina || (l->godina == n->godina && l->mesec < n->mesec)) {
                    n->sl = l;
                    l = n;
                }
                else {
                    // Ako ne treba na pocetak, onda treba da se doda dublje u listu
                    Beba *tmp = l;
                    // Trazimo odgovarajuce mesto
                    while(tmp->sl && (tmp->sl->godina > n->godina ||
                                      (tmp->sl->godina == n->godina && tmp->sl->mesec > n->mesec))) {
                        tmp = tmp->sl;
                    }
                    // Dodajemo n tako da bude tmp->n->sl
                    n->sl = tmp->sl;
                    tmp->sl = n;
                }
            }
        }
        // Obavezno zatvoriti datoteku!
        fclose(f);
        return l;
    }
}
// Vraca ukupan broj meseci iterativno
int broj_meseci_it(Beba *l, int d) {
    Beba *t = l;
    int ukupno = 0;

    while(t) {
        if(t->brm + t->brz > d) {
            ukupno ++;
        }

        t = t->sl;
    }

    return ukupno;
}
// Vraca ukupan broj meseci rekurzivno
int broj_meseci_rek(Beba *l, int d) {
    if(!l) return 0;
    // Ovaj skraceni zapis znaci: izracunaj broj meseci u ostatku liste i dodaj:
                            // - Ako je granicni uslov ispunjen: 1
                            // - Ako granicni uslov nije ispunjen: 0
    return broj_meseci_rek(l->sl, d) + (l->brm + l->brz > d ? 1 : 0);
}

// Pomocna funkcija koja poziva i broj_meseci_it i broj_meseci_rek u jednom
void broj_meseci(Beba *l) {
    int d;
    printf("Unesite najmanji broj dece za pretragu: ");
    gets(buffer);
    d = atoi(buffer);
    printf("Broj meseci sa vise od %d rodjene dece (it): %d\n", d, broj_meseci_it(l, d));
    printf("Broj meseci sa vise od %d rodjene dece (rek): %d\n", d, broj_meseci_rek(l, d));
}

void sortirano(Beba *l) {
    // Za novu pomocnu listu l2 mozemo koristiti istu strukturu podataka, samo zanemariti mesec
    Beba *l2 = NULL, *tmp;

    // za svaki unos
    for(tmp = l; tmp; tmp = tmp->sl)
    {
        int postoji = 0;

        // Vidi da li unos sa tom godinom vec postoji u l2, ako postoji preskoci
        for(Beba *tmp2 = l2; !postoji && tmp2; tmp2 = tmp2->sl)
        {
            if(tmp->godina == tmp2->godina) {
                postoji = 1;
            }
        }

        if(!postoji) {
            // Ako ne postoji, prebroj ukupan broj unosa za tu godinu u celoj listi l i dodaj u l2
            // um i uz su privremeni brojaci za ukupan broj muske i zenske dece u toj godini
            int um = 0, uz = 0;

            // Dovoljno je da proveravamo od tmp, jer u svim prethodnim elementima liste l se nije pojavila ta godina
            for(Beba *tmp2 = tmp; tmp2; tmp2 = tmp2->sl) {
                if(tmp2->godina == tmp->godina) {
                    um += tmp2->brm;3
                    uz += tmp2->brz;
                }
            }

            // Napravi cvor i umetni ga u listu, po slicnom principu kao u unosu
            Beba *n = napravi(0, tmp->godina, um, uz);

            if(!l2) {
                l2 = n;
            }
            else {
                if(l2->brm + l2->brz > n->brm + n->brz) {
                    n->sl = l2;
                    l2 = n;
                }
                else {
                    Beba *tmp2 = l2;

                    while(tmp2->sl && tmp2->sl->brm + tmp2->sl->brz < n->brm + n->brz) {
                        tmp2 = tmp2->sl;
                    }

                    n->sl = tmp2->sl;
                    tmp2->sl = n;
                }
            }
        }
    }

    // Odmah ispisujemo listu l2 i ujedno je brisemo
    tmp = l2;

    while(tmp) {
        printf("Godina %d. decaka: %d, devojcica: %d\n", tmp->godina, tmp->brm, tmp->brz);
        tmp = tmp->sl;
        free(l2);
        l2 = tmp;
    }
}

int main() {
    int op = meni();
    Beba *l = 0;

    while(1) {
        switch(op) {
            case 1: {
                    // U normalnim okolnostima bismo prvo obrisali listu
                    // mada se to nije trazilo na ispitu (i nije uradjeno ovde)!
                    l = ucitavanje();
                    break;
                }

            case 2: {
                    broj_meseci(l);
                    break;
                }

            case 3: {
                    sortirano(l);
                    break;
                }

            case 4: {
                    Beba *tmp = l;
                    // Ispis (provera ucitavanja) i brisanje liste
                    while(tmp) {
                        printf("%d.%d. decaka: %d, devojcica: %d\n", tmp->mesec, tmp->godina, tmp->brm, tmp->brz);
                        l = tmp->sl;
                        free(tmp);
                        tmp = l;
                    }

                    return 0;
                }
        }
        op = meni();
    }
}