#include <iostream>

using namespace std;

struct ElementMR{
unsigned int l,c;
double val;
};

struct NodMR{
ElementMR tuplu;
NodMR *next;
};

NodMR* InserareSf(NodMR* l,ElementMR e){
NodMR* nou=new NodMR;
nou->tuplu=e;
nou->next=NULL;
if(!l)
return nou;
else{
NodMR* temp=l;
while(temp->next)
temp=temp->next;
temp->next=nou;
return l;
}
}

NodMR* ConversieToLSMatriceRara(double A[][100], unsigned int m, unsigned int n,
char *err, unsigned int *nrEl){
*nrEl=0;
unsigned int i,j;
NodMR *lstMR=NULL;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(A[i][j])
(*nrEl)++;
double pondere=*nrEl;
pondere=pondere/(m*n);
if(pondere>=0.0015 && pondere<=0.03){
*err=1;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(A[i][j]){
ElementMR t;
t.l=i+1;
t.c=j+1;
t.val=A[i][j];
lstMR=InserareSf(lstMR,t);
}
return lstMR;
}
else{
*err=0;
return 0;
}
}

NodMR* StergereInc(NodMR* l){
if(l){
NodMR* temp=l;
l=l->next;
delete temp;
}
return l;
}


NodMR* ExtragereNodPoz(NodMR* l,unsigned int poz, unsigned int n){
if(poz<1 || poz >n)
return 0;
else{
NodMR *temp=l;
unsigned int i;
for(i=1;i<poz;i++)
temp=temp->next;
return temp;
}
}

bool esteMatriceRara(double nrElementeNenule, double nrLinii, double nrColoane)
{

double gradUmplere = 0;
gradUmplere = nrElementeNenule/(nrLinii * nrColoane);
if (gradUmplere < 0.03) return true;
else
return false;

}

// Exista nod pe linia si coloana precizata, intoarce true(adevarat)
bool existaNodPePozitia(NodMR* lista, int linia, int coloana, double * val)
{
lista = lista->next;
while (lista!= NULL)
{
if (lista->tuplu.l == linia && lista->tuplu.c == coloana)
{
*val = lista->tuplu.val;//valoarea se va putea lua prin referinta dupa executia metodei
return true;
}
lista = lista->next;
}

return false;
}

NodMR* citireListaMatriceRara(int nrElementeNenule)
{
NodMR* nod = new NodMR();
NodMR* capLista =nod;
nod->next = NULL;
int linia, coloana;
double val;

for (int i = 0; i < nrElementeNenule; i++)
{
cout<<"Dati pozitia pe linie:";
cin>>linia;//citesc pozitia pe linie
cout<<"Dati pozitia pe coloana:";
cin>>coloana;//citesc pozitia pe coloana
cout<<"Dati valoarea de pe linia "<<linia<<" si coloana "<<coloana<<endl;
cin>>val;

ElementMR elem;
elem.l = linia;
elem.c = coloana;
elem.val = val;
//inserare in lista
InserareSf(nod, elem);

}
return capLista;

}

void afisareLista(NodMR* lista)
{
lista = lista->next;
while (lista!= NULL)
{
cout<<"Linia: "<<lista->tuplu.l;
cout<<"Coloana: "<<lista->tuplu.c;
cout<<"Valoare: "<<lista->tuplu.val<<endl;
lista = lista->next;
}
}

//Adunarea a 2 matrici rare sub forma de liste
NodMR* adunareMatriciRare(NodMR* matr1, NodMR* matr2)
{
NodMR* capLista = new NodMR();
NodMR* nod = capLista;
NodMR* capListaMatrice1 =matr1;
NodMR* capListaMatrice2 =matr2;

matr1 = matr1->next;
while (matr1!= NULL) //primul nod contine doar referinta si nu informatie utila, de aceea se foloseste al doilea elem
{//parcurg prima matrice, daca gasesc elemente care nu se regasesc in adoua matrice le pun ca atare in matricea rezultat al adunarii
double val =0;
if (!existaNodPePozitia(capListaMatrice2, matr1->tuplu.l, matr1->tuplu.c,  &val ))
{
InserareSf(capLista,matr1->tuplu);
}
else
{
//daca exista un element pe aceeasi pozitie in maticea 2 ca cea din matricea 1, adaugam cele 2 valori si le punem in matricea rezultat al adunarii
ElementMR elem;
elem.l = matr1->tuplu.l;
elem.c =  matr1->tuplu.c;
elem.val = matr1->tuplu.val + val;

InserareSf(capLista,elem);
}
matr1 = matr1->next;
}

matr2 = matr2->next;
while (matr2!= NULL)
{//parcurg a doua matrice, daca gasesc elemente care nu se regasesc in prima matrice le pun ca atare in matricea rezultat al adunarii
double val =0;
if (!existaNodPePozitia(capListaMatrice1, matr2->tuplu.l, matr2->tuplu.c,  &matr2->tuplu.val ))
{

ElementMR elem;
elem.l = matr2->tuplu.l;
elem.c =  matr2->tuplu.c;
elem.val = matr2->tuplu.val;

InserareSf(capLista,elem);
}
        //daca exista. deja avem adunarea la pasul precedent
matr2 = matr2->next;
}



return capLista;
}


void main()
{
bool esteMatrRara = false;
int nrElementeNenule, nrLinii, nrColoane;
do
{
cout<<"Dati numarul de elemente nenule:";
cin>>nrElementeNenule;

cout<<"Dati numarul de linii ale matricei rare:";
cin>>nrLinii;

cout<<"Dati numarul de coloane ale matricei rare:";
cin>>nrColoane;

esteMatrRara = esteMatriceRara(nrElementeNenule, nrLinii, nrColoane);

if (esteMatrRara == false)
{
cout<<"Gradul de umplere depaseste 30%. Matricea nu este o matrice rara.";
}

}
while (esteMatrRara == false);
   
NodMR* listaMatriceRara1 = citireListaMatriceRara(nrElementeNenule);//se citeste prima matrice
cout<<"Afisare matrice rara 1";
afisareLista(listaMatriceRara1);

cout<<"Dati numarul de elemente nenule matricea a doua:";
cin>>nrElementeNenule;

NodMR* listaMatriceRara2 = citireListaMatriceRara(nrElementeNenule);//se citeste a doua matrice
cout<<"Afisare matrice rara 2";
afisareLista(listaMatriceRara2);

cout<<"Afisare matrice adunata rezultata";
NodMR* listaAdunata = adunareMatriciRare(listaMatriceRara1, listaMatriceRara2);
afisareLista(listaAdunata);

char c;
cin>>c;



}

//NodMR* lista1;


// double Mat[25][100],val;
// unsigned int m, n, i, j;
// unsigned int nrEl;
// char err;
// m=25;
// n=100;
// NodMR *lstMatRara=NULL;
// for(i=0;i<m;i++)
// for(j=0;j<n;j++)
// Mat[i][j]=0;
//
// char opt='d';
// while(opt=='d'){
// do{
// cout<<"Introduceti indexul de linie a elementului nenul: ";
// cin>>i;
// }
// while(i>25 || i==0);
// do{
// cout<<"Introduceti indexul de coloana a elementului nenul:";
// cin>>j;
// }
// while(j>100 || j==0);
// cout<<"Introduceti valoarea elementului nenul: ";
// cin>>val;
// if(!Mat[i-1][j-1])
// Mat[i-1][j-1]=val;
// else{
// cout<<"Pozitia indicata contine un element de valoare \
//nenula! Rescrieti elementul?(d/n): ";
// cin>>opt;
// if(opt=='d')
// Mat[i-1][j-1]=val;
// }
// cout<<"Continuati?(d/n): ";
// cin>>opt;
// }
//
// lstMatRara=ConversieToLSMatriceRara(Mat,m,n,&err,&nrEl);
//
// if(err){
// cout<<"Structura de tip Matrice Rara este:"<<endl;
// //afisare lista simpla
// for(i=1;i<=nrEl;i++){
// NodMR *t;
// t=ExtragereNodPoz(lstMatRara,i,nrEl);
// if(t){
// cout<<t->tuplu.l<<"\t"<<t->tuplu.c<<"\t" \
//<<t->tuplu.val<<endl;
// }
// }
//
// //stergere lista simpla
// while(lstMatRara)
// lstMatRara=StergereInc(lstMatRara);
// }
// else
// cout<<"Masivul bidimensional nu indeplineste criteriile \
//de matrice rara!"<<endl;
//
//
// //
// char c;
// scanf_s("%c", &c);
//}