#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdint.h>
#include "structs.h"
#include "commonFunctions.h"
#include "quicksort.h"

#define BUF_SIZE 1024
#define SWAP(a,b,t) t=a; a=b; b=t;
#define STRING_SIZE 1024

typedef struct {
	BaseType* a;
	int l;
	int r;
	int nth;
} PQSortArgs;

typedef struct {
	char fin1[STRING_SIZE];
	char fin2[STRING_SIZE];
	char fout[STRING_SIZE];
} PMergeArgs;

void assertNotNull(void* p, char* msg){
	if(p==NULL){
		terror(msg);
	}
}

void assertIntEQ(int a, int b, char* msg){
	if(a!=b){
		terror(msg);
	}
}

void assertIntGE(int a, int b, char* msg){
	if(a<b){
		terror(msg);
	}
}

int bufMerge(BaseType* a1, int n1, BaseType* a2, int n2, BaseType* m){
	int i1=0,i2=0;
	int j=0;

	while(i1<n1 && i2<n2){
		if(GT(a1[i1],a2[i2])){
			m[j]=a2[i2];
			i2++;
			j++;
		}else{
			m[j]=a1[i1];
			i1++;
			j++;
		}
	}

	while(i1<n1){
		m[j]=a1[i1];
		i1++;
		j++;
	}

	while(i2<n2){
		m[j]=a2[i2];
		i2++;
		j++;
	}

	return j;
}

void *PMerge(void* a){
	PMergeArgs* args = (PMergeArgs*)a;

	FILE* fin1 = fopen(args->fin1,"rb");
	assertNotNull(fin1,args->fin1);

	FILE* fin2 = fopen(args->fin2,"rb");
	assertNotNull(fin2,args->fin2);

	FILE* fout = fopen(args->fout,"wb");
	assertNotNull(fout,args->fout);

	BaseType *a1 = (BaseType*)calloc(BUF_SIZE,sizeof(BaseType));
	assertNotNull(a1,"calloc");

	BaseType *a2 = (BaseType*)calloc(BUF_SIZE,sizeof(BaseType));
	assertNotNull(a2,"calloc");

	BaseType *m = (BaseType*)calloc(2*BUF_SIZE,sizeof(BaseType));
	assertNotNull(m,"calloc");

	int i,j,k;
	int r1,r2,tmp;

	r1=fread(a1,sizeof(BaseType),BUF_SIZE,fin1);
	r2=fread(a2,sizeof(BaseType),BUF_SIZE,fin2);

	i=j=k=0;
	while(r1>0 && r2>0){
		while(i<r1 && j<r2){
			if(GT(a1[i],a2[j])){
				m[k]=a2[j];
				j++;
			}else{
				m[k]=a1[i];
				i++;
			}
			k++;
			if(k>=2*BUF_SIZE){
				tmp=fwrite(m,sizeof(BaseType),k,fout);
		    assertIntEQ(tmp,k,"fwrite");
				k=0;
			}
		}

		if(i>=r1){
			r1=fread(a1,sizeof(BaseType),BUF_SIZE,fin1);
			i=0;
		}

		if(j>=r2){
			r2=fread(a2,sizeof(BaseType),BUF_SIZE,fin2);
			j=0;
		}
	}

	if(k>0){
		tmp=fwrite(m,sizeof(BaseType),k,fout);
		assertIntEQ(tmp,k,"fwrite");
	}

	if(i<r1){
		tmp=fwrite(a1+i,sizeof(BaseType),r1-i,fout);
		assertIntEQ(tmp,r1-i,"fwrite");
	}

	if(j<r2){
		tmp=fwrite(a2+j,sizeof(BaseType),r2-j,fout);
		assertIntEQ(tmp,r2-j,"fwrite");
	}

	assertIntEQ(fclose(fin1),0,"fclose");
	assertIntEQ(fclose(fin2),0,"fclose");
	assertIntEQ(fclose(fout),0,"fclose");

	assertIntEQ(unlink(args->fin1),0,args->fin1);
	assertIntEQ(unlink(args->fin2),0,args->fin2);

	pthread_exit(NULL);
}

int partition(BaseType* a, int l, int r) {
   int i=l;
   int j=r+1;
   BaseType t;

   // l sera el pivote
   // y contendra la mediana de l, r y (l+r)/2
   int mid = (l+r)/2;

   if(GT(a[mid],a[r])) {
		 SWAP(a[mid],a[r],t);
   }

   if(GT(a[mid],a[l])) {
		 SWAP(a[mid],a[l],t);
   }

   if(GT(a[l],a[r])) {
		 SWAP(a[l],a[r],t);
	 }

	while (1) {
		do{
			++i;
		}while( !GT(a[i],a[l]) && i <= r );

		do{
			--j;
		}while( GT(a[j],a[l]) && j >= l);

		if( i >= j ) break;

		SWAP(a[i],a[j],t)
	}

	SWAP(a[l],a[j],t)

	return j;
}

int QsortC(BaseType* a, int l,int r) {
   int j;

	if( l < r ) {
 	// divide and conquer
       j = partition( a, l, r);
       //  j=(l+r)/2;
       QsortC( a, l, j-1);
       QsortC( a, j+1, r);
   }
   return 0;
}

void *PQSort(void* a){
	PQSortArgs *args=(PQSortArgs*)a;
	if(args->nth>1){
		int tmp;
		int j = partition(args->a,args->l,args->r);
		int np=1;
		if(args->r - args->l > 0)
			np = (args->nth*(j-args->l))/(args->r-args->l);
		if(np<1) np=1;
		if(np>=args->nth) np=args->nth-1;
		//printf("%d\t%d (%d)\t%d (%d)\n",args->r-args->l,j-args->l,np,args->r-j,args->nth-np);

		pthread_t* th = (pthread_t*)calloc(2,sizeof(pthread_t));
		assertNotNull(th,"calloc");

		PQSortArgs* nargs = (PQSortArgs*)calloc(2,sizeof(PQSortArgs));
		assertNotNull(args,"calloc");

		nargs[0].a=args->a;
		nargs[0].l=args->l;
		nargs[0].r=j-1;
		nargs[0].nth=np;
		tmp=pthread_create(th,NULL,PQSort,(void*)(nargs));
		assertIntEQ(tmp,0,"pthread_create");

		nargs[1].a=args->a;
		nargs[1].l=j+1;
		nargs[1].r=args->r;
		nargs[1].nth=args->nth-np;
		tmp=pthread_create(th+1,NULL,PQSort,(void*)(nargs+1));
		assertIntEQ(tmp,0,"pthread_create");

		tmp=pthread_join(th[0],NULL);
		assertIntEQ(tmp,0,"pthread_join");
		tmp=pthread_join(th[1],NULL);
		assertIntEQ(tmp,0,"pthread_join");

		free(th);
		free(nargs);
	}else{
		QsortC(args->a,args->l,args->r);
	}
	pthread_exit(NULL);
}

unsigned long timestart(){
	struct timeval tv;

	gettimeofday(&tv,NULL);

	return (tv.tv_usec/1000) + (tv.tv_sec*1000);
}

unsigned long timestop(unsigned long start){
	struct timeval tv;

	gettimeofday(&tv,NULL);

	return (tv.tv_usec/1000) + (tv.tv_sec*1000) - start;
}

int psort(int maxsize, int nproc, char* ifile, char* ofile){
	int tmp;
	int max=maxsize;
	int np=nproc;
	if(np<1) np=1;

	printf("Allocating %lu bytes.\n",max*sizeof(BaseType));
	BaseType* a = (BaseType*)calloc(max,sizeof(BaseType));
	assertNotNull(a,"calloc");

	FILE* fin=fopen(ifile,"rt");
	assertNotNull(fin,ifile);

	printf("Stage1: Quicksorts\n");
	unsigned long t = timestart();
	//Read + Quicksort + Write:
	char fname[strlen(ofile)+10];
	int nfile=0;

	do {
		//Read:
		// printf("Reading...\n");
		int n=fread(a,sizeof(BaseType),max,fin);
		if(n==0) break;

		//Quicksort:
		// printf("Quicksort %d\n",n);
		pthread_t th;
		PQSortArgs args;

		args.a=a;
		args.l=0;
		args.r=n-1;
		args.nth=np;
		tmp=pthread_create(&th,NULL,PQSort,(void*)(&args));
		assertIntEQ(tmp,0,"pthread_create");

		//Wait:
		tmp=pthread_join(th,NULL);
		assertIntEQ(tmp,0,"pthread_join");

		//Write:
		// printf("Writing...\n");
		sprintf(fname,"%s.%06d",ofile,nfile);
		FILE* fout=fopen(fname,"wb");
		assertNotNull(fout,"fname");

		tmp=fwrite(a,sizeof(BaseType),n,fout);
		assertIntEQ(tmp,n,"fwrite");

		tmp=fclose(fout);
		assertIntEQ(tmp,0,"fclose");

		nfile++;
	}while(!feof(fin));

	tmp=fclose(fin);
	assertIntEQ(tmp,0,"fclose");

	free(a);

	tmp=unlink(ifile);
	assertIntEQ(tmp,0,"unlink");

	printf("Stage1: %lu\n\n",timestop(t));

	//Merge:
	printf("Stage2: Merge\n");
	t = timestart();

	int curf=0;
	int i=0;
	int j=0;
	pthread_t th[np];
	PMergeArgs args[np];

	curf=0;
	while(nfile-curf>1){
		j=0;
		while(curf<nfile-1 && j<np){
			sprintf(args[j].fin1,"%s.%06d",ofile,curf);
			sprintf(args[j].fin2,"%s.%06d",ofile,curf+1);
			sprintf(args[j].fout,"%s.%06d",ofile,nfile+j);

			// printf("Merge(%d, %d) -> %d\n",curf,curf+1,nfile+j);
			tmp=pthread_create(th+j,NULL,PMerge,(void*)(args+j));
			assertIntEQ(tmp,0,"pthread_create");
			curf+=2;
			j++;
		}

		for(i=0;i<j;i++){
			tmp=pthread_join(th[i],NULL);
			assertIntEQ(tmp,0,"pthread_join");
		}

		nfile+=j;
	}

	printf("Stage2: %lu\n\n",timestop(t));

	//Bin2Text:
	printf("Stage3: Write output file\n");
	t = timestart();

	sprintf(fname,"%s.%06d",ofile,curf);
	if(nfile>0){
		tmp=rename(fname,ofile);
		assertIntEQ(tmp,0,"rename");
	} else {
		FILE *fout=fopen(ofile, "wb");
		assertNotNull(fout,"fopen");
		fclose(fout);
	}

	printf("Stage3: %lu\n",timestop(t));

	return 0;

}