/*
 * Arquivo para teste do número de colisões utilizando o resto
 * da divisão pelo tamanho da tabela.
 */

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

typedef int RA;

typedef struct tabela {
  int tam;  
  int* v;  /* Vetor para verificar o número de colisões.
             v[i] = número de elementos tais que h(x) == i */
} Tabela;

void cria_tabela(Tabela *ap_tab, int tam) {
  ap_tab->v = calloc(tam, sizeof(int));
  ap_tab->tam = tam;
}

void destroi_tabela(Tabela *ap_tab) {
  free(ap_tab->v);
}

void teste(int tam) {
  Tabela tab;
  FILE *f;
  RA ra;

  cria_tabela(&tab, tam);

  f = fopen("ra.txt", "r");
  while (fscanf(f, "%d", &ra)!= EOF) {
    int h = ra % tam;
    tab.v[h]++;
  }
  
  int i, colisoes = 0;
  for (i = 0; i < tab.tam; i++)
    if (tab.v[i] > 1)
      colisoes += tab.v[i] - 1;

  printf("Número de colisões: %d\n ", colisoes);

  destroi_tabela(&tab);
}

int main() {
  printf("Mod 64: \n");
  teste(64);

  printf("Mod 128: \n");
  teste(128);

  printf("Mod 100: \n");
  teste(100);

  printf("Mod 1000: \n");
  teste(1000);

  printf("Mod 101: \n");
  teste(101);

  printf("Mod 2001: \n");
  teste(2001);
  
  return 0;
}