// htable.h by Leo Reyzin CS 112B1 Spring 2003 HW 7
#include<string>

using namespace std;

// The linked list node
struct HashNode {
  HashNode() {next=NULL;}
  HashNode(string & newKey, int newData, HashNode * newNext)
    {key=newKey; data=newData; next=newNext;}

  string key;
  int data;
  HashNode * next;
};


class HashTable {

 public:
  HashTable();
  ~HashTable();

  // Initializes the table -- requires before any other operation.
  // Size is the desired table size.  Returns true if successful, false
  // if out of memory.
  bool Init(int size);

  // Inserts the data into the table, keyed by key.  Returns true
  // if successful, false if out of memory.
  bool Insert(string key, int data);

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

  // Removes entry with key from the table if it exists.
  // Returns true if key is in the table, false otherwise.
  bool Remove(string key);

  // 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 GiveStats(int & numEntries, double & averageSeek);

  // Pretty prints the whole table -- good for debugging.
  void Print();

 private:
  // Returns the hash value of the string.
  int Hash(string key);

  // The table of linked lists -- allocated in Init
  HashNode ** table;

  // The size of the above table
  int tableSize;
};