#include "PerfectHash.h"
#include <iostream.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>

#define RAND_METHOD
//#define HASH_DEBUG

#if defined DIV_METHOD

//
// Hash function H(m,i,k) = (k mod 2i + 100r + 1) mod r.
// Division method
//
inline int PerfectHash::H(int i, int k, int r) {
  return abs(k % (2*i + 100*r + 1)) % r;
};

#elif defined MULT_METHOD

//
// Hash function H(m,i,k) = frac(k(Ar + Bi + C)) * r
// Multiplication method
//
inline int PerfectHash::H(int i, int k, int r) {
  return abs(frac(k * (3.14159*i + 2.71828*r + 0.618339887)) * r);
};

#elif defined REC_METHOD

//
// Hash function H(m,i,k) = floor(A/(B*k + C*i)) mod r
// Reciprocal method
//
#define MAXINT (0x7FFFFFFF*1.0)

inline int PerfectHash::H(int i, int k, int r) {
// Experimenting
  double bob = floor(MAXINT*MAXINT / (double)((k+100*r+2*i)));
  return abs((int)bob % r);
};

#elif defined RAND_METHOD

//
// Hash function H(m,i,k) = srand(k + r*100), Ei(rand())
// Random method
//
inline int PerfectHash::H(int i, int k, int r) {
  srand(k + r*100);
  for (int z=0; z < i; z++)
    rand();
  return rand() % r;
};

#else
  #error No hash method defined
#endif


//
// Constructor requires size of table
//
PerfectHash::PerfectHash(int size) {
  insertions = collisions = moves = guesses = 0;
  freeslottime = 0;
  first = 0;

  s = size;
  N = size;

// Header is lookup into table
  Hp = new int[s];    memset(Hp,0,sizeof(int)*s);
  Hi = new int[s];    memset(Hi,0,sizeof(int)*s);
  Hr = new int[s];    memset(Hr,0,sizeof(int)*s);
// Standard hash table of size N
  Dk = new int[N];    memset(Dk,0,sizeof(int)*N);
  Dd = new Object[N]; memset(Dd,0,sizeof(Object)*N);

  srand(time(NULL));                // Needed for insert
}

//
// Return the element with the specified key 
//
Object PerfectHash::Search(Key key) {
  int x = key % s;
  if (Hr[x]==0)
    return NULL;
  int y = Hp[x] + H(Hi[x],key,Hr[x]);
  if (Dk[y] == key) {
    #ifdef HASH_DEBUG
      cout << "Found (" << key << "," << Dd[y] << ") at " << y << endl;
    #endif
    return Dd[y];
  }

  #ifdef HASH_DEBUG
    cout << "Lost " << key << " at " << x << endl;
  #endif
  return NULL;
}

//
// Find the index of any set of amount free slots in D
// This is very inefficient - it simply does a linear scan
// An optimal method might by a list of free blocks
//
int PerfectHash::FreeSlots(int amount) {
  int freeCount = 0, pos = 0;
  MyTime temp  = GetMyTime();

// Find first free block
  for (pos=first; pos<N && Dd[pos]!=NULL; pos++) ;
  first = pos;

// Find contiguous space
  for (; pos<N; pos++) {
    if (Dd[pos] == NULL) {
      freeCount++;
      if (freeCount == amount) {
        freeslottime+=(GetMyTime() - temp);
        return pos-amount+1;
      }
    } else
      freeCount = 0;
  }

  freeslottime+=(GetMyTime() - temp);
  return -1;
}


//
//  Insert an untyped element into the hash table
//
void PerfectHash::Insert(Key key, Object data) {
  int x = key % s;
  insertions++;

  if (Hr[x] == 0)  {
    int y = FreeSlots(1);
    if (y<0) return;
    assert(y>=0);
    Hp[x] = y;
    Hi[x] = 0;
    Hr[x] = 1;
    Dk[y] = key;
    Dd[y] = data;
    #ifdef HASH_DEBUG
      cout << "Inserted (" << key << "," << data << ") at " << y << endl;
    #endif
  } else {
    int  m, r, p, uniqueM;
    char temp_input;

    r = Hr[x];
    p = Hp[x];
    #ifdef HASH_DEBUG
        cout << "Inserting (" << key << "," << data << ") at " << x << endl;
        cout << "Insertion " << insertions << " just got complicated..." << (char *)data << endl;
    #endif
    collisions++;

    m = 1;
    do {
      m++;
      uniqueM = TRUE;
      guesses++;

      #ifdef HASH_DEBUG
        cout << "  Trying m = " << m << ", test = " << H(m,key,r+1) << ", r = " << r << endl;
      #endif

      for (int j=0; j<r && uniqueM; j++)
        if (Dk[p+j] == key) {
          cout << "FATAL ERROR: Duplicate keys!: " << (char *)data << "," << (char *)Search(key) << endl;
          cin >> temp_input;
        } else
        if (H(m,Dk[p+j],r+1) == H(m,key,r+1)) {
          uniqueM = FALSE;
          #ifdef HASH_DEBUG
            cout << "    Initial collide " << Dk[p+j] << "," << key << ";" << H(m,Dk[p+j],r+1) << "," <<  H(m,key,r+1) << endl;
          #endif
        } else
          for (int z=0; z<j && uniqueM; z++)
            if (H(m,Dk[p+j],r+1) == H(m,Dk[p+z],r+1)) {
              uniqueM = FALSE;
              #ifdef HASH_DEBUG
                cout << "   Collide " << Dk[p+j] << "," << Dk[p+z] << ";" << H(m,Dk[p+j],r+1) << "," <<  H(m,Dk[p+z],r+1) << endl;
              #endif
            }
    } while (!uniqueM);

    #ifdef HASH_DEBUG
      cout << "  Success: m = " << m << endl;
    #endif

    int y = FreeSlots(r+1);
    if (y<0) return;
    assert(y>=0);
    #ifdef HASH_DEBUG
      cout << "  new element inserted at " << y + H(m,key,r+1)<< endl;
    #endif

    Hp[x] = y;
    Hi[x] = m;
    Hr[x] = r+1;
    Dk[y + H(m,key,r+1)] = key;
    Dd[y + H(m,key,r+1)] = data;
    for (int j=0; j<r; j++) {
      int offset = y + H(m,Dk[p+j],r+1);

      #ifdef HASH_DEBUG
        cout << "  element " << p+j << " moved to " << y << " + " << offset-y << " = " << offset << endl;
      #endif
      moves++;

      Dk[offset] = Dk[p+j];
      Dd[offset] = Dd[p+j];
      Dd[p+j] = NULL;
      if (first > p+j)
        first = p+j;
    }
  }
}

//
// Print statistical information on hash table run
//
void PerfectHash::PrintStats() {
  cout << "Statistics for class PerfectHash(" << s << ", " << N << ")";

#if defined DIV_METHOD
  cout << " - Division method" << endl;
#elif defined MULT_METHOD
  cout << " - Multiplication method" << endl;
#elif defined REC_METHOD
  cout << " - Reciprocal method" << endl;
#elif defined RAND_METHOD
  cout << " - Random method" << endl;
#endif

  cout << "  insertions: " << insertions 
       << ", collisions = " << collisions << "(" << collisions*100/insertions  << "%)"
       << ", moves = " << moves << "(average = " << (float)moves/collisions+1.0 << ")" 
       << endl
       << "  guesses = " << guesses << "(average = " << (float)guesses/collisions << ")"
       << ", allocation time:" << (double) freeslottime / 1000
       << endl;

// Compute average R and largest R
  int maxR=0; int totalR=0;
  for (int i=0; i<s; i++) {
    totalR+=Hr[i];
    if (Hr[i]>maxR)
      maxR = Hr[i];
  }

  cout << "Statistics on R: " << endl
       << "  Average: " << (double)totalR/s << ", Largest = " << maxR
       << endl;

}