#include <X11/Xlib.h> /* Every Xlib program must include this */
#include <assert.h>   /* I include this to test return values the lazy way */
#include <unistd.h>   /* So we got the profile for 10 seconds */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define NIL (0)       /* A name for the void pointer */
#define W_WIDTH		(200)
#define W_HEIGHT	(200)
#define SLEEP		usleep
#define WAIT 		(0)
#define SWPWAIT		(1000L)
#define CMPWAIT		(0L)
#define MAX_NOMBRE	(300)
#define OPT_LEN		(3)
#define COUNT 		(0)

typedef unsigned short ush;
ush p[W_WIDTH];
Display *dpy;
Window w;
GC gc;

typedef enum { uniforme, gauss, ordenado, orden_inverso, cuasiordenado, diezvalores } ord_enum;

void initX(void);
void redraw(void);
void swap(ush *v, ush i, ush j);
void data_init(ord_enum);
void print_uso(char *);
double normal(double x0, double devstd);

void selection_sort(void);
void insertion_sort(void);
void bubble_sort(void);
void quick_sort(void);
void shaker_sort(void);
void shell_sort(void);
void merge_sort(void);

typedef struct {
	char nombre[MAX_NOMBRE];
	char opcion[OPT_LEN];
	void (*f)(void);
} algoritmo;

typedef struct {
	char nombre[MAX_NOMBRE];
	char opcion[OPT_LEN];
	ord_enum o;
} ord_item;

algoritmo alg[] = { 
	{"Selection Sort",	"sel",	selection_sort},
	{"Insertion Sort",	"ins",	insertion_sort},
	{"Bubble Sort",		"bub",	bubble_sort},
	{"QuickSort",		"qck",	quick_sort},
	{"Shaker Sort",		"shk",	shaker_sort},
	{"ShellSort",		"shl",	shell_sort},
	{"MergeSort",		"mrg",	merge_sort}
};

ord_item ord[] = {
	{"Random uniforme",				"uni", uniforme },
	{"Random gaussiana",			"gau", gauss },
	{"Ordenado",					"ord", ordenado },
	{"Orden Inverso",				"inv", orden_inverso },
	{"Casi Ordenado",				"cso", cuasiordenado },
	{"Solo 10 valores diferentes",	"10v", diezvalores }
};

#define CANT_ALG	(sizeof(alg)/sizeof(algoritmo))
#define CANT_ORD	(sizeof(ord)/sizeof(ord_item))

int main(int argc, char**argv)
{
	ush i;
	void (*sort)(void);
	ord_enum o;
	if(argc<3) {
		print_uso(argv[0]);
		exit(-1);
	}
	for(i=0;i<CANT_ALG;i++)
		if(!strncmp(argv[1],alg[i].opcion,OPT_LEN))
				break;
	if(i==CANT_ALG) {
		fprintf(stderr,"No conozco ese algoritmo\n\n");
		print_uso(argv[0]);
		exit(-1);
	}
	sort=alg[i].f;
	
	for(i=0;i<CANT_ORD;i++)
		if(!strncmp(argv[2],ord[i].opcion,OPT_LEN))
				break;
	if(i==CANT_ORD) {
		fprintf(stderr,"No conozco ese ordenamiento\n\n");
		print_uso(argv[0]);
		exit(-1);
	}
	o=ord[i].o;
	
	initX();
	
	/* XSynchronize(dpy,True); */
    /* Wait for the MapNotify event */
    for(;;) {
		XEvent e;
		XNextEvent(dpy, &e);
		if (e.type == MapNotify)
			break;
    }

	data_init(o);
	sort();
	redraw();
	
    /* Wait for 1 second */
    sleep(1);
	XCloseDisplay(dpy);
	printf("\n");
	return 0;
}

void initX(void)
{
	int blackColor, whiteColor;
	/* Open the display */
    dpy = XOpenDisplay(NIL);
    assert(dpy);
    /* Get some colors */
	blackColor = BlackPixel(dpy, DefaultScreen(dpy));
	whiteColor = WhitePixel(dpy, DefaultScreen(dpy));
    /* Create the window */
    w = XCreateSimpleWindow(dpy, DefaultRootWindow(dpy), 0, 0, 
		     W_WIDTH, W_HEIGHT, 0, blackColor, blackColor);

    /* We want to get MapNotify events */
    XSelectInput(dpy, w, StructureNotifyMask);

    /* "Map" the window (that is, make it appear on the screen) */
    XMapWindow(dpy, w);

    /* Create a "Graphics Context" */
    gc = XCreateGC(dpy, w, 0, NIL);

    /* Tell the GC we draw using the white color */
    XSetForeground(dpy, gc, whiteColor);
}

void selection_sort(void)
{
	ush i,j,min;
	for(i=0;i<W_WIDTH; i++) {
		min=i;
		for(j=i+1;j<W_WIDTH;j++){
			if(p[j] < p[min]) min=j;
			SLEEP(CMPWAIT);
		}
		swap(p,i,min);
		SLEEP(SWPWAIT);
		redraw();
	}
}

void insertion_sort(void)
{
	ush i,j,t;
	for(i=1;i<W_WIDTH;i++){
		t=p[i];
		for(j=i;j>0 && (p[j-1] > t); j--){
			p[j]=p[j-1];
			SLEEP(SWPWAIT);
			SLEEP(CMPWAIT);
			redraw();
		}
		p[j]=t;
	}
}

void swap(ush *v, ush i, ush j)
{
	ush temp;
	
	temp =v[i];
	v[i]=v[j];
	v[j]=temp;
}


void quicksort(ush *v,ush n)
{
	unsigned last,i;
	if (n<=1) return;
	swap(v,0,rand()%n);
	last=0;
	for(i=1;i<n;i++)
		if(v[i] < v[0]) {
			swap(v,++last,i);
			SLEEP(CMPWAIT);
			SLEEP(SWPWAIT);
			redraw();
		}
	swap(v,0,last);
	SLEEP(SWPWAIT);
	redraw();
	quicksort(v,last);
	quicksort(v+last+1, n-last-1);
}

void quick_sort(void){
	quicksort(p,W_WIDTH);
}

void bubble_sort(void)
{
	ush j,t=W_WIDTH-1,bound;
	while(t) {
		bound=t;
		t=0;
		for(j=0;j<bound;j++) {
			if(p[j]>p[j+1]) { 
					swap(p,j,j+1);
					SLEEP(CMPWAIT);
					SLEEP(SWPWAIT);
					t=j;
					redraw();
			}
		}
		/* redraw(); */
	}
}

void shaker_sort(void)
{
	ush j,t=W_WIDTH-1,ubound,lbound=0;
	while(t) {
		ubound=t;
		t=0;
		for(j=ubound;j>lbound;j--) {
			if(p[j-1]>p[j]) { 
					swap(p,j,j-1);
					SLEEP(CMPWAIT);
					SLEEP(SWPWAIT);
					t=j;
					redraw();
			}
		}
		lbound=t;
		for(j=lbound;j<ubound;j++) {
			if(p[j]>p[j+1]) { 
					swap(p,j,j+1);
					SLEEP(CMPWAIT);
					SLEEP(SWPWAIT);
					t=j;
					redraw();
			}
		}	
	}
}

void shell_sort(void)
{
	ush h,i;
	for(h=1;h<=W_WIDTH/9; h=3*h+1)
					;
	for(;h>0; h/=3)
		for(i=h; i<W_WIDTH; i++) {
			ush j=i,v=p[i];
			while(j>=h && v<p[j-h]) {
				p[j] = p[j-h]; 
				j -= h;
				SLEEP(CMPWAIT);
				SLEEP(SWPWAIT);
				redraw();
			}
			p[j]=v;
		}
	
}

void merge(ush *a, ush l,ush m, ush r)
{
	int i,j,k;
	static ush aux[W_WIDTH];
	for(i=m+1; i > l; i--) aux[i-1]=a[i-1];
	for(j=m; j<r; j++) aux[r+m-j] = a[j+1];
	for(k=l; k<=r; k++){
		if(aux[j]<aux[i])
		     a[k]=aux[j--]; 
		else a[k]=aux[i++];
		SLEEP(CMPWAIT);
		SLEEP(SWPWAIT);
		redraw();
	}
}


void mergesort(ush *a, ush l, ush r)
{
	ush m;
	if(r<=l) return;
	m=(r+l)/2;
	mergesort(a,l,m);
	mergesort(a, m+1, r);
	merge(a,l,m,r);
}


void merge_sort(void)
{
	mergesort(p,0,W_WIDTH-1);
}



void redraw(void)
{
	int i;
	static int c=0;
	if(c++>COUNT) {
		XClearWindow(dpy,w);

		/* Draw the points */
		for(i=0;i<W_WIDTH;i++)
   			XDrawPoint(dpy, w, gc, i,p[i]);  
	
	    /* Send the "Draw____" request to the server */
   		XFlush(dpy);
	//	SLEEP(WAIT);
		c=0;
	}
}

void data_init(ord_enum o)
{
	int i;
	/* Inicializar la matriz */
	for(i=0;i<W_WIDTH;i++) 
		p[i]=i;
	
	srand(23);
	
	switch(o) {
		case uniforme:
			for(i=0;i<W_WIDTH*2;i++){
				ush u=rand()%W_WIDTH,v=rand()%W_WIDTH;
				swap(p,u,v);
			}
			break;
		case gauss: 
			for(i=0;i<W_WIDTH;i++){
				p[i]=(ush)normal(W_WIDTH/2,W_WIDTH/8)%W_WIDTH;
			}
			break;
		case ordenado:
			break;
		case orden_inverso:
			for(i=0;i<W_WIDTH;i++) 
				p[i]=W_WIDTH-i-1;
			break;
		case cuasiordenado:
			for(i=0;i<W_WIDTH;i++){
				ush u=(rand()%(W_WIDTH/10-W_WIDTH/20)+i)%W_WIDTH;
				ush v=(rand()%(W_WIDTH/10-W_WIDTH/20)+i)%W_WIDTH;
				swap(p,u,v);
			}
			break;
		case diezvalores:
			for(i=0;i<W_WIDTH;i++){
				ush u=(rand()%10)*W_WIDTH/10;
				p[i]=u;
			}
			break;
			
	}
}

void print_uso(char *nomprog)
{
	ush i;
	fprintf(stderr,"Uso: %s alg ord\nalg es alguno de:\n",nomprog);
	for(i=0;i<CANT_ALG;i++)
		fprintf(stderr,"\t%s :\t%s\n",alg[i].opcion,alg[i].nombre);
	printf("ord es alguno de:\n");
	for(i=0;i<CANT_ORD;i++)
		fprintf(stderr,"\t%s :\t%s\n",ord[i].opcion,ord[i].nombre);
	
}

/* devuelve un double al azar con una
 *  * distribucion normal centrada en x0
 *   * y desvio standard devstd */
double normal(double x0, double devstd)
{
	int f=1;
	double u,v,x;
	while(f){
		while(!(u=random()/(double)RAND_MAX));
		v=random()/(double)RAND_MAX;
		x=sqrt(8/M_E)*(v-0.5)/u;
		if(x*x <= (-4)*log(u)) f=0;;
	}
	return x0+devstd*x;
}