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

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

// Allocate table data
  N = size;
  keys = new std::list[N];
  data = new std::list[N];
}


//
// Generic hash function H(key) = key mod N.
//
int ListHash::H(Key key) {
  return abs(key) % N;
};


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

  int pos = H(key);
  std::list   ::iterator keyI = keys[pos].begin();
  std::list::iterator objI = data[pos].begin();

  while (keyI != keys[pos].end()) {
    #ifdef HASH_DEBUG
      cout << "Found (" << key << "/" << *keyI << "," << *objI << ") at " << pos << endl;
    #endif
    if (*keyI == key)
      return *objI;
    ++keyI;
    ++objI;
    sSteps++;
  }
  #ifdef HASH_DEBUG
    cout << "Lost " << key << " at " << pos << endl;
  #endif

  return NULL;
}


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

  int pos = H(key);
  keys[pos].insert(keys[pos].end(), key);
  data[pos].insert(data[pos].end(), obj);
  if (keys[pos].size()>1) 
    collisions++;
  #ifdef HASH_DEBUG
    cout << "Inserted (" << key << "," << obj << ") at " << pos << " link " << keys[pos].size() << endl;
  #endif
}

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

  int len = 0;
  for (int i=0; ifloat)len/N << endl;
}