LO27/LibMatrix/matrix.c

/*
 * This is a cellular automaton library
 *
 * Copyright (C) 2016-2017 Antoine BARTUCCIO, Jean POREE DE RIDDER
 *
 * Licensed under the MIT License,(the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * hhttps://opensource.org/licenses/MIT
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 */

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

Matrix applyRules (Matrix matrix,int Rules, int N){
	int RulesMatrix[9];
	int i = 0;
	int power = 2;
	int sum = 0;
	int j = 0;
	Matrix tempMatrix1;
	Matrix tempMatrix2;

	if (Rules <= 0 || N < 1){
		return matrix;
	}

	while(power<=512){

		RulesMatrix[i] = Rules%power - sum;
		sum = Rules%power;

		if (RulesMatrix[i]!=0){
			i++;
		}

		power*=2;
	}

	tempMatrix1 = matrixFromRules(matrix, i, RulesMatrix);

	for (j=1;j<N;j++){
		tempMatrix2 = matrixFromRules(tempMatrix1,i, RulesMatrix);
		freeMatrix(tempMatrix1);

		tempMatrix1 = tempMatrix2;
	}

	return tempMatrix1;

}


Matrix createMatrix(){
	Matrix matrix;
	matrix.colCount = 0;
	matrix.rowCount = 0;
	matrix.cols = createList();
	matrix.rows = createList();
	return matrix;
}

Matrix setMatrixDim(Matrix matrix,int nbCols,int nbRows){
	matrix.colCount = nbCols;
	matrix.rowCount = nbRows;
	return matrix;
}

bool createMatrixElem(Matrix matrix, int ColPos, int RowPos){
	ListElement * Row = NULL;
	ListElement * Col = NULL;
	int error = 0;
	cellElement * elem = NULL;
	cellElement * tmp = NULL;

	if (matrix.colCount <= ColPos || matrix.rowCount <= RowPos ){
		return ERROR;
	}
	elem = createCellElem();
	setPositionIndex(elem,ColPos,RowPos);

	Row = getElementPos(matrix.rows,RowPos);
	if (Row != NULL && Row->data != NULL){

		if (Row->data->colIndex == ColPos){
			error ++;
		} else if (Row->data->colIndex > ColPos){
			elem->nextCol = Row->data;
			Row->data = elem;
		} else {
			tmp = Row->data;
			while (tmp->nextCol != NULL && tmp->nextCol->colIndex < ColPos){
				tmp=tmp->nextCol;
			}
			if (tmp->nextCol == NULL || tmp->nextCol->colIndex > ColPos){
				elem->nextCol = tmp->nextCol;
				tmp->nextCol = elem;
			}else {
				error ++;
			}
		}

	}else {
		push(matrix.rows,elem);
		matrix.rows->tail->pos = RowPos;
	}

	Col = getElementPos(matrix.cols,ColPos);
	if (Col != NULL && Col->data != NULL){

		if (Col->data->rowIndex == RowPos){
			error ++;
		} else if (Col->data->rowIndex > RowPos){
			elem->nextRow = Col->data;
			Col->data = elem;
		} else {
			tmp = Col->data;
			while (tmp->nextRow != NULL && tmp->nextRow->rowIndex < RowPos){
				tmp=tmp->nextRow;
			}
			if (tmp->nextRow == NULL || tmp->nextRow->rowIndex > RowPos){
				elem->nextRow = tmp->nextRow;
				tmp->nextRow = elem;
			}else {
				error ++;
			}
		}

	}else {
		push(matrix.cols,elem);
		matrix.cols->tail->pos = ColPos;
	}


	if (error != 0){
		freeCellElement(elem);
		return true;
	}else{
		return false;
	}

}

cellElement * findMatrixElem(Matrix matrix, int ColPos, int RowPos){
	ListElement * Row = NULL;
	cellElement * elem = NULL;

	Row = getElementPos(matrix.rows,RowPos);
	if (Row == NULL){
		return NULL;
	}
	elem = Row->data;

	while (elem != NULL && elem->colIndex != ColPos){
		elem = elem->nextCol;
	}

	return elem;
}

int deleteMatrixElem(Matrix matrix, int ColPos, int RowPos){
	cellElement * elem = NULL;
	cellElement * tmp = NULL;

	ListElement * Row = NULL;
	ListElement * Col = NULL;

	elem = findMatrixElem(matrix,ColPos,RowPos);
	if (elem == NULL){
		return 0;
	}

	Row = getElementPos(matrix.rows,RowPos);
	if (Row == NULL){
		return -1;
	}
	if (Row->data == NULL){
		removeElementPos(matrix.rows,RowPos);
		return -1;
	}

	if (Row->data->colIndex == ColPos){
		Row->data = elem->nextCol;
	} else {
		tmp = Row->data;
		while (tmp->nextCol != NULL && tmp->nextCol != elem){
			tmp = tmp->nextCol;
		}
		if (tmp->nextCol == NULL){
			return -3; /* should never happend */
		} else {
			tmp->nextCol = elem->nextCol;
		}

	}
	if (Row->data == NULL){
		removeElementPos(matrix.rows,RowPos);
	}


	Col = getElementPos(matrix.cols,ColPos);
	if (Col == NULL){
		return -2;
	}
	if (Col->data == NULL){
		removeElementPos(matrix.cols,ColPos);
		return -1;
	}
	if (Col->data->rowIndex == RowPos){
		Col->data = elem->nextRow;
	} else {
		tmp = Col->data;
		while (tmp->nextRow != NULL && tmp->nextRow != elem){
			tmp = tmp->nextRow;
		}
		if (tmp->nextRow == NULL){
			return -4; /* should never happend */
		} else {
			tmp->nextRow = elem->nextRow;
		}
	}
		if (Col->data == NULL){
		removeElementPos(matrix.cols,ColPos);
	}

	freeCellElement(elem);
	return 1;

}

bool getCellValue(Matrix matrix, int ColPos, int RowPos){
	if (matrix.colCount <= ColPos || matrix.rowCount <= RowPos){
		return ERROR;
	}

	if (findMatrixElem(matrix,ColPos,RowPos) == NULL){
		return false;
	}
	return true;
}

bool setCellValue(Matrix matrix, int ColPos, int RowPos,bool value){
	if (value == true){
		return createMatrixElem(matrix,ColPos,RowPos);
	}else{
		if ( deleteMatrixElem(matrix,ColPos,RowPos) >= 0 ){
			return true;
		}else{
			return false;
		}
	}
}

void printMatrix(Matrix matrix){
	int i = 0;
	int j = 0;
	bool b;

	printf("\n---PRINT MATRIX---\n");

	for (i=0;i<matrix.rowCount;i++){
		printf("| ");
		for (j=0;j<matrix.colCount;j++){

			b = getCellValue(matrix,j,i);
			if (b == true){
				printf("1 ");
			}else if (b == false){
				printf("0 ");
			}else{
				printf("X "); /* error out of bounds, should never happend*/
			}

		}
		printf("|\n");

	}

	printf("---END OF MATRIX---\n\n");
}

Matrix freeMatrix(Matrix matrix){
	int i = 0;
	int j = 0;
	
	for (i=0;i<matrix.rowCount;i++){
		for (j=0;j<matrix.colCount;j++){

			setCellValue(matrix,j,i,false);
			

		}
		
	}

	freeList(matrix.cols);
	freeList(matrix.rows);
	return matrix;
}

Matrix opMatrix(Matrix matrix1,Matrix matrix2,bool (operator)(bool, bool)){
	Matrix SumMatrix = createMatrix();
	int i =0;
	int j = 0;

	if (matrix1.colCount == matrix2.colCount && matrix1.rowCount == matrix2.rowCount){
		SumMatrix = setMatrixDim(SumMatrix,matrix2.colCount,matrix1.rowCount);
		for (i=0;i<SumMatrix.colCount;i++){
			for (j=0;j<SumMatrix.rowCount;j++){
				setCellValue(SumMatrix,i,j,operator(getCellValue(matrix1,i,j),getCellValue(matrix2,i,j)));
				
				}
		}
	}else{
		printf("\n- error : Matrices haven't the same size -\n");
		
		SumMatrix.colCount = -1;
		SumMatrix.rowCount = -1;
	}
	
	return SumMatrix;
	
}

Matrix sumMatrix(Matrix matrix1,Matrix matrix2){
	return opMatrix(matrix1,matrix2,OR);
}

Matrix mulMatrix(Matrix matrix1,Matrix matrix2){
	return opMatrix(matrix1,matrix2,AND);
}


Matrix colSequenceOnMatrix(Matrix m, bool (operator)(bool, bool)){
	bool a;
	bool b;
	int i;
	int j;
	Matrix newM = createMatrix();


	newM.rowCount = m.rowCount;
	if (m.colCount <= 1){
		newM.colCount = 0;
		return newM;
	}
	newM.colCount = m.colCount - 1;

	for (i=0;i < m.colCount - 1;i++){
		for (j=0;j < m.rowCount;j++){
			a = getCellValue(m, i, j);
			b = getCellValue(m, i + 1, j);
			if (operator(a, b)){
				setCellValue(newM, i, j, true);
			}
		}
	}
	return newM;
}

Matrix rowSequenceOnMatrix(Matrix m, bool (operator)(bool, bool)){
	bool a;
	bool b;
	int i;
	int j;
	Matrix newM = createMatrix();

	newM.colCount = m.colCount;
	if (m.rowCount <= 1){
		newM.rowCount = 0;
		return newM;
	}
	newM.rowCount = m.rowCount - 1;

	for (i=0; i < m.colCount;i++){
		for (j=0;j < m.rowCount - 1;j++){
			a = getCellValue(m, i, j);
			b = getCellValue(m, i, j + 1);
			if (operator(a, b)){
				setCellValue(newM, i, j, true);
			}
		}
	}
	return newM;
}

Matrix andColSequenceOnMatrix(Matrix m){
	return colSequenceOnMatrix(m, AND);
}

Matrix orColSequenceOnMatrix(Matrix m){
	return colSequenceOnMatrix(m, OR);
}

Matrix andRowSequenceOnMatrix(Matrix m){
	return rowSequenceOnMatrix(m, AND);
}

Matrix orRowSequenceOnMatrix(Matrix m){
	return rowSequenceOnMatrix(m, OR);
}

Matrix newMatrix(BooleanMatrix bmatrix){
	Matrix m = createMatrix();
	int i;
	int j;

	m.colCount = bmatrix.cols;
	m.rowCount = bmatrix.rows;

	for (i=0; i < m.rowCount ; i++){
		for (j=0; j < m.colCount; j++){
			if (bmatrix.data[i][j]){
				setCellValue(m, j, i, true);
			}
		}
	}

	return m;
}

BooleanMatrix createBooleanMatrix(int cols, int rows){
	BooleanMatrix matrix;
	int i;

	matrix.rows = rows;
	matrix.cols = cols;

	matrix.data = (bool**)malloc(matrix.rows * sizeof(bool*));
	if (matrix.data != NULL){
		for (i=0; i < matrix.rows; i++){
			matrix.data[i] = (bool*)malloc(matrix.cols * sizeof(bool));
		}
	}
	return matrix;
}

BooleanMatrix randomizeBooleanMatrix(BooleanMatrix matrix){
	int i;
	int j;
	int r;

	srand(time(NULL));

	for (i=0; i < matrix.rows; i++){
		for (j=0; j < matrix.cols; j++){
			r = rand() % 2;
			if (r == 1){
				matrix.data[i][j] = true;
			} else {
				matrix.data[i][j] = false;
			}
		}
	}

	return matrix;
}

void freeBooleanMatrix(BooleanMatrix matrix){
	int i;
	for (i=0; i < matrix.rows; i++){
		free(matrix.data[i]);
	}
	free(matrix.data);
}


Matrix matrixFromRules(Matrix m, int n, int rules[]){
	int i;
	int j;

	bool * bools = NULL;
	Matrix result = createMatrix();

	if (rules == NULL){
		result.colCount = 0;
		result.rowCount = 0;
		return result;
	}

	result.colCount = m.colCount;
	result.rowCount = m.rowCount;

	for (i=0; i < m.rowCount; i++){
		for (j = 0; j < m.colCount; j++){
			bools = getFromRules(m, j, i, n, rules);
			if (bools != NULL){
				if (MXOR(n, bools)){
					setCellValue(result, j, i, true);
				}
				free(bools);
			}
		}
	}
	return result;
}

bool MXOR(int n, bool bools[]){
	int i;
	bool r = false;
	for (i=0;i<n;i++){
		r = XOR(r, bools[i]);
	}
	return r;
}

bool firstRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos, RowPos));
}

bool leftRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos + 1, RowPos));
}

bool rightRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos - 1, RowPos));
}

bool topRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos, RowPos + 1));
}

bool bottomRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos, RowPos - 1));
}

bool topLeftRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos + 1, RowPos + 1));
}

bool topRightRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos - 1, RowPos + 1));
}

bool bottomLeftRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos + 1, RowPos - 1));
}

bool bottomRightRule(Matrix m, int ColPos, int RowPos){
	return errorToFalse(getCellValue(m, ColPos - 1, RowPos - 1));
}

bool * getFromRules(Matrix m, int ColPos, int RowPos, int n, int rules[]){
	bool * bools = (bool *)malloc(sizeof(bool) * n);
	int i;

	if (bools != NULL){
		for (i=0;i<n;i++){
			switch (rules[i]){
				case 8:
					bools[i] = topRule(m, ColPos, RowPos);
					break;
				case 128:
					bools[i] = bottomRule(m, ColPos, RowPos);
					break;
				case 2:
					bools[i] = leftRule(m, ColPos, RowPos);
					break;
				case 32:
					bools[i] = rightRule(m, ColPos, RowPos);
					break;
				case 4:
					bools[i] = topLeftRule(m, ColPos, RowPos);
					break;
				case 16:
					bools[i] = topRightRule(m, ColPos, RowPos);
					break;
				case 256:
					bools[i] = bottomLeftRule(m, ColPos, RowPos);
					break;
				case 64:
					bools[i] = bottomRightRule(m, ColPos, RowPos);
					break;
				case 1:
					bools[i] = firstRule(m, ColPos, RowPos);
					break;
			}
		}
	}

	return bools;

}

bool isMatrixEmpty(Matrix matrix){
	if (matrix.colCount < 1 || matrix.rowCount < 1){
		return true;
	}
	if (matrix.cols->size == 0 || matrix.rows->size == 0){
		return true;
	}
	return false;
}

bool isMatrixSquare(Matrix matrix){
	if (matrix.colCount == matrix.rowCount){
		return true;
	}
	return false;
}

bool isColumnEmpty(Matrix matrix,int nb){
	ListElement * Col = NULL;

	if (matrix.colCount < 1 || matrix.rowCount < 1){
		return true;
	}
	if (matrix.cols->size == 0 || matrix.rows->size == 0){
		return true;
	}
	
	Col = getElementPos(matrix.cols,nb);
	if (Col == NULL || Col->data == NULL){
		return true;
	}

	return false;
}

bool isRowEmpty(Matrix matrix,int nb){
	ListElement * Row = NULL;

	if (matrix.colCount < 1 || matrix.rowCount < 1){
		return true;
	}
	if (matrix.cols->size == 0 || matrix.rows->size == 0){
		return true;
	}
	Row = getElementPos(matrix.rows,nb);
	if (Row == NULL || Row->data == NULL){
		return true;
	}

	return false;
}

bool equalsMatrix(Matrix m1, Matrix m2){
	int i = 0;
	int j = 0;

	if (m1.colCount == m2.colCount && m1.rowCount == m2.rowCount){
		for (i=0;i<m2.colCount;i++){
			for (j=0;j<m1.rowCount;j++){
				if (getCellValue(m1,i,j)!=getCellValue(m2,i,j)){
					return false;
				}
				
			}
		}
	}else{
	
		return false;
	
	}

	return true;
}

void setRowToTrue(Matrix matrix, int RowNb){
	int i =0;
	for (i=0;i<matrix.colCount;i++){
		setCellValue(matrix,i,RowNb,true);	
	}
	
}

void setColToTrue(Matrix matrix, int ColNb){
	int i =0;
	for (i=0;i<matrix.rowCount;i++){
		setCellValue(matrix,ColNb,i,true);	
	}
	
}

void createSquare(Matrix matrix){
	setRowToTrue(matrix,matrix.rowCount/4);
	setRowToTrue(matrix,matrix.rowCount*3/4);
	setColToTrue(matrix,matrix.colCount/4);
	setColToTrue(matrix,matrix.colCount*3/4);
}