Rotate multi-dimension pointer

Question

If I have a multidimension pointer representation of a grid like so

char **p;
int w; // width (i.e. number of columns)
int h; // height (i.e. number of rows)

How do I go about creating a copy that is rotated by 90 degrees clockwise for NxM grid?

I've tried mallocing the height as the new width, and width as new height then transposing the values. Then I was going to finish by reversing the values of the row but I haven't managed to do this.

possible duplicate of [How to rotate a matrix 90 degrees without using any extra space?](http://stackoverflow.com/questions/3488691/how-to-rotate-a-matrix-90-degrees-without-using-any-extra-space) — Vijay, Apr 02 '12 at 08:54

torek · Answer 1 · 2012-04-02T09:27:15.833

Actual transposition is moderately painful: you have to move every element from "where it is now" to "where it should be in the transposition". If you really do have a pointer p pointing to the first of M pointers, and each of those M pointers points to the first of N chars (used as if it's an array of size M of arrays of size N of chars):

       +---+       +---+---+---+---+
p ---> | * | ----> | a | b | c | d |
       +---+       +---+---+---+---+
       | * | --
       +---+   \          +---+---+---+---+
       | * | -----------> | i | j | k | l |
       +---+     \        +---+---+---+---+
                  \
                   \    +---+---+---+---+
                    --> | e | f | g | h |
                        +---+---+---+---+

then you need a new pointer (which I will call q) pointing to the first of N pointers, each of which points to the first of M chars (note: this is a different transposition than you asked for):

       +---+        +---+---+---+
q ---> | * | -----> | a | e | i |
       +---+        +---+---+---+
       | * | --
       +---+   \
       | * |etc \     +---+---+---+
       +---+     ---> | b | f | j |
       | * |etc       +---+---+---+
       +---+

However, if you can live with relatively annoying subscript-writing and any cache miss effects on your runtime, you can simply access p[i][j] as p[j][i] or p[N-1-j][i], etc., to "pretend" that things are transposed. This might be easiest with some macros:

#define ORIENTATION_A(p, M, N, i, j)  ((p)[i][j])
#define ORIENTATION_B(p, M, N, i, j)  ((p)[(N)-1-(j)][i])
/* etc */

(note: none of the above is tested).

hellork · Answer 2 · 2012-04-03T06:03:48.873

When using type char **, since the fixed-size solution is already posted I thought I would chime in with a dynamic, \0 terminated solution that works with various-sized arrays. If it is possible to terminate the arrays h and w can be omitted. This function can figure out the h and w. Of course it may be changed to support h and w, but the powers that be would rather I get back to work funding their empire rather than providing free help.

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
/* rotate_array

    w                h
**p _______      **q ___
   |A B C D|\0 ===> |E A|\0
h  |E F G H|\0 ==>  |F B|\0 w
  NULL-----         |G C|\0
                    |H D|\0
                    NULL-
*/
char **rotate_array(char **p) {
    int w,h,hh;
    char **q;
    for (w=0;p[0][w];w++);
    for (hh=0;p[hh];hh++);
    if (!(q = malloc(w * sizeof q))) {
        perror ("malloc");
        exit (1);
    } fprintf (stderr,"made it\n");
    for (w=0;p[0][w];w++) {
        if (!(q[w] = malloc(hh))) {
            perror ("malloc");
            exit (1);
        } for (h=0;h<hh;h++) {
            q[w][hh-h-1] = p[h][w];
        } q[w][h]='\0';
    } q[w]=NULL;
    return q;
} void free_array(char **p) {
    int h;
    for (h=0;p[h];h++) {
        free (p[h]);
    } free (p);
}
// main
int main (int argc, char **argv) {
    int h;
    char *p[3]={"ABCD","EFGH",NULL};
    char **q;
    for (h=0;p[h];h++) {
        printf ("%s\n",p[h]);
    } printf ("\n");
    q = rotate_array (p);
    for (h=0;q[h];h++) {
        printf ("%s\n",q[h]);
    } free_array (q);
    return 0;
}

We have no indication that `p` is null-terminated, nor that `*p`, etc. point to null-terminated strings. Its entirely possible that `w` and `h` _are_ necessary. — Aaron Dufour, Apr 02 '12 at 15:27
Personal preference and desire to be different since the unterminated solution is already provided by somebody else. Anyways, it's trivial to modify mine to support h and w. Just remove the length checks and NULL terminators. — hellork, Apr 03 '12 at 05:59

Rotate multi-dimension pointer

2 Answers2