/* psort
 *
 * (C) 2003 Tiago Macambira
 *
 *
 * Customizations should be done @ common.h
 *
 * */

/* Definições comuns do programa*/
#include "common.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/* Medição de tempo */
#include <sys/time.h>
#include <sys/resource.h>




/* Sobra de codigo... deixe essas duas linhas... pq não?! Mal não fazem... */
#define V_VALUE 1000000
#define K_VALUE 10

/* verify
 *
 * Verifica se um dado vertor está ordenado
 *
 * int A[]      - Velor com os elementos supostamente ordenados
 * int n        - numero de elementos do vetor, contando com sentinela
 * int k        - numero de elementos de A[] que se deseja na ordenação parcial, *                contando com a sentinela.
 * 
 * retorno	- retorna 0 em caso de succeso e -1 em caso de erro
 */
int verify(int A[], int n, int k )
{
	int i, kth;

	for (i = 1; i < k; i++){
		if (A[i] < A[i -1]){
			return -1;
		}
	}
	kth=A[k-1];

	for (i = k; i < n; i++){
		if (kth > A[i]){
			return -1;
		}
	}

	return 0;
}

/* get_user_time
 *
 * return 	- Retorna o tempo que o processo consumiu executando operações
 * 		  em modo do usuário
 */
long get_user_time()
{
	struct rusage r;
	struct timeval v;

	getrusage(RUSAGE_SELF, &r);
	v = r.ru_utime;
	return v.tv_sec * 1000000 + v.tv_usec;
}



void evaluate_sort(int A[],int A_cpy[], int n, int k, const char* nome, void (*sort_f)())
{
	memcpy(A_cpy,A,n*sizeof(int));

#ifdef DO_COUNTING
	COUNT_RESET;
#endif
	
#ifdef CALC_USER_TIME
	long time_start, time_end;
	time_start=get_user_time();
#endif	
	(*sort_f)(A_cpy,n,k);
#ifdef CALC_USER_TIME
	time_end=get_user_time();
	printf("%-22s\tn=%07i\tk=%i\ttempo=%'li us.\n",nome,n,k,time_end - time_start);
#endif

#ifdef DO_COUNTING
	printf("%-22s\tn=%07i\tk=%i\tcomp=%09li\tswaps=%09li\n",nome,n,k,count_comp,count_swap);
#endif

	
}



void evaluate_all(int A[], int n, int k)
{
	int *tmp_A = NULL;

	tmp_A=(int*)malloc(n*sizeof(int));
	
	evaluate_sort(A,tmp_A,n,k,"partial_insertion_sort",partial_insertion_sort);
	evaluate_sort(A,tmp_A,n,k,"partial_selection_sort",partial_selection_sort);
	evaluate_sort(A,tmp_A,n,k,"partial_heap_sort",partial_heap_sort);
	evaluate_sort(A,tmp_A,n,k,"partial_quick_sort",partial_quick_sort);

	free(tmp_A);
}




void do_one_round(int A[],int n, int k)
{
	int i;
	/* Inicia vetor de permutação*/
	for (i = 0; i < n; i++)
		A[i] = i;
	Permut(A,n);

	evaluate_all(A, n, k);

	
}


int main()
{
	int *v=NULL;
	int n, k, r;
	int lista_k[6];

	for (n=10; n <2000000 ;n*=10){
		if(( v = (int*)malloc(n*sizeof(int)) )) {
			/* Sequência de incrementos: 1 elemento, 10 elementos, logn, sqr(n), 1/8n, 20%n */
			/* Ah! Que saudades de python... */
			lista_k[0] = 1;
			lista_k[1] = 10;
			lista_k[2] = log10(n);
			lista_k[3] = sqrt(n);
			lista_k[4] = n>>3;
			lista_k[5] = 2*(n/10);

			for (k = 0; k < 6; k++){
				if (k < n) {
					for (r = 0; r < 40; r++){
						do_one_round(v,n,lista_k[k]);
					}
				}
			}

			free(v);
		} else {
			printf("Não pude alocar memoria suficiente. %s, line %i\n",__FILE__,__LINE__);
		}
	};
	
	
	return 0;
}

int old_main()
{
	unsigned int x;
	int v[V_VALUE];



	for (x = 0; x < V_VALUE; x++)
		v[x] = x;
	
	Permut(v, V_VALUE);
	/*print_array(v,V_VALUE,"RAND");*/
	
#ifdef CALC_USER_TIME
	long time_start, time_end;
	time_start=get_user_time();
#endif
	partial_quick_sort(v, V_VALUE, K_VALUE);
#ifdef CALC_USER_TIME
	time_end=get_user_time();
	printf("Tempo de execução: %'li us.\n",time_end - time_start);
#endif
	print_array(v,K_VALUE,"SORT");

	
	if (verify(v,V_VALUE,K_VALUE)){
		printf("O vetor não está parcialmente ordenado\n");
	} else {
		printf("OK!\n");
	}
	
	return 0;
}