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

#include "timing.h"


void print_arr( int* arr, int len ) {

    unsigned int i;
    for( i = 0; i < len; ++i )
        printf( "%d  ", arr[i] );
    printf("\n");
}

int is_arr_sorted( int* arr, int len ) {

    int i;
    for( i = 0; i < len - 1; ++i )
        if( arr[i] > arr[i+1] )
            return 0;
    return 1;
}

/**
 * Determine the index of the beginning of each block
 * based on the global splitters
 */
void partition( int* data, int len, int* splitters, int num_sp, int* disp) {
	//we iterate the splitters
	int i;
	int k = 0;
	int split_count= 0;
	//relevant: disp[1] - disp[3]
	for(i = 0; i < len; i++) {
		if(data[0] < splitters[split_count]) {
			split_count++;
			disp[k] = i;
			k++;
		}
		if(data[i] < splitters[split_count]) {
			//nothing to do
		} else if(data[i] >= splitters[split_count]) {
			//save index, inc split_count
			split_count++;
			disp[k] = i;
			k++;
			if(split_count == num_sp ) {
				//done
				break;
			}
		}
	}
}

/**
 * Verify that all data is sorted globally
 */
int verify_results_eff( int* arr, int len, int myrank, int nprocs ) {
	//we consider qsort to work correctly, so the first element in an array ist the smallest, and the last element is the biggest
	//we only check, if the last element of the array in p[i] is smaller than the first element of p[i+1]
	int smallest;
	smallest = arr[0];
	int biggest	= arr[len-1];
	if(myrank == nprocs-1) {
		MPI_Recv(&biggest, 1, MPI_INTEGER, myrank -1, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		if(smallest > biggest) {
			return 0;
		}
	} else {
		MPI_Send(&biggest, 1, MPI_INTEGER, myrank +1, 0, MPI_COMM_WORLD);
		if(myrank != 0) {
			MPI_Recv(&biggest, 1, MPI_INTEGER, myrank -1, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			if(smallest > biggest) {
				return 0;
			}
		}
	}
    return 0;
}
 int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}
/**
 * Do the parallel sorting
 *
 * Note: The length of the local input array may change in this
 *       call
 */
void par_sort( int** orig_arr, int* orig_len, int myrank,
               int nprocs ) {

	int i;
    /* Sort locally */
	qsort(*orig_arr, (size_t) *orig_len, sizeof(int), cmpfunc);
    /* Select local splitters */
	//p-1 elemts per process
	//index = [n(i+1)]/p
	//we have p-1 splitters for each process
	int* splitters = malloc(sizeof(int) * (nprocs-1));
	for(i = 0;i < nprocs-1;i++) {
		 splitters[i] = orig_arr[(*orig_len * (i+1) ) / nprocs];
	}
	//each process stores its splitters in 'splitters' now
    /* Gather all the splitters on the root process */
	int* all_splitters = malloc(sizeof(int) * (nprocs *(nprocs -1)));
	//every process Sends its splitters to the root process
	MPI_Gather(splitters, (nprocs-1), MPI_INT,  all_splitters, (nprocs-1), MPI_INT, 0, MPI_COMM_WORLD );
	//since we need an array of the same length for the global splitters, we dont free it yet
	//sort the Gathered splitters
	if(myrank == 0) {
		qsort(*all_splitters, (size_t) nprocs *(nprocs -1), sizeof(int), cmpfunc);

    /* Select global splitters */
	//index = (p-1) * (i+1)
		for(i = 0; i < nprocs-1; i++) {
			splitters[i] = all_splitters[(nprocs-1) * (i+1)];
		}
	}
	MPI_Bcast(splitters, (nprocs-1), MPI_INT, 0, MPI_COMM_WORLD);
	//now the global splitters are in 'splitters' of every process

    /* Redistribute parts */
	int* disp = malloc(sizeof(int) * nprocs);
	for(i = 0; i < nrpocs; i++) {
		disp[i] = 0;
	}
    // Call partition()
	partition(*orig_arr, *orig_len, *splitters,(nprocs-1), *disp);
    // Tell each process how many elments I Send to it

	int* mess_len = 0;
	int x = 0;
	new_len = *orig_len;
	for(j = 1; j < nprocs; j++) {
		if((j-1)!=myrank) {
			for(i = 0; i < *orig_len; i++) {
				if(disp[j]== 0) {
					*mess_len = *orig_len-disp[j-1];
					//#mess_len elememts need to get Send to p[j-1]
					MPI_Send(*mess_len, 1, MPI_INTEGER, j-1, 0, MPI_COMM_WORLD);
					new_len = new_len - *mess_len;
					//allocate the Sending array
					int* send_arr = malloc(sizeof(int) * *mes_len);
					for(k=disp[j-1]; k < disp[j];k++) {
						send_arr[x] = orig_arr[k];
						x++;
					}
					MPI_Send(*send_arr, *mess_len, MPI_INTEGER, j-1, 1, MPI_COMM_WORLD);
					x = 0;
					break;
				}
				if(i == disp[j]) {
					//process j gets #i elements
					*mess_len = i -disp[j-1];
					//#mess_len elemets need to get Send to p[j-1]
					new_len = new_len - *mess_len;
					MPI_Send(*mess_len, 1, MPI_INTEGER, j-1, 0, MPI_COMM_WORLD);
					int* send_arr = malloc(sizeof(int) * mes_len);
					for(k=disp[j-1]; k < disp[j];k++) {
						send_arr[x] = orig_arr[k];
						x++;
					}
					MPI_Send(*send_arr, *mess_len, MPI_INTEGER, j-1, 1, MPI_COMM_WORLD);
					x = 0;
					if(j==nprocs-1 &&disp[j] != 0) {
						*mess_len = *orig_len-disp[j];
						new_len = new_len - *mess_len;
						//#mess_len elements need to get Send to p[j]
						MPI_Send(*mess_len, 1, MPI_INTEGER, j, 0, MPI_COMM_WORLD);
						int* send_arr = malloc(sizeof(int) * mes_len);
					for(k=disp[j-1]; k < disp[j];k++) {
						send_arr[x] = orig_arr[k];
						x++;
					}
					MPI_Send(*send_arr, *mess_len, MPI_INTEGER, j, 1, MPI_COMM_WORLD);
					x = 0;
					}
					break;

				}
			}
		}
	}
	//receiving of the messages
	for(i = 0; i < nprocs; i++) {
		if(myrank == i) {
			//nothing to do
		} else {
			MPI_Recv(*mess_len, 1, MPI_INTEGER, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			*orig_arr = realloc(*orig_arr, sizeof(int)*(new_len + *mess_len));
			MPI_Recv(*orig_arr, *mess_len, MPI_INTEGER, i, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		}

	}
	qsort(*orig_arr, (size_t) (new_len + *mess_len), sizeof(int), cmpfunc);



    // Allocate array of proper size
    // Send one block to each process (blocks could also be empty)

    /* Sort locally */

}

int main( int argc, char** argv ) {

    int myrank, nprocs;
    MPI_Init( &argc, &argv );
    MPI_Comm_rank( MPI_COMM_WORLD, &myrank );
    MPI_Comm_size( MPI_COMM_WORLD, &nprocs );

    init_clock_time ();

    /* Init the local part of the array */
    if( argc < 2 ) {
        printf( "Usage: %s <local_len>\n", argv[0] );
        exit( 1 );
    }
    int i, local_len = atoi( argv[1] );
    int* local_arr = malloc( local_len * sizeof(int) );

    /* Randomize the input */
    srand( time(NULL) * myrank );
    for( i = 0; i < local_len; ++i )
        local_arr[i] = rand();

    double start = get_clock_time();

    /* Parallel sort */
    par_sort( &local_arr, &local_len, myrank, nprocs );

    double elapsed = get_clock_time() - start;

    /* Verify the results */
    int res = verify_results_eff( local_arr, local_len, myrank, nprocs );
    if( myrank == 0 )
        printf( "Sorted: %d\n", res );

    /* Get timing - max across all ranks */
    double elapsed_global;
    MPI_Reduce( &elapsed, &elapsed_global, 1,
                MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD );
    if( myrank == 0 )
        printf( "Elapsed time (ms): %f\n", elapsed_global );

    free( local_arr );

    MPI_Finalize();

    return 0;
}