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

/* the number of data elements in each process */
#define N 25

/* initialize the data to random values based on rank (so they're different) */
void init(int* data, int rank) {
    int i;
    srand(time(NULL) + rank * 100);
    for (i = 0; i < N; i++) {
        data[i] = rand() % 100;
    }
}

/* print the data to the screen */
void print(int* data, int rank) {
    int i;
    printf("Process %d: ", rank);
    for (i = 0; i < N; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    fflush(stdout);
    sleep(1);
}

/* comparison function for qsort */
int cmp(const void* ap, const void* bp) {
    int a = * ((const int*) ap);
    int b = * ((const int*) bp);
    return a - b;
}


/* do the parallel odd/even sort */
void parallel_sort(int* data, int rank, int size) {
    // for each phase
    for (int phase = 0; phase < size; phase++) {
        // sort our data
        qsort(data, N, sizeof(int), &cmp);

        int partner_rank;
        if (phase % 2 == 0) {
            // even phase
            if (rank % 2 == 0) {
                partner_rank = rank + 1;
            } else {
                partner_rank = rank - 1;
            }
        } else {
            // odd phase
            if (rank % 2 == 0) {
                partner_rank = rank - 1;
            } else {
                partner_rank = rank + 1;
            }
        }

        // if our partner doesn't exist, move on
        if (partner_rank < 0 || partner_rank >= size) {
            continue;
        }

        //printf("In phase %d, process %d works with partner %d\n", phase, rank, partner_rank);

        // begin sending our data to partner
        MPI_Request request;
        MPI_Isend(data, N, MPI_INT, partner_rank, 0, MPI_COMM_WORLD, &request);

        // receive partners data
        int partner_data[N];
        MPI_Recv(partner_data, N, MPI_INT, partner_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

        //printf("Process %d received: ", rank);
        //for (int i = 0; i < N; i++) {
        //printf("%d ", partner_data[i]);
        //}
        //printf("\n");

        // wait for send to finish
        MPI_Wait(&request, MPI_STATUS_IGNORE);

        int temporary[N];

        if (rank < partner_rank) {
            int ours = 0;
            int theirs = 0;
            for (int i = 0; i < N; i++) {
                // take smaller N
                if (data[ours] < partner_data[theirs]) {
                    temporary[i] = data[ours];
                    ours++;
                } else {
                    temporary[i] = partner_data[theirs];
                    theirs++;
                }
            }
        } else {
            int ours = N - 1;
            int theirs = N - 1;
            for (int i = N - 1; i >= 0; i--) {
                // take bigger N
                if (data[ours] > partner_data[theirs]) {
                    temporary[i] = data[ours];
                    ours--;
                } else {
                    temporary[i] = partner_data[theirs];
                    theirs--;
                }
            }
        }

        // copy back onto our array
        //printf("Process %d takes: ", rank);
        for (int i = 0; i < N; i++) {
            data[i] = temporary[i];
            //printf("%d ", data[i]);
        }
        //printf("\n");
    }
}

int main(int argc, char** argv) {
    /* our rank and size */
    int rank, size;

    /* our processes data */
    int data[N];

    /* initialize MPI */
    MPI_Init(&argc, &argv);

    /* get the rank (process id) and size (number of processes) */
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    /* initialize the data */
    init(data, rank);

    /* do the parallel odd/even sort */
    parallel_sort(data, rank, size);

    int ready = 1;
    if (rank != 0) {
        MPI_Recv(&ready, 1, MPI_INT, rank - 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    }
    print(data, rank);
    if (rank != size - 1) {
        MPI_Send(&ready, 1, MPI_INT, rank + 1, 0, MPI_COMM_WORLD);
    }

    /* quit MPI */
    MPI_Finalize();
    return 0;
}