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

/* Atenção, r é um índice válido em v */
int maximo (int *v, int p, int r) {
    int i;
    int max = p;
    for (i = p + 1; i <= r; i++) {
        if (v[max] < v[i])
            max = i;
    }
    return max;
}

/* Ordena em ordem crescente o vetor v[p..r-1] */
void selectionSort (int *v, int p, int r) {
    int i, max, aux;
    for (i = r - 1; i >= p; i--) {
        max = maximo(v, p, i);
        aux = v[i];
        v[i] = v[max];
        v[max] = aux;
    }
}

/* Ordena em ordem crescente o vetor v[p..r-1] */
void selectionSortRec (int *v, int p, int r) {
    int max, aux;
    if (p >= r)
        return;
    max = maximo(v, p, r - 1);
    aux = v[r - 1];
    v[r - 1] = v[max];
    v[max] = aux;
    selectionSortRec(v, p, r - 1);
}

struct no {
    int val;
    struct no *prox;
};

int contaElems(struct no *cel) {
    if (cel == NULL)
        return 0;
    return 1 + contaElems(cel->prox);
}

int contaElemsIter(struct no *cel) {
    struct no *atual;
    int cont = 0;
    atual = cel;
    while (atual != NULL) {
        cont++;
        atual = atual->prox;
    }
    return cont;
}

struct no *criaListaDeVetor0(int *v, int tam) {
    int i;
    struct no *vcel = malloc(sizeof(struct no) * tam);
    for (i = 0; i < tam; i++) {
        vcel[i].val = v[i];
        if (i < tam - 1)
            vcel[i].prox = vcel + i + 1;
        else
            vcel[i].prox = NULL;

    }
    return vcel;
}

struct no* criaListaDeVetor(int *v, int tam) {
    int i;
    struct no *cel;
    struct no *ret = NULL;
    struct no *anterior = NULL;

    for (i = 0; i < tam; ++i) {
        cel = malloc(sizeof(struct no));
        if (i == 0)
            ret = cel;
        else
            anterior->prox = cel;
        cel->val = v[i];
        cel->prox = NULL;
        anterior = cel;
    }
    return ret;
}

struct no *criaListaDeVetorRec(int *v, int p, int r) {
    struct no *cel;
    if (p >= r)
        return NULL;
    cel = malloc(sizeof(struct no));
    cel->val = v[p];
    cel->prox = criaListaDeVetorRec(v, p + 1, r);
    return cel;
}

void imprimeLista(struct no* cel) {
    struct no *atual = cel;
    while (atual) {
        printf("%d ", atual->val);
        atual = atual->prox;
    }
    printf("\n");
}

void freeLista(struct no* cel) {
    struct no *atual = cel;
    struct no *prox;
    while (atual) {
        prox = atual->prox;
        free(atual);
        atual = prox;
    }
}

void geraVetor(int *v, int tamanho, int max) {
    int i;
    srand(clock());
    for (i = 0; i < tamanho; i++)
        v[i] = rand() % max;
}

void imprimeVetor(int *v, int tamanho) {
    int i;
    for (i = 0; i < tamanho; ++i) {
        printf("%d ", v[i]);
    }
    printf("\n");

}

struct dma {
    int dia, mes, ano;
};

int diferencaDatas(struct dma *d1, struct dma *d2) {
    int totalDias1, totalDias2, dif;
    totalDias1 = d1->ano * 365 + d1->mes * 30 + d1->dia;
    totalDias2 = d2->ano * 365 + d2->mes * 30 + d2->dia;
    dif = totalDias2 - totalDias1;
    return (dif < 0) ? -dif : dif;
}

int main(int argc, char *argv[]) {
    int tam;
    int *v, *aux;
    struct no *lista;

    if (argc != 2) {
        printf("Uso %s tamanho\n", argv[0]);
        exit(1);
    }
    tam = atoi(argv[1]);
    aux = malloc(tam * sizeof(int));
    v = malloc(tam * sizeof(int));
    geraVetor(aux, tam, 100);
    printf("Vetor original: ");
    imprimeVetor(aux, tam);

    /* Testa ordenação SelectionSort */
    /* Copia vetor original para v */
    memcpy(v, aux, sizeof(int) * tam);
    selectionSort (v, 0, tam);
    printf("SelectionSort: ");
    imprimeVetor(v, tam);

    /* Testa ordenação SelectionSort recursivo */
    /* Copia vetor original para v */
    memcpy(v, aux, sizeof(int) * tam);
    selectionSortRec (v, 0, tam);
    printf("SelectionSort Recursivo: ");
    imprimeVetor(v, tam);


    printf("\n");
    /* Criando e imprimindo listas ligadas */
    lista = criaListaDeVetor0(v, tam);
    printf("criaListaDeVetor0: ");
    imprimeLista(lista);
    printf("Contagem de elementos iterativa: %d recursiva %d\n",
           contaElemsIter(lista), contaElems(lista));
    /* como esta primeira versão alocou a lista de uma só vez
    a liberação da memória também deve ser de uma só vez */
    free(lista);

    printf("\n");
    /* Criando e imprimindo listas ligadas */
    lista = criaListaDeVetor(v, tam);
    printf("criaListaDeVetor: ");
    imprimeLista(lista);
    printf("Contagem de elementos iterativa: %d recursiva %d\n",
           contaElemsIter(lista), contaElems(lista));
    freeLista(lista);

    printf("\n");
    /* Criando e imprimindo listas ligadas */
    lista = criaListaDeVetorRec(v, 0, tam);
    printf("criaListaDeVetorRec: ");
    imprimeLista(lista);
    printf("Contagem de elementos iterativa: %d recursiva %d\n",
           contaElemsIter(lista), contaElems(lista));
    freeLista(lista);

    free(v);
    free(aux);
    return 0;
}