//------------------------------------------------
// Edit 27 Jan 2003 DLF namespace std for g++ v3.2
//------------------------------------------------

#ifndef _QUADRATIC_PROBING_H_
#define _QUADRATIC_PROBING_H_

#include <vector>
#include <string>
using namespace std;


// QuadraticProbing Hash table class
//
// CONSTRUCTION: an initialization for ITEM_NOT_FOUND
//               and an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Hashable find( x )     --> Return item that matches x
// void makeEmpty( )      --> Remove all items

template <class HashedObj>
class HashTable
{
   public:
      explicit HashTable( const HashedObj & notFound, int size = 101 );
      HashTable( const HashTable & rhs )
	 : ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND ),
	   array( rhs.array ), currentSize( rhs.currentSize ) { }
      
      const HashedObj & find( const HashedObj & x );
      
      void makeEmpty( );
      void insert( const HashedObj & x );
      void remove( const HashedObj & x );
      void printStats( );
      
      const HashTable & operator=( const HashTable & rhs );
      
      enum EntryType { ACTIVE, EMPTY, DELETED };
      
   private:
      struct HashEntry
      {
	    HashedObj element;
	    EntryType info;
	    
	    HashEntry( const HashedObj & e = HashedObj( ), EntryType i =EMPTY )
	       : element( e ), info( i ) { }
      };
      
      const HashedObj ITEM_NOT_FOUND;
      vector<HashEntry> array;
      unsigned int currentSize;
      
      bool isActive( int currentPos ) const;
      int findPos( const HashedObj & x );
      void rehash( );

      int probes;

      // struct for statistics
      struct {
         // insertion stats: max, total, # inserted
         int insMax;
         int insTtl;
         int insFal;
         int ins;

         // find successful stats: max, min, total, # of finds
         int findSMax;
         int findSMin;
         int findSTtl;
         int findS;

         // find failed stats: max, min, total, # of finds
         int findFMax;
         int findFMin;
         int findFTtl;
         int findF;
      } stats;

};

int hash( const string & key, int tableSize );
int hash( int key, int tableSize );

#include "QuadProbing.C"
#endif