#include <math.h>
#include <iostream.h>
#include <stdlib.h>

typedef long key ;
typedef int index ;

enum result {found, notfound} ;

enum state {busy, finished} ;

key empty = -1 ;

long collision; 

// -------------------------------------------------------------

/*
inline index hash(key k, index nstar) // Erste Hash-Funktion
{return (k%nstar) ; }  
*/

// -------------------------------------------------------------

inline index hash(key k, index nstar) // Zweite Hash-Funktion
{ double A=0.5*(sqrt(5)-1) ;
return (index) floor(nstar*(k*A-floor(k*A))) ; }  

// -------------------------------------------------------------

inline index coll(index s, index nstar, index ell ) // Erste Koll.-Auflösung
{
   index a=6543  ;
   collision++ ;
   return ( (s+(ell+1)*a)%nstar) ;
}

// -------------------------------------------------------------

/*
inline index coll(index s, index nstar, key x ) // Zweite Koll.-Auflösung
{
   collision++ ;
   return ( (  s+(x%(nstar-1)+1))%nstar) ;
}
*/

// -------------------------------------------------------------

void hash_placement(key *f, index nstar, key k)
{
   result freeplace = notfound ;
   index s = hash(k,nstar) ;
   index s0 = s ;
   state search = busy ;
   index ell = 0 ;

   while ( (freeplace==notfound) && (search==busy) )
   {
      if (f[s]==empty) freeplace = found ;
      else
      { s = coll(s, nstar, ell); ell++; }   //erste Koll.-Aufloesun
      // { s = coll(s, nstar, k); }        //zweite Koll.-Aufloesung
      if (s==s0) search = finished ;
   }
   if (freeplace==found) f[s] = k ;
}

// -------------------------------------------------------------

int main(int argc, char* argv[])
{
   index n = atoi(argv[1]) ;
   int wieoft = atoi(argv[2]), experimente ;
   long *coll_acc ;
   const index nstar = 1007 ;
   index i ;
   
   key *Tabelle ;
   
   Tabelle = (key *) malloc (nstar * sizeof(key)) ;
   
   coll_acc = (long *) malloc(n*sizeof(long)) ;

   for (i=0; i<n ; i++) coll_acc[i] = 0 ;

   for (experimente=0; experimente<wieoft ; experimente++)
   {
      for (i=0; i<nstar ; i++) Tabelle[i] = empty ;

      collision = 0 ;

      for (i=0; i<n ; i++)
      {
         hash_placement(Tabelle, nstar, random()) ;
         coll_acc[i] +=  collision ; collision = 0 ;
      }
   }

   for (i=0; i<n ; i++)
      coll_acc[i] += coll_acc[i-1] ;
   
   cout << "L[3] := [ [0,0]\n" ;
   for (i=0; i<n ; i++)
      cout << ",[" << i+1 << "," << coll_acc[i] << "/" << wieoft << "]\n" ;
   cout << "] ;\n" ;

   // for (i=0; i<nstar ; i++) cout << Tabelle[i]  << "\n" ;

}