// Jevin Olano
// jolano
// CSE 101
// October 24, 2019
// Matrix.c - implementation file for Matrix ADT

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include "Matrix.h"

// Constructors & Destructors ---------------------------

// Returns a reference to a new nXn Matrix object in the zero state.
Matrix newMatrix(int n) {
	Matrix M = malloc(sizeof(MatrixObj)); // matrix
	M->rows = calloc(n, sizeof(ListObj)); // rows
	for (int i = 0; i < n; i++) {
		M->rows[i] = newList(); // array elements
	}
	M->size = n;
	return M;
}

// Frees heap memory associated with *pM, sets *pM to NULL.
void freeMatrix(Matrix* pM) {
	Matrix M = *pM;
	makeZero(M);
	for (int i = 0; i < (M->size); i++) {
		freeList(&(M->rows[i])); // array elements
	}
	free(M->rows); // rows
	free(M); // matrix
	M = NULL;
}

// Access Functions -------------------------------------

// size()
// Return the size of square Matrix M.
int size(Matrix M) {
	return M->size;
}

// NNZ()
// Return the number of non-zero elements in M.
int NNZ(Matrix M) {
	int nonZeroCount = 0;
	for (int i = 0; i < (M->size); i++) {
		nonZeroCount += length(M->rows[i]);
	}
	return nonZeroCount;
}

// doubleEquals()
int doubleEquals(double a, double b) {
	return fabs(a - b) < 0.0000001 ? 1 : 0;
}


// equals()
// Return true (1) if matrices A and B are equal, false (0) otherwise.
int equals(Matrix A, Matrix B) {
	if (size(A) != size(B)) {
		return 0;
	}
	for (int i = 0; i < size(A); i++) {
		List rowA = A->rows[i];
		List rowB = B->rows[i];
		if (length(rowA) != length(rowB)) {
			return 0;
		}
		moveFront(rowA);
		moveFront(rowB);
		while (get(rowA) != NULL) {
			Entry entryA = (Entry) get(rowA);
			Entry entryB = (Entry) get(rowB);
			if (entryA->column != entryB->column || doubleEquals(entryA->value, entryB->value) == 0) {
				return 0;
			}
			moveNext(rowA);
			moveNext(rowB);
		}
	}
	return 1;
}

// Manipulation Procedures ------------------------------

// makeZero()
// Re-sets M to the zero Matrix.
void makeZero(Matrix M) {
	for (int i = 0; i < (M->size); i++) {
		if (isEmpty(M->rows[i])) {
			continue;
		}
		moveFront(M->rows[i]);
		while (get(M->rows[i]) != NULL) {
			free(get(M->rows[i]));
			moveNext(M->rows[i]);
		}
		clear(M->rows[i]); // array elements
	}
}

// newEntry()
Entry newEntry(int column, double value) {
	Entry entry = malloc(sizeof(EntryObj));
	entry->column = column;
	entry->value = value;
	return entry;
}

// appendToList()
// helper method to add non-zero entries
void appendToList(List list, Entry entry) {
	if (!doubleEquals(entry->value, 0)) {
		append(list, entry);
	} else {
		free(entry);
	}
}

// changeEntry()
// Changes the ith row, jth column of M to the value x.
// Pre: 1<=i<=size(M), 1<=j<=size(M)
void changeEntry(Matrix M, int i, int j, double x) {
	if (i < 1 || i > size(M)) {
		fprintf(stderr, "Error: row number is out of bounds\n");
		exit(1);
	}
	if (j < 1 || j > size(M)) {
		fprintf(stderr, "Error: column number is out of bounds\n");
		exit(1);
	}
	List row = M->rows[i-1];
	if (isEmpty(row)) {
		Entry entry = newEntry(j, x);
		appendToList(row, entry);
	} else {
		moveFront(row);
		int appendBool = 1;
		while (get(row) != NULL) {
			Entry entry = (Entry) get(row);
			if (entry->column == j) {
				if (doubleEquals(x, 0)) {
					delete(row);
				} else {
					entry->value = x;
				}
				appendBool = 0;
				break;
			} else if (entry->column < j) {
				moveNext(row);
			} else {
				if (!doubleEquals(x,0)) {
					insertBefore(row, newEntry(j, x));
				}
				appendBool = 0;
				break;
			}
		}
		if (appendBool == 1) {
			appendToList(row, newEntry(j, x));
		}
	}
}

// Matrix Arithmetic Operations -------------------------

// copy()
// Returns a reference to a new Matrix object having the same entries as A.
Matrix copy(Matrix A) {
	Matrix B = newMatrix(size(A));
	for (int i = 0; i < size(A); i++) {
		List rowA = A->rows[i];
		List rowB = B->rows[i];
		if (isEmpty(rowA)) {
			continue;
		}
		moveFront(rowA);
		while (get(rowA) != NULL) {
			Entry entryA = (Entry) get(rowA);
			Entry entryB = newEntry(entryA->column, entryA->value);
			appendToList(rowB, entryB);
			moveNext(rowA);
		}
	}
	return B;
}

// transpose()
// Returns a reference to a new Matrix object representing the transpose of A.
Matrix transpose(Matrix A) {
	Matrix B = newMatrix(size(A));
	for (int i = 0; i < size(A); i++) {
		List rowA = A->rows[i];
		if (isEmpty(rowA)) {
			continue;
		}
		moveFront(rowA);
		while (get(rowA) != NULL) {
			Entry entryA = (Entry) get(rowA);
			List rowB = B->rows[entryA->column - 1];
			Entry entryB = newEntry(i + 1, entryA->value);
			appendToList(rowB, entryB);
			moveNext(rowA);
		}
	}
	return B;
}

// scalarMult()
// Returns a reference to a new Matrix object representing xA.
Matrix scalarMult(double x, Matrix A) {
	Matrix B = copy(A);
	for (int i = 0; i < size(A); i++) {
		List rowB = B->rows[i];
		moveFront(rowB);
		while (get(rowB) != NULL) {
			Entry entry = (Entry) get(rowB);
			entry->value *= x;
			moveNext(rowB);
		}
	}
	return B;
}

// sum()
// Returns a reference to a new Matrix object A+B
// pre: size(A) == size(B)
Matrix sum(Matrix A, Matrix B) {
	if (size(A) != size(B)) {
		fprintf(stderr, "Error: calling sum() on matrices of different size\n");
		exit(1);
	}
	Matrix C = newMatrix(size(A));
	for (int i = 0; i < size(A); i++) {
		double *pSums = calloc(size(A), sizeof(double));

		List rowA = A->rows[i];
		moveFront(rowA);
		while (get(rowA) != NULL) {
			Entry entry = (Entry) get(rowA);
			pSums[entry->column - 1] = entry->value;
			moveNext(rowA);
		}

		List rowB = B->rows[i];
		moveFront(rowB);
		while (get(rowB) != NULL) {
			Entry entry = (Entry) get(rowB);
			pSums[entry->column - 1] += entry->value;
			moveNext(rowB);
		}

		List rowC = C->rows[i];
		for (int j = 0; j < size(A); j++) {
			if (!doubleEquals(pSums[j], 0)) {
				Entry sumEntry = newEntry(j + 1, pSums[j]);
				appendToList(rowC, sumEntry);
			}
		}
		free(pSums);
	}
	return C;
}

// diff()
// Returns a reference to a new Matrix object A-B
// pre: size(A) == size(B)
Matrix diff(Matrix A, Matrix B) {
	if (size(A) != size(B)) {
		fprintf(stderr, "Error: calling diff() on matrices of different size\n");
		exit(1);
	}
	Matrix C = newMatrix(size(A));
	for (int i = 0; i < size(A); i++) {
		double *pDiffs = calloc(size(A), sizeof(double));

		List rowA = A->rows[i];
		moveFront(rowA);
		while (get(rowA) != NULL) {
			Entry entry = (Entry) get(rowA);
			pDiffs[entry->column - 1] = entry->value;
			moveNext(rowA);
		}

		List rowB = B->rows[i];
		moveFront(rowB);
		while (get(rowB) != NULL) {
			Entry entry = (Entry) get(rowB);
			pDiffs[entry->column - 1] -= entry->value;
			moveNext(rowB);
		}

		List rowC = C->rows[i];
		for (int j = 0; j < size(A); j++) {
			if (!doubleEquals(pDiffs[j], 0)) {
				Entry sumEntry = newEntry(j + 1, pDiffs[j]);
				appendToList(rowC, sumEntry);
			}
		}
		free(pDiffs);
	}
	return C;
}

// vectorDot()
// Computes the vector dot product of two matrix rows represented by Lists Q and P
double vectorDot(List P, List Q, int size) {
	double *pP = calloc(size, sizeof(double));
	double *pQ = calloc(size, sizeof(double));

	moveFront(P);
	while (get(P) != NULL) {
		Entry entry = (Entry) get(P);
		pP[entry->column - 1] = entry->value;
		moveNext(P);
	}

	moveFront(Q);
	while (get(Q) != NULL) {
		Entry entry = (Entry) get(Q);;
		pQ[entry->column - 1] = entry->value;
		moveNext(Q);
	}

	double product = 0.0;

	for (int i = 0; i < size; i++) {
		product += pP[i] * pQ[i];;
	}

	free(pP);
	free(pQ);

	return product;
}

// product()
// Returns a reference to a new Matrix object AB
// pre: size(A) == size(B)
Matrix product(Matrix A, Matrix B) {
	if (size(A) != size(B)) {
		fprintf(stderr, "Error: calling product() on matrices of different size\n");
		exit(1);
	}

	Matrix C = newMatrix(size(A));
	Matrix bTr = transpose(B);

	for (int i = 0; i < size(A); i++) {
		for (int j = 0; j < size(bTr); j++) {
			Entry dotProduct = newEntry(j + 1, vectorDot(A->rows[i], bTr->rows[j], size(A)));
			appendToList(C->rows[i], dotProduct);
		}
	}
	freeMatrix(&bTr);
	return C;
}

// printMatrix()
// Prints a string representation of Matrix M to filestream out. Zero rows // are not printed. Each non-zero is represented as one line consisting
// of the row number, followed by a colon, a space, then a space separated
// list of pairs "(col, val)" giving the column numbers and non-zero values
// in that row. The double val will be rounded to 1 decimal point.
void printMatrix(FILE* out, Matrix M) {
	if (size(M) != 0) {
		for (int i = 0; i < size(M); i++) {
			if (isEmpty(M->rows[i])) {
				continue;
			}
			moveFront(M->rows[i]);
			fprintf(out, "%d:", i + 1);
			while (get(M->rows[i]) != NULL) {
				Entry entry = (Entry) get(M->rows[i]);
				fprintf(out, " (%d, %.1lf)", entry->column, entry->value);
				moveNext(M->rows[i]);
			}
			fprintf(out, "\n");
		}
	}
}