#include <stdio.h>

#define TABSIZE 17
#define TABSIZELESS1 (TABSIZE - 1)

int hash[TABSIZE];
int n;

int hashfunction(int key)
{
return (key % TABSIZE);
}

int increment(int key)
{
int work;

work = (key / TABSIZE) % TABSIZE;
if (!work)
  work = 1;
return work;
}

void initTable()
{
int i;
n = 0;
for (i=0;i<TABSIZE;i++)
  hash[i] = (-1);
}

void insert (int keyNew, int r[])
{
int i, ii, inc, init, j, jj, keyOld;

init = hashfunction(keyNew);
inc = increment(keyNew);
for (i=0;i<=TABSIZE;i++)
{
  printf("trying to add just %d to total of probe lengths\n",i+1);
  for (j=i;j>=0;j--)
  {
    jj = (init + inc * j) % TABSIZE;
    keyOld = r[jj];
    ii = (jj + increment(keyOld) * (i - j)) % TABSIZE;
    printf("i=%d j=%d jj=%d ii=%d\n",i,j,jj,ii);
    if (r[ii] == (-1))
    {
      r[ii] = keyOld;
      r[jj] = keyNew;
      n++;
      return;
    }
  }
}
}

void doInserts()
{
int key;
int i, j, k;
int probelengthtotal;
for (k=1;k<=TABSIZE;k++)
{
  scanf("%d",&key);
  insert(key, hash);
  printf("hash=%d increment=%d\n",hashfunction(key),increment(key));
  for (i=0;i<TABSIZE;i++)
    printf("%d %d\n",i, hash[i]);
  probelengthtotal = 0;
  for (i=0;i<=TABSIZELESS1;i++)
    if (hash[i] > (-1))
    {
      j = hashfunction(hash[i]);
      probelengthtotal++;
      while (i != j)
      {
        j = (j + increment(hash[i])) % TABSIZE;
        probelengthtotal++;
      }
    }
  printf("probelengthtotal=%d expected=%f\n",probelengthtotal,
    ((float)probelengthtotal)/n);
}
}

main()
{
initTable();
doInserts();
}