#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>


/*
 *  Funzione "merge" che ha in ingresso gli indici di un array con le rispettive lunghezze
 *  così da fingere due array differenti.
 *  Esegue un riordinamento tra le celle
 */
void merge(float *left, int llength, float *right, int rlength){

    //memoria temporanea allocata per gli array
    float *ltmp = (float *) malloc(llength * sizeof(float));
    float *rtmp = (float *) malloc(rlength * sizeof(float));

    //puntatori in memoria temporanea ad elementi che verranno ordinati
    float *ll = ltmp;
    float *rr = rtmp;

    float *result = left;

    //Copia dei riferimenti degli array nella locazione temporanea
    memcpy(ltmp, left, llength * sizeof(float));
    memcpy(rtmp, right, rlength * sizeof(float));


    while (llength > 0 && rlength > 0){

    	//merge del primo elemento di sinistra nel array principale
        //se è inferiore o uguale dell'elemento a destra
        if (*ll <= *rr) {

            *result = *ll;
            ++ll;
            --llength;
        }

        //altrimenti merge del primo elemento da destra nel array principale
        //se è più piccolo dell'elemento a sinistra
        else {

            *result = *rr;
            ++rr;
            --rlength;
        }

        ++result;//incremento indice
    }

    //tutti gli elementi sia di sinistra che di destra del array temporaneo
    //sono stati inseriti ordinati nel array principale

    //vengono ora re-immesso nel array principale il resto del array temporaneo sinistro e destro
    if (llength > 0)
        while (llength > 0) {
            *result = *ll;
            ++result;
            ++ll;
            --llength;
        }
    else
        while (rlength > 0) {
            *result = *rr;
            ++result;
            ++rr;
            --rlength;
        }

    //rilascio memoria usata per array temporanei
    free(ltmp);
    free(rtmp);
}


/*
 *  Funzione "mergeSort" che ha in ingresso un array con la rispettiva lunghezza
 *  Genera due processi, ognuno dei quali invoca questa stessa funzione "mergeSort"
 *  sulla metà del array a lui assegnata.
 *  Infine invoca la funzione "merge".
 */
void mergeSort(float *arr, int l){

	//check lunghezza array per uscita ricorsione
    if(l < 2) return;

    int middle = l/2; //indice metà array
    int llength = l-middle; //lunghezza totale array a cui sottraggo l'indice mediano
    int status; //per gestire le waitpid()

    //pipe
    int pipeSx[2]; //pipe nella quale il figlio sinistro legge e scrive, assieme al padre
    pipe(pipeSx);
    int pipeDx[2]; //pipe nella quale il figlio destro legge e scrive, assieme al padre
    pipe(pipeDx);

    int lchild; //intero contenente il file descriptor del figlio sinistro
    int rchild; //intero contenente il file descriptor del figlio destro


    /*
     * inizio figlio SINISTRO
     */

    lchild = fork(); //creazione figlio

    //check corretta creazione figlio
	if (lchild < 0) {
		perror("fork");
		exit(1);
	}
    if(lchild == 0){

        float n; //intero di supporto per lettura e scrittura da pipe
        float *sx; //riferimento per array

        //allocazione memoria per contenere l'array usato dal figlio
        sx= malloc(llength * sizeof(float));

        //ciclo di lettura pipe, precedentemente scritta dal padre, con salvataggio in array
        for(int i = 0; i<llength; i++){
            read(pipeSx[0], &n, sizeof(float));
            sx[i] = n;
        }

        //esecuzione mergeSort
        mergeSort(sx, llength);

        //ciclo di scrittura pipe, che verrà letta dal padre
        for(int i = 0; i<llength; i++){
            n = sx[i];
            write(pipeSx[1], &n, sizeof(int));
        }

        free(sx); //libero memoria allocata

        exit(0);
    }
    /*
     * fine figlio SINISTRO
     */

    /*
     * codice del padre dopo aver creato il figlio sinistro
     */
    else{

    /*
     * inizio figlio DESTRO
     */
    	rchild = fork(); //creazione figlio

    	//check corretta creazione figlio
	    if (lchild < 0) {
			perror("fork");
			exit(1);
		}

        if(rchild == 0){

            float n; //intero di supporto per lettura e scrittura da pipe
            float *dx; //riferimento per array

	        //allocazione memoria per contenere l'array usato dal figlio
            dx= malloc(middle * sizeof(float));

            //ciclo di lettura pipe, precedentemente scritta dal padre, con salvataggio in array
            for(int i = 0; i<middle; i++){
                read(pipeDx[0], &n, sizeof(float));
                dx[i] = n;
            }

            //esecuzione mergeSort
            mergeSort(dx, middle);

            //ciclo di scrittura pipe, che verrà letta dal padre
            for(int i = 0; i<middle; i++){
                n = dx[i];
                write(pipeDx[1], &n, sizeof(float));
            }

            free(dx); //libero memoria allocata
            exit(0);
        }
    /*
     * fine figlio DESTRO
     */

    /*
     * continuazione del padre
     */
     	//riferimenti array per contenere dati letti/scritti pipe
        float *rL, *rR;
        rL= arr;
        rR= arr+llength;

        float n,t; //interi di supporto per lettura e scrittura da pipe

       	//cicli per scrivere l'array sulle pipe dei figli
        for(int i = 0; i<llength; i++){
            n = rL[i];
            write(pipeSx[1], &n, sizeof(float));
        }
        for(int i = 0; i<middle; i++){
            t = rR[i];
            write(pipeDx[1], &t, sizeof(float));
        }

        //attesa della terminazione dei figli
        waitpid(lchild,&status,0);
        waitpid(rchild,&status,0);

        //cicli per leggere le pipe dai figli
        for(int i = 0; i<llength; i++){
            read(pipeSx[0], &n, sizeof(float));
            rL[i] = n;
        }
        for(int i = 0; i<middle; i++){
            read(pipeDx[0], &t, sizeof(float));
            rR[i] = t;
        }

        //richiamo funzione per riordinare l'array
        //con i rispettivi indici passati per argomento
        merge(rL, llength, rR, middle);
    }
}


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

    //check argomenti da prompt
    if (argc != 5) {
        printf("usage: %s <filename>\n", argv[0]);
        return 1;
    }

    //riferimenti per file.txt di input e output
    FILE *file_in, *file_out;


    //apertura stream input con check a seguire
    if(atoi(argv[2]) ==1 && atoi(argv[4]) == 2){
        file_in = fopen(argv[1], "r");
        if(file_in == NULL){
            printf("Errore apertura file\n");
            return 0;
        }
    }
    else if(atoi(argv[2]) == 2 && atoi(argv[4]) == 1){
        file_in = fopen(argv[3], "r");
        if(file_in == NULL){
            printf("Errore apertura file\n");
            return 0;
        }
    }

    float *array = NULL; //array su cui inserire i dati input
    int length = 0; //lungheza array
    char data_in[1000]; //intero di supporto per inserimento da file.txt ad array

    //importazione dati da input
    while (fscanf(file_in, "%s", &data_in) != EOF) {
        float supporto = atof(data_in);
        if(supporto==0){ }
        else{
            ++length;
            array = (float *) realloc(array, length * sizeof(float));
            array[length - 1] = supporto;
        }

    }

    fclose(file_in); //chiusura file input

    printf("Elementi letti dall'input: %d\n", length);


    mergeSort(array, length);

    printf("Fine mergeSort\n");

    //scrivo l'array post mergesort su file
    if(atoi(argv[2]) ==2 && atoi(argv[4]) == 1){
        file_out = fopen(argv[1], "w");
        if(file_out == NULL){
            printf("Errore apertura file\n");
            return 0;
        }
    }
    else if(atoi(argv[2]) == 1 && atoi(argv[4]) == 2){
        file_out = fopen(argv[3], "w");
        if(file_out == NULL){
            printf("Errore apertura file\n");
            return 0;
        }
    }

    for(int i=0; i< length; i++){
        int verifica = array[i];
        if(verifica == array[i]){
            fprintf(file_out, "%i\n", (int)array[i]);
        }
        else{
            fprintf(file_out, "%1.3f\n", array[i]);
        }
    }

    printf("\n");
    fclose(file_out);
    free(array); //liberazione array

}