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

void printTab(double **tab, int rows, int columns) {
	for(int i = 0; i < rows; i++) {
		for(int j = 0; j < columns; j++) {
			printf("%lf ", tab[i][j]);
		}
		printf("\n");
	}
}

void printTab2(double **tab, int rows) {
	double a;
	for(int i = 0; i < rows; i++) {
		a = tab[i][0];
		if(a != 0.0) {
			printf("%lf %d", a, (int) tab[i][1]);
			printf("\n");
		}
	}
}

int main(){
	int n, m, k, i, j, p;
	printf("Podaj n, m i k jako rozmiar macierzy NxM i liczbe niezerowych elementow:\n");
  	scanf("%d %d %d", &n, &m, &k);
	double **A;
	double **B;
	A = (double**)malloc(n * sizeof(double*));
	for (i = 0; i < n; i++)
		A[i] = (double*)malloc(m * sizeof(double));

	B = (double**)malloc(n * sizeof(double*));
	for (i = 0; i < n; i++)
		B[i] = (double*)malloc(m * sizeof(double));

	double **CRS;
	double **CCS;
	CRS = (double**)malloc(n * (k + 1) * sizeof(double*));
	for (i = 0; i < n * (k + 1); i++)
		CRS[i] = (double*)malloc(2 * sizeof(double));
	CCS = (double**)malloc(m * (k + 1) * sizeof(double*));
	for (i = 0; i < m * (k + 1); i++)
		CCS[i] = (double*)malloc(2 * sizeof(double));

  	srand(time(NULL));

	double a;
	int size;
	if(n < m) size = n;
	else size = m;

	for(i = 0; i < size; i++) {
		a = 1.0 + (double)rand() / RAND_MAX;
		A[i][i] = a;
	}

	for(i = 0; i < n; i++) {
		for(j = 0; j < k; j++) {
			p = rand() % m;
			while(p == i) p = rand () % m;
			a = (double)rand() / RAND_MAX;
			A[i][p] = a;
		}
	}

	//wypis macierzy
	printTab(A, n, m);

	int l = 0;
	printf("CRS:\n");
	for(i = 0; i < n; i++) {
		for(j = 0; j < m; j++) {
			a = A[i][j];
			if(a != 0.0){
				//printf("%lf %d\n", a, j);
				CRS[l][0] = a;
				CRS[l][1] = j;
				l++;
			}
		}
	}
	printTab2(CRS, n*(k+1));

	l = 0;
	printf("\nCCS:\n");
	for(i = 0; i < m; i++) {
		for(j = 0; j < n; j++) {
			a = A[j][i];
			if(a != 0.0){
				//printf("%lf %d\n", a, j);
				CCS[l][0] = a;
				CCS[l][1] = j;
				l++;
			}
		}
	}
	printTab2(CCS, m*(k+1));

	//dekompresja CRS
	int row = 0;
	int prevCol, col;
	double v;
	prevCol = (int)CRS[0][1];
	for(i = 0; i < n*(k+1); i++) {
		v = CRS[i][0];
		if(v != 0.0) {
			col = (int)CRS[i][1];
			if(col <= prevCol && i > 0){
			 	row++;
			}
			B[row][col] = v;
			prevCol = col;
		}
	}

	printTab(B, n, m);

	int error = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(A[i][j] != B[i][j]) error++;
		}
	}
	printf("CRS error: %d\n", error);


	return 0;

}