/*
 * Arquivo para teste do número de colisões utilizando 
 * a função midsquare (simplificada pois as chaves são inteiros).

 * Use o comando p/t no gdb para ver valores em binário.
 */

#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 bit_inicial, int nbits) {
  Tabela tab;
  FILE *f;
  RA ra;

  cria_tabela(&tab, 1 << nbits);

  f = fopen("ra.txt", "r");
  while (fscanf(f, "%d", &ra)!= EOF) {
    int h = (ra * ra);
    int masc = (1 << nbits) - 1;
    h = h >> (bit_inicial - nbits + 1);
    h = h & masc;
    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("Bit inicial: 16 - Número de bits: 47 \n");
  teste(16, 7);

  return 0;
}