Rotate a matrix of any size

[lovecreatesbeauty]

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?

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

/*Rotate a 4*4 matrix of integers by 90 degrees clockwise.*/

void rotate(void *matrix, const int width){
int (*array)[4] = matrix;
int (*tmp)[4];
int i, j;
size_t n = width * width * sizeof **array;

if(tmp = malloc(n)){
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(tmp + i) + j) = *(*(array + i) + j);

for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(array + j) + (width - 1 - i)) = *(*(tmp + i) + j);

free(tmp);
}
}

/*test*/
#include <stdio.h>

/*print the content of a matrix*/
void printa(void *matrix, const int width){
int (*array)[4] = matrix;
int i, j;
for (i = 0; i < width; ++i){
for (j = 0; j < width; ++j)
printf("%2d ", *(*(array + i) + j));
printf("\n");
}
}

#define WTH 4
int main(void){
int a[][WTH] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};

printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

rotate(a, WTH);
printa(a, WTH);
printf("\n");

return 0;
}

$ cc -ansi -pedantic -Wall -W rotate.c
rotate.c: In function `rotate':
rotate.c:13: warning: suggest parentheses around assignment used as
truth value
$ ./a.out
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

$

[Tom St Denis]

lovecreatesbeauty wrote:

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

It's OT but ...

"rotate by 90 degrees" is called a transposition. You don't need a
temp, hint: the new location for a value at x,y is the new destination
for a value at y,x.

Tom

[Peter Nilsson]

Tom St Denis wrote:

lovecreatesbeauty wrote:

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

It's OT but ...

"rotate by 90 degrees" is called a transposition. ...

You mean Outright Tripe? They're not even in the same equivalence
class. ;-)

--
Peter

[Peter Nilsson]

lovecreatesbeauty wrote:

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency?

Can the copy be saved?

Not sure what that means.

Comments on it are welcome.

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?

Yes.

#include <stddef.h>

You don't need this as size_t is supplied by both of the following
headers.

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

/*Rotate a 4*4 matrix of integers by 90 degrees clockwise.*/

void rotate(void *matrix, const int width){
int (*array)[4] = matrix;
int (*tmp)[4];
int i, j;
size_t n = width * width * sizeof **array;

size_t n = width * sizeof *array;

if(tmp = malloc(n)){

Given that the matrix is relatively small, just create a temp locally.

for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(tmp + i) + j) = *(*(array + i) + j);

Much clearer is...

tmp[i][j] = array[i][j];

But you can replace that whole thing with...

memcpy(tmp, array, n);

>
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(array + j) + (width - 1 - i)) = *(*(tmp + i) + j);

array[j][width - 1 -i] = tmp[i][j];

free(tmp);
}
}

Just an alternative...

#include <stddef.h>

#define countof(x) ((size_t) (sizeof (x) / sizeof *(x)))

void rotate(int array[][4])
{
size_t i, mi;
size_t j, mj;
size_t width = countof(array[0]);

for (i = 0, mi = width; i < mi--; i++)
for (j = 0, mj = width; j < mj--; j++)
{
int tmp = array[ i][ j];
array[ i][ j] = array[mj][ i];
array[mj][ i] = array[mi][mj];
array[mi][mj] = array[ j][mi];
array[ j][mi] = tmp;
}
}

--
Peter

[Eric Sosman]

Tom St Denis wrote:

lovecreatesbeauty wrote:

>>I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

It's OT but ...

"rotate by 90 degrees" is called a transposition. [...]

Well, I can't say "No, it's not" because the very fact
that you describe the maneuver as a transposition demonstrates
that the maneuver "is called" a transposition by at least one
person, to wit, you.

"Is *correctly* called" would be a different matter.

Myself, I call it "Haddocks' Eyes."

--
Eric Sosman
es*****@acm-dot-org.invalid

[lovecreatesbeauty]

Peter Nilsson wrote:

Just an alternative...

#include <stddef.h>

#define countof(x) ((size_t) (sizeof (x) / sizeof *(x)))

void rotate(int array[][4])
{
size_t i, mi;
size_t j, mj;
size_t width = countof(array[0]);

for (i = 0, mi = width; i < mi--; i++)
for (j = 0, mj = width; j < mj--; j++)
{
int tmp = array[ i][ j];
array[ i][ j] = array[mj][ i];
array[mj][ i] = array[mi][mj];
array[mi][mj] = array[ j][mi];
array[ j][mi] = tmp;
}
}

Yes, it's better.

[lovecreatesbeauty]

Peter Nilsson wrote:

lovecreatesbeauty wrote:

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?

Yes.

How can you do this? In your later example, the size info is tied to
the type declaration of the parameter of the function, though that size
of the array is not seen inside the function.

void rotate(int array[][4])

This function accepts a 4*4 array of integers. Can it accept a 3*3
array or a 40*40 array? Can it be changed to accept an array of any
size.

[Jakob Creutzig]

"Tom St Denis" <to********@gmail.comwrites:

lovecreatesbeauty wrote:

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

It's OT but ...

"rotate by 90 degrees" is called a transposition. You don't need a
temp, hint: the new location for a value at x,y is the new destination
for a value at y,x.

[Still more OT, but]

Err.. no. Consider

1 2 3 4

0 1 2 3

0 0 1 2

0 0 0 1

Rotating by 90 degrees clockwise:

0 0 0 1

0 0 1 2

0 1 2 3

1 2 3 4

Transposition (a_{x,y} <- a_{y,x}):

1 0 0 0

2 1 0 0

3 2 1 0

4 3 2 1

Rotating by 90 degrees clockwise is the same as
transposition plus inversion of row numbering, i.e.,

a_{x,y} <- a_{n-y, x},

where n is the size of the matrix.

The cost is ~n^2, same as writing the matrix in the first
place. Hence, unless your matrices are really large,
I won't bother much about optimising. If you have large
matrices and fewer than ~n^2 calls for matrix elements, you
might be better off without performing the rotation at all,
but instead using a trivial function get_rotated(a, x, y),
returning a_{n-y,x}.

Best,
Jakob

[milhous.30]

lovecreatesbeauty wrote:

I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.

Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?

you can do this with only one temp variable...dividing the array into a
set of 4 quadrents.
to rotate some x,y...y,-x...-x,-y...-y,x you would just use 3 swaps

//three constant time operations
swap(x,y,y,-x)
swap(-x,-y,x,y)
swap(-y,x,x,y)

Repeat this process for each element in one quadrent (loop n/4 times)

thus this operates in linear time and linear space:-)