#ifndef DYNAMIC_QUEUE_AS_ARRAY_H
#define DYNAMIC_QUEUE_AS_ARRAY_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 "ece250.h"
#include "Exception.h"

template <typename Object>
class Dynamic_queue_as_array
{
	private:
		int initial_size;
		int array_size;
		Object *array;
		int ihead;
		int itail;
		int count;
		bool halfed;
		// other integer member variables, as necessary

	public:
		Dynamic_queue_as_array( int = 10 );
		Dynamic_queue_as_array( const Dynamic_queue_as_array & );
		~Dynamic_queue_as_array();

		Dynamic_queue_as_array &operator = ( const Dynamic_queue_as_array & );

		Object head() const;
		int size() const;
		bool empty() const;
		int capacity() const;

		void enqueue( const Object & );
		Object dequeue();
		void clear();
		void double_size();
		void half_size();

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

template <typename Object>
Dynamic_queue_as_array<Object>::Dynamic_queue_as_array( int n ) {
    // Specified size was equal or less than 0
	if (n <= 0)
	{
		count = 0;
		array_size = 1;
		initial_size = 1;
	}
	// Specified size was n
	else if (n>0)
	{
		count = 0;
		array_size = n;
		initial_size = n;
	}
	// No specified size
	else
	{
		count = 0;
		array_size = 10;
		initial_size = 10;
	}
	array = new Object[array_size];
	ihead = 0;
	itail = -1;
	halfed = true;
}

template <typename Object>
Dynamic_queue_as_array<Object>::Dynamic_queue_as_array( const Dynamic_queue_as_array<Object> &queue ) {
	// Initialize your object and then call operator=
	*this = queue;
}

template <typename Object>
Dynamic_queue_as_array<Object>::~Dynamic_queue_as_array() {
	// Deconstructor
	delete[] array;
}

template <typename Object>
Dynamic_queue_as_array<Object> &Dynamic_queue_as_array<Object>::operator = ( const Dynamic_queue_as_array<Object> &rhs ) {
	// empty the current queue, if necessary, deallocating memory
	// make a copy of the queue rhs

	if (&rhs == this) // Same array so no need to copy
	{
		return *this;
	}

	delete[] array; // Delete old array

	array = new Object[rhs.array_size];//Make new array of same size

	int i = 0;
	// Loop through and add all the variables
	while( i < rhs.capacity())
	{
		array[i] = rhs.array[i];
		i++;
	}

    // Set all variables to rhs variables
	count = rhs.count;
	array_size = rhs.array_size;
	initial_size = rhs.initial_size;
	ihead = rhs.ihead;
	itail = rhs.itail;

}

template <typename Object>
int Dynamic_queue_as_array<Object>::size() const {
	// Return the number of objects in the queue
	return count;
}

template <typename Object>
int Dynamic_queue_as_array<Object>::capacity() const {
	// Return the maximum number of objects the queue can store
	return array_size;
}

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

template <typename  Object>
Object Dynamic_queue_as_array<Object>::head() const {
	// Returns the head of the queue
	if (empty())
        throw underflow();
    else
        return array[ihead];
}

template <typename Object>
void Dynamic_queue_as_array<Object>::enqueue( const Object &obj ) {

    // Check if the array is full
	if (size() == capacity())
		double_size();

	itail++;
    // Loop the tail back to the front of the queue if its at the end
	if (itail > capacity()-1)
		itail = 0;

    // Add object to queue
    array[itail] = obj;
    count++;

}

template <typename Object>
Object Dynamic_queue_as_array<Object>::dequeue() {

	if (empty())
		throw underflow();

    // Save the old head so it can be returned
	Object oldhead = array[ihead];

    array[ihead] = 0;
    ihead++;

    // Loop the head back to the front of the queue if its at the end
    if (ihead > capacity()-1)
        ihead = 0;

    count--;

    // Check to see if the array capacity needs to be halfed.
    // halfed is always true except during the halfing process
    // Prevents multiple resizes during the halfing process
    if (halfed== true)
    {
        if (size() <= capacity()/4)
        {
            if (capacity()>initial_size)
                half_size();
        }
    }

	return oldhead;
}

template <typename Object>
void Dynamic_queue_as_array<Object>::clear() {

    // Make a new array of the initial size
	Object *new_array = new Object[initial_size];
	delete[] array;
	array = new_array;

    // Clear all variables
	array_size = initial_size;
	count = 0;
	ihead = 0;
	itail = -1;
}

template <typename Object>
void Dynamic_queue_as_array<Object>::double_size() {
    halfed = false;

	Object *new_array = new Object[2*capacity()];

    // Copy over all the values to the new array
	int i = 0;
	while( size() > 0)
	{
		new_array[i] = dequeue();
		i++;
	}

    // Update all array values
	ihead = 0;
	itail = i-1;
	array_size = array_size*2;
	count = i;

    // update array
    delete[] array;
	array = new_array;
    halfed = true;
}

template <typename Object>
void Dynamic_queue_as_array<Object>::half_size() {
    halfed = false;

	Object *new_array = new Object[capacity()/2];

    // Copy over all values to the new array
	int i = 0;
	while( size() > 0)
	{
		new_array[i] = dequeue();
		i++;
	}

    // Update variables
	ihead = 0;
	itail = i-1;
	array_size = array_size/2;
	count = (capacity()/2);

    // Update array
	delete[] array;
	array = new_array;
    halfed = true;
}

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

template <typename T>
std::ostream &operator << ( std::ostream &out, const Dynamic_queue_as_array<T> &queue ) {
	// I don't know how you are implementing your queue so I cannot print it.
	// If you want, you can print whatever you want here and then call cout
	// in the driver.

	// Remember to redirect to out, e.g.,
	//      out << "Hello!";

    int i =0;
	while(i < queue.capacity())
	{
		out << queue.array[i] << " ";
		i++;
	}

    out << std::endl << "head: " <<queue.ihead << " [" << queue.array[queue.ihead] << "]  tail: " << queue.itail << " [" << queue.array[queue.itail] << "]  size: " << queue.size() << "  array_size: " << queue.capacity();
	return out;
}

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

#endif