Rotate a 2D array in-place without using a new array - best C++ solution?

Question

Dear Folks, One of my students asked me this kind of homework with C++ arrays. It seemed quite interesting for me, so, though I have solved this problem, I wanted to share my solution with you and know another variants and opinions. The problem is following:

Problem It is given a 2D dynamic quadratic matrix (array) A(nxn). It is required to rotate the array by 90 degree anticlockwise, that is to say, after rotation A[1,1] field should contain the value of A[1,n] and A[1,n] field should contain the value of A[n,n]. And also it is required that while solving this problem you should not use any other array.

My solution I have told to the student to do the following (will represent steps schematically):
I have suggested to define a class which, as its member, will have the 2D array. And to define a operation which will return reference on A[j,n+1-i] element when the user will request A[i,j] one. In two words I have suggested to create a wrapper for the array, and manipulate by array through the wrapper.

Please share with me your solution. Thanks in advance.

Answer 1

See http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array

Answer 2

Wikipedia has an article on in-place matrix transposition.

Consider:

a b c
e f g
x y z

transpose:
a e x
b f y
c g z

rotated 90 deg CCW:
c g z
b f y
a e x

So after you have the transpose, reverse the rows, which you can do in-place easily.

Answer 3

You can use a "four-way-swap" and a nested loop with some rotation magic (worked out on paper):

template <typename T>
void swap(T& a, T& b, T& c, T& d)
{
    T x(a);
    a = b;
    b = c;
    c = d;
    d = x;
}

template <typename T, size_t dim>
void rotate(T (&matrix)[dim][dim])
{
    const size_t d = dim-1;
    for (size_t y = 0; y < dim/2; ++y)
    {
        for (size_t x = y; x < d-y; ++x)
        {
            swap(matrix[y  ][x  ],
                 matrix[x  ][d-y],
                 matrix[d-y][d-x],
                 matrix[d-x][y  ]);
        }
    }
}

Test program:

template <typename T, size_t dim>
void print(T (&matrix)[dim][dim])
{
    for (size_t y = 0; y < dim; ++y)
    {
        for (size_t x = 0; x < dim; ++x)
        {
            std::cout << matrix[y][x] << ' ';
        }
        std::cout << '\n';
    }
}

int main()
{
    int matrix[4][4] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    rotate(matrix);
    print(matrix);
}

Output:

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

Now you just have to convert that from template-form to dynamic-form ;)