#include "common.h"
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

#define BEEN_HERE printf("DEBUG, __LINE__=%i\n",__LINE__)


/**
 *
 * Interface  
 *
 *
 * */
inline int partition(int A[], int lower, int upper);



/**
 *
 * Implementação 
 *
 *
 * */


int deterministic_selection_partition(int A[], int lower, int upper, int pivot)
{
	int i,j;
	
	i=lower;
	j=upper;
	
	while (i<j) {
	    while (A[i] < pivot){ i++;};
	    while (A[j] > pivot){ j--;};
	    if (j < i) {
		    break;
	    } else {
		    swap(&A[i], &A[j]);
	    }
	}

	return j;
}



int deterministic_selection_median( int A[], int n, int k)
{
	int i =0;
	int pos;
	int res = -1; /* for debugin purposes*/
	int *tmp_A = NULL;
	int left_over= n%5;	
	int partitions = left_over==0?(n/5):(n/5)+1;

	if (n < 2) {
		return A[0];
	}
	
	tmp_A = (int*)malloc(partitions*sizeof(int));
	for(i = 0; (i < n/5) && (n >= 5) ; i++) {
		pos=5*i;
		insertion_sort(&A[pos],5);
		tmp_A[i]=A[pos+2];
	}

	if (left_over > 0){
		pos=5*i;
		/*pos=n-left_over;*/ /* i foi incrementado no for...*/
		insertion_sort(&A[pos],left_over);
		tmp_A[i]=A[pos+(left_over/2)];
	}
	/*print_array(A,n,"ORIG");
	if (partitions < 100) print_array(tmp_A,partitions,"PART");*/
	
	res = deterministic_selection_median(tmp_A,partitions,k);
	
	free(tmp_A);
	tmp_A=NULL;

	return res;
}

/* NOTE
 *
 * In this function we name are variables differently then Cormen:
 * int i	- this is the number of elements on the lower side of the
 * 		  partition ( Cormen would name it k....)
 * int k	- This is the position we are seeking: the kth element...
 * 		  Remember in C, array[0...n-1] unless array=(real_array -1)
 * 		  (got it?!)
 * int n	- The number of elements in the array
 *
 * retult	- The value of the kth element.... */
int deterministic_selection( int A[], int n, int k)
{
	int median, i;
	
	printf("DEBUG det_sel: n=%i, k=%i, median=?', i=?\n",n,k);
	/* Cormen, 1st ed, pg 190*/
	/* Steps 1 and 2 & 3 */
	median = deterministic_selection_median(A, n, k);
	i = deterministic_selection_partition(A,0,n-1,median); /*C=>upper=n-1*/
	printf("DEBUG det_sel: n=%i, k=%i, median='%i', i=%i\n",n,k,median,i);
	
	if (k == i + 1){
		return A[i];
	} else if (k < i) {
		return deterministic_selection(A,i+1,k);
	} else {
		return deterministic_selection(&A[i+1],n-(i+1),k - (i+1));
	}

}




void quicksort(int A[], int lower, int upper)
{
	int m;

	if (lower < upper) {
		m = partition(A, lower,upper);
		quicksort (A, lower, m);
		quicksort (A, m + 1, upper);
	}
}

int partition(int A[], int lower, int upper)
{
	int i,j,pivot;
	
	pivot = A[(lower+upper)/2];
	i=lower;
	j=upper;
	
	while (i<j) {
	    while (A[i] < pivot){ i++;};
	    while (A[j] > pivot){ j--;};
	    if (j < i) {
		    break;
	    } else {
		    swap(&A[i], &A[j]);
	    }
	}

	return j;
}





/*int partition_1(int A[], int lower, int upper)
{
	int m,pivot;
	
	swap(&A[lower], &A[(upper+lower)/2]);
	pivot = A[lower];
	m = lower;
	for (i = lower + 1; i <= upper; i++)
		if (A[i] < pivot) {
			m++;
			swap(&A[m], &A[i]);
	}
	swap(&A[lower], &A[m]);
}*/



void partial_quick_sort( int A[], int n, int k)
{
	/* quicksort(A,1,n-1);*/
	int i =	0;
	//i = deterministic_selection(A,n,k);
	i = deterministic_selection_median(A,585938,10);

	printf(">> %'i <<\n",i);
}