13 KiB
% Cellular Automaton LO27 % Bartuccio Antoine \cr Porée De Ridder Jean % Autumn 2016
\newpage
Introduction
The goal of this project is to provide a library containing a new abstract data type called Matrix with associated function to manipulate them. The final program have to enable a user to test the library in an interactive and practical way.
Since we decided to not store false value \footnote{cellElement does not contains values anymore, their existence is their value}in our matrix and to not store the colElement and rowElement \footnote{they are unified and renamed as listElement}that are empty, we decided not to worry too much about performances and we encapsulated all access to stored data in the Matrix structure to avoid too much complexity and allow more modularity, readability and re-usability. We created high level tools to manipulate our matrix and used it all along the project.
For compilation we didn't used the -ansi flag since we had to deal with both clang and gcc for compilation and clang didn't accept this flag. Instead, we used the -std=c89 flag witch contains the same rules but is accepted on both softwares. Compiling with -ansi still works.
We decided to create two different library. One for the graphical interface (which require SDL2) and the other with the Matrix data type) so this way you may just have to compile one lib if you don't need the gui.
Description of abstract data types
Every function and data type are described in the documentation given with the project. This documentation is generated with doxygen.
\newpage
Algorithmic
The most interesting function are getCellValue and setCellValue. Those are the one we rely on the most. They are our way of dealing with our complex data structure allowing us to avoid to store false values. They are the functions that need the more computational power on the long run but are really useful due to their level of abstraction and their high level.
getCellValue is a simple function based on findMatrixElem :
getCellValue(matrix:Matrix, ColPos:integer , RowPos:integer ) : bool
BEGIN
if ( colCount(matrix) <= ColPos OR rowCount(matrix) <= RowPos)
getCellValue <- ERROR
endif
if (findMatrixElem( matrix , ColPos , RowPos ) = NULL)
getCellValue <- false
endif
getCellValue <- true
END
findMatrixElem( matrix:Matrix , ColPos:integer, RowPos:integer ) : *cellElement
BEGIN
Row:ListElement <- NULL
elem:*cellElement <- NULL
Row <- getElementPos(rows(matrix),RowPos)
if (Row = NULL)
findMatrixElem <- NULL
endif
elem <- data(Row)
while (elem != NULL AND colIndex(elem) != ColPos)
elem <- nextCol(elem)
endwhile
findMatrixElem <- elem
END
setCellValue is a simple function based on createMatrixElem and deleteMatrixElement :
setCellValue(matrix:Matrix, ColPos:integer, RowPos:integer,value:bool):bool
BEGIN
if (value = true)
setCellValue <- createMatrixElem(matrix,ColPos,RowPos)
else
if ( deleteMatrixElem(matrix,ColPos,RowPos) >= 0 )
setCellValue <- true
else
setCellValue <- false
endif
endif
END
createMatrixElem( matrix:Matrix, ColPos:integer, RowPos:integer):bool
Row:*ListElement <-NULL
Col:*Listelemnt <- NULL
error:integer <- 0
elem: *cellElement <- NULL
tmp: *cellElement<- NULL
if (colCount(matrix) <= ColPos OR rowCount(matrix) <= RowPos )
createMatrixElem <- ERROR /* out of bounds */
endif
elem <- createCellElem()
setPositionIndex(elem,ColPos,RowPos)
Row <- getElementPos(rows(matrix),RowPos)
if (Row != NULL AND data(Row) != NULL)
if (colIndex(data(Row)) = ColPos)
error ++ /* the element already exists */
else
if (colIndex(data(Row)) > ColPos)
nextCol(elem) <- data(Row)
data(Row) <- elem
endif
else
tmp <- data(Row)
/* searching the previous element */
while ( nextCol(tmp) != NULL AND nextCol(colIndex(tmp)) < ColPos) do
tmp <- nextCol(tmp)
endwhile
if ( nextCol(tmp) = NULL OR colIndex(nextCol(tmp)) > ColPos)
nextCol(elem) <- nextCol(tmp)
nextCol(tmp) <- elem
else
error ++ /* the element already exists */
endif
endif
else
/* if the list is empty */
push(rows(matrix),elem)
pos(tail(rows(matrix))) <- RowPos
endif
Col <- getElementPos(cols(matrix),ColPos)
if (Col != NULL AND data(Col) != NULL)
if (rowIndex(data(Col)) = RowPos)
error ++ /* the element already exists */
else
if (rowIndex(data(Col)) > RowPos)
nextRow(elem) <- data(Col)
data(Col) <- elem
endif
else
tmp <- data(Col)
/* searching the previous element */
while (nextRow(tmp) != NULL AND rowIndex(nextRow(tmp)) < RowPos) do
tmp <- nextRow(tmp)
endwhile
if (nextRow(tmp) = NULL OR rowIndex(nextRow(tmp)) > RowPos)
nexRow(elem) <- nextRow(tmp)
newRow(tmp) <- elem
else
error ++ /* the element already exists */
endif
endif
else
/* if the list is empty */
push(cols(matrix),elem)
pos(tail(cols(matrix))) <- ColPos
endif
if (error != 0)
/* if the element already exists, free it */
freeCellElement(elem)
createMatrixElem <- true
else
createMatrixElem <- false
endif
END
deleteMatrixElem(matrix:Matrix,ColPos:integer, RowPos:integer ):integer
BEGIN
elem : *cellElement <- NULL
tmp : *cellElement <- NULL
Row : *ListElement <- NULL
Col : *ListElement <- NULL
elem <- findMatrixElem(matrix,ColPos,RowPos)
if (elem = NULL)
/* if the element does not exists */
deleteMatrixElem <- 0
endif
Row <- getElementPos(rows(matrix),RowPos)
if (Row = NULL)
/* this shouldn't happend */
deleteMatrixElem <- -1
endif
if (data(Row) = NULL)
/* this shouldn't happend too */
removeElementPos(rows(matrix),RowPos)
deleteMatrixElem <- -1
endif
if (colIndex(data(Row)) = ColPos)
/* the element is the first element */
data(Row) <- nextCol(elem)
else
tmp <- data(Row)
/* finding prefious element */
while (nextCol(tmp) != NULL AND nextCol(tmp) != elem) do
tmp <- nextCol(tmp)
endwhile
if (nextCol(tmp) != NULL)
/* linking correctly the previous element */
nextCol(tmp) <- nextCol(elem)
endif
endif
if (data(Row) = NULL)
/* if the row is empty now we delete it to save memory */
removeElementPos(rows(matrix),RowPos)
endif
Col <- getElementPos(cols(matrix),ColPos)
if (Col = NULL)
/* this shouldn't happend */
deleteMatrixElem <- -2
endif
if (data(Col) = NULL)
/* this shouldn't happend too */
removeElementPos(cols(matrix),ColPos)
deleteMatrixElem <- -1
endif
if (rowIndex(data(Col)) = RowPos)
/* the element is the first element */
data(Col) <- nextRow(elem)
else
tmp <- data(Col)
/* finding prefious element */
while (nextRow(tmp) != NULL AND nextRow(tmp) != elem) do
tmp <- nextRow(tmp)
endwhile
if (nextRow(tmp) != NULL)
/* linking correctly the previous element */
nextRow(tmp) <- nextRow(elem)
endif
endif
if (data(Col) = NULL)
/* if the col is empty now we delete it to save memory */
removeElementPos(cols(matrix),ColPos)
endif
freeCellElement(elem)
deleteMatrixElem <- 1
END
Functions andColSequenceOnMatrix and orColSequenceOnMatrix are implemented with colSequenceOnMatrix and are really not interesting so we're gonna provide the algorithm of the last one :
colSequenceOnMatrix(m:Matrix, operator:(function(bool, bool):bool)): Matrix
BEGIN
a:bool
b:bool
i:integer
j:integer
newM:Matrix <- createMatrix()
rowCount(newM) <- rowCount(m)
if (colCount(m) <= 1) then
colCount(newM) <- 0
colSequenceOnMatrix <- newM
endif
colCount(newM) <- value(colCount(m)) - 1
for i from 0 to value(colCount(m)) - 2 do
for j from 0 to value(rowCount(m)) - 2 do
a <- getCellValue(m, i, j)
b <- getCellValue(m, i + 1, j)
if operator(a, b) then
setCellValue(newM, i, j, true)
endif
endfor
endfor
colSequenceOnMatrix <- newM
END
This is the same thing for andRowSequenceOnMatrix and orRowSequenceOnMatrix :
rowSequenceOnMatrix(m:Matrix, operator:(function(bool, bool):bool)): Matrix
BEGIN
a:bool
b:bool
i:integer
j:integer
newM:Matrix <- createMatrix()
colCount(newM) <- value(colCount(m))
if value(rowCount(m)) <= 1 then
rowCount(newM) <- 0
rowSequenceOnMatrix <- newM
endif
rowCount(newM) <- value(rowCount(m)) - 1
for i from 0 to value(rowCount(m)) - 1 do
for j from 0 to value(colCount(m)) - 1 do
a <- getCellValue(m, i, j)
b <- getCellValue=(m, i, j + 1)
if operator(a, b) then
setCellValue(newM, i, j, true)
endif
endfor
endfor
rowSequenceOnMatrix <- newM
END
Here are the algorithm of the function applyRules and all the one related to it :
applyRules ( matrix:Matrix, Rules:integer, N:integer):Matrix
BEGIN
RulesMatrix :integer[9] /* the size is the number of fundamental rules */
i:integer <- 0
power:integer <- 2
sum:integer <- 0
j:integer <- 0
tempMatrix1:Matrix
tempMatrix2:Matrix
if (Rules <= 0 OR N < 1)
applyRules <- matrix
endif
/* decompotition of the rule in basic rules */
while(power <= 512) do
RulesMatrix[i] <- Rules%power - sum
sum <- Rules%power
if (RulesMatrix[i]!=0)
i++
endif
power <- power*2
endwhile
/* application of the rule */
tempMatrix1 <- matrixFromRules(matrix, i, RulesMatrix)
for j from 0 to N do
tempMatrix2 <- matrixFromRules(tempMatrix1 ,i, RulesMatrix)
freeMatrix(tempMatrix1)
tempMatrix1 <- tempMatrix2
endfor
applyRules <- tempMatrix1
END
matrixFromRules(m:Matrix, n:integer, rules:integer[0...n-1]):Matrix
BEGIN
i:integer
j:integer
bools:bool[n-1]
result:Matrix <- createMatrix()
if (isEmpty(rules)){
colCount(result) <- 0
rowCount(result) <- 0
matrixFromRules <- result
}
colCount(result) <- value(colCount(m))
rowCount(result) <- value(rowCount(m))
for i from 0 to value(rowCount(m)) - 1 do
for j from 0 to value(colCount(m)) do
bools <- getFromRules(m, j, i, n, rules)
if not isEmpty(bools) then
if MXOR(n, bools) then
setCellValue(result, j, i, true)
endif
endif
endfor
endfor
matrixFromRules <- result
END
getFromRules(m:Matrix, ColPos:integer, RowPos:integer, n:integer, int rules: integer[0...n-1]):bool[0...n-1]
BEGIN
bools:bool[0...n-1]
i:integer
for i from 0 to n-1 then
switch rules[i]
case 8
bools[i] <- topRule(m, ColPos, RowPos)
case 128
bools[i] <- bottomRule(m, ColPos, RowPos)
case 2
bools[i] <- leftRule(m, ColPos, RowPos)
case 32
bools[i] <- rightRule(m, ColPos, RowPos)
case 4
bools[i] <- topLeftRule(m, ColPos, RowPos)
case 16
bools[i] <- topRightRule(m, ColPos, RowPos)
case 256
bools[i] <- bottomLeftRule(m, ColPos, RowPos)
case 64
bools[i] <- bottomRightRule(m, ColPos, RowPos)
case 1
bools[i] <- firstRule(m, ColPos, RowPos)
endswitch
endfor
getFromRules <- bools
END
\newpage
Conclusion
As we said before, we decided to not store false values in our matrix. So, by default, all values are set to false and every time we created a new matrix, we only used setCellValue for true values.
To easily handle errors, we added ERROR to the bool enum. It was handy to detect out of bounds values and could be treated as false values on applyRules with the errorToFalse function.
We created OR, AND and XOR function. OR and AND were created for colSequenceOnMatrix and rowSequenceOnMatrix to be passed as pointers. The XOR function was created for readability. We also added MXOR function to apply XOR on a given array of boolean.
On applyRules, we decided to create an array with a static size of 9 integers. We agreed on this value because it was the maximum possible number of rules that could be applied at the same time and because it was the most balanced choice between performances and memory. Actually, 9 integers doesn't take so much memory and avoided to use malloc and realloc that relied on systems calls and on the operating system will that could slow down the process of factorization.
For boolean matrix, we created a structure to easily handle the size inside all our function and to respect the given prototype where we should have guessed the size.
Our program is fully functional but encounter, as we predicted, some performance issues on big matrix. We tested for our SDL GUI (that should only used on big matrix) a 1900x1080 sized matrix and it was long to process (more than 5 seconds). It was due to the original design we had to follow and would have been a lot faster with only a simple array-based allocated matrix keeping all false values.
We also had troubles with the freeMatrix function that is not really optimized. Our first attempt without slow setCellValue and getCellValue functions was a nightmare to understand and caused memory loss. It was unreadable and we both decided to prioritize readability over performances. Memory loss was unacceptable since the main goal was to sacrifice computational power to save memory.