#ifndef _LVPQUEUE_H_
#define _LVPQUEUE_H_

#include "cvclibdef.h"
#include "vector.h"


#define QDEFAULT_SIZE 10;

template <class itemType>
class queue
{
	public:
		// constructors/destructor
		queue() : mySize(0), myFront(0), myBack( -1 ), myElements(QDEFAULT_SIZE) { }
		queue(const queue<itemType> & q) : mySize(q.mySize), myFront(q.myFront), myBack(q.myBack), myElements(q.myElements)
		~queue( ) { }

		// assignment
		const queue & operator = (const queue<itemType> & rhs)
		// postcondition: normal assignment via copying has been performed     
		{
			if( this != &rhs) 
			{   
				mySize = rhs.mySize;               // copy all fields of rhs
			    myElements.resize(rhs.myElements.length());  // resize storage
				myFront = 0;
				myBack = mySize - 1;               // index from 0 .. mySize - 1

				int k;
				int rhsk = rhs.myFront;
        
				for(k=0; k < mySize; k++)
				{
					myElements[k] = rhs.myElements[rhsk];
					Increment(rhsk);
				}
			}    
			return *this;
		}

		const itemType & queue<itemType>::front() const { return myElements[myFront]; }

		bool         isEmpty() const { return mySize == 0; }
		int          length() const { return mySize; }


		// modifiers
		void enqueue(const itemType & item)   
		{
			if (mySize >= myElements.length()) // grow if necessary to add element
			{
				DoubleQueue();
			}
    
			Increment(myBack);                // add element at back of queue
			myElements[myBack] = item;
			mySize++;
		}


		void dequeue()
		// precondition: queue is [e1, e2, ..., en] with n >= 1
		// postconditions:  queue is [e2, ..., en] and item == e1
		{
			if (isEmpty())
			{
				cerr << "dequeue from empty queue" << endl;
				exit(1);
			}
    
			mySize--;                       // one fewer element
			Increment(myFront);
		}


		void dequeue(itemType & item)
		{
			if (isEmpty())
			{
				cerr << "dequeue from empty queue" << endl;
				exit(1);
			}
			item = myElements[myFront];
			mySize--;                       // one fewer element
			Increment(myFront);    
		}


		void makeEmpty()
		{
			mySize = 0;
			myFront = 0;
			myBack = -1;
		}

	private:
		int mySize;                    // # of elts currently in queue
		int myFront;                   // index of first element
		int myBack;                    // index of last element
		vector<itemType> myElements; // internal storage for elements
        // private helper functions
		void DoubleQueue()   
		{
			vector<itemType> temp(myElements.length()*2);   // new storage
			int j,k=myFront;                                  // copy to 0..
			for(j=0; j < mySize; j++)
			{
				temp[j] = myElements[k];
				Increment(k);
			}
			myElements = temp;     // reset private vars to mirror new storage
			myFront = 0;
			myBack = mySize-1;
		}



		void Increment( int & val ) const
		{
			val++;
			if (val >= myElements.length() )
		        val = 0;
    
		}


};







#endif