#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
#include <string.h>
#include <sys/time.h>

/*
    This program aims to test the effect of using POSIX threads by using 4 pthreads to sort a given array using the merge sort algorithm.
    Made by: Marwan Mokhles Abdallah ID  #4926
 */

#define LINE_MAX 1024 // CONSTANT DEFINES HOW MANY CHARACTERS ALLOWED IN THE INPUT LINE
#define MAX_THREADS 4 // MAX NUMBER OF THREADS TO BE USED IN THIS PROGRAM
#define MAX_LENGTH 100 // MAX LENGTH OF THE ARRAY

int inputArray[MAX_LENGTH]; // THE ARRAY ON WHICH MERGE SORT IS TO BE APPLIED
int input_count;    // STORING COUNT OF ELEMENTS INPUT INTO THE ARRAY

void parse2intarr(char* line, int elements[]);  // FUNCTION THAT SPLITS A LINE STRING AND PARSES THE OUTPUT TO AN INTEGER ARRAY
void parallel_msort();                          // INTERMEDIATE FUNCTION THAT CALLS THE MERGE SORT - IRRELEVANT FUNCTIONS
void *threaded_merge_sort(void* arg);           // FUNCTION THAT DIVIDES THE WORK AND ASSIGNS EACH PART TO A THREAD
void copyInput(int arr[]);                      // FUNCTION THAT COPIES THE ELEMENTS ARRAY TO THE INPUTARRAY
char* getCurrentTime();                         // FUNCTION THAT RETURNS THE CURRNT TIME IN A STRING FORMAT
void merge(int low, int mid, int high);         // FUNCTION THAT APPLIES A MERGE ON THE SPLIT ARRAYS DURING MERGE SORT
void msort(int low, int high);                  // FUNCTION THAT IS CALLED RECURSIVELY TO APPLY MERGE SORT
void merge_resultant();                         // FUNCTION THAT MERGES THE RESULTANT SUBARRAYS
void sortTest();                                // FUNCTION THAT TESTS FOR THE ASCENDING ORDER OF THE ARRAY

int main()
{
    clock_t tstart, tend;       // VARIABLES USED TO CALCULATE TIME TAKEN
    FILE *f;
    int i=0;
    char line[LINE_MAX];        // STRING TO STORE THE INPUT LINE OF INTEGERS
    f=fopen("input.txt", "r");
    if (f != NULL)
    {
        while (fscanf(f,"%d\n",&input_count)!=-1)       //  READING THE INPUT.TXT FILE
        {
            fgets(line, LINE_MAX,f);
        }
        fclose(f);
        printf("\n%s\n",getCurrentTime());              // PRINTS TO VALIDATE INPUT AND STARTING TIME
        printf("\nElements Count: %d",input_count);
        printf("\nElements: %s\n\n",line);
        int elements[input_count];                      //  A TEMPORARY INTEGER ARRAY USED TO STORE THE VALUES RETURNED FROM PARSE2INTARRAY
        parse2intarr(line,elements);                    //  FUNCTION CALL TO POPULATE ELEMENTS ARRAY
        copyInput(elements);                            //  FUNCTION CALL TO POPULATE INPUTARRAY ARRAY
        tstart = clock();                               //  START CALCULATING TIME
        parallel_msort();                               //  START THE MERGE SORT
        tend = clock();                                 //  END TIME CALCULATION
        printf("\nArray in order: ");
        for(i=0;i<input_count;i++)                      //  PRINT THE SORTED ARRAY
        {
            printf("%d ", inputArray[i]);
        }
        sortTest();
        printf("\nTime Taken: %f\n\n",(tend - tstart) /(double)CLOCKS_PER_SEC);     // PRINT TIME TAKEN
    }else{
        printf("ERROR: Opening file failed!\n");                    // IN CASE OF NOT BEING ABLE TO OPEN THE FILE
        exit(-1);
    }
    return 0;
}

// FUNCTION THAT COPIES THE ELEMENTS ARRAY TO THE INPUTARRAY
void copyInput(int arr[])
{
    int i, count = input_count;
    for(i = 0; i < count; i++)
    {
        inputArray[i] = arr[i];
    }
}

// FUNCTION THAT RETURNS THE CURRNT TIME IN A STRING FORMAT
char* getCurrentTime()
{
    time_t rawtime;
    struct tm * timeinfo;
    time ( &rawtime );
    timeinfo = localtime (&rawtime);
    return asctime (timeinfo);
}

void sortTest() {
    for (int i = 1; i < input_count; i ++) {
        if (inputArray[i] < inputArray[i - 1]) {
            printf("\nERROR: Element %d is not in the correct spot\n", inputArray[i]);
            return;
        }
    }
    printf("\n\nSORTING TEST RESULT: SUCCESSFUL! ARRAY IS SORTED ASCENDINGLY! \n");
}

// FUNCTION THAT SPLITS A LINE STRING AND PARSES THE OUTPUT TO AN INTEGER ARRAY
void parse2intarr(char* line, int elements[])
{
    int i=0;
    char *token= strtok(line, " \t");           //  LINE TOKENIZED TO TOKEN
    while (token) {
        elements[i]=atoi(token);
        token = strtok(NULL, " \t");            //  TOKEN TOKENIZED TO GET THE NEXT INTEGER
        i++;
     }
}

// FUNCTION THAT MERGES ALL PARTS SORTED BY THREADS
void merge_resultant()
{
    int low = 0;
    int mid = (input_count / 2) - 1;
    int high = input_count - 1;
    merge(low, mid / 2, mid - 1);           // MERGING THE FINAL ARRAY PARTS
    merge(mid, mid + (high-mid)/2, high);
    merge(low, mid, high);
}

// INTERMEDIATE FUNCTION THAT CALLS THE MERGE SORT - IRRELEVANT FUNCTIONS
void parallel_msort(){
    int thread_count, i, count = input_count;
    if(count < MAX_THREADS)                                     // IN CASE THE ARRAY LENGTH IS LESS THAN THE MAX NUMBER OF THREADS
        thread_count = count;                                   // THE NUMBER OF ELEMENTS IS EQUAL TO NUMBER OF THREADS
    else
        thread_count = MAX_THREADS;                             // ELSE MAX NUMBER OF THREADS IS USED
    pthread_t threads[thread_count];
    for(i = 0; i < thread_count ; i++)
    {
        if(pthread_create(&threads[i], NULL,threaded_merge_sort,(void *)i))         // CREATING THREADS
        {
            printf("ERROR: failed to create thread %d.", i);
            exit(-1);
        }
        else{
            merge_resultant();
        }
    }
    for(i = 0; i < thread_count; i++) {                                 // JOINING THREADS
        pthread_join(threads[i], NULL);
    }

}

// FUNCTION THAT IS CALLED RECURSIVELY TO APPLY MERGE SORT
void merge(int low, int mid, int high)
{
    int i = 0, j = 0, k = 0;
    int right = high - mid;
    int left = mid - low + 1;
    int leftArr[left], rightArr[right];


    for (int i = 0; i < left; i ++) {               // POPULATING THE LEFT ARRAY
        leftArr[i] = inputArray[low + i];
    }

    for (int j = 0; j < right; j ++) {              //  POPULATING THE RIGHT ARRAY
        rightArr[j] = inputArray[mid + 1 + j];
    }
    i = 0;
    j = 0;
    while(i < left && j < right) {                  //  MERGING AND PLACING RESULTS IN THE INPUTARRAY
        if (leftArr[i] <= rightArr[j]) {
            inputArray[low + k] = leftArr[i];
            i ++;
        } else {
            inputArray[low + k] = rightArr[j];
            j ++;
        }
        k ++;
    }
    while (i < left) {                              //  MERGING THE REMAINING ARRAY PARTS
        inputArray[low + k] = leftArr[i];
        k ++;
        i ++;
    }
    while (j < right) {
        inputArray[low + k] = rightArr[j];
        k ++;
        j ++;
    }
    }


// FUNCTION THAT APPLIES A MERGE ON THE SPLIT ARRAYS DURING MERGE SORT
void msort(int low, int high)
{
    int mid = low + (high - low) / 2; // COMPUTING MID POINT OF THE ARRAY
    if (low < high) {
        msort(low, mid);         // RECURSIVELY SORTING THE  LEFT ARRAY
        msort(mid + 1, high);    // RECURSIVELY SORTING THE RIGHT ARRAY
        merge(low, mid, high);        // MERGING BOTH ARRAYS
    }
}

// FUNCTION THAT DIVIDES THE WORK AND ASSIGNS EACH PART TO A THREAD
void *threaded_merge_sort(void* arg)
{
    int high, low, mid;
    int thread_id = (int)arg;     // INITIALISING THREAD ID FROM THE COUNTER PARALLELM_SORT
    printf("\nthread_id = %d",thread_id);
    if(input_count < MAX_THREADS)           // IN CASE INPUT COUNT IS LESS THAN MAX_THREADS, LET 1 THREAD HANDLE THE INPUT
    {
        high = input_count-1;
        low = 0;
        mid = low + (high - low) / 2;
        msort(low, mid);
        msort(mid + 1, high);
        merge(low, mid, high);
    }
    else                                // IN CASE INPUT COUNT IS EQUAL TO OR GREATER THAN MAX_THREADS, LET MAX_THREADS THREADS HANDLE THE INPUT
    {
        high = (thread_id + 1) * (input_count / MAX_THREADS) - 1;
        low = thread_id * (input_count / MAX_THREADS);                // ARRAY IS SPLIT INTO PARTS DEPENDING ON MAX_THREADS SO THAT EACH THREAD GETS TO HAVE (1/MAX_THREADS) THE WORK
        mid = low + (high - low) / 2;
        if (low < high) {                                   // APPLYING MERGE SORT TO THE ASSIGNED PARTS OF THE ARRAY
            msort(low, mid);
            msort(mid + 1, high);
            merge(low, mid, high);
        }
    }
    return NULL;
}