#include "QuadraticProbing.h"
#include "Except.h"
#include <stdlib.h>
#pragma warning (disable: 4068)
#pragma warn -csu
#ifdef SAFE_STL
#include "StartConv.h"
#endif
bool isPrime( int n );
int nextPrime( int n );
template <class Object>
HashTable<Object>::
HashTable( )
: array( nextPrime( 101 ) )
{
makeEmpty( );
}
template <class Object>
void HashTable<Object>::
insert( const Object & x )
{
int currentPos = findPos( x );
if( isActive( currentPos ) )
throw DuplicateItemException( );
array[ currentPos ] = HashEntry( x, ACTIVE );
if( ++occupied > array.size( ) / 2 )
rehash( );
}
template <class Object>
void HashTable<Object>::
rehash( )
{
vector<HashEntry> oldArray = array;
array.resize( nextPrime( 2 * oldArray.size( ) ) );
for( int j = 0; j < array.size( ); j++ )
array[ j ].info = EMPTY;
makeEmpty( );
for( int i = 0; i < oldArray.size( ); i++ )
if( oldArray[ i ].info == ACTIVE )
insert( oldArray[ i ].element );
}
template <class Object>
unsigned int hash( const Object & key )
{
unsigned int hashVal = 0;
const char *keyp = reinterpret_cast<const char *>( & key );
for( size_t i = 0; i < sizeof( Object ); i++ )
hashVal = ( hashVal << 5 ) ^ keyp[ i ] ^ hashVal;
return hashVal;
}
template <class Object>
int HashTable<Object>::
findPos( const Object & x ) const
{
int collisionNum = 0;
int currentPos = hash( x ) % array.size( );
while( array[ currentPos ].info != EMPTY &&
array[ currentPos ].element != x )
{
currentPos += 2 * ++collisionNum - 1; if( currentPos >= array.size( ) )
currentPos -= array.size( );
}
return currentPos;
}
template <class Object>
void HashTable<Object>::
remove( const Object & x )
{
int currentPos = findPos( x );
if( isActive( currentPos ) )
array[ currentPos ].info = DELETED;
else
throw ItemNotFoundException( );
}
template <class Object>
Cref<Object> HashTable<Object>::
find( const Object & x ) const
{
int currentPos = findPos( x );
if( isActive( currentPos ) )
return Cref<Object>( array[ currentPos ].element );
else
return Cref<Object>( );
}
template <class Object>
void HashTable<Object>::
makeEmpty( )
{
occupied = 0;
for( int i = 0; i < array.size( ); i++ )
array[ i ].info = EMPTY;
}
template <class Object>
bool HashTable<Object>::
isActive( int currentPos ) const
{
return array[ currentPos ].info == ACTIVE;
}
unsigned int hash( const string & key )
{
unsigned int hashVal = 0;
for( int i = 0; i < key.length( ); i++ )
hashVal = ( hashVal << 5 ) ^ key[ i ] ^ hashVal;
return hashVal;
}
bool isPrime( int n )
{
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}
int nextPrime( int n )
{
if( n % 2 == 0 )
n++;
for( ; !isPrime( n ); n += 2 )
;
return n;
}
#ifdef SAFE_STL
#include "EndConv.h"
#endif