/*
 ============================================================================
Curso: Ciência da Computação
Turma: 4NA - 4º Período
Disciplina: Estrutura de Dados II
Professor: Rafael Nunes
Alunos: Vitor Iyomassa, João Gouveia, Frederico Perpétuo
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#define TAMANHO_MAXIMO_NOME_SOLDADOS 20

typedef struct lista TLista;

struct lista {
    char nomeSoldado[TAMANHO_MAXIMO_NOME_SOLDADOS];
    TLista* prox;
};

//protótipos
TLista* inicializaListaSoldados();
TLista* insereSoldadoNoCirc(TLista*, char*);
void imprimeSoldadosCirc(TLista*);
int verificaCircVazio(TLista*);
int verificaNumeroSoldados(TLista*);
TLista* sorteiaSoldado(TLista*);
TLista* excluiSoldadoDoCirc(TLista*, char*);
int sorteiaN(void);
void executaJosephus(TLista*, TLista*, int);

//funções de entrada de dados

TLista* lerNomeSoldadosArquivoTxt(TLista*, char*);
TLista* lerNome20Soldados(TLista*);
TLista* lerNomeUsuariosPeloUsuario(TLista*);

int main(void) {
    setbuf(stdout, NULL);

    TLista* listaSoldados = inicializaListaSoldados();
    TLista* soldadoSorteado = inicializaListaSoldados();
    int n = sorteiaN();
    int op;

    do{
        printf("#*#*#*#*#*#*#*#*#* O Problema de Josephus (Tenenbaum, 1989) #*#*#*#*#*#*#*#*#*\n");
        printf("Escolha uma opcao abaixo para a entrada de dados: \n");
        printf("1 - Ler os nomes do arquivo nomes.txt\n");
        printf("2 - Ler os nomes de 20 soldados por uma funcao\n");
        printf("3 - Entrar com os nomes dos soldados manualmente\n");

        printf("opcao: ");
        scanf("%d", &op);
        if(op < 1 || op > 3){
            printf("\nOpcao invalida!\n");
        }
    }while(op < 1 || op > 3);

    if(op == 1){
        printf("AVISO: Essa funcao deve ser usada somente no linux,\n"
                " pois em nossos testes ela nao se comportou bem no\n"
                " windows caso esteja testando no linux, favor ir no\n "
                "codigo e descomentar a linha 69 e excluir a 70!!!\n");
        //listaSoldados = lerNomeSoldadosArquivoTxt(listaSoldados, "nomes.txt");
        exit(1);
    }else if(op == 2){
        listaSoldados = lerNome20Soldados(listaSoldados);
    }else{
        fflush(stdin);
        listaSoldados = lerNomeUsuariosPeloUsuario(listaSoldados);
    }

    soldadoSorteado = sorteiaSoldado(listaSoldados);

    executaJosephus(listaSoldados, soldadoSorteado, n);

    printf("\nExecucao finalizada!\n");
    return EXIT_SUCCESS;
}

/**
 * Função que inicializa a lista para que a mesma nao seja um ponteiro apontando pro nada
 */
TLista* inicializaListaSoldados(){
    return NULL;
}

/**
 * Função que insere um soldado em uma lista
 */
TLista* insereSoldadoNoCirc(TLista* lista, char* nome){
    TLista* aux, *aux2;
    aux = (TLista*) malloc(sizeof(TLista));
    strcpy(aux->nomeSoldado, nome);

    if (verificaCircVazio(lista)) {
        aux->prox = aux;
        lista = aux;
    } else {
        aux->prox = lista;
        aux2 = lista;
        do {
            aux2 = aux2->prox;
        } while (aux2->prox != lista);
        aux2->prox = aux;
    }
    return lista;
}

/**
 * Função que imprime a lista de soldados no console
 */

void imprimeSoldadosCirc(TLista* lista) {
    TLista* aux;
    if (verificaCircVazio(lista)) {
        printf("\nLista vazia!\n");
    } else {
        aux = lista;
        do {
            if (aux->prox != lista) {
                TLista* excluiSoldadoDoCirc(TLista*, char*);
                printf("%s - ", aux->nomeSoldado);
            } else {
                printf("%s", aux->nomeSoldado);
            }
            aux = aux->prox;
        } while (aux != lista);
    }
}

/**
 * Função que verifica se a lista de soldados esta vazia
 */

int verificaCircVazio(TLista* lista){
    return !lista;
}

/**
 * Função que verifica a quantidade de soldados na lista
 */
int verificaNumeroSoldados(TLista* lista){
    TLista* aux = lista;
    int cont = 0;

    if (aux){
        do {
            cont++;
            aux = aux->prox;
        } while (aux != lista);
    }

    return cont;
}

/*
 * Função que sorteia um soldado na lista
 */

TLista* sorteiaSoldado(TLista* lista) {
    int tamanhoLista = verificaNumeroSoldados(lista);
    int indiceSoldadoSorteado;
    int aux = 0;
    TLista* soldadoSorteado = lista;

    srand((unsigned) time(NULL));

    if (lista != NULL) {
        do {
            indiceSoldadoSorteado = rand()
                    % (int) pow(10, ((int) log10(tamanhoLista)) + 1);
        } while (indiceSoldadoSorteado >= tamanhoLista);

        do{
            soldadoSorteado = soldadoSorteado->prox;
            aux++;
        }while(aux != indiceSoldadoSorteado);
        return soldadoSorteado;
    }
    return NULL;
}

/**
 * Função que exclui um soldado da lista
 */

TLista* excluiSoldadoDoCirc(TLista* lista, char* nomeMorto){
    TLista* aux = lista;
    TLista* soldadoExcluido = inicializaListaSoldados();
    do{
        aux = aux->prox;
    }while(strcmp(aux->prox->nomeSoldado, nomeMorto) != 0);
    soldadoExcluido = aux->prox;
    aux->prox = aux->prox->prox;
    if(soldadoExcluido == lista){
        lista = aux;
    }
    free(soldadoExcluido);
    return lista;
}

/**
 * Função que sorteia um n, que por sua vez discrimina de quanto sera o numero de saltos do algoritimo
 */

int sorteiaN(void){
    srand((unsigned) time(NULL));
    int n;
    do{
        n = rand()%10;
    }while(n < 2);
    return n;
}

/**
 * Função que executa o algoritimo de Josephus
 */

void executaJosephus(TLista* listaSoldados, TLista* soldadoSorteado, int n){
    int iteracao = 0;
    int aux = 1;
    TLista* aux2 = NULL;
    TLista* soldadoAtual = soldadoSorteado;
    TLista* sobrevivente = inicializaListaSoldados();

    printf("Execucao do Algoritimo");
    printf("\n=================================\n");
    printf("\nDados recebidos:\n");
    printf("Lista de soldados: ");
    imprimeSoldadosCirc(listaSoldados);
    printf("\nSoldado Sorteado = %s", soldadoSorteado->nomeSoldado);
    printf("\nN: %i", n);
    printf("\n=================================\n");
    while(verificaNumeroSoldados(listaSoldados) != 1){
        iteracao++;
        printf("iteracao %i: \n", iteracao);
        while(aux < n){
            soldadoAtual = soldadoAtual->prox;
            aux++;
        }
        aux = 1;
        aux2 = soldadoAtual->prox;
        printf("\nSoldado excluido: %s\n", soldadoAtual->nomeSoldado);
        if(listaSoldados == soldadoAtual){
            listaSoldados = listaSoldados->prox;
        }
        soldadoAtual = excluiSoldadoDoCirc(listaSoldados, soldadoAtual->nomeSoldado);
        soldadoAtual = aux2;
        printf("\nnum soldados = %i\n", verificaNumeroSoldados(listaSoldados));
    }
    printf("\nsoldado sobrevivente: %s", listaSoldados->nomeSoldado);
}

/**
 * Função que busca os nomes dos soldados no arquivo. Essa função funcionou
 * bem no linux, no windows não apresentou estabilidade
 */

TLista* lerNomeSoldadosArquivoTxt(TLista* lista, char* path){
    char* nome;
    FILE *file;
    file = fopen(path, "rt");
    if (file) {
        while (fgets(nome,150, file)) {
            nome[strlen(nome)-1] = '\0';
            lista = insereSoldadoNoCirc(lista, nome);
        }
        fclose(file);
    }else{
        printf("\nAquivo nomes.txt nao encontrado\n");
    }

    return lista;
}

/**
 * Função que coloca 20 soldados numa lista
 */
TLista* lerNome20Soldados(TLista* lista){
    if(verificaCircVazio(lista)){
        lista = insereSoldadoNoCirc(lista, "Joao");
        lista = insereSoldadoNoCirc(lista, "Fred");
        lista = insereSoldadoNoCirc(lista, "Vitor");
        lista = insereSoldadoNoCirc(lista, "Xulambs");
        lista = insereSoldadoNoCirc(lista, "Rafael");
        lista = insereSoldadoNoCirc(lista, "Ze");
        lista = insereSoldadoNoCirc(lista, "Dilma");
        lista = insereSoldadoNoCirc(lista, "Aecio");
        lista = insereSoldadoNoCirc(lista, "Renan");
        lista = insereSoldadoNoCirc(lista, "Delcidio");
        lista = insereSoldadoNoCirc(lista, "Faustao");
        lista = insereSoldadoNoCirc(lista, "Hebe");
        lista = insereSoldadoNoCirc(lista, "Gugu");
        lista = insereSoldadoNoCirc(lista, "Silvio");
        lista = insereSoldadoNoCirc(lista, "Santos");
        lista = insereSoldadoNoCirc(lista, "Liminha");
        lista = insereSoldadoNoCirc(lista, "Eneas");
        lista = insereSoldadoNoCirc(lista, "Bolsonaro");
        lista = insereSoldadoNoCirc(lista, "Jean");
        lista = insereSoldadoNoCirc(lista, "Willys");
    }
    return lista;
}

/**
 * Função que le o nome dos soldados por teclado
 */

TLista* lerNomeUsuariosPeloUsuario(TLista* listaSoldados){
    char resp;
    char nome[TAMANHO_MAXIMO_NOME_SOLDADOS];
    if(verificaCircVazio(listaSoldados)){
        do {
            printf("Entre com o nome do soldado: ");
            fflush(stdin);
            scanf("%s", &nome);
            listaSoldados = insereSoldadoNoCirc(listaSoldados, nome);
            do {
                printf("Deseja inserir mais um soldado? (S/N): ");
                setbuf(stdin, NULL);
                scanf("%c", &resp);
                if (resp != 'S' && resp != 's' && resp != 'N' && resp != 'n') {
                    printf("Resposta inválida\n");
                }

            } while (resp != 'S' && resp != 's' && resp != 'N' && resp != 'n');

        } while (resp != 'N' && resp != 'n');
    }

    return listaSoldados;
}