#include "mpi.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define addElement(v, value) (v[++v[0]] = value)
#define ctoi(x) ((x)-'0')
#define itoc(x) ((x)+'0')
#define max(a,b) ( (a) > (b) ? a : b)
#define min(a,b) ( (a) < (b) ? a : b)

#define TRUE 1
#define FALSE 0

#define ROOT 0
#define NOPARENT -1

#define NONEXT -1
#define BROADCAST -2
#define WAKEUPMESASGE -3

#define READY 1
#define END 2
#define WAKEUP 3

#define SLEEP 3
#define LEADER 4
#define LOST 5


int rank, size;
int* neighbours, *routingTable, *ready, **graph;
FILE* logFile;
MPI_Status status;
MPI_Request request;
int leader, adjount;

typedef struct{
    int from;
    int to;
    char message[200]; //nu pot pune char* deoarece trimit in retea aceasta structura si nu merge cu pointer....
} TMessage, *Message;

typedef struct{
    Message* messages;
    int allocatedMessages;
    int messagesCount;
} TMessageBox, *MessageBox;

MessageBox messageBox;

Message createMessage(char* message, int to){
    Message newMessage = (Message)malloc(sizeof(TMessage));
    //newMessage->message = strdup(message);
    strcpy(newMessage->message, message);
    newMessage->to = to;
    newMessage->from = rank;

    return newMessage;
}

MessageBox createMessageBox(){
    MessageBox newBox = (MessageBox)malloc(sizeof(TMessageBox));
    newBox->allocatedMessages = 10;
    newBox->messages = (Message*)malloc(newBox->allocatedMessages * sizeof(Message));
    newBox->messagesCount = 0;

    return newBox;
}

void freeMessageBox(MessageBox *box){
    free ((*box)->messages);
    free(*box);
}

void createMessageStructFormat(MPI_Datatype* structType){

    const int nitems=3;
    int blocklengths[3] = {1, 1, 200};
    MPI_Datatype types[3] = {MPI_INT, MPI_INT, MPI_CHAR};
    MPI_Datatype mpi_message_type;
    MPI_Aint     offsets[3];

    offsets[0] = offsetof(TMessage, from);
    offsets[1] = offsetof(TMessage, to);
    offsets[2] = offsetof(TMessage, message);

    MPI_Type_create_struct(nitems, blocklengths, offsets, types, structType);
    MPI_Type_commit(structType);

}

void addMessageToBox(MessageBox box, Message message){
    box->messages[box->messagesCount] = message;

    box->messagesCount++;
    if(box->messagesCount == box->allocatedMessages){

        box->allocatedMessages *= 2;
        Message* newMessages = realloc(box->messages, box->allocatedMessages * sizeof(Message*));
        //Check(newMessages == NULL, "Eroare la alocarea de mai multe mesaje");
        if(!newMessages){
            printf("Eroare la alocare\n");
            exit(0);
        }

        box->messages = newMessages;
    }
}

char* myItoa(int x){

    char* buffer = (char*)malloc(33 * sizeof(char));
    char* p = buffer;
    while(x>0){
        int r = x % 10;
        *p = itoc(r);
        p++;
        x = x / 10;
    }
    *p = 0;
    int len = p - buffer, i;
    for(i=0; i<len/2; i++){
        char aux = buffer[i];
        buffer[i] = buffer[len-i-1];
        buffer[len-i-1] = aux;
    }

    return buffer;
}

void printMessages(MessageBox box){
    //printf("Mesajele procesului cu ID: %i\n", rank);
    int i;
    for(i=0; i<box->messagesCount; i++)
        printf("(S:%i, D:%s I:%i): %s\n", box->messages[i]->from , (box->messages[i]->to == BROADCAST ? "BCAST" : myItoa(box->messages[i]->to)) , i, box->messages[i]->message );
}

void Check(int condition, char* message){
    if(condition){
        if(rank == 0)
            printf("%s\n", message);
        MPI_Finalize();
        exit(0);
    }
}

void neighbOR(int *a, int *b){
    int i;
    for(i=0; i<size; i++)
        if(a[i] == NOPARENT)
            a[i] = b[i];
}

void printArray(int*a, int size){
    int i;
    for(i=0; i<size; i++)
        printf("%3i", a[i]);
    printf("\n");
}


void printNeighbours(int *v){
    printf("%i\t", rank);
    printArray(v+1, v[0]);
}

void printRoutingTable(int *v){
    printf("%i\t", rank);
    printArray(v, size);
}

void printGraph(int** graph){
    int i, j;
    for(i=0; i<size; i++){
        int j = 0, k=1, len = graph[i][0];

        while(k<=len){
            while(j < graph[i][k]){
                printf("0 ");
                j++;
            }
            printf("1 ");
            k++;
            j++;
        }
        while(j++ < size)
            printf("0 ");
        printf("\n");
    }
}

char* concat(char* a, char* b){
    char *c = (char*)malloc(strlen(a) + strlen(b));
    strcpy(c, a);
    strcat(c, b);

    return c;
}


int** readGraph(char* fileName){
    // function only called by ROOT!
    // size * size matrix to be returned
    // size lines to be read from the file (one process is a bunker -- a vertex)
    Check(rank != ROOT, "Doar root are acces in aceasta functie!");
    int** graph = (int**)calloc(size, sizeof(int*));
    FILE *in = fopen(fileName, "rt");
    Check(!in, "Eroare la deschiderea fisierului.");
    int i, result;

    for(i=0; i<size; i++){
        char* line;
        size_t lineSize;
        result = getline(&line, &lineSize, in);

        char* p = strtok(line, " ");
        p = strtok(NULL, " "); // '-'-ul
        graph[i] = (int*)calloc(size + 1, sizeof(int)); //conform conventiei, aloc size + 1 elemente, deoarece la [0] voi avea size-ul listei curente de vecini!! (atentie la trimiteri si alocari ulterioare)

        while(p = strtok(NULL, " "))
            addElement(graph[i], atoi(p));
    }

    fclose(in);
    return graph;
}

int* readGraphLine(char* fileName){

    FILE *in = fopen(fileName, "rt");
    Check(!in, "Eroare la deschiderea fisierului.");
    int* neighbours;
    int i=0, result;
    char line[100];
    size_t lineSize;

    while(i++ != rank){
        fgets(line, 100, in);
        //result = getline(&line, &lincreateMessageSeSize, in);
    }

    //result = getline(&line, &lineSize, in);
    fgets(line, 100, in);

    char* p = strtok(line, " ");
    p = strtok(NULL, " "); // '-'-ul
    neighbours = (int*)calloc(size + 1, sizeof(int)); //conform conventiei, aloc size + 1 elemente, deoarece la [0] voi avea size-ul listei curente de vecini!! (atentie la trimiteri si alocari ulterioare)

    while(p = strtok(NULL, " "))
        addElement(neighbours, atoi(p));

    fclose(in);
    return neighbours;
}

int* createSonda(){
    int* sonda = (int*)malloc(sizeof(int) * size);
    int i;
    for(i=0; i<size; i++)
        sonda[i] = NOPARENT;

    return sonda;
}

void fixNeighbours(int* routingTable){
    int i;
    /* Recreez vecinii dupa rularea STP-ului */
    neighbours[0] = 0;
    for(i=0; i<size; i++)
        if(routingTable[i] == rank){
            neighbours[0]++;
            neighbours[neighbours[0]] = i;
        }
    //printNeighbours(neighbours);
}

void fixRoutingTable(int* routingTable, int* neighbours){
    int* neighbourArray = (int*)calloc(size, sizeof(int));
    int i;

    //printRoutingTable(routingTable);

    for(i=1; i<=neighbours[0]; i++)
        neighbourArray[neighbours[i]] = 1;
    neighbourArray[rank] = 1; //bug la root

    //neighbourArray[rank] = 0; // ma trec si pe mine

    /* Pentru a nu face O(N^2) cautari, salvez intr-un vector de vecini, lista de vecini */
    /* Daca avem 0->1->2->4->8, noua ne afiseaza pe routingTable[8] = 4, nu 1, deci fac un while pana am vecin (adica 1) */
    for(i=0; i<size; i++){
        while(neighbourArray[routingTable[i]] != 1)
            routingTable[i] = routingTable[routingTable[i]];

    }

    for(i=0; i<size; i++){
        if(routingTable[i] == rank)
            routingTable[i] = i;
    }

    routingTable[rank] = -1;

    //printRoutingTable(routingTable);
    free(neighbourArray);
}

void readNeighbours( char* fileName ){

    if(rank == ROOT){
        graph = readGraph(fileName);
        //printGraph(graph);
        neighbours = graph[0];
    }
    else{
        neighbours = readGraphLine(fileName);
    }
}

void logGraph(){
    int i;
    if(rank == ROOT){
        fprintf(logFile, "Matrice de adiacenta\n");
        for(i=0; i<size; i++){
            int j;
            for(j=0; j<size; j++){
                fprintf(logFile, "%i ", graph[i][j]);
            }
            fprintf(logFile, "\n");
        }
    }
}

void logRoutingTable(){
    int i;
    fprintf(logFile, "%i: ", rank);
    for(i=0; i<size; i++){
        fprintf(logFile, "%i ", routingTable[i]);
    }
    fprintf(logFile, "\n");
}

void createRoutingTable(){
    int i;
    if(rank == ROOT){

        //printNeighbours(neighbours);

        /* ROOT trimite catre toti vecinii sai si asteapta un vector pe care va face neighbOR */
        int *sonda = createSonda();
        int tmp[size];

        for(i=1; i<=neighbours[0]; i++){
            MPI_Send(sonda, size, MPI_INT, neighbours[i], 0, MPI_COMM_WORLD);
        }

        for(i=1; i<=neighbours[0]; i++){
            MPI_Recv(tmp, size, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
            neighbOR(sonda, tmp);
        }

        /* Aceasta este tabela de rutare a lui ROOT. Acum trimit catre toti conectati direct ca si ei sa-si formeze tabela lor de rutare pe baza acesteia. */
        routingTable = sonda;
        /* Tablela de rutare imi pune last_hop in acest punct pentru orice nod. last_hop nu este neaparat un vecin cu nodul curent, deci caut next_hop. */

        for(i=0; i<size; i++){
            if(routingTable[i] == rank){ // trimit celor conectati direct (root nu are parinte)
                MPI_Send(routingTable, size, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
        }

        //printRoutingTable(routingTable);
        fixNeighbours(routingTable);
        fixRoutingTable(routingTable, neighbours);

    }

    else{

        int tmp[size], parent;
        MPI_Recv(tmp, size, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
        parent = status.MPI_SOURCE; // imi aflu parintele

        //printf("Parintele lui %i este %i\n", rank, parent);

        int *sonda = createSonda();
        for(i=1; i<=neighbours[0]; i++){
            if(neighbours[i] == parent)
                continue;
            MPI_Isend(sonda, size, MPI_INT, neighbours[i], 0, MPI_COMM_WORLD, &request);
        }

        for(i=1; i<neighbours[0]; i++){
            MPI_Recv(tmp, size, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
            neighbOR(sonda, tmp);
        }

        sonda[rank] = parent;
        MPI_Send(sonda, size, MPI_INT, parent, 0, MPI_COMM_WORLD);

        //printNeighbours(neighbours);

        // Primesc tabela de rutare de la parent si mi-o creez pe a mea de la el
        MPI_Recv(sonda, size, MPI_INT, parent, 0, MPI_COMM_WORLD, &status);
        sonda[parent] = rank; //ajung la parinte prin mine (dar tot retin ca el e parinte in STP in acea variabila)
        sonda[rank] = NONEXT; //de la mine la mine am ajuns deja (:D)
        routingTable = sonda;

        for(i=0; i<size; i++){
            if(routingTable[i] == rank && i != parent) // trimit celor conectati direct (root nu are parinte)
                MPI_Send(routingTable, size, MPI_INT, i, 0, MPI_COMM_WORLD);
        }

        //printRoutingTable(routingTable);
        fixNeighbours(routingTable);
        fixRoutingTable(routingTable, neighbours);

    }

    if(rank == ROOT)
        logGraph();
    logRoutingTable();

}

void readMessages(char* fileName){

    FILE *in = fopen(fileName, "rt");
    Check(!in, "Eroare la deschiderea fisierului");
    int i, lines, result;
    size_t lineSize;
    char line[100];
    int source, destination;

    fgets(line, 100, in);
    lines = atoi(line);

    messageBox = createMessageBox();

    for(i=0; i<lines; i++){
        char *p, *q;
        fgets(line, 100, in);

        p = line;
        q = line;
        while(*p != ' ')
            p++;
        *p = '\0'; // modific spatiul in 0 pentru atoi

        source = atoi(q); //atoi se opreste la primul 0 (^)
        if(source != rank)
            continue;

        p++;
        q = p;
        //printf("%i\n", source);

        while(*p != ' ')
            p++;
        *p = 0;

        if(strcmp(q, "B") == 0)
            destination = BROADCAST;

        else
            destination = atoi(q); //atoi se opreste la primul 0 (^);

        q = p+1;
        if(q[strlen(q)-1] == '\n')
            q[strlen(q)-1] = 0;

        addMessageToBox(messageBox, createMessage(q, destination));
        //printf("Source: %i, Destination: %i, Line: %s\n", source, destination, q);
    }

    fclose(in);
}

void createReadyTopology(MPI_Datatype messageStructType){
    int allReady = size - 1;
    ready = (int*)calloc(size, sizeof(int));
    ready[rank] = 1;

    /* Imi trimit confirmarea pe broadcast (catre toti la next-hop) */
    int i;
    Message readyMessage = createMessage("READY", BROADCAST);
    Message recvMessage = (Message)malloc(sizeof(TMessage));

    //printNeighbours(neighbours);

    for(i=1; i<=neighbours[0]; i++){
        MPI_Send(readyMessage, 1, messageStructType, neighbours[i], READY, MPI_COMM_WORLD);
    }

    /* Cat timp mai sunt procese de la care nu am primit confirmarea de ready nu trec mai departe */
    /* De asemenea, rutez toate mesajele care nu-mi sunt destinate */
    while(allReady > 0){
        MPI_Recv(recvMessage, 1, messageStructType, MPI_ANY_SOURCE, READY, MPI_COMM_WORLD, &status);
        if(recvMessage->to == BROADCAST){
             if( status.MPI_TAG == READY && ready[recvMessage->from] == 0 ){ // mi-e destinat mie ?
                ready[recvMessage->from] = 1;
                allReady--;
            }

            // Trimit mesajul tuturor vecinilor, mai putin celui care a trimis
            for(i=1; i<=neighbours[0]; i++){
                if( neighbours[i] != status.MPI_SOURCE )
                    MPI_Send(recvMessage, 1, messageStructType, neighbours[i], READY, MPI_COMM_WORLD);

            }
        }
    }

    free(readyMessage);
    free(recvMessage);

    //printf("Procesul %i a terminat de rutat complet\n", rank);
}

void sendMyMessages(MessageBox myMessageBox, MPI_Datatype messageStructType){
    int i, j;
    for(i=0; i<myMessageBox->messagesCount; i++){
        fprintf(logFile, "[%i] Trimit mesajul%s prin %s\n", rank, myMessageBox->messages[i]->to == BROADCAST ? "" : concat("spre ",myItoa(myMessageBox->messages[i]->to)), myMessageBox->messages[i]->to == BROADCAST ? "BROADCAST" : myItoa(routingTable[myMessageBox->messages[i]->to]));
        if(myMessageBox->messages[i]->to == BROADCAST){
            for(j=1; j<=neighbours[0]; j++)
                MPI_Send(myMessageBox->messages[i], 1, messageStructType, neighbours[j], 0, MPI_COMM_WORLD);
        }
        else
            MPI_Send(myMessageBox->messages[i], 1, messageStructType, routingTable[myMessageBox->messages[i]->to], 0, MPI_COMM_WORLD);
    }
    ready[rank] = 0;

    Message endMessage = createMessage("END", BROADCAST);
    for(i=1; i<=neighbours[0]; i++)
        MPI_Send(endMessage, 1, messageStructType, neighbours[i], END, MPI_COMM_WORLD);

    free(endMessage);
}

void routeMessages(MPI_Datatype messageStructType){
    int i, allDone = 1; // Mesajele mele sunt trimise
    Message recvMessage = (Message)malloc(sizeof(TMessage));

    //printNeighbours(neighbours);

    while(allDone < size){ // Rutez toate mesajele care trec prin mine pana toate au inchis conexiunea.

        MPI_Recv(recvMessage, 1, messageStructType, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

        if(recvMessage->to == BROADCAST){
             if( status.MPI_TAG == END && ready[recvMessage->from] == 1 ){
                ready[recvMessage->from] = 0;
                allDone++;
                //fprintf(logFile, "[%i] Am primit un mesaj de BROADCAST (END) trimis de %i\n", rank, recvMessage->from, neighbours[0]-1 );
            }
            else{
                fprintf(logFile, "[%i] Am primit un mesaj de BROADCAST trimis de %i: %s\n", rank, recvMessage->from, recvMessage->message);
            }


            // Trimit mesajul tuturor vecinilor, mai putin celui care a trimis
            for(i=1; i<=neighbours[0]; i++){

                if( neighbours[i] != status.MPI_SOURCE ){
                    MPI_Send(recvMessage, 1, messageStructType, neighbours[i], status.MPI_TAG, MPI_COMM_WORLD);
                }

            }

        }
        else{ //Mesaj destinat cuiva (eu sau cineva care routeaza prin mine)
            if(recvMessage->to == rank){ // destinat mie
                fprintf(logFile, "[%i] Am primit un mesaj de la %i: %s\n", rank, recvMessage->from, recvMessage->message );
            }
            else{
                fprintf(logFile, "[%i] Routez un mesaj de la %i prin %i\n", rank, recvMessage->from, routingTable[recvMessage->to] );
                MPI_Send(recvMessage, 1, messageStructType, routingTable[recvMessage->to], 0, MPI_COMM_WORLD);
            }
        }

    }

    fprintf(logFile, "[%i] Am primit toate mesajele!\n", rank);
    free(recvMessage);
}

void initializeLogFile(int logPart){
    if(logPart > 1)
        fclose(logFile);

    char* fileName = concat(concat("log", myItoa(logPart)), ".txt");
    if(rank == 0){
        logFile = fopen(fileName, "wt");
        fprintf(logFile, "Etapa: %i\n", logPart);
        fclose(logFile);
    }
    logFile = fopen(fileName, "at");
}

void wakeUpCall(MPI_Datatype messageStructType){

    /* Etapa de wake-up */
    int ws = 0, wr = 0;
    int i, r = neighbours[0], id;
    leader = rank;
    Message wakeUpMessage = createMessage("WAKEUP", WAKEUPMESASGE);
    Message recvMessage = (Message)malloc(sizeof(TMessage));

    if(neighbours[0] == 1 && rank != ROOT) { // p este initiator
        ws = TRUE;
        for(i=1; i<=neighbours[0]; i++){ // fa q € vecini
            MPI_Send(wakeUpMessage, 1, messageStructType, neighbours[i], WAKEUP, MPI_COMM_WORLD); //send wake-up
        }
    }

    do{
        MPI_Recv(recvMessage, 1, messageStructType, MPI_ANY_SOURCE, WAKEUP, MPI_COMM_WORLD, &status);
        fprintf(logFile, "[%i] Am primit wake-up call de la %i [%i]\n", rank, status.MPI_SOURCE, wr);
        wr++;
        if(ws == FALSE){
            ws = TRUE;
            for(i=1; i<=neighbours[0]; i++) // fa q € vecini
                MPI_Send(wakeUpMessage, 1, messageStructType, neighbours[i], WAKEUP, MPI_COMM_WORLD); //send wake-up
        }
    } while(wr < neighbours[0]);

    free(wakeUpMessage);
    free(recvMessage);
}

int leaderFunction(int a, int b){
    return min(a,b);
}

void selectAdjount(MPI_Datatype messageStructType){
    int i;
    if(rank == leader){
        // Aleg adjunctul random
        srand (time(NULL));
        adjount = (rand() % neighbours[0]) + 1;

        Message message = createMessage(myItoa(adjount), BROADCAST);
        for(i=1;i<=neighbours[0]; i++)
            MPI_Send(message, 1, messageStructType, neighbours[i], 0, MPI_COMM_WORLD);
        adjount = adjount;
        free(message);
    }
    else{
        Message recvMessage = (Message)malloc(sizeof(TMessage));
        MPI_Recv(recvMessage, 1, messageStructType, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
        for(i=1; i<=neighbours[0]; i++){
            if(neighbours[i] != status.MPI_SOURCE)
                MPI_Send(recvMessage, 1, messageStructType, neighbours[i], 0, MPI_COMM_WORLD);

        }
        adjount = atoi(recvMessage->message);
        free(recvMessage);
    }
}

void selectLeader(MPI_Datatype messageStructType){

    Message recvMessage = (Message)malloc(sizeof(TMessage));

    int i, r = neighbours[0], id;
    leader = rank;

    // END ETAPA WAKE-UP
    int *rec = (int*)calloc(neighbours[0], sizeof(int));
    int *positionsInNeighbours = (int*)calloc(size, sizeof(int));

    for( i=1; i<=neighbours[0]; i++)
        positionsInNeighbours[neighbours[i]] = i;

    while( r > 1 ) {
        MPI_Recv(&id, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
        r--;
        rec[positionsInNeighbours[status.MPI_SOURCE]] = TRUE;
        leader= leaderFunction(leader, id);
    }

    int lastNeighbour;
    for(i=1; i<=neighbours[0]; i++)
        if(rec[i] == FALSE){
            lastNeighbour = neighbours[i];
            break;
        }

    /* Comunic cu al n-lea vecin de la care n-am primit mesaj */
    MPI_Send(&leader, 1, MPI_INT, lastNeighbour, 0, MPI_COMM_WORLD);
    MPI_Recv(&id, 1, MPI_INT, lastNeighbour, 0, MPI_COMM_WORLD, &status);
    leader = leaderFunction(leader, id);

    for(i=1; i<=neighbours[0]; i++){
        if(neighbours[i] != lastNeighbour) // trimit catre toti vecinii mai putin last neighbour ceea ce am calculat eu.
            MPI_Send(&leader, 1, MPI_INT, neighbours[i], 0, MPI_COMM_WORLD);
    }

    free(recvMessage);
}

void selectLeaderAndAdjount(MPI_Datatype messageStructType){
    wakeUpCall(messageStructType);
    selectLeader(messageStructType);
    selectAdjount(messageStructType);
}

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

    MPI_Init(&argc, &argv);
    Check(argc != 3, "Formatul parametrilor gresit (./a.out fis_topologie fis_mesaje)");
    initializeLogFile(1); // initializez logul pentru etapa 1

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    readNeighbours(argv[1]); // creez vectorul neighbours
    //printNeighbours(neighbours);

    createRoutingTable(); //creez vectorul routingTable
    //printRoutingTable(routingTable);

    initializeLogFile(2); // initializez logul pentru etapa 2
    readMessages(argv[2]); //creez MessageBox-ul messageBox
    //printMessages(messageBox);

    MPI_Datatype messageStructType;
    createMessageStructFormat(&messageStructType);

    createReadyTopology(messageStructType); // dupa acest pas, tot vectorul ready[SIZE] va fi true
    //printArray(ready, size);

    sendMyMessages(messageBox, messageStructType); // trimit mesajele din Message Box-ul procesului catre destinatia dorita
    routeMessages(messageStructType);
    freeMessageBox(&messageBox);

    initializeLogFile(3); // logul pentru etapa 3
    selectLeaderAndAdjount(messageStructType);
    fprintf(logFile, "[%i] Leader:%i - Adjunct:%i\n", rank, leader, adjount);
    //printf("%i %i\n", leader, adjount);

    fclose(logFile);
    MPI_Finalize();
    return 0;
}