7
\$\begingroup\$

I have this C program that rotates a character matrix. This is a straightforward rewrite of this Java implementation. Both versions do additional \$\Theta(mn)\$ preprocessing and require \$\Theta(mn)\$ additional space in order to run arbitrary rotations in \$\Theta((m + n) \min (m, n)) = \Theta(\max(m, n)\min(m, n)) = \Theta(mn)\$ time.

rotable_char_matrix.h

#ifndef ROTABLE_CHAR_MATRIX_H
#define ROTABLE_CHAR_MATRIX_H

#include <stdlib.h>

typedef struct rotation_list_node {
    size_t x;
    size_t y;
    struct rotation_list_node* prev;
    struct rotation_list_node* next;
} rotation_list_node;

typedef struct rotable_char_matrix {
    size_t rows;
    size_t cols;
    size_t number_of_rotation_lists;
    size_t buffer_capacity;
    size_t buffer_size;
    char* data;
    char* buffer;
    rotation_list_node** rotations_list_heads;
    size_t* rotation_list_lengths;
} rotable_char_matrix;

/********************************
* Initializes a rotable matrix. *
********************************/
void rotable_char_matrix_init(rotable_char_matrix* matrix,
                              size_t rows,
                              size_t columns);

/******************************************
* Releases all the resources of a matrix. *
******************************************/
void rotable_char_matrix_clean(rotable_char_matrix* matrix);

/***********************************************
* Reads an individual character from a matrix. *
***********************************************/
char rotable_char_matrix_get(rotable_char_matrix* matrix,
                             size_t x,
                             size_t y);

/*********************************************************
* Writes a character at a particular spot in the matrix. *
*********************************************************/
void rotable_char_matrix_set(rotable_char_matrix* matrix,
                             size_t x,
                             size_t y,
                             char value);

/**************************************************************************
* Rotates the entire matrix 'abs(count)' steps. Positive value of 'count' *
* rotates clockwise, negative value of 'count' rotates counter-clockwise. *
**************************************************************************/
void rotable_char_matrix_rotate(rotable_char_matrix* matrix,
                                int count);

/***********************************************
* Returns the number of columns in the matrix. *
***********************************************/
size_t rotable_char_matrix_columns(rotable_char_matrix* matrix);

/********************************************
* Returns the number of rows in the matrix. *
********************************************/
size_t rotable_char_matrix_rows(rotable_char_matrix* matrix);

#endif /* ROTABLE_CHAR_MATRIX_H */

rotable_char_matrix.c

#include "rotable_char_matrix.h"
#include <stdlib.h>
#define MIN(X,Y) (((X) < (Y)) ? (X) : (Y))

/********************************************************
* Checks that the number of requested rows is not zero. *
********************************************************/
static void check_number_of_rows(size_t rows)
{
    if (rows == 0)
    {
        abort();
    }
}

/***********************************************************
* Checks that the number of requested columns is not zero. *
***********************************************************/
static void check_number_of_cols(size_t cols)
{
    if (cols == 0)
    {
        abort();
    }
}

/*******************************************************************************
* Populate the 'rotation_list_index'th rotation list. The list with index zero *
* is the outermost.                                                            *
*******************************************************************************/
static void populate_rotation_list_at_index(rotable_char_matrix* matrix,
                                            size_t rotation_list_index)
{
    rotation_list_node* previous_node = NULL;
    rotation_list_node* current_node;
    size_t x;
    size_t y;

    for (x = rotation_list_index; x != matrix->cols - rotation_list_index; x++)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = x;
        current_node->y = rotation_list_index;

        if (previous_node == NULL)
        {
            matrix->rotations_list_heads[rotation_list_index] = current_node;
        }
        else
        {
            previous_node->next = current_node;
            current_node->prev = previous_node;
        }

        previous_node = current_node;
    }

    for (y = rotation_list_index + 1;
         y != matrix->rows - rotation_list_index - 1;
         y++)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = matrix->cols - rotation_list_index - 1;
        current_node->y = y;
        previous_node->next = current_node;
        current_node->prev = previous_node;
        previous_node = current_node;
    }

    for (x = matrix->cols - rotation_list_index - 1;
         x > rotation_list_index;
         x--)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = x;
        current_node->y = matrix->rows - rotation_list_index - 1;
        previous_node->next = current_node;
        current_node->prev = previous_node;
        previous_node = current_node;
    }

    /**************************************************************************
    * If in the above loop 'rotation_list_index' is zero, the loop will never *
    * terminate. For this reason, we "unroll" the last iteration out of it.   *
    **************************************************************************/
    current_node = malloc(sizeof(*current_node));
    current_node->x = rotation_list_index;
    current_node->y = matrix->rows - rotation_list_index - 1;
    previous_node->next = current_node;
    current_node->prev = previous_node;
    previous_node = current_node;

    for (y = matrix->rows - rotation_list_index - 2;
         y > rotation_list_index;
         y--)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = rotation_list_index;
        current_node->y = y;
        previous_node->next = current_node;
        current_node->prev = previous_node;
        previous_node = current_node;
    }

    previous_node->next = matrix->rotations_list_heads[rotation_list_index];
    matrix->rotations_list_heads[rotation_list_index]->prev = previous_node;
    matrix->rotation_list_lengths[rotation_list_index] =
        2 * (matrix->cols - 2 * rotation_list_index) +
        2 * (matrix->rows - 2 * (rotation_list_index + 1));
}

/**************************************************
* Populates all the rotation lists of the matrix. *
**************************************************/
static void populate_rotation_lists(rotable_char_matrix* matrix)
{
    size_t rotation_list_index;

    for (rotation_list_index = 0;
         rotation_list_index != matrix->number_of_rotation_lists;
         rotation_list_index++)
    {
        populate_rotation_list_at_index(matrix, rotation_list_index);
    }
}

/********************************
* Initializes a rotable matrix. *
********************************/
void rotable_char_matrix_init(rotable_char_matrix* matrix,
                              size_t rows,
                              size_t cols)
{
    if (matrix != NULL)
    {
        check_number_of_rows(rows);
        check_number_of_cols(cols);
        matrix->rows = rows;
        matrix->cols = cols;
        matrix->data = calloc(rows * cols, sizeof(char));
        matrix->buffer_capacity = rows + cols - 2;
        matrix->buffer = malloc(sizeof(char) * (matrix->buffer_capacity));
        matrix->buffer_size = 0;
        matrix->number_of_rotation_lists = MIN(rows / 2, cols / 2);
        matrix->rotation_list_lengths =
        malloc(matrix->number_of_rotation_lists *
               sizeof(*matrix->rotation_list_lengths));

        matrix->rotations_list_heads =
        malloc(matrix->number_of_rotation_lists *
               sizeof(*matrix->rotations_list_heads));

        populate_rotation_lists(matrix);
    }
}

/*************************
* Frees a rotation list. *
*************************/
static void free_single_rotation_list(rotation_list_node* head)
{
    rotation_list_node* current_node;
    rotation_list_node* next_node;
    head->prev->next = NULL;

    for (current_node = head; current_node != NULL; current_node = next_node)
    {
        next_node = current_node->next;
        free(current_node);
    }
}

/********************************************
* Frees all the rotation lists of a matrix. *
********************************************/
static void free_rotation_lists(rotable_char_matrix* matrix)
{
    size_t rotation_list_index;

    for (rotation_list_index = 0;
         rotation_list_index != matrix->number_of_rotation_lists;
         rotation_list_index++)
    {
        free_single_rotation_list(
                            matrix->rotations_list_heads[rotation_list_index]);
    }
}

/******************************************
* Releases all the resources of a matrix. *
******************************************/
void rotable_char_matrix_clean(rotable_char_matrix* matrix)
{
    free_rotation_lists(matrix);
    free(matrix->buffer);
    free(matrix->data);
    free(matrix->rotation_list_lengths);
    free(matrix->rotations_list_heads);
}

/***********************************************
* Reads an individual character from a matrix. *
***********************************************/
char rotable_char_matrix_get(rotable_char_matrix* matrix, size_t x, size_t y)
{
    return matrix->data[matrix->cols * y + x];
}

/*********************************************************
* Writes a character at a particular spot in the matrix. *
*********************************************************/
void rotable_char_matrix_set(rotable_char_matrix* matrix,
                             size_t x,
                             size_t y,
                             char value)
{
    matrix->data[matrix->cols * y + x] = value;
}

/******************************************************************************
* Rotates a 'rotation_list_index'th rotation list in the matrix 'count' steps *
* counter-clockwise.                                                          *
******************************************************************************/
static void rotate_rotation_list_counter_clockwise(rotable_char_matrix* matrix,
                                                   size_t rotation_list_index,
                                                   size_t count)
{
    rotation_list_node* source_node;
    rotation_list_node* target_node;

    source_node = matrix->rotations_list_heads[rotation_list_index];
    target_node = source_node;

    size_t i;

    for (i = 0; i != count; i++)
    {
        matrix->buffer[i] = rotable_char_matrix_get(matrix,
                                                    source_node->x,
                                                    source_node->y);
        source_node = source_node->next;
    }

    for (i = 0;
         i != matrix->rotation_list_lengths[rotation_list_index] - count;
         i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                rotable_char_matrix_get(matrix,
                                                        source_node->x,
                                                        source_node->y));
        target_node = target_node->next;
        source_node = source_node->next;
    }

    for (i = 0; i != count; i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                matrix->buffer[i]);

        target_node = target_node->next;
    }
}

/******************************************************************************
* Rotates a 'rotation_list_index'th rotation list in the matrix 'count' steps *
* clockwise.                                                                  *
******************************************************************************/
static void rotate_rotation_list_clockwise(rotable_char_matrix* matrix,
                                           size_t rotation_list_index,
                                           size_t count)
{
    rotation_list_node* source_node;
    rotation_list_node* target_node;

    source_node = matrix->rotations_list_heads[rotation_list_index];
    target_node = source_node;

    size_t i;

    for (i = 0; i != count; i++)
    {
        matrix->buffer[i] = rotable_char_matrix_get(matrix,
                                                    source_node->x,
                                                    source_node->y);
        source_node = source_node->prev;
    }

    for (i = 0;
         i != matrix->rotation_list_lengths[rotation_list_index] - count;
         i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                rotable_char_matrix_get(matrix,
                                                        source_node->x,
                                                        source_node->y));
        target_node = target_node->prev;
        source_node = source_node->prev;
    }

    for (i = 0; i != count; i++)
    {
        rotable_char_matrix_set(matrix,
                                target_node->x,
                                target_node->y,
                                matrix->buffer[i]);

        target_node = target_node->prev;
    }
}

/*******************************************************************************
* Rotates the 'rotation_list_index'th rotation list of a matrix 'count' steps. *
* If count is positive, rotates clockwise. Otherwise, rotates                  *
* counter-clockwise.                                                           *
*******************************************************************************/
static void rotate_rotation_list(rotable_char_matrix* matrix,
                                 size_t rotation_list_index,
                                 int count)
{
    size_t current_rotation_list_length;
    int count2;

    current_rotation_list_length =
    matrix->rotation_list_lengths[rotation_list_index];

    count %= (int) current_rotation_list_length;

    if (count == 0)
    {
        /* Nothing to do. */
        return;
    }

    if (count < 0)
    {
        /* Rotate counter-clockwise. */
        count = -count;
        count2 = (int)(current_rotation_list_length) - count;

        if (count < count2)
        {
            rotate_rotation_list_counter_clockwise(matrix,
                                                   rotation_list_index,
                                                   count);
        }
        else
        {
            rotate_rotation_list_clockwise(matrix,
                                           rotation_list_index,
                                           count2);
        }
    }
    else
    {
        /* Rotate clockwise. */
        count2 = (int)(current_rotation_list_length) - count;

        if (count < count2)
        {
            rotate_rotation_list_clockwise(matrix,
                                           rotation_list_index,
                                           count);
        }
        else
        {
            rotate_rotation_list_counter_clockwise(matrix,
                                                   rotation_list_index,
                                                   count2);
        }
    }
}

/**************************************************************************
* Rotates the entire matrix 'abs(count)' steps. Positive value of 'count' *
* rotates clockwise, negative value of 'count' rotates counter-clockwise. *
**************************************************************************/
void rotable_char_matrix_rotate(rotable_char_matrix* matrix, int count)
{
    size_t rotation_list_index;

    for (rotation_list_index = 0;
         rotation_list_index != matrix->number_of_rotation_lists;
         rotation_list_index++)
    {
        rotate_rotation_list(matrix, rotation_list_index, count);
    }
}

/***********************************************
* Returns the number of columns in the matrix. *
***********************************************/
size_t rotable_char_matrix_columns(rotable_char_matrix* matrix)
{
    return matrix->cols;
}

/********************************************
* Returns the number of rows in the matrix. *
********************************************/
size_t rotable_char_matrix_rows(rotable_char_matrix* matrix)
{
    return matrix->rows;
}

main.c

#include "rotable_char_matrix.h"
#include <stdio.h>

#define ROWS 4
#define COLS 5

static void print_matrix(rotable_char_matrix* matrix)
{
    size_t row;
    size_t col;

    for (row = 0; row != rotable_char_matrix_rows(matrix); row++)
    {
        for (col = 0; col != rotable_char_matrix_columns(matrix); col++)
        {
            printf("%c", rotable_char_matrix_get(matrix, col, row));
        }

        puts("");
    }
}

int main(int argc, const char * argv[]) {
    int count;
    int tokens_read;
    rotable_char_matrix matrix;
    rotable_char_matrix_init(&matrix, ROWS, COLS);
    char c = 'a';
    size_t row;
    size_t col;

    for (row = 0; row < ROWS; row++)
    {
        for (col = 0; col < COLS; col++)
        {
            rotable_char_matrix_set(&matrix, col, row, c++);
        }
    }

    for (;;)
    {
        print_matrix(&matrix);
        printf("\n> ");
        tokens_read = scanf("%d", &count);

        if (tokens_read != 1 || feof(stdin) || ferror(stdin))
        {
            break;
        }

        rotable_char_matrix_rotate(&matrix, count);
    }

    rotable_char_matrix_clean(&matrix);
    return 0;
}

Critique request

I would like to hear anything that comes to mind.

\$\endgroup\$
3
\$\begingroup\$

Overall, I have very little negative to say about your code. Still, there are some things I'd like to nitpick about a little:

  1. I'm not convinced that it is still appropriate to define MIN as a macro in our modern times. You likely know about all the drawbacks macros have (no type safety, proneness to bad behavior because of missing parentheses etc.), and you don't have any significant drawbacks if you defined it as a function (except for the issue of type rigidity, which does not apply in your case, however, since you only use MIN once and could define it for the appropriate type).
  2. In my opinion, check_number_of_rows and check_number_of_columns are rather obfuscating the underlying code. Since both of these functions consist of a simple check, and their names do not actually convey what is checked, you are actually losing clarity here. Encountering calls to these functions in the code inevitably makes you go back and read their definitions, because the name just suggests that a check is carried out, not what check. My suggestion would be an assert-like method to which you pass a condition and which calls abort if that condition is not met. That way, you abstract a part of the functionality away (the fail-on-error), but retain the self-explaining property of those checks.
  3. You can omit the parentheses around the argument of sizeof if it is not a type argument. For example, sizeof(*current_node) can be written as sizeof *current_node. The advantage of removing the parentheses here is to make it clear when the argument is a variable and when it is a type name.
  4. I don't know how much you care about such things, but ideally, you should check the return value of functions that could fail. This includes malloc, and if your program fails, it is a matter of grace and correctness whether you let it just crash or fail gracefully (correctness in a sense that failing gracefully implies that you accounted for a certain edge condition, such as out-of-memory).
  5. Consider factoring "run once"-code out of loops. For example,

    rotation_list_node* previous_node = NULL;
    rotation_list_node* current_node;
    size_t x;
    size_t y;
    
    for (x = rotation_list_index; x != matrix->cols - rotation_list_index; x++)
    {
        current_node = malloc(sizeof(*current_node));
        current_node->x = x;
        current_node->y = rotation_list_index;
    
        if (previous_node == NULL)
        {
            matrix->rotations_list_heads[rotation_list_index] = current_node;
        }
        else
        {
            previous_node->next = current_node;
            current_node->prev = previous_node;
        }
    
        previous_node = current_node;
    }
    

    (taken from populate_rotation_list_at_index) can be rewritten as

    rotation_list_node* previous_node;
    rotation_list_node* current_node;
    size_t x;
    size_t y;
    
    previous_node = malloc(sizeof *previous_node);
    previous_node->x = rotation_list_index;
    previous_node->y = rotation_list_index;
    
    matrix->rotations_list_heads[rotation_list_index] = previous_node;
    
    for (x = rotation_list_index + 1; x != matrix->cols - rotation_list_index;
         x++) {
        current_node = malloc(sizeof *current_node);
        current_node->x = x;
        current_node->y = rotation_list_index;
    
        previous_node->next = current_node;
        current_node->prev = previous_node;
    
        previous_node = current_node;
    }
    

    which features a simpler for-loop body in exchange for some code duplication (which could be reduced by a create_node()-function if desired). Gain some, lose some. I personally prefer the latter version, but ultimately this is just a personal preference.

  6. You should refactor rotate_rotation_list_clockwise and rotate_rotation_list_counter_clockwise. Currently, both methods have 44 lines (counting empty lines), of which 37 are the same. This makes my DRY alarm bell go wild. Although the situation is somewhat difficult, the most concise way to join these methods into one generic implementation would be to either use a macro to determine whether you want to move in clockwise (i.e. have all relevant lines be of the form source_node = source_node->prev;) or counter-clockwise (i.e. have all relevant lines be of the form source_node = source_node->next;) direction. There are also other alternatives: For example, you could pass the nodes through a callback instead to determine which direction the rotation should move in, or you could join the two functions into one by adding an additional parameter which tells the direction and just have an if on it.

\$\endgroup\$
2
\$\begingroup\$

Naming

Good naming conventions.

Information hiding

This is my primary review point.

The definition of rotation_list_node is not needed in rotable_char_matrix.h.

typedef struct rotation_list_node rotation_list_node;

is sufficient.

The complete definition should exist in rotable_char_matrix.c to unburden the user of rotable_char_matrix details and prevent direct access.

Further, consider doing the same for rotable_char_matrix. This implies the initialization returning a pointer rather than the calling code allocating space. Also some get/set functions needed. Yet data abstraction helps in the long run.

Auto formating

The below and others imply a manual formating and is unproductive. Adopt a suitable auto-formating style and tool.

        matrix->buffer[i] = rotable_char_matrix_get(matrix,
                                                    source_node->x,
                                                    source_node->y);

vs.

        matrix->buffer[i] = rotable_char_matrix_get(matrix, 
            source_node->x, source_node->y);

Minor

With printf("\n> "); tokens_read = scanf("%d", &count);, better to insure output is printed before scanning with a fflush(stdout);.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.