//
// CS251 Data Structures
// Hash Table template
//
#include <assert.h>
#include <stdlib.h>
#include <string.h>
///////////////////////////////////////////
//
// Class that defines a template for a hash table
// The keys are of type const char * and the data
// can be any type.
//
// Use like this:
//  HashTable hashTableInt<int>;
//
//
///////////////////////////////////////////
// Each hash entry stores a key, object pair
template <typename Data>
struct HashTableEntry {
  const char * _key;
  Data _data;
  HashTableEntry * _next;
};
 
// This is a Hash table that maps string keys to objects of type Data
template <typename Data>
class HashTable {
 public:
  // Number of buckets
  enum { TableSize = 2039};
  // Array of the hash buckets.
  HashTableEntry<Data> **_buckets;
 
  // Obtain the hash code of a key
  int hash(const char * key);
 public:
  HashTable();
 
  // Add a record to the hash table. Returns true if key already exists.
  // Substitute content if key already exists.
  bool insertItem( const char * key, Data data);
 
  // Find a key in the dictionary and place in "data" the corresponding \
record
  // Returns false if key is does not exist
  bool find( const char * key, Data * data);
 
// Removes an element in the hash table. Return false if key does not 
//exist.
  bool removeElement(const char * key);
};
 
template <typename Data>
int HashTable<Data>::hash(const char * key)
{
  // TODO: Compute the hash number from the key string
  return (int)key;
}
 
template <typename Data>
HashTable<Data>::HashTable()
{
  // TODO: Initialize the hash table
}
 
template <typename Data>
bool HashTable<Data>::insertItem( const char * key, Data data)
{
  // TODO: Insert a key,data pair inside the hash table.
  // Return true if the entry already exists or false if
  // it does not exist.
  return false;
}
 
template <typename Data>
bool HashTable<Data>::find( const char * key, Data * data)
{
  // TODO: Find the data associated to a key. The data is
  // stored in the *data passed as parameter.
  // Return true if the entry is found or false otherwise.
  return false;
}
 
template <typename Data>
bool HashTable<Data>::removeElement(const char * key)
{
  // TODO: Remove the element that has this key from the hash table.
  // Return true if the entry is found or false otherwise.
  return false;
}
/////////////////////////////////////
//
// Class used to iterate over the hash table
//
/////////////////////////////////////
 
template <typename Data>
class HashTableIterator {
  int _currentBucket; // Current bucket that is being iterated
  HashTableEntry<Data> *_currentEntry; // Current entry iterated
  HashTable<Data> * _hashTable;  // Pointer to the hash table being iterated
 public:
  HashTableIterator(HashTable<Data> * hashTable);
  bool next(const char * & key, Data & data);
};
 
template <typename Data>
HashTableIterator<Data>::HashTableIterator(HashTable<Data> * hashTable)
{
  // TODO: Initialize iterator. "hashTable" is the table to be iterated.
}
 
template <typename Data>
bool HashTableIterator<Data>::next(const char * & key, Data & data)
{
  // TODO: Returns the next element in the hash table.
  // The key and data values are stored in the references passed
  // as argument. It returns true if there are more entries or
  // false otherwise.
  return false;
}

 
 
//
// CS251 Data Structures
// Hash Table template
//
#include <assert.h>
#include <stdlib.h>
#include <string.h>
///////////////////////////////////////////
//
// Class that defines a template for a hash table
// The keys are of type const char * and the data
// can be any type.
//
// Use like this:
//  HashTable hashTableInt<int>;
//
//
///////////////////////////////////////////
 
// Each hash entry stores a key, object pair
template <typename Data>
struct HashTableEntry {
  const char * _key;
  Data _data;
  HashTableEntry * _next;
};
 
// This is a Hash table that maps string keys to objects of type Data
template <typename Data>
class HashTable {
 public:
  // Number of buckets
  enum { TableSize = 2039};
 
  // Array of the hash buckets.
  HashTableEntry<Data> **_buckets;
 
  // Obtain the hash code of a key
  int hash(const char * key);
 
 public:
  HashTable();
  // Add a record to the hash table. Returns true if key already exists.
  // Substitute content if key already exists.
  bool insertItem( const char * key, Data data);
 
 
  // Find a key in the dictionary and place in "data" the corresponding record
  // Returns false if key is does not exist
  bool find( const char * key, Data * data);
  // Removes an element in the hash table. Return false if key does not exist.
  bool removeElement(const char * key);
};
 
template <typename Data>
int HashTable<Data>::hash(const char * key)
{
  // TODO: Compute the hash number from the key string
  int sum=0;
  int len = strlen(key);
  for(int i=0; i < len; i++)
  {
    sum = sum + key[i];
  }
  return sum % TableSize;
}
 
 
template <typename Data>
HashTable<Data>::HashTable()
{
  // TODO: Initialize the hash table
  _buckets = new HashTableEntry<Data> * [TableSize];
  for(int i=0; i < TableSize; i++)
  {
    _buckets[i] = NULL;
  }
}
 
template <typename Data>
bool HashTable<Data>::insertItem( const char * key, Data data)
{
  // TODO: Insert a key,data pair inside the hash table.
  // Return true if the entry already exists or false if
  // it does not exist.
  int i = hash(key);
  HashTableEntry<Data> *e = _buckets[i];
 
  while(e != NULL && strcmp(key, e->_key) != 0)
  {
    e = e->_next;
  }
 
  if(e != NULL)
  {
    //key exists
    e->_data = data;
    return true;
  }
 
  //key does not exist
  e = new HashTableEntry<Data>;
  assert(e != NULL);
 
  e->_key = key;
  e->_data = data; //add entry to beg. of list
  e->_next = _buckets[i];
  _buckets[i] = e;
  return false;
}
 
 
template <typename Data>
bool HashTable<Data>::find( const char * key, Data * data)
{
  // TODO: Find the data associated to a key. The data is
  // stored in the *data passed as parameter.
  // Return true if the entry is found or false otherwise.
  int i = hash(key);
  HashTableEntry<Data> *e = _buckets[i];
 
  while(e != NULL && strcmp(key, e->_key) != 0)
  {
    e = e->_next;
  }
 
  //key is found
  if(e != NULL)
  {
    *data = e->_data;
    return true;
  }
 
  //key was not found
  return false;
}
 
template <typename Data>
bool HashTable<Data>::removeElement(const char * key)
{
  // TODO: Remove the element that has this key from the hash table.
  // Return true if the entry is found or false otherwise.
  int i = hash(key);
  HashTableEntry<Data> *eC = _buckets[i];
  HashTableEntry<Data> *eP = NULL;
 
  while(eC != NULL && strcmp(key, eC->_key) != 0)
  {
    eP = eC;
    eC = eC->_next;
  }
 
  //key is found
  if(eC != NULL)
  {
    if(eP != NULL)
      eP->_next = eC->_next;
    else
      _buckets[i] = eC->_next;
    return true;
  }
 
  //key is not found
  return false;
}
 
 
/////////////////////////////////////
//
// Class used to iterate over the hash table
//
/////////////////////////////////////
template <typename Data>
class HashTableIterator {
  int _currentBucket; // Current bucket that is being iterated
  HashTableEntry<Data> *_currentEntry; // Current entry iterated
  HashTable<Data> * _hashTable;  // Pointer to the hash table being iterated
 public:
  HashTableIterator(HashTable<Data> * hashTable);
  bool next(const char * & key, Data & data);
};
 
template <typename Data>
HashTableIterator<Data>::HashTableIterator(HashTable<Data> * hashTable)
{
  // TODO: Initialize iterator. "hashTable" is the table to be iterated.
   _hashTable =  hashTable;
}
 
template <typename Data>
bool HashTableIterator<Data>::next(const char * & key, Data & data)
{
  // TODO: Returns the next element in the hash table.
  // The key and data values are stored in the references passed
  // as argument. It returns true if there are more entries or
  // false otherwise.
  return false;
}