//---------------------------------------------------------------------
// File: queue.template
// Name: Sharon M. Tuttle
// last modified: 4-01-05
//
// Template class name: queue
//
// Description: a collection of items such that entries can be
//    inserted at one end (called the rear) and removed at the
//    other end (called the front).
//    This version does NOT have a fixed capacity.
// 
// Implementation notes: 
//     * uses a linked list of elements of the node template class
//     * if there is insufficient dynamic memory, then the
//       following methods throw bad_alloc: enqueue
//---------------------------------------------------------------------

#include <cassert> // provides assert
#include <iostream>
//
// note: because this is a template class, it is included
//    in the header file (at the bottom), and not compiled
//    separately. Thus, the header file is not included here!
//
#include "node.h"
using namespace std;

/*****************************************************/
/* CONSTRUCTORS and DESTRUCTOR                       */
/*****************************************************/

// constructor
//
// postcondition: creates an empty queue instance
//
template <typename Item>
queue<Item>::queue()
{
    used = 0;
    front = NULL;
    rear = NULL;
}

// copy constructor 
//
// adapted from list_copy, Savitch and Main
//
template <typename Item>
queue<Item>::queue(const queue<Item>& source)
{
    node<Item> *source_curr, *new_curr;

    // start copy out as empty, but with the same value of used
    //    as the source being copied
    front = NULL;
    rear = NULL;
    used = source.used;

    // handle the case of the empty queue
    if (source.front == NULL)
    {
        return; // source is empty, so this copy is, too
    }

    // if source is NOT empty, make a copy of it

    // cause new copy to now have source front's data;
    front = new node<Item>(source.front->get_data());

    // start a pointer walking through the new copy
    //    starting from its front
    new_curr = front;

    // is there another in the source left to be copied?
    source_curr = source.front->get_next();

    // while there is another node in the source left
    //     to be copied...
    while (source_curr != NULL)
    {
        // add a new node to the new copy with the data in
        //    that node;
        new_curr->set_next(new node<Item>(source_curr->get_data()));

        // move the new copy's pointer to the new node
        new_curr = new_curr->get_next();

        // WHAT IF we're at the source's rear? Let's set 
        //    copy's rear, too, at that point;
        if (course_curr == source.rear)
        {
            rear = new_curr;
        }

        // is there another in the source left to be copied?
        source_curr = source_curr->get_next();
    }
}

// destructor 
//
template <typename Item>
queue<Item>::~queue()
{
    node<Item> *curr_ptr, *node_to_delete;

    curr_ptr = front;

    // need to deallocate EACH node in the queue
    while (curr_ptr != NULL)
    {
        node_to_delete = curr_ptr;
        curr_ptr = curr_ptr->get_next();
        delete node_to_delete;
    }

    // playing it safe...
    front = NULL;
    rear = NULL;
    used = 0;
}


/*************************************************************/
/* ACCESSORS and other constant member functions (observers) */
/*************************************************************/

// is_empty
//
// postcondition: returns true if queue is empty, and
//    returns false otherwise
//
template <typename Item>
bool    queue<Item>::is_empty( ) const
{
    return (used == 0);
}

// get_front
//
// precondition: is_empty() == false
//
// postcondition: returns the value of the front item of the
//    queue, BUT the queue is unchanged.
//
template <typename Item>
Item    queue<Item>::get_front( ) const
{
    assert(is_empty() == false);

    return(front->get_data());
}

/*****************************************************/
/* MODIFIERS and other modifying member functions    */
/*****************************************************/

// enqueue
//
// postcondition: a new copy of entry has been enqueueed
//    onto the (rear of the) queue
//
template <typename Item>
void    queue<Item>::enqueue(const Item& entry)
{
    node<Item> *temp;

    temp = new node<Item>(entry);

    // what if I am trying to enqueue onto an empty queue?
    if (rear == NULL)
    {
        front = temp;  // we have a new front in this case, too!
    }

    else
    {
        // old rear element's next field needs to point 
        //    to "new" rear element
        rear->set_next(temp);
    }

    // in EITHER case, now, rear can safely be made to
    //    point to the new rear element
    rear = temp;

    used++;
}

// dequeue
//
// precondition: is_empty() == false
//
// postcondition: the front item of the queue has been
//    removed, and its value is returned
//
template <typename Item>
Item   queue<Item>::dequeue( )
{
    value_type dequeued_item;
    node<Item>*      temp;

    assert(is_empty() == false);

    used--;

    // remember: if we reach here, we KNOW that queue is
    //    not empty

    dequeued_item = front->get_data();

    // keep track of item to be removed
    temp = front;

    // now it should be safe to make front point to the
    //    new front element
    front = front->get_next();

    // what if queue is empty? then need to set rear to NULL,
    //    too. (and queue is empty if front is NOW null...)
    if (front == NULL)
    {
        rear = NULL;
    }

    // free the space for this dequeued node from the heap,
    //    so it be be re-allocated for other uses
    delete temp;

    return dequeued_item;
}