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

struct info {
    char nome[50];
};

typedef struct Elemento {
    struct info info;
    struct Elemento *prox;
} Elemento;

typedef struct entrada {
    struct info *dados;
    struct entrada *prox;
} entrada;

#define TAMANHO_HASH 100
entrada *hash_nomes[TAMANHO_HASH];

unsigned long hash(char *str){
    unsigned long hash = 5381;
    int c;
    while (c = *str++)
        hash = ((hash << 5) + hash) + c;

    return hash;
}

int adiciona_se_inexistente(struct info* dados){
    unsigned long key = hash(dados->nome) % TAMANHO_HASH;

    entrada *corrente = hash_nomes[key];
    while (corrente != NULL){
        if (strcmp(corrente->dados->nome, dados->nome) == 0){
            return 0;
        }
        corrente = corrente->prox;
    }

    entrada *nova = malloc(sizeof(entrada));
    nova->prox = hash_nomes[key];
    nova->dados = dados;
    hash_nomes[key] = nova;
    return 1;
}


void remove_duplicados(Elemento* agenda){
    Elemento *corrente = agenda, *anterior = NULL;

    while (corrente != NULL){
        if (adiciona_se_inexistente(&corrente->info) == 0){
            anterior->prox = corrente->prox;
            Elemento* remover = corrente;
            corrente = corrente -> prox;
            free(remover);
        }
        else {
            anterior = corrente;
            corrente = corrente -> prox;
        }
    }
}

void mostrar_lista(Elemento* agenda){
    Elemento *p;
    for(p = agenda; p != NULL; p = p -> prox){
        printf("%s -> ", p->info.nome);
    }

    printf(" NULL");
}

int main() {
    Elemento *agenda = malloc(sizeof(Elemento));
    strcpy(agenda->info.nome,"ana");
    Elemento *agenda2 = malloc(sizeof(Elemento));
    strcpy(agenda2->info.nome,"ana");
    Elemento *agenda3 = malloc(sizeof(Elemento));
    strcpy(agenda3->info.nome,"carla");
    Elemento *agenda4 = malloc(sizeof(Elemento));
    strcpy(agenda4->info.nome,"vitor");
    Elemento *agenda5 = malloc(sizeof(Elemento));
    strcpy(agenda5->info.nome,"vitor");
    Elemento *agenda6 = malloc(sizeof(Elemento));
    strcpy(agenda6->info.nome,"ana");

    agenda->prox = agenda2;
    agenda2->prox = agenda3;
    agenda3->prox = agenda4;
    agenda4->prox = agenda5;
    agenda5->prox = agenda6;
    agenda6->prox = NULL;

    memset(hash_nomes, 0, sizeof(hash_nomes));
    mostrar_lista(agenda);
	remove_duplicados(agenda);
	printf("\n\nDuplicados removidos\n\n");
	mostrar_lista(agenda);

	return 0;
}