// htable.cpp by Leo Reyzin. CS112B1 Spring 2003 HW7.

#include<iostream>
#include"htable.h"


HashTable::HashTable()
{
  table = NULL;
  tableSize = 0;
}

HashTable::~HashTable()
{
  int location;
  HashNode *cur, *temp;

  if (table != NULL) {
    for (location = 0; location < tableSize; location++) {
      for (cur = table[location]; cur != NULL;) {
	temp = cur -> next;
	delete cur;
	cur = temp;
      }
    }
  delete [] table;
  }
}

// Initializes the table -- requires before any other operation.
// Size is the desired table size.  Returns true if successful, false
// if out of memory.
bool HashTable::Init(int size)
{
  int location;
  if ((table = new (nothrow) HashNode* [size]) == NULL)
    return false;

  tableSize = size;
  for (location = 0; location < tableSize; location++)
    table[location] = NULL;
  return true;
}


// Inserts the data into the table, keyed by key.  Returns true if successful,
// false if out of memory.
bool HashTable::Insert(string key, int data)
{
  int location;
  HashNode * temp;

  location = Hash(key);
  temp = table[location];
  table[location] = new (nothrow) HashNode (key, data, temp);
  if (table[location]==NULL) {
    table[location]=temp;
    return false;
  }
  return true;
}

// Returns true if key is in the table, false otherwise.  Return the
// associated data via parameter passed in by reference.
bool HashTable::Find(string key, int & data)
{
  int location;
  HashNode * cur;

  location = Hash(key);
  for (cur = table[location]; cur != NULL; cur = cur->next)
    if (cur->key == key) {
      data = cur->data;
      return true;
    }

  return false;
}

// Removes entry with key from the table if it exists.
// Returns true if key is in the table, false otherwise.
bool HashTable::Remove(string key)
{
  int location;
  HashNode * cur, * prev;

  location = Hash(key);

  for (cur = table[location]; cur != NULL; cur = cur->next) {
    if (cur->key == key) {
      if (prev == NULL)
        prev->next = cur->next;
      else
	table[location] = cur->next;
     delete cur;
     return true;
    }
    prev = cur;
  }

  return false;
}

// Returns the hash value of the string.
int HashTable::Hash(string key)
{
  int total=0;
  int i;

  for (i=0; i<key.length(); i++)
    total = (total+key[i]) % tableSize;
  return total;
}

// Returns the number of entries in the table and the average seek time
// (the average number of comparisons) required to find an entry
// that is in the table.  The two values are returned via
// variables passed in by reference.
void HashTable::GiveStats(int & numEntries, double & averageSeek)
{
  int totalDistance=0, entryDistance, location;
  HashNode * cur;

  numEntries = 0;

  for (location = 0; location < tableSize; location++) {
    entryDistance = 0;
    for (cur = table[location]; cur != NULL; cur=cur->next) {
      numEntries++;
      entryDistance++;
      totalDistance += entryDistance;
    }
  }

  averageSeek = ((double)totalDistance)/((double)numEntries);
}


// Pretty prints the whole table -- good for debugging.
void HashTable::Print() 
{
  int location;
  HashNode * cur;

  for (location = 0; location < tableSize; location++) {
    cout << location << ": ";
    for (cur = table[location]; cur != NULL; cur = cur->next) {
      cout << cur->key << ' ' << cur->data;
      if (cur->next!=NULL) {
	cout  << ", ";
      }
    }
    cout << endl;
  }
}

// End of file