/*
 * Parrallel Bubble Sort in UPC
 *
 * NOTE: only prints output when built with the -DOUTPUT flag
 */
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
//#include "upc.h"

/* shared variables */

shared int * shared array;
shared upc_lock_t * shared locks[THREADS*2];

int main(argc,argv) 
	int argc;
	char *argv[];
{
	/* local variables per thread */
	int curlock, N, oldlock, sectionSize, temp;
	int mc, firsttime, done;
	int i, j, l;				// counters for loops

	/*
#ifdef TIMED
	int starttime, endtime;		// used for measuring run time
#endif
*/
	/* make sure proper arguments passed in */
/*	if (argc < 1) {
		printf("oops, forgot the number of elements\n");
		exit(-1);
	}
*/
	/* get number of elements */
//	N = atoi(argv[1]);

	/* allocate shared arrays and initialize stuff */
	/*
	if (MYTHREAD == 0){
		array = (shared int *)upc_global_alloc(THREADS, N*sizeof(int));
		for (i=0; i<(THREADS*2); ++i)
			locks[i] = upc_global_lock_alloc();

	}
	*/
	
	//sectionSize = N/2;
	curlock = MYTHREAD*2;

	/* initialize array */
//	upc_barrier;

//	srand48(MYTHREAD*N);
//	upc_forall(i=0; i<N*THREADS; ++i; &array[i])
//		array[i] = lrand48();

	/* Thread 0 prints out the unsorted array */
	
	/*
#ifdef OUTPUT
	upc_barrier;
	if (MYTHREAD == 0) {
		printf("Unsorted array:\n");
		j = 0; i = 0;
		while (j < N*THREADS){
			printf("\t%d (Thread<%d> i<%d>)\n",array[i],upc_threadof(&array[i]),i);
			
			i += THREADS;
			if (i >= N*THREADS) {
				i = i%(N*THREADS)+1;
			}

			++j;
		}
		printf("------------------------------\n");
	}
	fflush(stdout);
#endif
*/
	/* sort elements */
	i = MYTHREAD; // start of this threads section
	j = N*MYTHREAD; mc = 0;	
	firsttime = 1; done = 0;
	upc_lock(locks[curlock]);

/*	
#ifdef OUTPUT
	if (MYTHREAD == 0) printf("Starting sort\n");
#endif
*/
	/* synchronize before sorting */
	upc_barrier;
/*
#ifdef TIMED
	if (MYTHREAD == 0) starttime = time(NULL);
#endif
*/
	do {
		/* if back where I started, see if I should terminate */
		if (j == N*MYTHREAD) {
			if (firsttime) firsttime = 0;
			else {
				if (mc == 0) {
					done = 1;
					upc_unlock(locks[curlock]);
				}
				mc = 0;
			}
		}

		/* if at the end of a section... */
		if (!done) {
			if (j%sectionSize == sectionSize-1) {
				oldlock = curlock;
				curlock = (curlock+1)%(THREADS*2);

				/* obtain lock of next section */
				upc_lock(locks[curlock]);
			}

			/* check to see if last element in current section *
			 * is greater then the first element of the next   *
			 * section, if so, swap.						   */
			l = i + THREADS;
			if (l >= N*THREADS) 
				l = l%(N*THREADS)+1;
		//	if (array[i] > array[l]) {
				//printf("T%d: swapping %d [%d] & %d [%d]\n",MYTHREAD,array[i],i,array[l],l);
				temp = array[i];
				array[i] = array[l];
				array[l] = temp;
				mc = 1;
		//	}

			if (j%sectionSize == sectionSize-1) {
				/* release lock of current section */
				upc_unlock(locks[oldlock]);
			}

			/* increment counter, wrap to beginning of array *
			 * when at the last element.					 */
			i += THREADS;
			if (i >= N*THREADS)
				i = i%(N*THREADS)+1;
			if (i == N*THREADS-1) i = 0;
			j = (j+1)%(N*THREADS);
			if (j == N*THREADS-1) j = 0;
		}
	} while (!done);

	/* synchronize before Thread 0 prints sorted array */
	upc_barrier;
	
/*	
#ifdef TIMED
	if (MYTHREAD == 0) endtime = time(NULL);
#endif
	
#ifdef OUTPUT
	if (MYTHREAD == 0) printf("Done sorting\n");
#endif
*/

	/* Thread 0 prints out the sorted array */

	/*
#ifdef OUTPUT
	if (MYTHREAD == 0) {
		printf("------------------------------\nSorted array:\n");
		j = 0; i = 0;
		while (j < N*THREADS){
			printf("\t%d (Thread<%d> i<%d>)\n",array[i],upc_threadof(&array[i]),i);

			i += THREADS;
			if (i >= N*THREADS) {
				i = i%(N*THREADS)+1;
			}
			++j;
		}
		/* free memory used by shared array */
//		upc_free(array);
//	}
//	fflush(stdout);
//#endif

/*
#ifdef TIMED
	if (MYTHREAD == 0) {
		printf("------------------------------\n");
		printf("Start time: %d secs\nEnd time:   %d secs\nTotal time:  %d secs\n",
				starttime, endtime, (endtime-starttime));
		printf("------------------------------\n");
	}
#endif
*/
	return 0;
}