#pragma warning(disable:4786) 

#ifndef HashTable_H
#define HashTable_H

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


// QuadraticProbing Hash table class.
// Object must have operator!= and global function
//    unsigned int hash( const Object & x );
// CONSTRUCTION: with no parameters or another hash table.
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Object find( x )       --> Return item that matches x
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Throws exceptions as warranted

template <class Object>
class HashTable
{
  public:
    HashTable(double moc );

	virtual int findPos( const Object & x );
    void makeEmpty( );
	void insert( const Object & x );
    void remove( const Object & x );
    Object * find( const Object & x );
	int getSize() {
		int size = 0;
		for( int j = 0; j < array.size( ); j++ )
			if (array[ j ].info == ACTIVE)
				size++;
		return size;	
	};
	int getLookups(){
		return lookups;
	};
	int getCapacity(){
		return array.size();
	};
	double getLambda(){
		return static_cast<double>(getSize())/static_cast<double>(getCapacity());
	}

    enum EntryType { ACTIVE, EMPTY, DELETED };
  private:
    struct HashEntry
    {
        Object    element;
        EntryType info;

        HashEntry( const Object & e = Object( ), EntryType i = EMPTY )
          : element( e ), info( i ) { }
    };
    
    int occupied;
	
    bool isActive( int currentPos ) const;
    void rehash( );
	bool isPrime( int n ) const;
	int nextPrime( int n ) const;
	double maxOccupiedPercentage; 
  protected:
	int lookups;
	unsigned int hash( const string & key ) const;
	vector<HashEntry> array;
};

template <class Object>
class LinearHashTable : public HashTable<Object> {
	public:

	LinearHashTable(double moc) : HashTable<Object>(moc) {};

	virtual findPos( const Object & x )
	{
		int collisionNum = 0;
		int currentPos = hash( x ) % array.size( );
		lookups++;
		while( array[ currentPos ].info != EMPTY &&
			   array[ currentPos ].element != x )
		{	
			lookups++;
			currentPos++; 
			if( currentPos >= array.size( ) )
			 currentPos -= array.size( );
		}
		return currentPos;
	}

};
#include "HashTable.cpp"

#endif