#ifndef _QUADRATIC_PROBING_H_
#define _QUADRATIC_PROBING_H_
#include "Wrapper.h"
#ifndef SAFE_STL
#include <string>
#include <vector>
using std::vector;
using std::string;
#else
#include "vector.h"
#include "mystring.h"
#include "StartConv.h"
#endif
template <class Object>
class HashTable
{
public:
HashTable( );
void makeEmpty( );
void insert( const Object & x );
void remove( const Object & x );
Cref<Object> find( const Object & x ) const;
enum EntryType { ACTIVE, EMPTY, DELETED };
private:
struct HashEntry
{
Object element;
EntryType info;
HashEntry( const Object & e = Object( ), EntryType i = EMPTY )
: element( e ), info( i ) { }
};
vector<HashEntry> array;
int occupied;
bool isActive( int currentPos ) const;
int findPos( const Object & x ) const;
void rehash( );
};
unsigned int hash( const string & key );
#include "EndConv.h"
#include "QuadraticProbing.cpp"
#endif