#ifndef DYNAMIC_DOUBLE_HASH_TABLE_H
#define DYNAMIC_DOUBLE_HASH_TABLE_H

/*****************************************
 * UW User ID:  pagunnew
 * Submitted for ECE 250
 * Semester of Submission:  Winter 2011
 *
 * By submitting this file, I affirm that
 * I am the author of all modifications to
 * the provided code.
 *****************************************/

#include "Exception.h"
#include "ece250.h"

enum state { EMPTY, OCCUPIED, DELETED };

template<typename Object>
class Dynamic_double_hash_table
{
	private:
		int power;
		int count;
		int deleted_count;
		int array_size;
		int initial_size;

		Object *array;
		state *occupied;

		int h1( const Object & ) const;
		int h2( const Object & ) const;

		void double_size();
		void half_size();
		void re_hash();

	public:
		Dynamic_double_hash_table( int = 5 );
		~Dynamic_double_hash_table();
		int size() const;
		int capacity() const;
		double load_factor() const;
		double deleted_factor() const;
		bool empty() const;
		bool member( const Object & ) const;
		Object bin( int ) const;

		void print() const;

		void insert( const Object & );
		bool remove( const Object & );
		void clear();

	// Friends

	template <typename T>
	friend std::ostream &operator << ( std::ostream &, const Dynamic_double_hash_table<T> & );
};

template<typename Object>
Dynamic_double_hash_table<Object>::Dynamic_double_hash_table( int m ):
	power( (m < 2 ? 2 : m) ), count( 0 ), deleted_count( 0 ),
	array_size( 1 << power ),
	initial_size( 1 << power ),
	array( new Object[array_size] ),
	occupied( new state[array_size] )
{
    // Constructor
    // Set all values to empty
	for ( int i = 0; i < array_size; ++i ) {
		occupied[i] = EMPTY;
	}
}

template<typename Object>
Dynamic_double_hash_table<Object>::~Dynamic_double_hash_table() {
    // Destructor
    // Delete the two array pointers
    delete[] array;
    delete[] occupied;
}

template<typename Object>
int Dynamic_double_hash_table<Object>::size() const {
    // Return the number of items in the array
	return count;
}

template<typename Object>
int Dynamic_double_hash_table<Object>::capacity() const {
    // Return the maximum number of elements the array can hold, aka the size of the array
	return array_size;
}

template<typename Object>
double Dynamic_double_hash_table<Object>::load_factor() const {
    // Returns the number of elements in the array divided by the size of the array
	return static_cast<double>(count)/static_cast<double>(array_size);
}

template<typename Object>
double Dynamic_double_hash_table<Object>::deleted_factor() const {
    // Returns the number of deleted items in the array divided by the size of the array
	return static_cast<double>(deleted_count)/static_cast<double>(array_size);
}

template<typename Object>
bool Dynamic_double_hash_table<Object>::empty() const {
    // Return true if the table is empty, false otherwise
	if(size() == 0)
        return true;
    else
        return false;
}

template<typename Object>
int Dynamic_double_hash_table<Object>::h1( const Object & obj ) const {
    // Hash function 1. Gets the initial position to place the object
	int result = static_cast<int>( obj ) & (array_size - 1);

	return result < 0 ? (result + array_size) : result;
}

template<typename Object>
int Dynamic_double_hash_table<Object>::h2( const Object & obj ) const {
    // Hash function 2. Get the size of the jump size if the initial position is full
	int result = (static_cast<int>( obj ) / array_size) & (array_size - 1);

	return (result < 0) ? ((result + array_size) | 1) : (result | 1);
}

template<typename Object>
bool Dynamic_double_hash_table<Object>::member( const Object & obj ) const {
    // Checks if the object is in the hash table
    // Use the hash functions to get the initial value and jump
    int hashvalue = h1(obj);
    int jump = h2(obj);

    // Try to find the object
    while(occupied[hashvalue] != EMPTY)
    {
        if (array[hashvalue] == obj)
        {
            // Don't return deleted entries
            if(occupied[hashvalue] == DELETED)
            {
                return false;
            }
            return true;
        }
        hashvalue += jump; // Add the jump
        hashvalue %= array_size; // Compensate for wraparound
    }
    return false;
}

template<typename Object>
Object Dynamic_double_hash_table<Object>::bin( int n ) const {
	// Returns the object at a specified location
	return array[n];
}

template<typename Object>
void Dynamic_double_hash_table<Object>::insert( const Object & obj ) {
    // Inserts the object into the hash table if it is not already in there.
    // Increases the size of the hash table if it is too full

    // Check if object is in the hash table
    if(member(obj))
    {
        return;
    }
    // Check if the hash table is too full
    if(load_factor() == 0.75)
    {
        double_size();
    }

    // Use the hash functions to get the initial value and jump
    int hashvalue = h1(obj);
    int jump = h2(obj);
    // Try to insert the object
    while(occupied[hashvalue] == OCCUPIED)
    {
        hashvalue += jump; // Add the jump
        hashvalue %= array_size; // Compensate for wraparound
    }

    // Corrects deleted_count when the user inserts and deletes the same object multiple times in a row
    if(occupied[hashvalue] == DELETED)
    {
        deleted_count--;
    }

    // Update values
    array[hashvalue] = obj;
    occupied[hashvalue] = OCCUPIED;
    count++;
}

template<typename Object>
bool Dynamic_double_hash_table<Object>::remove( const Object & obj ) {
    // Tries to remove an object from the hash table. Returns true if it does, false otherwise

    // Use the hash functions to get the initial value and jump
    int hashvalue = h1(obj);
    int jump = h2(obj);

    // Try to find the object
    while(occupied[hashvalue] != EMPTY)
    {
        // Check if the object was found
        if(array[hashvalue] == obj)
        {
            // If the value is deleted keep then it can't be removed again
            if(occupied[hashvalue] == DELETED)
            {
                return false;
            }
            // Update values
            occupied[hashvalue] = DELETED;
            count--;
            deleted_count++;
            // Check if the hash table is too empty
            if(load_factor() == 0.25)
            {
                if(initial_size != array_size)
                {
                    half_size();
                }
            }
            // Check if there are too many deleted entries
            if(deleted_factor() == 0.25)
            {
                re_hash();
            }

            return true;
        }
        hashvalue += jump; // Add the jump
        hashvalue %= array_size; // Compensate for wraparound
    }
    return false;
}

template<typename Object>
void Dynamic_double_hash_table<Object>::clear() {
    // Clear everything and set the arrays to the initial size
    // The new arrays
    Object *cleared_array = new Object[initial_size];
    state *cleared_occupied = new state[initial_size];

    // Clear all values and update arrays
    delete[] array;
    delete[] occupied;
    array = cleared_array;
    occupied = cleared_occupied;
    array_size = initial_size;
	deleted_count = 0;
	count = 0;
}

template<typename Object>
void Dynamic_double_hash_table<Object>::re_hash() {
    // Rehash all values
    Object *rehash_array = new Object[array_size];
    state *rehash_occupied = new state[array_size];

    // Find all occupied locations, and move them
    for(int i = 0; i < array_size; i++)
    {
        if(occupied[i] == OCCUPIED)
        {
            // Use the hash functions to get the initial value and jump
            int hashvalue = h1(array[i]);
            int jump = h2(array[i]);

            // Try to insert the object
            while(rehash_occupied[hashvalue] == OCCUPIED)
            {
                hashvalue += jump; // Add the jump
                hashvalue %= array_size; // Compensate for wraparound
            }
            rehash_array[hashvalue] = array[i];
            rehash_occupied[hashvalue] = OCCUPIED;
        }
    }

    delete[] array;
    delete[] occupied;
    // Update values
    array = rehash_array;
    occupied = rehash_occupied;
    deleted_count = 0;
}

template<typename Object>
void Dynamic_double_hash_table<Object>::double_size() {
    // Doubles the size of the hash table
    // New arrays with the correct size
    Object *doubled_array = new Object[array_size*2];
    state *doubled_occupied = new state[array_size*2];

    // Add everything from the old array to the new array
    for(int i = 0; i < array_size; i++)
    {
        doubled_array[i] = array[i];
        doubled_occupied[i] = occupied[i];
    }
    delete[] array;
    delete[] occupied;
    // Update values
    array = doubled_array;
    occupied = doubled_occupied;
    array_size *=2;
    power++;
    // re_hash to order things properly and get rid of deleted values
    re_hash();
}

template<typename Object>
void Dynamic_double_hash_table<Object>::half_size() {
    // Halves the size of the hash table
    // New arrays with the correct size
    Object *halfed_array = new Object[array_size/2];
    state *halfed_occupied = new state[array_size/2];

    // Add values from the old array to the new array
    for(int i = 0, j = 0; i < array_size; i++)
    {
        // Only have space in the new array for occupied values so only add those
        if(occupied[i] == OCCUPIED)
        {
            // We have to add the values starting at the beginning of the new array
            // other wise the location may not exist
            halfed_array[j] = array[i];
            halfed_occupied[j] = occupied[i];
            j++;
        }
    }
    delete[] array;
    delete[] occupied;

    // Update values
    array = halfed_array;
    occupied = halfed_occupied;
    array_size /=2;
    power --;
    // re_hash to order things properly
    re_hash();
}



// You can modify this function however you want:  it will not be tested

template <typename T>
std::ostream &operator << ( std::ostream &out, const Dynamic_double_hash_table<T> &list ) {
    for(int i = 0; i < list.array_size; i++)
    {
        out << list.occupied[i] << " ";
    }
    out << std::endl;
    for(int i = 0; i < list.array_size; i++)
    {
        out << list.array[i] << " ";
    }

	return out;
}

// Is an error showing up in ece250.h or elsewhere?
// Did you forget a closing '}' ?

#endif