/* par20_ex3_t13_14.c SJ */

/*

 13. Parallelize an algorithm to find one common value of two unsorted integer arrays. The input
is two arrays A and B, and length (N), return value is a value that can be found from both
arrays, or ?1 if there are no common values. You can find a sequential O(n^2) implementation
at Moodle. Make a parallel OpenMP version of it. Notice that O(n^2) is not optimal, but we?ll
ignore it this week.

 14. Parallelize the algorithm to find all common values of two unsorted integer arrays. The input is
two arrays A, B, lengths (N), return value is a pointer to an array of the common values. Further,
one more parameter is a pointer to an integer, into which the algorithm stores the number of
found common elements. You can find a sequential O(n^2) implementation at Moodle. Make a
parallel OpenMP version of it. Notice that O(n^2) is not optimal, but we?ll ignore it this week.


*/


#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#include <omp.h>


// function prototypes
int firstindex(const int *A, int N, int s, int x);
int any_common_element(int *A, int *B, int N);
int any_common_element_par(int *A, int *B, int N);
int *all_common_elements(int *A, int *B, int N, int *NC);
int *all_common_element_par(int *A, int *B, int N, int *NC);
void generateinput(int **A, int N, int factor);
void generateuniqueinput(int **A, int N, const int *B, int NB);


double ltime();


int main(int argc, char *argv[]) {
	int N = 10000;
	int *A = NULL, *B = NULL;
	int P = 4, i;
	double starttime, endtime, seqtime, partime;

	// 1st parameter: input size
	if (argc > 1)
		N = atoi(argv[1]);

	// second parameter: number of threads
	if (argc > 2)
		P = atoi(argv[2]);
	else
		P = omp_get_num_procs();

	if (P > 64)
		P = 64;

	omp_set_num_threads(P);

	printf("Testing any_common_element\n");

	// use this to find some common elements:
	generateinput(&A, N, 3);
    // generateinput(&B, N, 3);

	// use this to not find -- better speedup for any_common_element ;-)
	generateuniqueinput(&B, N, A, N);

	if (N <= 20) {
	    printf("A: ");
		for (i = 0; i < N; i++)
			 printf(" %d", A[i]);
		printf("\n");

        printf("B:");
        for (i = 0; i < N; i++)
            printf( " %d", B[i]);
        printf("\n");
    }

	starttime = ltime();
	int res = any_common_element(A, B, N);
	endtime = ltime();
	seqtime = endtime-starttime;
	printf("Sequential, common=%d, N=%d, time = %.6lf s\n", res, N, seqtime);

	starttime = ltime();
	res = any_common_element_par(A, B , N);
	endtime = ltime();
	partime = endtime-starttime;
	printf("Parallel, common=%d, N=%d, time = %.6lf s\n", res, N, partime);
	printf("Speedup %6.2f, P = %d, efficiency = %4.2f\n", seqtime/partime, P,
		   (seqtime/partime)/P);


	printf("\n------\nTesting all_common_elements\n");

	free(B);
    generateinput(&B, N, 3);

    if (N <= 20) {
        printf("A: ");
        for (i = 0; i < N; i++)
            printf(" %d", A[i]);
        printf("\n");

        printf("B:");
        for (i = 0; i < N; i++)
            printf( " %d", B[i]);
        printf("\n");
    }


    int *common = NULL;
	int ncommon = -2;
	starttime = ltime();
    common = all_common_elements(A, B, N, &ncommon);
	endtime = ltime();
	seqtime = endtime-starttime;
	printf("Sequential, ncommon=%d, N=%d, time = %.6lf s\n", ncommon, N, seqtime);

	if (ncommon < 10) {
		for (i = 0; i < ncommon; i++)
			printf("%d ", common[i]);
		printf("\n");
	}

	free(common);
    common = NULL;
    ncommon = -2;


	starttime = ltime();
    common = all_common_element_par(A, B, N, &ncommon);
	endtime = ltime();
	partime = endtime-starttime;
	printf("Parallel, ncommon=%d, N=%d, time = %.6lf s\n", ncommon, N, partime);
	printf("Speedup %6.2f, P = %d, efficiency = %4.2f\n", seqtime/partime, P,
		   (seqtime/partime)/P);

	if (ncommon < 10) {
        for (i = 0; i < ncommon; i++)
            printf("%d ", common[i]);
        printf("\n");
    }
    free(common);


	free(A);
	free(B);

	return 0;

} // main() 



/* generate random input, smaller factor = more probably common elements */
/* larger factor -> less probably common elements */
void generateinput(int **A, int N, int factor) {
	int i;
	*A = (int*)malloc(N*sizeof(int));
	for(i = 0; i < N; i++) {
		(*A)[i] = rand() % (N*factor);
	}
}

/* generate random input, no common elements with B */
/* N*NB time complexity */
void generateuniqueinput(int **A, int N, const int *B, int NB) {
	int i = 0;
	int factor = 5;
	*A = (int*)malloc(N*sizeof(int));
	while (i < N) {
		int r = rand() % (N*factor);
		if (firstindex(B, NB, 0, r) < 0)
			(*A)[i++] = r;
	}
}

/* returns the first occurrence of element x in array A starting from index s */
/* returns -1 if x is not in A[s..N-1] */
inline int firstindex(const int *A, int N, int s, int x) {
    int i;
    for (i = s; i < N; i++)
        if (A[i] == x)
            return i;
    return -1;
}



/* find whether arrays A and B (both N elements) have a common element or not */
/* returns one such element, -1 if not found */
int any_common_element(int *A, int *B, int N) {
	int i;
	for (i = 0; i < N; i++) 
		if (firstindex(B, N, 0, A[i]) > 0)
			return A[i];
	return -1;
}

/* find whether arrays A and B (both N elements) have a common element or not */
/* returns one such element, -1 if not found */
int any_common_element_par(int *A, int *B, int N) {
    // TODO: make parallel
    int i;
    for (i = 0; i < N; i++)
        if (firstindex(B, N, 0, A[i]) > 0)
            return A[i];
    return -1;
}


/* returns an array of elements that are present in both arrays A and B */
/* each elements is in the result only once even if there are more than two such elements */
/* returns the new array and stores to *NC the number of elements stored to result */
int *all_common_elements(int *A, int *B, int N, int *NC) {
	int *C = (int*) malloc(N * sizeof(int));
	int nc = 0;
	int i;
	for (i = 0; i < N; i++) {
        if (firstindex(B, N, i+1, A[i]) > 0) {
			if (firstindex(C, nc, 0, A[i]) < 0)
                C[nc++] = A[i];
			continue;
		} // if
	} // for

	*NC = nc;
	return C;
}

/* returns an array of elements that are present in both arrays A and B */
/* each elements is in the result only once even if there are more than two such elements */
/* returns the new array and stores to *NC the number of elements stored to result */
int *all_common_element_par(int *A, int *B, int N, int *NC) {
    // TODO make parallel
    int *C = (int*) malloc(N * sizeof(int));
    int nc = 0;
    int i;
    for (i = 0; i < N; i++) {
        if (firstindex(B, N, i+1, A[i]) > 0) {
            if (firstindex(C, nc, 0, A[i]) < 0)
                C[nc++] = A[i];
            continue;
        } // if
    } // for

    *NC = nc;
    return C;
}

// we can use the OpenMP timer instead of standard library timer
#define useomptime 1

// seconds.microseconds
double ltime()
{
#ifdef useomptime
    return omp_get_wtime();
#else
    struct timeval tv;
    struct timezone tz;
    gettimeofday(&tv, &tz);
    return tv.tv_sec + (double)tv.tv_usec/1000000;
#endif
}