//sa nu uit sa modific la nume cu strcpy
#include <iostream>
#include "schelet1.h"

/* TODO
* de inlocuit implementarile cu cele scrise de mana pentru
* lista, stiva, coada (numai cele necesare)
*/

#include <list>
#include <stack>
#include <queue>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

/**/
using namespace std;
////////////////////////ARBORE/////////////////////////
Nod* rad_arbore = NULL;


//capetele de la liste
Nod* cap_supermarket;
Nod* cap_to_buy;
Nod* cap_bought;
//int nr1,nr2;

//cerinte
int C[NR_CERINTE];
int buget;
//din propunere: scoatem
//char* nume_arbore;
//char* categorie_arbore;
//int cantitate_arbore;

void citeste_date_intrare(char* *argv)
{
    citeste_lista_1(argv[1]);
    citeste_lista_2(argv[2]);
    citeste_fisier_3(argv[3]);
}

Nod* citeste_lista_din_fisier(char* nume_fisier, int tip_lista)
{
    FILE* fin;
    Nod* cap_lista = NULL;
    Nod *p,*q;
    int i;
    int nr;

    if((fin = fopen(nume_fisier,"rt")) == NULL)
    {
        printf("Fisierul %s nu poate fi deschis", nume_fisier);
        exit(1);
    }
    //din propunere:
    fscanf(fin, "%d", &nr);
    for(i = 0;i < nr;i++)
    {
        q = citeste_nod(fin, tip_lista);
        if(i == 0)
        {
            cap_lista = p = q;
        }
        else
        {
            leaga_noduri(p, q);
            p = q;
        }
    }
    fclose(fin);
    return cap_lista;
}
void citeste_lista_1(char *file_supermarket)
{
    cap_supermarket = citeste_lista_din_fisier(file_supermarket, TIP_LISTA_1);
}
void citeste_lista_2(char *file_to_buy)
{
    cap_to_buy = citeste_lista_din_fisier(file_to_buy, TIP_LISTA_2);
}
void citeste_fisier_3(char *cerinte)
{
    FILE *f3;
    int i;
    if((f3=fopen(cerinte,"rt"))==NULL)
    {
        printf("Fisierul cerinte nu poate fi deschis");
        exit(1);
    }
    for(i = 1;i <= NR_CERINTE;i++)
    {
        fscanf(f3,"%d",&C[i]);
    }

    fscanf(f3,"%d",&buget);

    //fscanf(f3,"%s",nume_arbore);
    //fscanf(f3,"%s",categorie_arbore);
    //fscanf(f3,"%d",&cantitate_arbore);
    fclose(f3);
}

void rezolva_cerinte()
{

    /* TODO
    *  descrierea conditiilor pentru ca o cerinta
    * sa fie rezolvata
    */

    if(C[1]) {
        rezolva_cerinta_1();
    }
    if(C[2]) {
        rezolva_cerinta_2();
    }
    if(C[3]) {
        rezolva_cerinta_3();
    }
    if(C[4]) {
        rad_arbore = rezolva_cerinta_4(rad_arbore);
    }
    if(C[5]) {
        rezolva_cerinta_5(NULL, NULL);
    }
}

void rezolva_cerinta_1()
{
    Nod *p;
    //parcurg lista supermarket
    for(p=cap_supermarket;p!=NULL;p=p->urm)
    {
        if(p->stoc==0) //daca stocul este nul
        {
            cap_to_buy = sterge_dupa_nume(cap_to_buy, p->nume);
        }
    }
}
void rezolva_cerinta_2()
{
    Nod* p_to_buy;
    Nod* p_market;
    Nod* p_bought;
    Nod* q_bought;

    cap_bought = NULL;
    for(p_to_buy = cap_to_buy;p_to_buy != NULL;p_to_buy = p_to_buy->urm)
    {
        int cantitate;
        p_market = gaseste_dupa_nume(cap_supermarket, p_to_buy->nume);
        cantitate = calcul_cantitate(buget, p_market, p_to_buy);
        buget -= cantitate * (p_market->pret);
        if(cantitate != 0)  //adaugam la lista de cumparate
        {
            q_bought = new Nod;
            *q_bought = *p_to_buy; //copiere bit cu bit
            leaga_noduri(q_bought, NULL);
            leaga_noduri(NULL, q_bought);
            if(cap_bought == NULL)
            {
                cap_bought = p_bought = q_bought;
            }
            else
            {
                leaga_noduri(p_bought, q_bought);
                p_bought = q_bought;
            }
        }
    }
}
void rezolva_cerinta_3()
{
    Nod *parcurgator;
    Nod *parcurgatornou;
    Nod *t;
    Nod *p,*q;
    Nod *nod_minim;
    for(t=cap_to_buy;t!=NULL;t=t->urm) //parcurg lista to buy
    {
        for(parcurgator=cap_supermarket;parcurgator!=NULL;parcurgator=parcurgator->urm) //parcurg lista supermarket
        {
            if(strcmp(t->nume,parcurgator->nume)==0) //daca gasesc produsul
            {
                if(t->cantitate<=parcurgator->cantitate) //daca, cantitatea de cumparat e mai mica decat cea din supermarket
                                                        //adaug in lista bought primul element
                {
                    p = new Nod;
                    if(p==NULL)
                    {
                        printf("Alocare dinamica esuata");
                        exit(1);
                    }
                    strcpy(p->nume,t->nume);
                    strcpy(p->categorie,t->categorie);
                    p->cantitate=t->cantitate;
                    p->urm=NULL;
                    cap_bought=p;
                    t=t->urm; //altfel trece in bucla infinita
                    break;
                }
            }
        }
        //acelasi lucru fac pentru urmatoarele elemente si creez clasic lista de cumparaturi
        for(parcurgatornou=parcurgator->urm;parcurgatornou!=NULL;parcurgatornou=parcurgatornou->urm)
        {
            if(strcmp(t->nume,parcurgatornou->nume)==0)
            {
                if(t->cantitate<=parcurgatornou->cantitate)
                {
                    q = new Nod();
                    if(q==NULL)
                    {
                        printf("Alocare dinamica esuata");
                        exit(1);
                    }
                    strcpy(q->nume,t->nume);
                    strcpy(q->categorie,t->categorie);
                    q->cantitate=t->cantitate;
                    q->urm=NULL;
                    q->ant=p;
                    p->urm=q;
                    p=q;
                    break;
                }
            }
        }
    }
    for(t=cap_to_buy;p!=NULL;p=p->urm) //parcurg lista to buy
    {
        for(parcurgator=cap_supermarket;parcurgator!=NULL;parcurgator=parcurgator->urm) //parcurg lista supermarket
        {
            if(strcmp(t->nume,parcurgator->nume)==0) //daca gasesc elementul
            {
                if(t->cantitate > parcurgator->cantitate) //daca are cantiatea mai mare decat cea de cumparat
                {
                    if(cap_bought==NULL) //in cazul in care toate elementele din lista au cantitaea mai mare decat trebuie
                    {
                        p = new Nod;
                        if(p==NULL)
                        {
                            printf("Alocare dinamica esuata");
                            exit(1);
                        }
                        strcpy(p->nume,t->nume);
                        strcpy(p->categorie,t->categorie);
                        p->cantitate=parcurgator->cantitate;
                        //scad cantitatea din supermarket din cea din to_buy
                        t->cantitate = t->cantitate - parcurgator->cantitate;
                        p->urm=NULL;
                        cap_bought=p;
                        parcurgator=parcurgator->urm; //trecem la noul element din supermarket

                        nod_minim=parcurgator;
                        //aici verific care e nodul cu diferenta minima
                        while(parcurgator!=NULL)
                        {
                            if((strcmp(t->categorie,parcurgator->categorie)==0)&&
                               ((t->pret - nod_minim->pret)>(t->pret - parcurgator->pret)))
                            {
                                nod_minim=parcurgator;
                            }
                            parcurgator=parcurgator->urm;
                        }
                        q = new Nod;
                        if(q==NULL)
                        {
                            printf("alocare dinamica esuata");
                            exit(1);
                        }
                        strcpy(q->nume,nod_minim->nume);
                        strcpy(q->categorie,nod_minim->categorie);
                        q->cantitate=t->cantitate; //ce ramane din cantitatea initiala

                        q->urm=NULL;
                        q->ant=p;
                        p->urm=q;
                        p=q;
                        break;
                    }
                    else
                    {
                        //bag elementul in lista bought si copiez fiecare camp inclusiv cantitatea din lista supermarket(parcurgator in cazul meu)
                        q = new Nod;
                        if(q==NULL)
                        {
                            printf("alocare dinamica esuata");
                            exit(1);
                        }
                        strcpy(q->nume,t->nume);
                        strcpy(q->categorie,t->categorie);
                        q->cantitate=parcurgator->cantitate;
                        //scad cantitatea din supermarket din cea din to_buy
                        t->cantitate=t->cantitate - parcurgator->cantitate;
                        q->urm=NULL;
                        q->ant=p;
                        p->urm=q;
                        p=q;
                        parcurgator=parcurgator->urm; //trecem la noul element din supermarket

                        while(parcurgator!=NULL)
                         //aici verific care e nodul cu diferenta minima
                        {
                            if((strcmp(t->categorie,parcurgator->categorie)==0)&&
                               ((t->pret - nod_minim->pret)>(t->pret - parcurgator->pret)))
                            {
                                nod_minim=parcurgator;
                            }
                            parcurgator=parcurgator->urm;
                        }

                        q = new Nod;
                        if(q==NULL)
                        {
                            printf("alocare dinamica esuata");
                            exit(1);
                        }
                        strcpy(q->nume,nod_minim->nume);
                        strcpy(q->categorie,nod_minim->categorie);
                        q->cantitate=t->cantitate; //ce ramane din cantitatea initiala

                        q->urm=NULL;
                        q->ant=p;
                        p->urm=q;
                        p=q;
                        break;
                    }
                }
            }
        }
    }
}
Nod* rezolva_cerinta_4(Nod* radacina)
{
    Nod *p;
    for(p = cap_bought;p != NULL;p = p->urm)
    {
        Nod* nod_nou = new Nod;
        *nod_nou = *p;
        leaga_noduri(nod_nou, NULL);
        leaga_noduri(NULL, nod_nou);
        radacina = adauga_in_arbore(radacina, nod_nou);
    }
    return radacina;
}
//aici a  afisat RSD-ul ca sa-ti arat cum e
void afisare_arbore(FILE* fout, Nod* p)
{
    if(p)
    {
        fprintf(fout, "%d ", p->cantitate);
        afisare_arbore(fout, p->ant);
        afisare_arbore(fout, p->urm);
    }
}
void rezolva_cerinta_5(Nod* cap, int* rezultat)
{
    stack<int> stiva_pozitii;
    stack<int> stiva_valori;

    for(int poz = 0;cap != NULL; poz++, cap = cap->urm)
    {
        while(!stiva_valori.empty() && stiva_valori.top() > cap->pret)
        {
            stiva_valori.pop();
            stiva_pozitii.pop();
        }
        rezultat[poz] = stiva_valori.empty() ? poz : poz - 1 - stiva_pozitii.top();
        stiva_pozitii.push(poz);
        stiva_valori.push(cap->pret);
    }
}

void scrie_date_iesire(char* nume_f_out)
{
    FILE* fout;
    if((fout = fopen(nume_f_out,"wt")) == NULL)
    {
        printf("Fisierul %s nu poate fi deschis", nume_f_out);
        exit(1);
    }
    if(C[1])
    {
        afisare_lista_in_fisier(fout, cap_to_buy, TIP_LISTA_2);
    }
    //TODO: afisare pentru fiecare cerinta
    if(C[5])
    {
        afisare_arbore(fout, rad_arbore);
    }

    fclose(fout);

}

Nod* citeste_nod(FILE* fin, int tip_lista)
{
    Nod* q = new Nod;
    if(q == NULL)
    {
        printf("Alocare dinamica esuata");
        exit(1);
    }
    switch(tip_lista)
    {
    case TIP_LISTA_1:
        {
            fscanf(fin,"%s",q->nume);
            fscanf(fin,"%s",q->categorie);
            fscanf(fin,"%d",&(q->pret));
            fscanf(fin,"%d",&(q->cantitate));
            fscanf(fin,"%d",&(q->stoc));
            break;
        }
    case TIP_LISTA_2:
        {
            fscanf(fin,"%s",q->nume);
            fscanf(fin,"%s",q->categorie);
            fscanf(fin,"%d",&(q->cantitate));
            break;
        }
    }
    leaga_noduri(q, NULL);
    leaga_noduri(NULL, q);
    return q;
}
void leaga_noduri(Nod* n1, Nod* n2)
{
    if(n1 != NULL)
    {
        n1->urm = n2;
    }
    if(n2 != NULL)
    {
        n2->ant =  n1;
    }
}
Nod* sterge_dupa_nume(Nod* cap_lista, char* nume_cautat)
{
    Nod* temp;
    Nod* p = cap_lista;
    while((temp = gaseste_dupa_nume(p, nume_cautat)) != NULL)
    {
        p = temp->urm;
        leaga_noduri(temp->ant, temp->urm);
        if(temp == cap_lista)
        {
            cap_lista = p;
        }
        free(temp);
    }
    return cap_lista;
}
Nod* gaseste_dupa_nume(Nod* cap_lista, char* nume_cautat)
{
    Nod* p = cap_lista;
    while(p != NULL)
    {
        if(strcmp(p->nume, nume_cautat) == 0)
        {
            return p;
        }
        p = p->urm;
    }
    return NULL;
}
int calcul_cantitate(int buget, Nod* p_market, Nod* p_to_buy)
{
    int buget_necesar = (p_to_buy->cantitate) * (p_market->pret);
    if(buget_necesar > buget)
    {
        buget_necesar = buget;
    }
    return buget_necesar / (p_market->pret);
}
Nod* adauga_in_arbore(Nod* radacina, Nod* nod_nou)
{
    if(radacina == NULL)
    {
        return nod_nou;
    }
    else if(radacina->cantitate <= nod_nou->cantitate)
    {
        radacina->ant = adauga_in_arbore(radacina->ant, nod_nou);
        return radacina;
    }
    else
    {
        return adauga_in_arbore(nod_nou, radacina);
    }
}

void afisare_lista_in_fisier(FILE* fout, Nod* cap_to_buy, int tip_lista)
{
    Nod* p = cap_to_buy;
    for(;p != NULL;p = p->urm)
    {
        switch(tip_lista)
        {
        case TIP_LISTA_1:
            {
                fprintf(fout,"%s %s %d %d %d\n",p->nume, p->categorie, p->pret, p->cantitate, p->stoc);
                break;
            }
        case TIP_LISTA_2:
            {
                fprintf(fout,"%s %s %d\n",p->nume, p->categorie, p->cantitate);
                break;
            }
        }
    }
}