#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int**
shiftGrid(int** grid, int gridSize, int* gridColSize, int k, int* returnSize,
          int** returnColumnSizes)
{
    int **ret = calloc(gridSize + 1, sizeof(int*));

    long total_size = 0;

    *returnSize = gridSize;
    *returnColumnSizes = calloc(gridSize + 1, sizeof(int));
    for ( int i = 0; i < gridSize; ++i ) {
        int col_size = gridColSize[i];

        (*returnColumnSizes)[i] = col_size;
        ret[i] = calloc(col_size + 1, sizeof(**ret));

        total_size += col_size;
    }

    int *intermed = calloc(total_size + 1, sizeof(int));
    long intermed_size = 0;

    for ( int i = 0; i < gridSize; ++i ) {
        int col_size = gridColSize[i];
        for ( int j = 0; j < col_size; ++j ) {
            intermed[intermed_size++] = grid[i][j];
        }
    }

    for ( int i = 0; i < k; ++i ) {
        int last = intermed[intermed_size-1];
        int *interinter = calloc(intermed_size, sizeof(int));
        for ( int j = 0; j < intermed_size; ++j ) {
            interinter[j] = intermed[j];
        }
        for ( int j = 0; j < intermed_size-1; ++j ) {
            intermed[j+1] = interinter[j];
        }
        //memmove(intermed+1, intermed, intermed_size-2);
        free(interinter);
        intermed[0] = last;
    }

    intermed_size = 0;
    for ( int i = 0; i < gridSize; ++i ) {
        int col_size = gridColSize[i];
        for ( int j = 0; j < col_size; ++j ) {
            ret[i][j] = intermed[intermed_size++];
        }
    }
    free(intermed);
    return ret;
}

struct matrix {
    int **data;
    unsigned long first_size;
    unsigned long second_size;
};

char *
matrix_to_cstr(const struct matrix *m)
{
    static char data[1024] = {0};
    static unsigned long cap = 1024;

    unsigned long size = 0;

    memset(data, 0, cap);

    data[size++] = '[';
    for ( unsigned long i = 0; i < m->first_size; ++i ) {
        if ( i == 0 ) {
            data[size++] = '[';
        } else {
            data[size++] = ',';
            data[size++] = '[';
        }
        for ( unsigned long j = 0; j < m->second_size; ++j ) {
            if ( j == 0 ) {
                data[size++] = m->data[i][j] + 48;
            } else {
                data[size++] = ',';
                data[size++] = m->data[i][j] + 48;
            }
        }
        data[size++] = ']';
    }

    data[size++] = ']';
    data[size++] = '\0';

    char *ret = calloc(size+1, sizeof(char));
    memcpy(ret, data, size);

    return ret;
}


void
r(const struct matrix *m, int k, const struct matrix *exp)
{

    (void) exp;
    struct matrix ret = *m;
    int t1;
    int *t2 = NULL;
    int sizes[m->first_size];
    for ( unsigned long i = 0; i < m->first_size; ++i ) {
        sizes[i] = m->second_size;
    }
    ret.data = shiftGrid(m->data, m->first_size, sizes, k, &t1, &t2);
    char *m_cstr = matrix_to_cstr(m);
    char *ret_cstr = matrix_to_cstr(&ret);
    char *exp_cstr = matrix_to_cstr(exp);
    printf("shiftGrid(%s, %d) = %s | exp: %s", m_cstr, k, ret_cstr, exp_cstr);

    free(m_cstr);
    free(ret_cstr);
    free(exp_cstr);
    free(t2);
    for ( unsigned long i = 0; i < m->first_size; ++i ) {
        free(ret.data[i]);
    }
    free(ret.data);
}

int
main(void)
{
    int in11[] = {1,2,3};
    int in12[] = {4,5,6};
    int in13[] = {7,8,9};
    int *in1[] = {in11,in12,in13};
    struct matrix min1 = {in1, 3, 3};
    int exp11[] = {9,1,2};
    int exp12[] = {3,4,5};
    int exp13[] = {6,7,8};
    int *exp1[] = {exp11,exp12,exp13};
    struct matrix mexp1 = {exp1, 3, 3};
    r(&min1, 1, &mexp1);

    int in21[] = {1};
    int *in2[] = {in21};
    struct matrix min2 = {in2, 1, 1};
    int exp21[] = {1};
    int *exp2[] = {exp21};
    struct matrix mexp2 = {exp2, 1, 1};
    r(&min2, 100, &mexp2);

    return 0;
}