#include "QuadraticProbing.h"
#include <iostream>
using namespace std;

/**
 * Internal method to test if a positive number is prime.
 * Not an efficient algorithm.
 */
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;
}

/**
 * Internal method to return a prime number at least as large as n.
 * Assumes n > 0.
 */
int nextPrime( int n )
{
    if( n % 2 == 0 )
        ++n;

    for( ; !isPrime( n ); n += 2 )
        ;

    return n;
}

template <typename HashedObj>
explicit HashTable<HashedObj>::HashTable( int size = 101 ) : array( nextPrime( size ) )
    { makeEmpty( ); }



template <typename HashedObj>
bool HashTable<HashedObj>::isActive( int currentPos ) const
    { return array[ currentPos ].info == ACTIVE; }

template <typename HashedObj>
int HashTable<HashedObj>::findPos( const HashedObj & x ) const
{
    int offset = 1;
    int currentPos = myhash( x );

    while( array[ currentPos ].info != EMPTY &&
            array[ currentPos ].element != x )
    {
        currentPos += offset;  // Compute ith probe
        offset += 2;
        if( currentPos >= array.size( ) )
            currentPos -= array.size( );
    }

    return currentPos;
}

template <typename HashedObj>
void HashTable<HashedObj>::rehash( )
{
    vector<HashEntry> oldArray = array;

        // Create new double-sized, empty table
    array.resize( nextPrime( 2 * oldArray.size( ) ) );
    for( auto & entry : array )
        entry.info = EMPTY;

        // Copy table over
    currentSize = 0;
    for( auto & entry : oldArray )
        if( entry.info == ACTIVE )
            insert( std::move( entry.element ) );
}

template <typename HashedObj>
size_t HashTable<HashedObj>::myhash( const HashedObj & x ) const
{
    static hash<HashedObj> hf;
    return hf( x ) % array.size( );
}