/* Implementacao do jogo Mega Quadra.
 * Objetivo: funcionalidades principais e logica do jogo exigido no TP2 de alg2
 * Observacoes: algumas funcoes necessitam de um paramentro que indica se estah
 * em teste ou nao, isso evita que o log exiba 40000 operacoes para cada teste
 *
 * Autores: Bruno Freitas Tissei e Felipe Shi Iu Wu
 * Disciplina: Algoritmos e Estrutura de Dados II
 * Entrega: 13/12/2015 */
#include "main.h"

// vetor principal e vetor auxiliar que permite a ordenacao do vetor sem altera-lo
int vetor[MAX], vetorCopia[MAX];
// vetor que armazena os numeros escolhidos pelo usuario durante o jogo
int numeros[4];
// matriz que armazena NTEST (10000) vetores para teste
// e matriz que permite a ordenacao da matriz sem altera-la
int matriz[NTEST][MAX], matrizCopia[NTEST][MAX];
// string auxiliar para criacao do log
char straux[MAXS];

// programa principal onde ficam o menu principal e o inicio do programa
int main() {
    // opcao escolhida pelo usuario
    int opc;
    // tamanho do vetor e numero maximo
    int tam, maxrand;
    srand(time(NULL));
    iniciaLog(); 

    printf("\n===================================================================\n");
    printf("                         ** MEGA QUADRA **                           \n");
    do {
        printf("Insira o tamanho do vetor (menor que %d): ", MAX);
        scanf("%d", &tam);
    } while (tam >= MAX);
    sprintf(straux, "Definido o tamanho do vetor: %d", tam);
    imprimeLog(straux, true);

    printf("Insira o numero maximo do vetor: ");
    scanf("%d", &maxrand);
    sprintf(straux, "Definido o numero maximo do vetor: %d", maxrand);
    imprimeLog(straux, true);

    // gera o vetor principal para o jogo
    gerarVetor(vetor, tam, maxrand, false);
 
    printf("\n===================================================================\n");
    printf("                         ** MEGA QUADRA **                           \n");
    // opcoes de escolha do usuario
    printf("1. Imprimir vetor\n2. Jogar\n3. Gerar outro vetor\n4. Testar tempos de ordenacao\n0. Terminar programa\n");
    printf("Insira o codigo da operacao desejada: ");
    while (scanf("%d", &opc) && opc != 0) {
        switch(opc) {
            case 1:
                imprimirVetor(vetor, tam, false);
                break;
            case 2:
                jogar(vetor, tam, maxrand);
                break;
            case 3:
                do {
                    printf("\nInsira o tamanho do vetor (menor que %d): ", MAX);
                    scanf("%d", &tam);
                } while (tam >= MAX);
                printf("Insira o numero maximo do vetor: ");
                scanf("%d", &maxrand);
                gerarVetor(vetor, tam, maxrand, false);
                break;
            case 4:
                testar(tam, maxrand);
                break;
        }
        printf("\n===================================================================\n");
        printf("                         ** MEGA QUADRA **                           \n");
        printf("1. Imprimir vetor\n2. Jogar\n3. Gerar outro vetor\n4. Testar tempos de ordenacao\n0. Terminar programa\n");
        printf("Insira o codigo da operacao desejada: ");
    }

    fechaLog();
    return 0;
}

// imprime um vetor de tamanho tam
void imprimirVetor(int vetor[], int tam, bool ordenado) {
    int i;
    // opcoes diferentes caso o vetor esteja ordenado
    if (ordenado) {
        printf("\nVEJA O RESULTADO DO SORTEIO:\n");
        imprimeLog("Veja o vetor ordenado: [\n\t", false);
    } else {
        printf("\nVETOR:\n");
        imprimeLog("Veja o vetor: [\n\t", false);
    }

    for (i = 0; i < tam; i++) {
        printf("%d ", vetor[i]);
        sprintf(straux, "%d", vetor[i]);
        imprimeLog(straux, false);

        // exibe apenas 20 numeros por linha para melhor visualizacao do vetor
        // e nao insere espaco depois da ultima linha
        if ((i + 1) % 20 == 0 && i != tam - 1) {
            printf("\n");
            imprimeLog("\n\t", false);
        // insere separador entre os numeros somente se estiver na mesma linha
        // se nao for o ultimo elemento
        } else if (i != tam - 1) {
            printf("- ");
            imprimeLog(", ", false);
        }
    }
    imprimeLog("\n]", true);
    printf("\n");
}

// executa o teste que mede o tempo de ordenacao de 10000 vetores
// para cada algoritmo de ordenacao (InsertSort, BubbleSort, QuickSort Recursivo e
// QuickSort Iterativo)
void testar(int tam, int maxrand) {
    int i;
    double tempoAnterior, tempoPosterior, duracao;
    char c;

    // avisa que estah em teste, pois o teste pode demorar
    printf("\nTestando...\n");
    imprimeLog("Iniciei o teste de ordenacao", true);

    // gera os NTEST (10000) vetores aleatorios e os coloca na matriz
    for (i = 0; i < NTEST; i++)
        gerarVetor(matriz[i], tam, maxrand, true);
    sprintf(straux, "Gerei %d vetores diferentes de tamanho %d com numeros aleatorios de 1 a %d", 
            NTEST, tam, maxrand);
    imprimeLog(straux, true);

    // replica a matriz para a matrizCopia para poder ordena-la sem alterar a original
    // isso permite testar o tempo de ordenacao de cada algoritmo para os mesmos vetores
    for (i = 0; i < NTEST; i++)
        replicaVetor(matriz[i], matrizCopia[i], tam);
    sprintf(straux, "Salvei os %d vetores originais para serem ordenados", NTEST);
    // obtem o tempo anterior ordena os vetores e obtem o tempo posterior
    // o tempo de ordenacao eh a diferenca entre os tempos
    imprimeLog(straux, true);
    tempoAnterior = getTime();
    for (i = 0; i < NTEST; i++)
        selectSort(matriz[i], tam);
    tempoPosterior = getTime();
    duracao = tempoPosterior - tempoAnterior;
    sprintf(straux, "SelectSort ordenou %d vetores em %.0lfns (%.3lfs)", NTEST, duracao, duracao / NANO);
    imprimeLog(straux, true);
    printf("SelectSort ordenou %d vetores em %.0lfns (%.3lfs)\n", 
            NTEST, duracao, duracao / NANO); 

    // o mesmo procedimento eh aplicado ao BubbleSort
    for (i = 0; i < NTEST; i++)
        replicaVetor(matriz[i], matrizCopia[i], tam);
    sprintf(straux, "Salvei os %d vetores originais para serem ordenados", NTEST);
    imprimeLog(straux, true);
    tempoAnterior = getTime();
    for (i = 0; i < NTEST; i++)
        bubbleSort(matriz[i], tam);
    tempoPosterior = getTime();
    duracao = tempoPosterior - tempoAnterior;
    sprintf(straux, "BubbleSort ordenou %d vetores em %.0lfns (%.3lfs)", NTEST, duracao, duracao / NANO);
    imprimeLog(straux, true);
    printf("BubbleSort ordenou %d vetores em %.0lfns (%.3lfs)\n", 
            NTEST, duracao, duracao / NANO); 

    // o mesmo procedimento eh aplicado ao QuickSort Recursivo
    for (i = 0; i < NTEST; i++)
        replicaVetor(matriz[i], matrizCopia[i], tam);
    sprintf(straux, "Salvei os %d vetores originais para serem ordenados", NTEST);
    imprimeLog(straux, true);
    tempoAnterior = getTime();
    for (i = 0; i < NTEST; i++)
        quickSortR(matriz[i], 0, tam - 1);
    tempoPosterior = getTime();
    duracao = tempoPosterior - tempoAnterior;
    sprintf(straux, "QuickSort Recursivo ordenou %d vetores em %.0lfns (%.3lfs)", NTEST, duracao, duracao / NANO);
    imprimeLog(straux, true);
    printf("QuickSort Recursivo ordenou %d vetores em %.0lfns (%.3lfs)\n", 
            NTEST, duracao, duracao / NANO); 

    // o mesmo procedimento eh aplicado ao QuickSort Iterativo
    for (i = 0; i < NTEST; i++)
        replicaVetor(matriz[i], matrizCopia[i], tam);
    sprintf(straux, "Salvei os %d vetores originais para serem ordenados", NTEST);
    imprimeLog(straux, true);
    tempoAnterior = getTime();
    for (i = 0; i < NTEST; i++)
        quickSortI(matriz[i], 0, tam - 1);
    tempoPosterior = getTime();
    duracao = tempoPosterior - tempoAnterior;
    sprintf(straux, "QuickSort Iterativo ordenou %d vetores em %.0lfns (%.3lfs)", NTEST, duracao, duracao / NANO);
    imprimeLog(straux, true);
    printf("QuickSort Iterativo ordenou %d vetores em %.0lfns (%.3lfs)\n", 
            NTEST, duracao, duracao / NANO); 

    // avisa ao usuario e reporta no log que o teste terminou
    imprimeLog("Terminei o teste de ordenacao", true);
    printf("\nFIM DE TESTE.\n");

    // tempo de espera para o usuario poder visualizar o resultado dos testes
    printf("Para continuar precione ENTER");
    scanf("%c%c", &c, &c);
}

// funcao que executa o jogo Mega Quadra, onde o usuario insere 4 numeros
// e eh verificado quandos dos numeros escolhidos estao em um vetor
// gerado aleatoriamente de tamanho tam
void jogar(int vetor[], int tam, int maxrand) {
    int i;
    // numero de acertos do usuario
    int acertos;
    // opcoes de ordenacao escolhidas pelo usuario e variavel que armazena o resultado da pesquisa
    int ordenacao, pesquisa;
    double tempoAnterior, tempoPosterior, duracao;
    // alternativa de jogar novamente, comeca em 'y' para iniciar o jogo pela primeira vez
    char alternativa = 'y';

    // o jogo reinicia enquanto o usuario decide continuar
    while (alternativa == 'y') {
        acertos = 0;
        imprimeLog("Iniciei o jogo Mega Quadra", true);
        replicaVetor(vetor, vetorCopia, tam);
        imprimeLog("Salvei o vetor original para ser ordenado", true);

        // le os numeros escolhidos pelo usuario e verifica se estao entre 1 e o numero maximo determinado
        // anteriormente
        printf("\nInsira quatro numeros para testar a sua sorte: ");
        scanf("%d %d %d %d", &numeros[0], &numeros[1], &numeros[2], &numeros[3]); 
        for (i = 0; i < 4; i++)
            while (numeros[i] > maxrand) {
                printf("O %do numero deve estar entre 1 e %d: ", i + 1, maxrand);
                scanf("%d", &numeros[i]);
            }
        sprintf(straux, "Numeros %d, %d, %d e %d foram escolhidos", numeros[0], numeros[1], numeros[2], numeros[3]);
        imprimeLog(straux, true);

        // o usuario escolhe o algoritmo de ordenacao que deseja
        printf("\nEscolha o metodo de ordenacao:\n");
        printf("1. SelectSort\n");
        printf("2. BubbleSort\n");
        printf("3. QuickSort (Recusivo)\n");
        printf("4. QuickSort (Iterativo)\n");
        printf("Insira o codigo da operacao desejada: ");
        scanf("%d", &ordenacao);

        switch(ordenacao) {
            case 1:
                selectSort(vetorCopia, tam);
                imprimeLog("Ordenei o vetor usando SelectSort", true);
                break;
            case 2:
                bubbleSort(vetorCopia, tam);
                imprimeLog("Ordenei o vetor usando BubbleSort", true);
                break;
            case 3:
                quickSortR(vetorCopia, 0, tam - 1);
                imprimeLog("Ordenei o vetor usando QuickSort Recursivo", true);
                break;
            case 4:
                quickSortI(vetorCopia, 0, tam - 1);
                imprimeLog("Ordenei o vetor usando QuickSort Iterativo", true);
                break;
        }
        imprimirVetor(vetorCopia, tam, true);
        
        // obtem o tempo anterior executa a pesquisa binaria nos vetores e obtem o tempo posterior
        // o tempo de pesquisa eh a diferenca entre os tempos
        tempoAnterior = getTime();
        for (i = 0; i < 4; i++) {
            pesquisa = pesquisaBin(vetorCopia, numeros[i], 0, tam);
            if (pesquisa != -1) {
                sprintf(straux, "Encontrei o elemento %d na posicao %d usando pesquisa binaria", numeros[i], pesquisa);
                imprimeLog(straux, true);
                acertos++;
            } else {
                sprintf(straux, "Nao encontrei o elemento %d no vetor usando pesquisa binaria", numeros[i]);
                imprimeLog(straux, true);
            }
        }
        tempoPosterior = getTime();
        duracao = tempoPosterior - tempoAnterior;
        sprintf(straux, "As quatro pesquisas binarias foram executadas em %.0lfns", duracao);
        imprimeLog(straux, true);
        printf("\nQuatro pesquisas binarias foram feitas em %.0lfns\n", duracao);

        // faz o mesmo procedimento para a pesquisa sequencial
        tempoAnterior = getTime();
        for (i = 0; i < 4; i++) {
            pesquisa = pesquisaBin(vetorCopia, numeros[i], 0, tam);
            if (pesquisa != -1) {
                sprintf(straux, "Encontrei o elemento %d na posicao %d usando pesquisa sequencial", numeros[i], pesquisa);
                imprimeLog(straux, true);
                acertos++;
            } else {
                sprintf(straux, "Nao encontrei o elemento %d no vetor usando pesquisa sequencial", numeros[i]);
                imprimeLog(straux, true);
            }
        }
        tempoPosterior = getTime();
        duracao = tempoPosterior - tempoAnterior;
        sprintf(straux, "As quatro pesquisas sequenciais foram executadas em %.0lfns", duracao);
        imprimeLog(straux, true);
        printf("Quatro pesquisas sequenciais foram feitas em %.0lfns\n", duracao);

        // o numero de acertos e dividido por dois, pois a mesma variavel foi incrementada nas duas pesquisas
        acertos /= 2;
        sprintf(straux, "Encontrei %d numero(s), ao total, no vetor", acertos);
        imprimeLog(straux, true);

        // informa a quantidade de numeros acertados, if adapta o printf para o plural
        // ou caso nenhum numero foi encontrado
        if (!acertos)
            printf("\nVOCE NAO ACERTOU NENHUM NUMERO! JOGUE DE NOVO!\n");
        else if (acertos == 1)
            printf("\nVOCE ACERTOU 1 NUMERO!\n");
        else
            printf("\nVOCE ACERTOU %d NUMEROS!\n", acertos);
        imprimeLog("Terminei o jogo Mega Quadra", true);

        // pergunta se o usuario deseja jogar novamente,
        // caso a resposta nao for y ou n, pergunta novamente
        do {
            printf("Voce deseja jogar novamente? (y/n): ");
            scanf("%c", &alternativa);
        } while (scanf("%c", &alternativa) && alternativa != 'y' && alternativa != 'n');
    }
}

// copia o vetor a para o vetor b, ambos de tamanho tam
void replicaVetor(int a[], int b[], int tam) {
    int i;

    for (i = 0; i < tam; i++)
        b[i] = a[i];
}

// gera um vetor aleatorio de tamanho tam com numeros de 1 a maxr 
void gerarVetor(int vetor[], int tam, int maxr, bool teste) {
    int i;

    if (!teste) 
        printf("\nGerando vetor aleatorio...\n");

    for (i = 0; i < tam; i++)
        vetor[i] = (rand() % maxr) + 1;

    if (!teste) 
        printf("VETOR ALEATORIO GERADO COM SUCESSO!\n");

    if (!teste) {
        sprintf(straux, "Gerei um vetor de tamanho %d com numeros aleatorios de 1 a %d", 
                tam, maxr);
        imprimeLog(straux, true);
    }
}