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

/*
PROGRAMA: tabla_hash.cpp
DESCRIPCIÓN: Implementar una tabla hash con claves tipo cadena
AUTOR: Fco. J. Hedz. L.
Fceha Inicial: 21/Oct/2014
Fecha Actualización: 28/Oct/2014
*/

//Definiendo una lista
typedef struct _nodo{
	char IFE[18];
	char nombre[100];
	struct _nodo *siguiente;
}tipoNodo;

//Definir la estructura de datos de nuestra tabla hash
typedef struct _tabla{
	int ocupado;
	char IFE[18];
	char nombre[100];
	//Para encadenamiento separado
	tipoNodo *lista;
}tipoTablaHash;

//PARAMETROS
#define M 5

//PROCEDIMIENTOS
int funcion_hashCadena(char *clave_k);
void Alta(tipoTablaHash *Tabla, int indice_k, char *clave_k, char *nombre_k);
void DesplegarTabla(tipoTablaHash *Tabla);

void insertar(tipoNodo **lista, char *clave_k, char *nombre_k);
int EstaEnLaTabla(tipoTablaHash Tabla_k, char *clave_k);


int main(void){
	tipoTablaHash Tabla[M];
	char clave_k[18];
	char nombre_k[100];
	int indice_k;
	int op = 6;

	//Inicialización
	for (int i = 0; i < M; i++){
		Tabla[i].ocupado = 0;//0-->No ocupado, 1-->Ocupado
		//Tabla[i].lista = NULL;
	}

	do{
		printf("\n1. Altas");
		printf("\n2. Desplegar tabla");
		printf("\n6. Salir");

		printf("\nElige una opción: ");
		scanf("%d", &op);

		switch (op){
			case 1:
				printf("\nIngresa la clave del IFE: ");
				scanf("%s",clave_k);
				printf("\nIngresa el nombre: ");
				scanf("%s",nombre_k);
				indice_k = funcion_hashCadena(clave_k);
				Alta(Tabla,indice_k,clave_k,nombre_k);
			break;
			case 2:
				DesplegarTabla(Tabla);

			break;
		}
	
	}while (op!=6);


	system("pause");
	return(0);
}

int funcion_hashCadena(char *clave_k){
	int hash = 0;
	int R = 31;
	for (int i = 0; i < strlen(clave_k); i++){
		hash = (R*hash + clave_k[i]) % M;
	}
	return(hash);
}

void Alta(tipoTablaHash *Tabla, int indice_k, char *clave_k, char *nombre_k){
	
	if(Tabla[indice_k].ocupado == 1){//Está ocupado entonces: Encadenamiento o sondeo
		if (EstaEnLaTabla(Tabla[indice_k], clave_k)){
			printf("\nEl IFE ya está dado de alta...\n");
		}
		else{
			insertar(&Tabla[indice_k].lista, clave_k, nombre_k);
		}
	}
	else{
		strcpy(Tabla[indice_k].IFE, clave_k);
		strcpy(Tabla[indice_k].nombre, nombre_k);
		Tabla[indice_k].ocupado = 1;
		Tabla[indice_k].lista = NULL;
	}
}
int EstaEnLaTabla(tipoTablaHash Tabla_k, char *clave_k){
	int ban = 0;
	if (!strcmp(Tabla_k.IFE, clave_k)){
		ban = 1;
	}
	else{
		tipoNodo *aux;
		aux = Tabla_k.lista;
		while (aux != NULL){
			if (!strcmp(aux->IFE, clave_k)){
				ban = 1;
				break;
			}
			aux = aux->siguiente;
		}
	}
	return(ban);
}

void insertar(tipoNodo **lista, char *clave_k, char *nombre_k){
	//Crear memoria del nodo nuevo
	tipoNodo *nodo_nuevo;
	nodo_nuevo = (tipoNodo *)malloc(sizeof(tipoNodo));

	strcpy(nodo_nuevo->IFE, clave_k);
	strcpy(nodo_nuevo->nombre, nombre_k);

	if (*lista == NULL){//Lista vacía
		nodo_nuevo->siguiente = NULL;
		*lista = nodo_nuevo;
	}
	else{
		//Programar cuando la lista no está vacía...
		nodo_nuevo->siguiente = *lista;
		*lista = nodo_nuevo;
	}
}

void DesplegarTabla(tipoTablaHash *Tabla){
	printf("\nTabla Hash: ");
	for (int i = 0; i < M; i++){
		if (Tabla[i].ocupado == 1){
			printf("\n<%s> <%s>", Tabla[i].IFE, Tabla[i].nombre);
			tipoNodo *aux;
			aux = Tabla[i].lista;
			while (aux != NULL){
				printf(" --> <%s> <%s>", aux->IFE, aux->nombre);
				aux = aux->siguiente;
			}
		}
		else{
			printf("\n<--> <-->");
		}
	}
}