// Compiled with: g++ -Wall -std=c++14 -pthread

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//This is NOT an in-place algorithm
//x' = x*cos(a) - y*sin(b)
//y' = x*sin(a) + y*cos(b)
//With this we rotate around the center of the matrix
//If matrix is n x n. Memory Complexity O(n^2)
//Runtime Complexity O(n^2)
void rotate(vector<vector<int>>& matrix) {
    // Copia
    vector<vector<int>> _matrix = matrix;
    for (int i = 0; i < matrix.size(); ++i){
        for (int j = 0; j < matrix.size(); ++j){
            matrix[i][j] = _matrix[matrix.size() - 1 - j][i];
        }
    }
}


//This is an in-place algorithm
//If matrix is n x n. Memory Complexity O(1)
//Runtime Complexity O(n^2)
//This is faster because the second for loop iterates as maximum n/2.
void rotate_2(vector<vector<int>>& matrix) {

    // swap -> 1 variable extra y 2 assignments
    // 3 swaps -> 6 cambios (9)
    // ---------> 4 + 1 temp (5)
    //
    int n = matrix.size();
    for (int i = 0; i < n; ++i){
        for (int j = i + 1; j < n - i; ++j){
            // aqui ya se donde tiene que ir cada uno de estos 4 numeros
            // (i,j), (j, n-1-i), (n-1-i, n-1-j), (n-1-j, i)
            // 3 swaps
            // int temp = matrix[i][j];
            // matrix[i][j] = matrix[n - 1 - j][i];
            // matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
            // matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
            // matrix[j][n - 1 - i] = temp;
            swap(matrix[i][j], matrix[j][n - 1 - i]);
            swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
            swap(matrix[i][j], matrix[n - 1 - j][i]);
        }
    }
}


//This is an in-place algorithm
//If matrix is n x n. Memory Complexity O(1)
//Runtime Complexity O(n^2)
void rotate_flipao(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; ++i){
        for (int j = i + 1; j < n; ++j){
            swap(matrix[i][j], matrix[j][i]);
        }
    }

    for (int i = 0; i < n; ++i){
        reverse(matrix[i].begin(), matrix[i].end()); //O(n)
    }
}

void print_matrix(const vector<vector<int>>& matrix) {
    for (auto& row : matrix) { // const, auto, & || const-> no se pueda modificar | auto = vector<int> | & = ref
        for (auto i : row) {
            cout << i << " ";
        }
        cout << endl;
    }
}

int main(){

    vector<vector<int>> matrix_1 =
    {{1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
    {13, 14, 15, 16}};

    vector<vector<int>> matrix_2 =
    {{1, 2, 3, 4, 101},
    {5, 6, 7, 8, 102},
    {9, 10, 11, 12, 103},
    {13, 14, 15, 16, 104},
    {17, 18, 19, 20, 105}};

    cout<<"---Test 1 ----"<<endl;
    cout<<"Original matrix:"<<endl;
    print_matrix(matrix_1);
    cout<<"Rotated matrix:"<<endl;
    rotate_2(matrix_1);
    print_matrix(matrix_1);

    cout<<endl<<"---Test 2 ----"<<endl;
    cout<<"Original matrix:"<<endl;
    print_matrix(matrix_2);
    cout<<"Rotated matrix:"<<endl;
    rotate_2(matrix_2);
    print_matrix(matrix_2);

    return 0;
}