sparse.c

#include "sparse.h"

void sparse_debug(sparse_matrix* m)
{
    for(int r = 0; r < m->rows; r++)
    {
        printf("row %d:\n", r);
        sparse_cell* c = m->row[r];
        while(c != NULL)
        {
            printf("\t%d = %d\n", c->col, c->val);
            c = c->next;
        }
    }
}

/*!
@brief      constructs a new, blank matrix
@param      rows    the number of row the matrix has
@param      cols    the number of columns the matrix has
@returns    a pointer to the newly created matrix
*/
sparse_matrix* sparse_new(int rows, int cols)
{
    sparse_matrix* the_matrix = malloc( sizeof(sparse_matrix) );
    the_matrix->rows = rows;
    the_matrix->cols = cols;
    the_matrix->row = calloc(rows, sizeof(sparse_cell));
    return the_matrix;
}
/*!
@brief      the destructor for sparse_matrix. Frees all the memory!
*/
void sparse_destroy(sparse_matrix* self)
{
    for(int i = 0; i <self->rows; i++)
    {
        sparse_cell* c = self->row[i];
        while(c != NULL)
        {
            sparse_cell* tmp = c;
            c = c->next;
            free(tmp);
        }
    }
    free(self);
}
/*!
@brief      sets the cell specified by row, col to the value. If the cell does not exist, it is created
@param      self        the matrix to set the value in
@param      row         the row of the cell
@param      col         the column of the cell
@param      val         the value to set the cell to
@returns    void
*/
void sparse_set_cell(sparse_matrix* self, int row, int col, int val)
{
    if(self->row[row] == NULL)
    {
        // there are no cells in this row yet
        self->row[row] = malloc(sizeof(sparse_cell));
        self->row[row]->col = col;
        self->row[row]->val = val;
        self->row[row]->next = NULL;
    }
    else
    {
        sparse_cell* c = self->row[row];
        while(c->next != NULL && c->col != col)
        {
            c = c->next;
        }
        if(c->col == col)
        {
            c->val = val;
        }
        else
        {
            if(c->next == NULL)
            {
                // create new cell
                c->next = malloc(sizeof(sparse_cell));
                c->next->col = col;
                c->next->val = val;
                c->next->next = NULL;
            }
            else
            {
                fprintf(stderr, "sparse_set_cell()\tError: Did not find column value and list end is not NULL\n");
            }
        }
    }
}
/*!
@brief      returns the cell at a specific location in the matrix, or NULL if no such cell exists
@param      self        the matrix to search
@param      row         the row of the value
@param      col         the column of the value
@returns    the cell at the specified row and column
*/
sparse_cell* sparse_cell_at(sparse_matrix* self, int row, int col)
{
    sparse_cell* c = self->row[row];
    while(c != NULL)
    {
        if(c->col == col)
        {
            return c;
        }
        c = c->next;
    }
    return NULL;
}
/*!
@brief      returns the item at a specific location in the matrix
@param      self        the matrix to search
@param      row         the row of the value
@param      col         the column of the value
@returns    the value of the cell at the specified row and column
*/
int sparse_value_at(sparse_matrix* self, int row, int col)
{
    sparse_cell* c = sparse_cell_at(self, row, col);
    return c == NULL ? 0 : c->val;
}

/*!
@brief      reads the file in and creates a matrix representation
@param      filename    the file to read the matrix from
@param      transpose   if true, switch the rows and columns
@returns    A pointer to the newly created matrix, or NULL on error
*/
sparse_matrix* sparse_read(char* filename, bool transpose)
{
    char buffer[34]; /* 3 * 10 for the numbers + 2 commas + 2 new line */
    // open file
    FILE* f = fopen(filename, "rt");
    if( f == NULL )
    {
        fprintf(stderr, "sparse_read()\tERROR: could not open input file '%s'\n", filename);
        return NULL;
    }
    // get dimensions
    int num_rows;
    int num_cols;
    if( fgets(buffer, 34, f) != NULL )
    {
        sscanf(buffer, "%d,%d", &num_rows, &num_cols);
    }
    else
    {
        fprintf(stderr, "sparse_read()\tERROR: could not read dimensions of matrix.\n");
    }
    if(transpose)
    {
        int temp = num_rows;
        num_rows = num_cols;
        num_cols = temp;
    }
    sparse_matrix* the_matrix = sparse_new(num_rows, num_cols);
    // get values
    int the_row;
    int the_col;
    int the_val;
    while( !feof(f) )
    {
        if(fgets(buffer, 34, f) != NULL)
        {
            if(sscanf(buffer, "%d,%d,%d", &the_row, &the_col, &the_val) == 3)
            {
                if(!transpose)
                {
                    sparse_set_cell(the_matrix, the_row, the_col, the_val);
                }
                else
                {
                    sparse_set_cell(the_matrix, the_col, the_row, the_val);
                }
                //printf("sparse_read()\tRead (%d, %d, %d)\n", the_row, the_col, the_val);
                //printf("(90, 25) = %d\n", sparse_value_at(the_matrix, 90, 25));
                //sparse_debug(the_matrix);
            }
        }
        
    }
    fclose(f);
    return the_matrix;
}

/*!
@brief      writes the matrix to the specified file
@param      self        the matrix to write out
@param      filename    the location of the file to write to
@returns    true if successful, false otherwise
*/
bool sparse_write(sparse_matrix* self, char* filename)
{
    FILE* f = fopen(filename, "wt");
    if(filename == NULL)
    {
        f = stdout;
    }
    if(f == NULL)
    {
        fprintf(stderr, "sparse_write()\tFailed to open file '%s' for writing.\n", filename);
        return false;
    }
    //-=-=-=-=-=
    fprintf(f, "%d,%d\n", self->rows, self->cols);
    for(int r = 0; r < self->rows; r++)
    {
        for(int c = 0; c < self->cols; c++)
        {
            if(sparse_value_at(self, r, c) != 0)
            {
                fprintf(f, "%d,%d,%d\n", r, c, sparse_value_at(self, r, c));
            }
        }
    }
    fclose(f);
    return true;
}

/*!
@brief      transposes the matrix i.e. interchanges the rows and columns
@param      self    the matrix to transpose
@returns    a new matrix, which is the transposed version of self.
*/
sparse_matrix* sparse_transposed(sparse_matrix* self)
{
    sparse_matrix* to_return = sparse_new(self->cols, self->rows);
    for(int r = 0; r < self->rows; r++)
    {
        for(int c = 0; c < self->cols; c++)
        {
            int val = sparse_value_at(self, r, c);
            if(val != 0)
            {
                //printf("sparse_transposed() - value at %d %d is non-zero (%d)!\n", r, c, val);
                sparse_set_cell(to_return, c, r, val);
            }
        }
    }
    return to_return;
}
/*!
@brief      adds two matrices together, into a new matrix. For a more efficient function, see sparse_add
@param      a   the first matrix
@param      b   the second matrix
@returns    a pointer to a new matrix, which is the value of a * b, or NULL if the matrices are not compatible
*/
sparse_matrix* sparse_sum(sparse_matrix* a, sparse_matrix* b)
{
    if(a->rows != b->rows || a->cols != b->cols)
    {
        fprintf(stderr, "sparse_sum() - dimensions not compatible.");
        return NULL;
    }
    sparse_matrix* to_return = sparse_new(a->rows, a->cols);
    for(int r = 0; r < a->rows; r++)
    {
        for(int c = 0; c < a->cols; c++)
        {
            int val = sparse_value_at(a, r, c) + sparse_value_at(b, r, c);
            if(val != 0) sparse_set_cell(to_return, r, c, val);
        }
    }
    return to_return;
}

/*!
@brief      adds the values of matrix b to matrix a. This is more efficient than sparse_sum.
@param      a   the matrix to add the values too
@param      b   the matrix to get the second set of values from
@returns    matrix a.
*/
sparse_matrix* sparse_add(sparse_matrix* a, sparse_matrix* b)
{
    if(a->rows != b->rows || a->cols != b->cols)
    {
        fprintf(stderr, "sparse_sum_() - dimensions not compatible.");
        return NULL;
    }
    // start with the non-zero cells in matrix a
    // matching cells in b are marked by negating the column
    for(int r = 0; r < a->rows; r++)
    {
        sparse_cell* cell_a = a->row[r];
        while(cell_a != NULL)
        {
            sparse_cell* cell_b = sparse_cell_at(b, r, cell_a->col);
            if(cell_b != NULL)
            {
                cell_a->val += cell_b->val;
                cell_b->col *= -1; // negate column to mark that this cell has been dealt with
            }
            cell_a = cell_a->next;
        }
    }
    // deal with the non-zero cells in matrix b.
    // cells with a positive column value are added into matrix a.
    // cells with a negative column value are "fixed", by making the column positive again.
    for(int r = 0; r < b->rows; r++)
    {
        sparse_cell* cell = b->row[r];
        while(cell != NULL)
        {
            if(cell->col >= 0)
            {
                //printf("sparse_add()\t\tat (%d, %d) - setting to %d\n", r, cell->col, cell->val);
                sparse_set_cell(a, r, cell->col, cell->val);
            }
            else
            {
                cell->col *= -1; // fix matrix b
            }
            cell = cell->next;
        }
    }
    return a;
}
/*!
@brief      multiplies two matrices together
@param      a   the first matrix
@param      b   the second matrix
@returns    a pointer to a new matrix, which is the result of a . b, or NULL if the matrices are not compatible
*/
sparse_matrix* sparse_mul(sparse_matrix* a, sparse_matrix* b)
{
    if(a->cols != b->rows) { fprintf(stderr, "sparse_mul() - ERROR: Matrices do not have compatible dimensions\n"); return NULL; }
    sparse_matrix* ab = sparse_new(a->rows, b->cols);
    for(int i = 0; i < a->rows; i++)
    {
        for(int j = 0; j < b->cols; j++)
        {
            int sum = 0;
            for(int k = 0; k < a->cols; k++)
            {
                sum += sparse_value_at(a, i, k) * sparse_value_at(b, k, j);
            }
            sparse_set_cell(ab, i, j, sum);
        }
    }
    return ab;
}

/*!
@brief      multiplies two matrices together
@param      a   the first matrix
@param      b   the second matrix. This should be transposed before being passed here
@returns    a pointer to a new matrix, which is the result of a . b, or NULL if the matrices are not compatible
@warning    matrix b should be transposed before being passed to this function
*/
sparse_matrix* sparse_mul_optimised(sparse_matrix* a, sparse_matrix* b)
{
    if(a->cols != b->cols) { fprintf(stderr, "sparse_mul_optimised() - ERROR: Matrices do not have compatible dimensions\n"); return NULL; }
    sparse_matrix* ab = sparse_new(a->rows, b->rows);
    for(int i = 0; i < a->rows; i++)
    {
        for(int j = 0; j < b->rows; j++)
        {
            int sum = 0;
            sparse_cell* cell_a = a->row[i];
            while(cell_a != NULL)
            {
                sum += cell_a->val * sparse_value_at(b, j, cell_a->col);
                cell_a = cell_a->next;
            }
            // if(cell_a != NULL && cell_b != NULL)
            // {
            //     for(int k = 0; k < a->cols; k++)
            //     {
            //         sum += sparse_value_at(a, i, k) * sparse_value_at(b, j, k);
            //     }
            // }
            
            sparse_set_cell(ab, i, j, sum);
        }
    }
    return ab;
}

/*!
@brief      compares two matrices
@param      a    the first matrix
@param      b    the second matrix
@returns    true if matricies are equal, false otherwise
*/
bool sparse_is_equal(sparse_matrix* a, sparse_matrix* b)
{
    if(a == NULL || b == NULL) return false;
    if(a->rows != b->rows) return false;
    if(a->cols != b->cols) return false;
    if(a == b) return true;
    bool valid = true;
    for(int r = 0; r < a->rows; r++)
    {
        for(int c = 0; c < a->cols; c++)
        {
            if(sparse_value_at(a, r, c) != sparse_value_at(b, r, c))
            {
                fprintf(stderr, "sparse_is_equal() - Failed at (%d, %d): %d != %d\n", r, c, sparse_value_at(a, r, c), sparse_value_at(b, r, c));
                valid = false; // it would be more efficient to return false here, but to aid debugging we continue
            }
        }
    }
    return valid;
}