//---------------------------------------------------------
// A modified queue class.
//
// Implement a circular queue.
//
// D. Searls
// Mar 2009
//---------------------------------------------------------

#ifndef H_QUEUECLASS
#define H_QUEUECLASS
 
#include<iostream>
using namespace std;

template<class itemType>
class queue
{  
private:

    itemType* arr;
    
    //-----------------------------------------------------
    // head points at the first item in the queue. If the
    // queue is empty, head is invalid.
    //
    // tail points at the last item in the queue. If the
    // queue is empty, tail is invalid.
    //-----------------------------------------------------
    
    unsigned int n;
    unsigned int head;
    unsigned int tail;
    unsigned int capacity;
  
public:

    //-----------------------------------------------------
    // Default Constructor
    //
    // Constructs an empty queue.
    //-----------------------------------------------------
    queue()
    {
        try
        {
            capacity = 100;
            arr = new itemType[capacity];
            n = 0;
            head = capacity;
            tail = capacity;
            
        }
        catch (bad_alloc bae)
        {
            cout << "FATAL ERROR: Memory allocation failure.";
            cout << endl << endl;
            exit (0);
        }
    }
    
    //-----------------------------------------------------
    // Initialization Constructor
    //
    // Construct a queue with the specified capacity.
    //
    // The specified capacity must be > 0.
    //
    // In Parameter: maxCapacity
    //-----------------------------------------------------
    queue(int maxCapacity)
    {
        try
        {
            if (maxCapacity > 0)
            {
                capacity = maxCapacity;
            }
            else
            {
                capacity = 100;
            }
            arr = new itemType[capacity];
            n = 0;
            head = capacity;
            tail = capacity;
        }
        catch (bad_alloc bae)
        {
            cout << "FATAL ERROR: Memory allocation failure.";
            cout << endl << endl;
            exit (0);
        }
    }
    
    //-----------------------------------------------------
    // Copy Constructor
    //
    // Create a new queue that is an exact copy of the
    // specified queue.
    //
    // In Parameter: q
    //-----------------------------------------------------
    queue(const queue& q)
    {
        unsigned int curr;
        
        try
        {
            capacity = q.capacity;
            arr = new itemType[capacity];
            if (q.n == 0)
            {
                n = 0;
                head = capacity;
                tail = capacity;
            }
            else
            {
                curr = q.head;
                do
                {
                    arr[curr] = q.arr[curr];
                    curr = (curr + 1) % capacity;
                } while (curr != (tail + 1) % capacity);
                
                n = q.n;
                head = q.head;
                tail = q.tail;
            }
            
        }
        catch (bad_alloc bae)
        {
            cout << "FATAL ERROR: Memory allocation failure.";
            cout << endl << endl;
            exit (0);
        }
    }
    
    //-----------------------------------------------------
    // Destructor
    //
    // Return the memory allocated for the queue back to
    // the operating system.
    //-----------------------------------------------------
    ~queue()
    {        
        delete [] arr;
    }
    
    //-----------------------------------------------------
    // enqueue
    //
    // Add the specified item at the back of the queue.
    //
    // The application program should verify that the queue
    // is not full before invoking this function. If the
    // queue is full, this function does nothing.
    //
    // In Parameter: item
    //-----------------------------------------------------
    void enqueue(const itemType& item)
    {
        if (empty())
        {
            head = 0;
            tail = 0;
            arr[tail] = item;
            n++;
        }
        else if (!full())
        {
            tail = (tail + 1) % capacity;
            arr[tail] = item;            
            n++;
        }
    }
    
    //-----------------------------------------------------
    // dequeue
    //
    // Remove and discard the item at the front of the queue.
    //
    // The application program should verify the the queue
    // is not empty before invoking this function. If the
	// queue is empty, this function does nothing.
    //-----------------------------------------------------
    void dequeue()
    {
        if (!empty())
        {
            if (n == 1)
            {
                head = capacity;
                tail = capacity;
            }
            else
            {
                head = (head + 1) % capacity;
            }
            n--;
        }
    }
    
    //-----------------------------------------------------
    // clear
    //
    // Remove all of the items from the queue.
    //-----------------------------------------------------
    void clear()
    {
        n = 0;
        head = capacity;
        tail = capacity;
    }
    
    //-----------------------------------------------------
    // size
    //
    // Return the number of items in the queue.
    //-----------------------------------------------------
    unsigned int size()
    {
        return n;
    }
        
    //-----------------------------------------------------
    // empty
    //
    // Return true if the stack is empty and false
    // otherwise.
    //-----------------------------------------------------
    bool empty()
    {
        return (n == 0);
    }
    
    //-----------------------------------------------------
    // full
    //
    // Return true if the stack is full and false
    // otherwise.
    //-----------------------------------------------------
    bool full()
    {
        return (n == capacity);
    }
  
    //-----------------------------------------------------
    // front
    //
    // Return the item at the front of the queue.
    //
    // The application program should verify that the queue
    // is not empty before invoking this function.
    //-----------------------------------------------------
    itemType front()
    {
        return arr[head];
    }
    
    //-----------------------------------------------------
    // back
    //
    // Return the item at the back of the queue.
    //
    // The application program should verify that the queue
    // is not empty before invoking this function.
    //-----------------------------------------------------
    itemType back()
    {
        return arr[tail];
    }
};

#endif