#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

 

 

int row = 40000 , col = 40000;
static int A[40000][40000];
static int N[100] = {0};
void SmartTranspose(int A[row][col]);
void Transpose(int A[row][col], int x, int y, int w, int h);
void InitializeMatrix(int X[row][col]);
void PrintMatrix(int X[row][col]);
void CheckTranspose(int X[row][col], int Y[row][col]);
double pow(double x, double y);
int matrix = 0;
void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1);

int main(){

srand(time(NULL));

double sizes = 0;
int count = 0;


for(sizes = 20; sizes < 30; sizes++)
{
N[count] = floor(pow(2, (sizes/9)));
printf("N %d\n", N[count]);
count++; }

for (matrix = 0; matrix <= count -1 ; matrix++){

InitializeMatrix(A);
printf("N %d\n",N[matrix]);
printf("\nOriginal matrix: \n");
PrintMatrix(A);

//printf("begin\n");
fflush(stdout);

SmartTranspose(A);
//printf("Time Taken to transpose: %f\n",(double)(time(NULL) - start));

printf("E\n");

printf("\nTransposed matrix: \n");
PrintMatrix(A);
//CheckTranspose(A, B);

}
return 0;
}

 

void InitializeMatrix(int A[row][col]){
for(int row2=0; row2<N[matrix]; row2++)
{
for( int col2=0; col2<N[matrix]; col2++)
{
A[row2][col2] = rand() ;
}
}
}

void PrintMatrix(int X[row][col]){
for(row=0; row<N[matrix]; row++)
{
for(col=0; col<N[matrix]; col++)
{
printf("%d ", X[row][col]);
}

printf("\n");
}
}

void CheckTranspose(int X[row][col], int Y[row][col]){
for(row=0; row<N[matrix]; row++)
{
for(col=0; col<N[matrix]; col++)
{
if (X[row][col] != Y[col][row])
printf("error as: %d\n", X[row][col]);
}

}
printf("Transpose has passed inspection\n");
}

void SmartTranspose(int A[row][col]){

Transpose(A, 0, 0, N[matrix], N[matrix]);

}

void Transpose(int A[row][col], int x, int y, int w, int h){
int Temp;
if ((w - x) * (h - y ) <= 4 ){
for (int row1 = x + 1 ; row1 < w ; row1++)
for (int col1 = y ; col1 < row1 ; col1++){
Temp = A[row1][col1];
printf("transp: %d %d\n", A[row1][col1], A[col1][row1]);
A[row1][col1] = A[col1][row1];
A[col1][row1] = Temp;

}

}
else
{
int halfh = h / 2;
int halfw = w / 2;
Transpose(A, x, y, halfw , halfh);
Transpose(A, x + halfw, y + halfh, w , h);
TransposeSwap(A, x + halfw, y, w, halfh, x, y + halfh, halfw , h);
}

}

 

 

void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1){
int Temp; int row2 = x1; int col2 = y1;
if ((w - x ) * (h - y) <= 4 && (w1 - x1 ) * (h1 - y1) <= 4){

for(int row1=x; row1< w ; row1++)
{
for(int col1=y ; col1<h; col1++)
{
Temp = A[row1][col1] ;
printf("swapping: %d %d\n", A[row1][col1], A[col1][row1]);
A[row1][col1] = A[col1][row1];
A[col1][row1] = Temp;
}
}
}

else
{ printf("RECURSE");
int halfh = h / 2;
int halfw = w / 2;
int halfh1 = h1 / 2;
int halfw1 = w1 / 2;
TransposeSwap(A, x, y, halfw , halfh, x1, y1, halfw1, halfh1);
TransposeSwap(A, x + halfw, y , w, h - halfh, x1, y1 + halfh1, halfw1, h1 );
TransposeSwap(A, x , y + halfh , halfw, h, x1 + halfw1, y1, w1, halfh1 );
TransposeSwap(A, x + halfw , y + halfh , w, h, x1 + halfw1, y1 + halfh1, w1, h1 );
}

}