/*
 * Arquivo para teste do número de colisões utilizando folding.
 */

#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() {
  Tabela tab;
  FILE *f;
  RA ra;

  cria_tabela(&tab, 297);

  f = fopen("ra.txt", "r");
  while (fscanf(f, "%d", &ra)!= EOF) {
    int p1 = ra % 100; 
    int p2 = (ra % 10000)/ 100;
    int p3 = ra / 10000;
    int h = p1 + p2 + p3;
    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() {
  teste();

  return 0;
}