#ifndef __HASH
#define __HASH

#include <iostream>

// Simple Exception Class Example
class HashException {
  string msg;

 public:
  HashException () { msg = "Hash Exception"; }
  HashException (const char* s) { msg = s; }
  HashException (const string s) { msg = s; }

  virtual string getMsg () const { return msg; }

};

// Node used for defining the hash internal array
template <class K, class D>
class __HashNode {
 public:
  unsigned short used;
  K key;
  D data;

  // Default Constructor
  __HashNode () { used = 0; }

  // Helper Operators
  friend bool operator < (const __HashNode& p1, const __HashNode& p2)
    { return p1.key < p2.key; }
  friend bool operator > (const __HashNode& p1, const __HashNode& p2)
    { return p1.key > p2.key; }
  friend bool operator <= (const __HashNode& p1, const __HashNode& p2)
    { return p1.key < p2.key; }
  friend bool operator >= (const __HashNode& p1, const __HashNode& p2)
    { return p1.key >= p2.key; }
  friend bool operator == (const __HashNode& p1, const __HashNode& p2)
    { return p1.key == p2.key; }
};


// Hash Class Definition
// Implementation: Open Addressing, Linear Probing
template <class K, class D>
class Hash {
  long crtSize, crtUsed;
  __HashNode<K, D> *table;

  // Hash Function
  long hash (const string s) const
    { 
      long v = 0;
      for (int i = 0; i < s.length (); i++)
	v  = (v << 5) + s[i];
      return v; 
    }

 public:
  // Constructors and Destructors
  Hash ();
  Hash (const long Size);
  ~Hash ();

  // Hash Methods
  virtual void Insert (const K key, const D data);
  virtual void Delete (const K key);
  virtual D& Lookup (const K key) const;

  // Friendly operator for checking the content
  friend ostream& operator << (ostream& out, const Hash& h)
    { return out; }

};

// Constructors
template <class K, class D>
Hash<K,D>::Hash ()
{
  crtUsed = 0; crtSize = 100;
  table = new __HashNode<K,D> [crtSize];
}

template <class K, class D>
Hash<K,D>::Hash (const long Size)
{
  crtUsed = 0; crtSize = Size;
  table = new __HashNode<K,D> [crtSize];
}

// Destructors
template <class K, class D>
Hash<K,D>::~Hash ()
{
  delete [] table;
}

// Insertion
template <class K, class D>
void Hash<K,D>::Insert (const K key, const D data)
{
  if (crtUsed < crtSize)
    {
      crtUsed++;
      long v = hash (key) % crtSize;
      for (; table[v].used == 1; v = (v+1) % crtSize);
      table[v].used = 1;
      table[v].key = key;
      table[v].data = data;
    }
  else
    {
      throw HashException ("Hash is full");
    }
}

// Deletion
template <class K, class D>
void Hash<K,D>::Delete (const K key)
{
  long v = hash (key) % crtSize;

  // Search for the key position
  for (long vs = v; 
       (table[v].used == 1) && (table[v].key != key); 
       v = (v+1) % crtSize)
    if ((v+1) % crtSize == vs)
      throw HashException (key + ": key not found");
  // Mark it as deleted
  if (table[v].used == 1)
    {
      table[v].used = 2;
      crtUsed--;
    }
  else
    {
      throw HashException (key + ": key not found");
    }
}

// Lookup
template <class K, class D>
D& Hash<K,D>::Lookup (const K key) const 
{
  long v = hash (key) % crtSize; 

  // Search for the key position
  for (long vs = v; 
       (table[v].used == 1) && (table[v].key != key); 
       v = (v+1) % crtSize)
    if ((v+1) % crtSize == vs)
      throw HashException (key + ": key not found");
  if (table[v].used == 1)
    {
      return table[v].data;
    }
  else
    {
      throw HashException (key + ": key not found");
    }
}


#endif // __HASH