/*
 bitonic.c 

 This file contains two different implementations of the bitonic sort
        recursive  version :  recBitonicSort()
        imperative version :  impBitonicSort() 
 

 The bitonic sort is also known as Batcher Sort. 
 For a reference of the algorithm, see the article titled 
 Sorting networks and their applications by K. E. Batcher in 1968 


 The following codes take references to the codes avaiable at 

 http://www.cag.lcs.mit.edu/streamit/results/bitonic/code/c/bitonic.c

 http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm

 http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm 
 */

/* 
------- ---------------------- 
   Nikos Pitsianis, Duke CS 
-----------------------------
*/

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

typedef enum { false, true } bool;
struct timeval startwtime, endwtime;
double seq_time;

int threads; //number of threads
int N; // data array size
int *a; // data array to be sorted
unsigned randSeed; //seed array initialisation

const int ASCENDING  = 1;
const int DESCENDING = 0;

void getArgs(int argc, char** argv);
void init(void);
void print(void);
int qSortAscending (const void * a, const void * b);
int qSortDescending (const void * a, const void * b);

/** the main program **/ 
int main(int argc, char **argv) {
	getArgs(argc, argv);
	a = (int *) malloc(N * sizeof(int));
	randSeed = (unsigned) time(NULL);

	//Sorts using the qSort algorithm
	init();

	gettimeofday (&startwtime, NULL);
	qsort(a, N, sizeof(int), qSortAscending);
	gettimeofday (&endwtime, NULL);

	seq_time = (double)((endwtime.tv_usec - startwtime.tv_usec)/1.0e6
		+ endwtime.tv_sec - startwtime.tv_sec);

	printf("%f\n", seq_time);

	free(a);
}

/** -------------- SUB-PROCEDURES  ----------------- **/ 

void getArgs(int argc, char** argv){
	if (argc != 2) {
		printf("Usage: %s p q\nwhere:\n\tP=2^p is the the number of threads(power of two)\n\tN=2^q is problem size (power of two)\n", 
			argv[0]);
		exit(1);
	}
	N = 1<<atoi(argv[1]);
}

/** procedure init() : initialize array "a" with data **/
void init() {
	srand(randSeed);
	int i;
	for (i = 0; i < N; i++) {
		a[i] = rand() % N; // (N - i);
	}
}

/** procedure  print() : print array elements **/
void print() {
	int i;
	for (i = 0; i < N; i++) {
		printf("%d\n", a[i]);
	}
	printf("\n");
}

/** function used by qsort for comparing **/
int qSortAscending (const void * a, const void * b) {
	return ( *(int*)a - *(int*)b );
}

/** function used by qsort for comparing **/
int qSortDescending (const void * a, const void * b) {
	return ( *(int*)b - *(int*)a );
}