/* par20_ex6_x2.c SJ */

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


double ltime();
char *randomString(int n, int nchar);
void printsubstring(char *A, int start, int count);
int longestRepeatingSubstring(const char *A, int len, int *Rpos1, int *Rpos2);
int longestRepeatingSubstring_mpi(char *A, int len, int *Rpos1, int *Rpos2);


int main(int argc, char *argv[]) {
    char *input;
    int N = 50; // 10000;	// string length
    int maxchar = 2;    // character set size
    int P, PID;

    int pos1, pos2, len;

    double starttime, endtime, seqtime, partime;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &PID);
    MPI_Comm_size(MPI_COMM_WORLD, &P);


    if (argc > 1)
        N = atoi(argv[1]);
    if (argc > 2)
        maxchar = atoi(argv[2]);


    if (PID == 0) {
        // process 0 creates the input

        input = randomString(N, maxchar);

        if (N <= 80)
            printf("Input: %s\n", input);

        // sequential execution
        starttime = ltime();
        len = longestRepeatingSubstring(input, N, &pos1, &pos2);
        endtime = ltime();
        seqtime = endtime - starttime;

        printf("\nLongest repeating (seq): len=%d, ", len);
        printf("pos1=:%d (", pos1);
        if (len < 80) printsubstring(input, pos1, len);
        printf(") pos2=%d: (", pos2);
        if (len < 80) printsubstring(input, pos2, len);
        printf(")\n");
        printf("Sequential %.6lf s\n", seqtime);

        // parallel execution

        MPI_Barrier(MPI_COMM_WORLD);    // barriers just to ensure fair timing
        starttime = ltime();
        len = longestRepeatingSubstring_mpi(input, N, &pos1, &pos2);
        MPI_Barrier(MPI_COMM_WORLD);
        endtime = ltime();
        partime = endtime - starttime;

        // report results
        printf("\nLongest repeating (par): len=%d, ", len);
        printf("pos1=:%d (", pos1);
        if (len < 80) printsubstring(input, pos1, len);
        printf(") pos2=%d: (", pos2);
        if (len < 80) printsubstring(input, pos2, len);
        printf(")\n");
        printf("Parallel %.6lf s\n", partime);
        printf("Speedup: %.2f\n", seqtime / partime);

        free(input);

    } else {
        // all other processes just participate in computation
        MPI_Barrier(MPI_COMM_WORLD);
        longestRepeatingSubstring_mpi(NULL, N, NULL, NULL);
        MPI_Barrier(MPI_COMM_WORLD);
    }

    MPI_Finalize();

    return 0;
}

void printsubstring(char *A, int start, int count) {
    int i;
    for (i = start; i < start + count; i++)
        putchar(A[i]);
}


/**
 * Generate random string of length n
 * @param n  string length
 * @param nchar how many different characters to use
 * @return the new string, of NULL of n<0
 */
char *randomString(int n, int nchar) {
    int i;
    char *s;
    char base = '0';
    if (n < 0)
        return NULL;
    if (nchar > 26)
        nchar = 26;
    if (nchar > 10)
        base = 'a';
    s = (char *) malloc(n + 1);
    for (i = 0; i < n; i++)
        s[i] = base + rand() % nchar;
    s[n] = '\0';
    return s;
}


/**
 * Longest repeating substring of string A.
 * The substrings may overlap partially.
 * @param A input string
 * @param len  length of A (redundant)
 * @param Rpos1 pointer to which the first starting position is stored (or -1 if no duplicate char)
 * @param Rpos2 pointer to which the second starting position is stored (or -1 if no duplicate char)
 * @return the length of the longest repeating substring, or 0 if no character occurs twice
 */
int longestRepeatingSubstring(const char *A, int len, int *Rpos1, int *Rpos2) {
    int maxlen = 0; // longest repeating found this far
    int maxpos1 = -1;
    int maxpos2 = -1;

    int offset = 1; // difference of starting positions
    while (offset < len - 1) {

        int pos1 = 0;   // start from beginning
        int pos2 = offset;
        int samelen = 0;    // how many same characters encountered
        int samestart1 = -1;    // start index of current streak of same charcters
        int samestart2 = -1;

        while (pos2 < len) {    // pos2 > pos1, iterate to the end
            if (A[pos1] == A[pos2]) {   // same character
                if (samestart1 == -1) { // start of new common sequence
                    samestart1 = pos1;
                    samestart2 = pos2;
                }
                samelen++;
                if (samelen > maxlen) { // new maximum found
                    maxpos1 = samestart1;
                    maxpos2 = samestart2;
                    maxlen = samelen;
                }
            } else {    // different character, reset counters
                samelen = 0;
                samestart1 = -1;
                samestart2 = -1;
            }
            pos1++;
            pos2++;
        }
        offset++;
    }
    // store results and return
    *Rpos1 = maxpos1;
    *Rpos2 = maxpos2;
    return maxlen;
}


/**
 * Longest repeating substring of string A.
 * The substrings may overlap partially.
 * All processes have correct len.
 * Only PID 0 has something meaningful in parameters A, Rpos1, Rpos2. Others have NULL.
 * Only PID 0 is required to return the result.  Others may return garbage.
 * @param A input string
 * @param len  length of A (redundant)
 * @param Rpos1 pointer to which the first starting position is stored (or -1 if no duplicate char)
 * @param Rpos2 pointer to which the second starting position is stored (or -1 if no duplicate char)
 * @return the length of the longest repeating substring, or 0 if no character occurs twice
 */
int longestRepeatingSubstring_mpi(char *A, int len, int *Rpos1, int *Rpos2) {
    int maxlen = 0; // local results
    int index1 = -1;
    int index2 = -1;
    int P, PID;

    // get P and PID
    MPI_Comm_rank(MPI_COMM_WORLD, &PID);
    MPI_Comm_size(MPI_COMM_WORLD, &P);

    // all others need buffer for input data
    if (PID != 0)
        A = (char *) malloc(len * sizeof(char));
    else
        ; // TODO, possibly something else

    // TODO

    // 0 delivers the input

    // everyone does own part of the whole work

    // TODO

    if (PID == 0) { // 0 returns the best result
        // TODO

        *Rpos1 = index1;    // return  result
        *Rpos2 = index2;
        return maxlen;
    } else {
        free(A);    // others clean up and return without result
        return 0;
    }


} // longestRepeatingSubstring_mpi()

/* timestamp in seconds */
double ltime() {
    return MPI_Wtime();
}