#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <math.h>
#include "MyTime.h"

#include "PerfectHash.h"
#include "LinearHash.h"
#include "QuadraticHash.h"
#include "DoubleHash.h"
#include "ListHash.h"

#define NUMWORDS  15338
#define TABLESIZE NUMWORDS

int key_String(char *string) {                  

/*
  These are alternative key generators.  They are very poor choices however, since they result
  in statistical anomolies and cannot be analyzed outside of the scope of a particular
  language and platform.

  return abs((int)string);
  return abs((int)(string)*strlen(string));
*/

// An excellent string key generator.
  int h = 0;
  int off = 0;
  char *val = string;
  int len = strlen(string);

// This did not create any duplicate keys
  for (int i = len ; i > 0; i--)
    h = (h * 37) + val[off++];

/* This resulted in duplicate keys!!!
  if (len < 16) {
    for (int i = len ; i > 0; i--) {
      h = (h * 37) + val[off++];
    }
  } else {
    // only sample some characters
    int skip = len / 16;
    for (int i = len ; i > 0; i -= skip, off += skip) {
      h = (h * 39) + val[off];
    }
  }
*/
  return abs(h);
}

//
// Select a particular type of hash table to test
//
HashTable * selectTable() {
  char  choice;
  float sizeFactor;

  cout << "CMSC441 Hash table test bed.  Select hash table:" << endl;
  cout << "  1] Linear Probing"    << endl;
  cout << "  2] Quadratic Probing" << endl;
  cout << "  3] Double Hash"       << endl;
  cout << "  4] Chaining"          << endl;
  cout << "  5] Perfect Hashing "  << endl;
  cout << ">";
  cin >> choice;
  cout << "  Table size factor: " << endl;
  cout << ">";
  cin >> sizeFactor;

  int size = (int) TABLESIZE * sizeFactor;

  switch(choice) {
    case '1': return new LinearHash(size);
    case '2': return new QuadraticHash(size);
    case '3': return new DoubleHash(size);
    case '4': return new ListHash(size);
    case '5': return new PerfectHash(size);
    default:  return NULL;
  }
}

//
// Load the test data set
//
int LoadTestSet(Object *&testSet, int *&keySet) {
// Open sample data file, allocate memory
  ifstream dataset("hashkeys2.txt");
  testSet = new Object[NUMWORDS];
  keySet  = new int   [NUMWORDS];

  char word[500];
  int  len,n = 0;

// Load all keys in data file
  while  (dataset.is_open() && !dataset.eof() && n<NUMWORDS) {
    dataset.getline(word,sizeof(word)-1);              // Read key
    if ((len = strlen(word)) > 0) {                    // Valid key?
      testSet[n] = (Object)new char[len+1];            // Copy into object array
      strcpy((char *)testSet[n],word); 
      keySet[n] = key_String(word);                    // Compute its key
      n++;
    }
  }
  return n;
}

//
// Main test routine
//
int main() {
  Object    *testSet;
  int       *keySet;
  HashTable *hash;
  int        testNum;
  MyTime     start, doneInsert, doneSearch;

// Select hash table
  hash    = selectTable();
  if (hash==NULL) return 1;

// Load objects into array
  cout << "Loading..." << endl;
  testNum = LoadTestSet(testSet, keySet);
  cout << "Loaded " << testNum << " hash objects" 
       << endl;

  start = GetMyTime();

// Add all objects
  for (int n=0; n<testNum; n++) {
 //   cout << "Insert: n = " << n << endl;
    hash->Insert(keySet[n], testSet[n]);
  }

  doneInsert = GetMyTime();

// Search for all objects
  Object search;
  for (n=0; n<testNum; n++) {
    search = (char *)hash->Search(keySet[n]);
    if (search==NULL) ;
 //     cout << "Failure on " << n << ": " << testSet[n] << " = " << keySet[n] << endl;
  }

  doneSearch = GetMyTime();

  hash->PrintStats();
  cout << "Insertion time: " << (double)(doneInsert - start)      / GetMyAccuracy() << endl;
  cout << "Search time:    " << (double)(doneSearch - doneInsert) / GetMyAccuracy() << endl;
  return 0;
}