#include "LinearHash.h"
#include <assert.h>
#include <memory.h>
#include <iostream.h>

#define EMPTY_KEY  (-1)

//
// Constructor requires size of table
//
LinearHash::LinearHash(int size) {
  iSteps = sSteps = collisions = insertions = searches = 0;

// Allocate table data
  N = size;
  keys = new Key[N];       memset(keys,EMPTY_KEY,sizeof(Key)*N);
  data = new Object[N];    memset(data,        0,sizeof(Object)*N);
}


//
// Generic hash function for linear hashing H(key,index,c) = (k + ci) mod N.
//
#define c ((N/3)+1)
int LinearHash::H(Key key, int index) {
  return abs(key + c*index) % N;
};


//
// Return the element with the specified key 
//
Object LinearHash::Search(Key key) {
  searches++;

  int pos;

  for (int i=0; i < N; i++) {
    sSteps++;
    pos = H(key,i);

    if (keys[pos] == key) {
      #ifdef HASH_DEBUG
        cout << "Found (" << key << "," << data[pos] << ") at " << pos << endl;
      #endif
      return data[pos];
    }

    if (keys[pos] == EMPTY_KEY)
      break;
  }

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


//
//  Insert an untyped element into the hash table
//
void LinearHash::Insert(Key key, Object obj) {
  insertions++;

  for (int i=0; i<N; i++) {
    iSteps++;
    int pos = H(key,i);
    if (keys[pos] == -1) {
      #ifdef HASH_DEBUG
        cout << "Inserted (" << key << "," << data << ") at " << pos << endl;
      #endif
      keys[pos] = key;
      data[pos] = obj;
      if (i>0)
        collisions++;
      return;
    }
  }
}

//
// Print statistical information on hash table run
//
void LinearHash::PrintStats() {
  cout << "Statistics for class LinearHash(" << N << "): " << endl;
  cout << "  insertions: " << insertions 
       << ", collisions = " << collisions << "(" << collisions*100/insertions  << "%)" 
       << ", iSteps = " << iSteps << "(average = " << (float)iSteps/collisions << ")"  << endl 
       << "  searches = " << searches
       << ", sSteps = " << sSteps << "(average = " << (float)sSteps/searches << ")" 
       << endl;
}