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

#define clrscr() system("cls")
#define pause()  system("pause")

//costante di grandezza della tabella
#define DIM_TABLE 5
//costante di grandezza del nome
#define DIM_NOME  20
//struttura dati di un esame
struct esame {
        int matricola;
        char nome[DIM_NOME];
        int voto;
};

//tabella hash
struct esame table[DIM_TABLE];

int hash(char nome[]);                        //genera il corrispondente valore hash
void hash_flush_table(void);                  //azzera la tabella
int hash_add_element(struct esame element);   //aggiunge un elemento alla tabella
int hash_search_element(struct esame element);//ricerca un elemento alla tabella

int hash(char nome[]) {
  //ptr = puntatore all'esame
  //return = valore hash
  int i,res;
  res = 0; //risultato
  for(i=0;nome[i]!='\0';i++){
    res += ((int) nome[i])*(32^i);
    //printf("%c = %i * 32^%d \n",nome[i],(int) nome[i],i);
  }
  return res;
}

void hash_flush_table(void){
  int i;
  for(i=0;i<DIM_TABLE;i++) {
    strcpy(table[i].nome,"");
    // table[i].nome = '\0';
    table[i].matricola = 0;
    table[i].voto = 0;
  }
}

void hash_show_table() {
  int i;
  for(i=0;i<DIM_TABLE;i++){
    printf("L: %i NOME: %20s MATRICOLA: %6i VOTO: %2i\n",i,
               table[i].nome,
               table[i].matricola,
               table[i].voto);
    if(!((i+1)%20)) pause(),clrscr();
  }
}

int hash_add_element(struct esame element){
  //element = esame che viene inserito
  //return = ritorna la posizione dove è stato inserito
  int i;
  i = hash(element.nome) % DIM_TABLE;
  if(table[i].matricola == 0) {
    table[i].matricola = element.matricola;
    strcpy(table[i].nome,element.nome);
    table[i].voto = element.voto;
    return i;
  } else {
    int tempi,temp; //variabili temporanee su cui metto il primo valore e
                    //l'indice
    tempi = i;
    temp = table[i].matricola;
    table[i].matricola = 0;
    printf("COLLISIONE");
    //LINEAR PROBING
    for(i=++i%DIM_TABLE;table[i].matricola != 0;i=++i%DIM_TABLE)
      ;
    if(i == tempi){
      table[tempi].matricola = temp;
      return -1;
    } else {
      table[tempi].matricola = temp;
      table[i].matricola = element.matricola;
      strcpy(table[i].nome,element.nome);
      table[i].voto = element.voto;
      return i;
    }
  }
}

int hash_search_element(struct esame element) {
  //element = esame che viene ricercato
  //return = ritorna la posizione dove è stato inserito o -1 se non trovato
  //NA: Gestisce gli omonimi!
  int i;
  i = hash(element.nome) % DIM_TABLE;
  if(table[i].matricola==element.matricola) {
    //se è uguale è stato trovato
    return i;
  }else if(table[i].matricola==0){
    //se matricola è vuota
    return -1;
  }else{
    int tempi,temp; //variabili temporanee su cui metto il primo valore e
                    //l'indice
    tempi = i;
    temp = table[i].matricola;
    table[i].matricola = 0;
    //table[i].matricola = element.matricola;
    //LINEAR PROBING
    for(i=++i%DIM_TABLE;
        table[i].matricola!=0&&table[i].matricola!=element.matricola;
        i=++i%DIM_TABLE)
      ;
    if(i == tempi){
      table[tempi].matricola = temp;
      return -1;
    }else if(table[i].matricola==0){
      table[tempi].matricola = temp;
      return -1;
    }else {
      table[tempi].matricola = temp;
      return i;
    }
  }
}

main(){
  /* PROVA DELLA FUZIONE HASH
  struct esame prova;
  int k;
  pause();
  strcpy(prova.nome, "SERGIO DE BARI");
  pause();
  k = hash(prova.nome);
  pause();
  printf("\nVALORE HASH: %i\n",k);
  printf("E sarà posizionato nell'area %i",(k%DIM_TABLE));
  pause();
  */
  int i,k;
  struct esame element;
  hash_flush_table();
  printf("Quanti valori vuoi inserire?");
  for(scanf("%i",&i);i>0;i--) {
    printf("NOME");
    scanf("%s",&element.nome);
    printf("MATRICOLA");
    scanf("%i",&element.matricola);
    printf("VOTO");
    scanf("%i",&element.voto);

    k =(hash_add_element(element));
    if(k == -1) {
      printf("NON INSERITO\n");
    } else {
      printf("INSERITO IN %i\n",k);
    }
  }
  hash_show_table();
  printf("inserisci l'elemento da cercare:");
  printf("NOME");
  scanf("%s",&element.nome);
  printf("MATRICOLA");
  scanf("%i",&element.matricola);
  k = hash_search_element(element);
    if(k == -1) {
      printf("NON TROVATO\n");
    } else {
      printf("TROVATO IN %i\n",k);
    }
  pause();
}