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

#define TRUE  1
#define FALSE 0
#define FREI  -1
#define UNGUELTIG  -1

#define n 15
#define p 67
#define m n

int S[n] = {2,5,9,13,20,25,30,51,52,53,54,55,59,61,66};
int hashpos[n];  /* speichert für jeden Schlüssel die Hashposition gegeben
                    durch h */

int T1_bs[n]; /* 2 * b_i^2 */
int T1_d[n];
int T1_a[n];
int T1_b[n];

int T2[10*n];



int main (void)
{
    int a, b;  /* definiert h \in H_1(n) */
    int it1=0, it2=0; /* Anzahl Iterationen, um h bzw. T1 zu finden */
    int sum;
    int i;
    int pos;
    int ok;
    time_t t;
    
    srand((unsigned) time(&t));
    
    /* finde h \in H_1(n) mit Summe(b_i)^2 <= 5n */
    do {
      a = rand() % p;
      b = rand() % p;
      
      for (i=0; i<n; i++)
          T1_bs[i] = 0;

      for (i=0; i<n; i++)
      {
          hashpos[i] = ((a*S[i] + b) % p) % m;
          T1_bs[hashpos[i]]++;
      }
      
      sum = 0;
      for (i=0; i<n; i++)
          sum += T1_bs[hashpos[i]]*T1_bs[hashpos[i]];
      it1++;
      
    } while (sum>5*n);


    /* Initialisierungen - setze T1_bs und T1_d */
    sum = 0;
    for (i=0; i<n; i++)
    {
        T1_a[i] = UNGUELTIG;
        T1_bs[i] = 2 * T1_bs[i] * T1_bs[i];
        T1_d[i] = sum;
        sum += T1_bs[i];
    }

    
    /* Finde für jedes T1[i] die passende Hashfunktion */
    do {
      for (i=0; i<n; i++)
        if (T1_a[i] == UNGUELTIG)
        {
          T1_a[i] = rand() % p;
          T1_b[i] = rand() % p;
        }
      
      ok = TRUE;
      
      for (i=0; i<10*n; i++)
        T2[i] = FREI;
      
      for (i=0; i<n; i++)
        if (T1_a[i] != UNGUELTIG)
        {
          pos = ((T1_a[hashpos[i]] * S[i] + T1_b[hashpos[i]]) % p)
                % T1_bs[hashpos[i]];
          pos += T1_d[hashpos[i]];
		     
          if (T2[pos] != FREI)
          {
              T1_a[hashpos[i]] = UNGUELTIG;
              ok = FALSE;
          }
          else
              T2[pos] = S[i];
        }
      it2++;
      
    } while (!ok);
    
   
    printf ("Input: n=%i, p=%i\n", n, p);

    printf ("Hashfunktion h: a=%i, b=%i\n", a, b);
    printf ("Iterationen für h: %i\n", it1);
    
    printf ("\nT1:  bi  2bi^2     di      a      b\n");
    for (i=0; i<n; i++)
        printf ("%7i %6i %6i %6i %6i\n", (int) sqrt (T1_bs[i]/2),
                T1_bs[i], T1_d[i], T1_a[i], T1_b[i]);
    printf ("Iterationen für T1: %i\n", it2);
    
    printf ("\nT2:   i    S[]\n");
    for (i=0; i<10*n; i++)
      if (T2[i] != -1)
        printf ("%7i %6i\n", i, T2[i]);
}