Rotate an image (2D array) by 90 degrees recursively with low memory usage

Question

I'm looking for comments on coding style, passing arguments, ...etc.

#include <iostream>

using namespace std;

void printImage(int** img, int N){

    //check if image pointer is NULL
    if(img == NULL){
        return;
    }

    //check if any of the columns of the image are null (since its essentially an array of pointers)
    for(int i=0; i<N ; i++){
        if(img[i] == NULL){
            return;
        }
    }

    for(int i=0; i<N ; i++){
        for(int j=0; j<N ; j++){
            cout<<img[i][j]<<",";
        }
        cout<<endl;
    }
}

// ROTATE IMAGE BY 90 DEGREES RECURSIVELY
void do_rotateImageInplace(int** img, int N, int row, int col){

    //base condition --> return: do this by check if we need to go deeper into the "peels of the onion :)"
    if(row > N-row-1 || col < 0 || N==1)
    {
        return;
    }

    // Tmp usage --> to store row or column being rotated
    int* tmp = new int[N-row];

    //backup row
    for(int i=row; i<N-row ; i++){
        tmp[i]=img[i][col];
    }

    //copy row into col
    for(int i=N-row-1; i>=row ; i--){
        img[i][col] = img[row][i];
    }

    //swap tmp with end row
    for(int i=N-row-1 ; i>=row ; i-- ){
        int tmpVal = img[col][i];
        img[col][i] = tmp[N-i-1];
        tmp[N-i-1] = tmpVal;
    }


    // Swap end row into first col
    for(int i=N-(row)-2 ; i>=row ; i--){
        int tmpVal = img[i][row];
        img[i][row] = tmp[N-i-1];
        tmp[N-i-1]=tmpVal;
    }

    // Swap first column backup into first row
    for(int i=row+1; i<N-(row)-1 ; i++){
        img[row][i] = tmp[i];
    }

    delete[] tmp;

    do_rotateImageInplace(img, N, row+1, col-1);
}

void rotateImageInplace(int** img, int N){

    // Check if image pointer is NULL
    if(img == NULL){
        return;
    }

    // Check if any of the columns of the image are null (since its essentially an array of pointers)
    for(int i=0; i<N ; i++){
        if(img[i] == NULL){
            return;
        }
    }

    // If image is less than 2 in size
    if(N<2){
        return;
    }

    do_rotateImageInplace(img, N, 0, N-1);
}



int main(){

    //TEST CASES:
    int N = 5;
    int** img = new int*[N];
    int val = 0;
    for(int i=0; i<N ; i++){
        img[i] = new int[N] {val++,val++,val++,val++,val++};
    }

    cout<<"******* original image ******"<<endl;
    printImage(img, N);

    rotateImageInplace(img, N);

    cout<<"******* rotated image ******"<<endl;
    printImage(img, N);

    for(int i=0; i<N ; i++){
        delete img[i];
    }
    delete[] img;

}

Answer 1

First of all, I don't see why do_rotateImageInplace shall be recursive. And indeed, it is a tail recursive, and as such is trivially converted into a loop.

Second, the comments are seriously misleading. This is what they say:

//backup row
//copy row into col
    (hmm... now `col` is permanently destroyed)
//swap tmp with end row
    (hmm... the comment above says that tmp istelf is a row. Why would I want to swap rows?)

etc.

The only useful comment is about peeling the onion. And a good comment really wants to be a function name. So

for (int layer = 0; layer < N/2; layer++)
    rotate_layer_inplace(img, N, layer);

seems like what you are trying to do.

Answer 2

As its stands, your code is written in old-style C++. I would like to point you towards some improvements to bring it closer to modern C++.

• You are making excessive use of raw pointers and manual memory allocation/deallocation. You don't have to, and shouldn't do it in C++. The language and libraries provide container classes and smart pointers so that you don't have to waste time writing complex resource handling code and producing fragile/error-prone code. Instead of using:

  int** img = new int*[N];
  

  You should be using a std::vector:

  vector<vector<int>> img(width, vector<int>(height));
  

  Access it the same way, with [][] subscript operators, but get automatic memory management, no chance of memory leaks and debug bounds checking (might need to enable the latter in your compiler). Also no increase in memory usage if you specify the size upfront.

  When using a vector, however, you need to pay attention when passing it as a function parameter. Since the default in C++ is a copy, you will probably want to pass it by reference most of the time.

• You are still using NULL, which is deprecated since C++11 in favor of nullptr.

• Minor issue of using namespace std. This is not a problem inside an implementation file, but never do it in a header file, since it imports all symbols of a namespace. If using namespace appears in a header file, the imported symbols would leak to every other file that #includes the header, increasing chances of name collision. This question on StackOverflow elaborates more on the subject.

• Single letter variables and function parameters are usually a bad choice, with the exception of loop counters and indexes. N is a little too vague for a parameter name. Consider naming it imageSize or width instead.

• Lack of spacing on calls to cout affects readability:

      cout<<img[i][j]<<",";
  

  They would be more pleasant to read with spacing between the << operators and parameters:

  cout << img[i][j] << ",";
  

• Another minor issue, do_rotateImageInplace() is breaking your naming convention. Perhaps rename it to doRotateImageInplace() to ensure uniformity.