#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_

template <class KEY, class DATA> class HashTable;

template <class KEY, class DATA>
class HashEntry {

  friend class HashTable<KEY, DATA>;

  KEY _key;
  DATA _data;
  HashEntry<KEY, DATA> *_next;

public:

  KEY getKey(void);
  DATA getData(void);
  HashEntry<KEY, DATA>* getNext(void);
};



template <class KEY, class DATA>
class HashTable {

public:

  // The first argument is the table size.  The second returns
  // a hash value for the given key; this does not need to be
  // mod size because the table performs this operation automatically.
  // The final argument is a function which returns true iff two
  // keys are equal.
  HashTable(int size, int (*hash_fn)(KEY), int (*key_eq)(KEY,KEY));
  ~HashTable();

  // Returns the size of the hashtable
  int size(void);

  // Returns the number of elements in the HashTable
  int numElements(void);

  // This function attempts to find the given key in the table.
  // If it is found and data_out is non-null, the data associated
  // with the key is placed in data_out, and true is returned.
  // If the data is not found, false is returned.  If the key is
  // in the table multiple times, a random occurrence is returned.
  int find(KEY key, DATA *data_out);
  
  // This function returns the list of HashEntries associated with
  // a particular key.  This is a peculiar operation, only necessary
  // for implementing hash-join.  It would not be in a typical
  // hash table implementation.  
  HashEntry<KEY, DATA> *getBucket(KEY key);

  // This function inserts a key, data pair into the table.  Note
  // that if the key is non-unique, find may behave badly.
  // Cf.  "Hash Tables Behaving Badly", the failed NBC sitcom.
  void insert(KEY key, DATA data);

private:

  HashEntry<KEY, DATA>** _table;
  int _size, _numElts;
  int (*_hashFn)(KEY);
  int (*_eqFn)(KEY,KEY);
};


#endif