/*                                                           Pontificia Universidade Catolica
 *  Campinas - Sao Paulo - Brasil
 *  mai/2004
 *
 * 	Segundo Trabalho Estrutura de Dados 2
 *
 *	Tempo de ordenacao usando mais variados algoritmos existentes.
 * 
 *	Desenvolvedores:  	Cesar Kallas		:RA 02099224	cesarkallas@gmx.net
 *					Renan Mathias	:RA 02513386	renanmathias@terra.com.br
 *
 * Ultima atualizacao: 26/05/2004
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <string.h>
#define VALOR 123456
#define MICRO_PER_SECOND 1000000
#define maxOfVetor 1000000

typedef struct tempos
{
	float bolha;
	float quickSort;
	float heapSort;
	float insertionSort;
	float mergeSort;
	float selectionSort;
	float total;
	float gerarDados;
	float lerArquivo;
} t_metodos;

void bolha(int *vetor, int tamanho_vetor)
{
	int i,j;
	int teste=1;
	int aux;
	
	for(i=0; i<(tamanho_vetor-1) && teste==1; i++)
	{
		teste=0;
		for(j=0; j<(tamanho_vetor-i-1); j++)
			if(vetor[j] > vetor[j+1])
			{
				teste=1;
				aux = vetor[j];
				vetor[j] = vetor[j+1];
				vetor[j+1] = aux;
			}
	}
}

void quickSort(int *vetor, int aux, int ini, int fim)
{
	int flag=1, i, j;
   
	if(ini<fim)
	{
		i=ini;
		j=fim;
		while(i<j)
		{
			if(vetor[i] > vetor[j])
			{
				aux = vetor[i];
				vetor[i] = vetor[j];
				vetor[j] = aux;
				flag=flag*(-1);
			}
			if(flag==1) j--;
				else
				i++;
		}
		quickSort(vetor, aux, ini, j-1);
		quickSort(vetor, aux, j+1, fim);
	}	
}

void selectionSort(int *vetor, int tamanho_vetor)
{
	int menor;
	int aux;
	int i, j;
  
	for (i=0; i<tamanho_vetor; i++)
	{
		menor=i;
		for (j=i; j<tamanho_vetor; j++)
		{
			if (vetor[j] < vetor[menor])
				menor = j;
			
			aux = vetor[i];
			vetor[i] = vetor[menor];
			vetor[menor] = aux;
		}
	}
}

void insertionSort(int *vetor, int tamanho_vetor)
{
	int i, k;
	int aux;
  
	for(k=1; k<tamanho_vetor; k++)
	{
		aux = vetor[k];
		for (i=k-1; i>=0 && aux < vetor[i]; i--)
			vetor[i+1] = vetor[i];
		vetor[i+1] = aux;
	}
}

void addHeap(int *vetor, int l, int r)
{ 
	int i,j;
	int aux;
  
	i=l;
	j = 2*i+1;
	aux = vetor[i];
	
	while (j<=r)
	{
		if(j<=r-1)
			if(vetor[j] < vetor[j+1])
			j++;
			
		if(aux < vetor[j])
		{
			vetor[i] = vetor[j];
			i=j;
			j=2*i+1;
		}
		else
			j = r+1;
	}
	vetor[i] = aux;
}

void heapSort(int *vetor, int tamanho_vetor)
{  
	int r,l;
	int aux;
	r=tamanho_vetor-1;
	
	for (l=tamanho_vetor/2-1; l>=0; l--)
		addHeap(vetor, l, r);
		l=0;
	
	for (r=tamanho_vetor-2; r>= 0; r--)
	{
		aux = vetor[0];
		vetor[0] = vetor[r+1];
		vetor[r+1] = aux;
		addHeap(vetor, l, r);
	}
}

void merge(int *vetor, int left, int right)
{
	int mid=(left+right)/2, size = (right-left+1);
	int aux[size];
	int x, y, put;
  
	int count=0;
	for(x=left;x<=mid;x++,count++)
	{
		aux[count]=vetor[x];
	}
	for(x=right;x>=mid+1;x--,count++)
	{
		aux[count]=vetor[x];
	}
	for(x=0,y=size-1,put=left;x<=y;put++)
	{
		if(aux[x] <= aux[y])
		{
			vetor[put]=aux[x];
			x++;
		}
		else
		{
			vetor[put]=aux[y];
			y--;
		}
	}

}

void mergeSort(int *vetor, int ini, int fim)
{
	int medio;
	if (ini < fim)
	{
		medio = (ini + fim)/2;
		mergeSort (vetor, ini, medio);
		mergeSort (vetor, medio+1, fim);
		merge (vetor, ini, fim);
	}
}


void gerarDados(int *vetor, int *tamanho_vetor, t_metodos *tempo)
{
  
	int i;
	
	/* Quando gerado uma nova base de dados para ordenacao,
	 * os tempos antigos sao apagados
	 */	
	tempo->bolha=0.0;
	tempo->quickSort=0.0;
	tempo->heapSort=0.0;
	tempo->insertionSort=0.0;
	tempo->mergeSort=0.0;
	tempo->selectionSort=0.0;
	tempo->total=0.0;
	tempo->gerarDados=0.0;
	tempo->lerArquivo=0.0;
		
	if(*tamanho_vetor < 1)
		*tamanho_vetor = 1;
	
	srand(time(NULL));
		
	for(i=0; i < (*tamanho_vetor); i++)
	{
		vetor[i] = rand() % 123456;
	}
   
}

void ordene(int metodo, int *vetorCopia, int tamanho_vetor)
{
	/* variavel auxiliadora utilizada por alguns metodos */
	int aux;
	
	switch(metodo)
	{
		case 1:	bolha(vetorCopia, tamanho_vetor); break;
		case 2: quickSort(vetorCopia, aux, 0, tamanho_vetor-1); break;
		case 3: selectionSort(vetorCopia, tamanho_vetor); break;
		case 4: insertionSort(vetorCopia, tamanho_vetor); break;
		case 5: heapSort(vetorCopia, tamanho_vetor); break;
		case 6: mergeSort(vetorCopia, 0, tamanho_vetor-1); break;
		default: break;
	}
}

void copiarVetor(int *vetor_original, int *vetor_copia, int tamanho_vetor)
{
	/* essa funcao existe porque, se ao passar o vetor de dados para alguma funcao de ordenacao
	 * a mesma ira ordenar a base de dados, sendo assim o proximo metodo que queira usar a mesma
	 * base de dados, tera a base de dados ja ordenada. Para isso sempre eh criado uma copia da base de dados
	 * e utilizada a copia. vetor -> ponteiro.
	 */
	int i;
	
	for(i=0; i<tamanho_vetor; i++)
		vetor_copia[i] = vetor_original[i];
}

float diftempo(struct timeval t_inicio, struct timeval t_fim)
{
	/* calcula a diferenca entre o tempo inicial e o final, requisitados por gettimeofday 
	 * A diferenca eh a soma do tempo em segundo (final-inicial) mais a soma do tempo
	 * em micro-segundos divididos por MICRO_PER_SECOND. Note o seguinte, nada mais
	 * eh que a soma do tempo em segundo com o restante do tempo em micro-segundos convertidos
	 * para segundos, pois gettimeofday eh uma estrutura que retorna o tempo em segundos e o restante dele
	 * em micro-segundos.
	 */
	float t_diferenca;
	t_diferenca  = ( t_fim.tv_sec  - t_inicio.tv_sec );
	t_diferenca += ( t_fim.tv_usec - t_inicio.tv_usec )/(float)MICRO_PER_SECOND;

	return t_diferenca;
}

int gravarResultados(t_metodos tempo, char *nomeArquivo, int tamanho_vetor)
{
	FILE *arquivo;
	
	arquivo = fopen(nomeArquivo, "wt");
	
	if(arquivo==NULL)
		return 0;
	
	fprintf(arquivo, "tamanhoVetor   %10d\n", tamanho_vetor);
	fprintf(arquivo, "bolha          %.10f\n", tempo.bolha);
	fprintf(arquivo, "quickSort      %.10f\n", tempo.quickSort);
	fprintf(arquivo, "heapSort       %.10f\n", tempo.heapSort);
	fprintf(arquivo, "insertionSort  %.10f\n", tempo.insertionSort);
	fprintf(arquivo, "mergeSort      %.10f\n", tempo.mergeSort);
	fprintf(arquivo, "selectionSort  %.10f\n", tempo.selectionSort);
	fprintf(arquivo, "todos_metodos  %.10f\n", tempo.total);
	//fprintf(arquivo, "gerarDados     %.10f\n", tempo.gerarDados);
	fprintf(arquivo, "lerArquivo     %.10f\n", tempo.lerArquivo);
		
	fclose(arquivo);
	return 1;
}

void exibirVetor(int *vetor, int tamanho_vetor)
{
	int i;
	
	for(i=0; i< tamanho_vetor; i++)
		printf("\nvetor[%d] -> %d", i+1, vetor[i]);
}
	
int main(int argc, char *argv)
{
  
	char opcao[1];
	int vetor[maxOfVetor], vetorCopia[maxOfVetor];
	int tamanho_vetor=0;

	/* Estruturas abaixo sao usadas para o calculo do tempo */
	struct timeval t_inicio;
	struct timeval t_fim;
	
	t_metodos tempo;
    
	while(1)
	{
		printf("\n\n\n\n\n");
		printf("============================================================ \n");
		printf("Trabalho 2 - Estrutura de Dados 2             Tempo Gasto    \n");
		printf("------------------------------------------------------------ \n");
		printf("1. Gerar dados em memoria                     %.10f s\n", tempo.gerarDados);
		//printf("2. Ler dados de um arquivo                    %.10f s\n", tempo.lerArquivo);
		printf("2. Exibir vetor gerado                               \n");
		printf("------------------------------------------------------------ \n");
		printf("a. Ordenar dados metodo bolha                 %.10f s\n", tempo.bolha);
		printf("b. Ordenar dados metodo quicksort             %.10f s\n", tempo.quickSort);
		printf("c. Ordenar dados metodo selection sort        %.10f s\n", tempo.selectionSort);
		printf("d. Ordenar dados metodo insertion sort        %.10f s\n", tempo.insertionSort);
		printf("e. Ordenar dados metodo heap sort             %.10f s\n", tempo.heapSort);
		printf("f. Ordenar dados metodo merge sort            %.10f s\n", tempo.mergeSort);
		printf("g. Ordenar automaticamente metodo a metodo    %.10f s\n", tempo.total);
		printf("h. Gravar todos resultados obtidos em arquivo\n");
		printf("--------------------------------------------tam vetor %.6d \n", tamanho_vetor);
		printf("q. Sair \n\n");
		printf(": ");
		scanf("%1s", &opcao);
  
		if(!strcmp(opcao, "q"))
			break;
		
		if(!strcmp(opcao, "1"))
		{
			printf("Tamanho do vetor [max %d] ? ", maxOfVetor-1);
			scanf("%6d", &tamanho_vetor);
			
			gettimeofday(&t_inicio, NULL);
				gerarDados(vetor, &tamanho_vetor, &tempo);
			gettimeofday(&t_fim, NULL);
			
			tempo.gerarDados = diftempo(t_inicio, t_fim);
		}
		
		if(tamanho_vetor > 0)
		{
			if(!strcmp(opcao, "2"))
				exibirVetor(vetor, tamanho_vetor);
			
			if(!strcmp(opcao, "a"))
			{
				copiarVetor(vetor, vetorCopia, tamanho_vetor);
			 
				gettimeofday(&t_inicio, NULL);
					ordene(1, vetorCopia, tamanho_vetor);
				gettimeofday(&t_fim, NULL);
			
				tempo.bolha = diftempo(t_inicio, t_fim);
			}
			
			if(!strcmp(opcao, "b"))
			{
				copiarVetor(vetor, vetorCopia, tamanho_vetor);
			 
				gettimeofday(&t_inicio, NULL);
					ordene(2, vetorCopia, tamanho_vetor);
				gettimeofday(&t_fim, NULL);
			  
				tempo.quickSort = diftempo(t_inicio, t_fim);
			}
			
			if(!strcmp(opcao, "c"))
			{
				copiarVetor(vetor, vetorCopia, tamanho_vetor);
			  
				gettimeofday(&t_inicio, NULL);
					ordene(3, vetorCopia, tamanho_vetor);
				gettimeofday(&t_fim, NULL);
			
				tempo.selectionSort = diftempo(t_inicio, t_fim);
			}
			
			if(!strcmp(opcao, "d"))
			{
				copiarVetor(vetor, vetorCopia, tamanho_vetor);
			  
				gettimeofday(&t_inicio, NULL);
					ordene(4, vetorCopia, tamanho_vetor);
				gettimeofday(&t_fim, NULL);
			
				tempo.insertionSort = diftempo(t_inicio, t_fim);
			}
			
			if(!strcmp(opcao, "e"))
			{
				copiarVetor(vetor, vetorCopia, tamanho_vetor);
			  
				gettimeofday(&t_inicio, NULL);
					ordene(5, vetorCopia, tamanho_vetor);
				gettimeofday(&t_fim, NULL);
			
				tempo.heapSort = diftempo(t_inicio, t_fim);  
			}
			
			if(!strcmp(opcao, "f"))
			{
				copiarVetor(vetor, vetorCopia, tamanho_vetor);
			  
				gettimeofday(&t_inicio, NULL);
					ordene(6, vetorCopia, tamanho_vetor); 
				gettimeofday(&t_fim, NULL);
			
				tempo.mergeSort = diftempo(t_inicio, t_fim);  
			}
			
			if(!strcmp(opcao, "g"))
			{
				int i;
				
				gettimeofday(&t_inicio, NULL);
				for(i=1; i<7; i++)
				{
					copiarVetor(vetor, vetorCopia, tamanho_vetor);
					ordene(i, vetorCopia, tamanho_vetor);
				}
				gettimeofday(&t_fim, NULL);
			
				tempo.total = diftempo(t_inicio, t_fim);
				
				gettimeofday(&t_inicio, NULL);
					copiarVetor(vetor, vetorCopia, tamanho_vetor);
				gettimeofday(&t_fim, NULL);
				
				tempo.total = tempo.total - (6 * diftempo(t_inicio, t_fim));
				/* O tempo total de ordenacao de todos metodos eh o tempo gasto por eles menos o tempo gasto
				  * para criar os vetores copias.
				  */
			}
			
			if(!strcmp(opcao, "h"))
			{
				char nomeArquivo[50];
								
				printf("\n Digite o nome do arquivo: ", nomeArquivo);
				scanf("%50s", nomeArquivo);
				
				if(!gravarResultados(tempo, nomeArquivo, tamanho_vetor))
					printf("Erro ao gravar o arquivo");
			}
			
		}else
		{
			printf("\a\n Primeiramente gere o vetor\n");
			sleep(1);
		}
	}
	
	return 0;
}