/***********************************************************************
* linkedlist.h
*
* Header file for a simple inplementation of an expandable queue
*
* Using templates allow the queue to be used, without modification or
* strange type-casting, to store absolutely any type of data. This
* is accomplished by the compiler using the template to construct
* new classes at compile-time to implement queue functionality for the
* specified type (as opposed to a java generic which uses the same
* collective in the background and bolts on type casting and type
* checking).
*
* Note that there is no corresponding .cpp file. Templates MUST BE
* implemented in a single file to work correctly (or at all).
*
* Written by Paul Bonamy - 8 July 2010
************************************************************************/

#ifndef EQUEUE_H
#define EQUEUE_H

#include <iostream>
using namespace std;

/***********************************************************************
 * really, really simple node class.
 * Could be expanded with accessor methods, additional data, etc
 ***********************************************************************/
template <typename T> class Node {
// this ^ tells the compiler that this is a template, and we'll be
// receiving a type, named T, to be used throughout the class
    public:
        /*
         * You can use T to specify that the compile should use the
         * user-specified type for a particular variable. It works
         * anywhere you'd use a datatype.
         */
        T value;      // value stored in the list
        
        /*
         * Because this is a template class, it's name isn't Node, it's
         * Node<T>. You can't separate the class from it's template nature,
         * and the compiler treats type T as a fundimental part of the class
         * name. Be sure to include the <T> whenever you refer to the
         * class.
         */
        Node<T> * next;    // next node in the list. set to 0 if last node
        Node<T> * prev;    // previous node in the list, 0 if first node
        Node() { next = prev = 0; } // default constructor. pretty trivial
};

/***********************************************************************
 * Simple expandable queue class. uses a linked list in the background
 * Implements basic enqueue, dequeue, and empty
 ***********************************************************************/
template <typename T> class EQueue {
    /*
     * Since we want to expose the Node's template nature to the user,
     * the EQueue class itself also needs to be a template. Note that we
     * can use the type T to provide a type for the Nodes
     */
    private: 
        Node<T> * head;    // address of first node in the list
        Node<T> * tail;    // address of last node in the list
    
    public:
        EQueue();   // default constructor
        ~EQueue();  // destructor
        void enqueue(T v); // enqueue a value
        int dequeue(T &v); // dequeue a value
        void empty();   // delete all values in the queue
};

/***********************************************************************
 * template <typename T> EQueue<T>::EQueue<T>() 
 *
 * default constructor for the EQueue class.
 * Only needs to initialize head and tail to 0
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> EQueue<T>::EQueue() {
    /*
     * Member functions of template classes are templates themselves,
     * so we have to declare them as such. Note also that we need to
     * specify the class name as EQueue<T> in the fully-qualified name
     */
    head = 0; // set head to 0 aka NULL, so we can detect empty queues
    tail = 0; // ditto
    return;
}

/***********************************************************************
 * template <typename T> EQueue<T>::~EQueue()
 *
 * destructor for the EQueue class.
 * Delete all nodes in the queue and return
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> EQueue<T>::~EQueue() {
    empty(); // we could code the delete here, but let's use empty()
    return;
}

/***********************************************************************
 * template <typename T> void EQueue<T>::enqueue(T v)
 *
 * Enqueue a given value by inserting it at the head of the list
 *
 * v -> value to add to list / no return
 ***********************************************************************/
template <typename T> void EQueue<T>::enqueue(T v) {
    // note that the thing we receive is of type T
    
    // set up the new node, assign it the correct value, place at head
    Node<T> * newbie = new Node<T>();
    newbie->value = v;
    newbie->next = head;
    newbie->prev = 0;
    head = newbie;
    
    if (tail == 0) {
        // the queue is empty, so we have to set the tail pointer, too
        tail = newbie;
    }
    else {
        // queue is non-empty, so current head needs to know about new head
        head->next->prev = head;
    }
    
    return;
}

/***********************************************************************
 * int EQueue::dequeue(int &v)
 *
 * Dequeue one value from the queue, and return it to the user.
 * Also returns a status values so we know if dequeue succeeded.
 *
 * v -> reference to variable to receive dequeued value
 * returns 1 for successful dequeue, 0 otherwise
 ***********************************************************************/
template <typename T> int EQueue<T>::dequeue(T &v) {
    Node<T> * temp; // temporary handle for last node
    
    if(tail == 0) {
        // queue is empty, return suitable status
        return 0;
    }
    
    v = tail->value;    // get ready to return value
    temp = tail;    // get a pointer to the last element
    
    if(tail == head) {
        // equeue had one entry and is now empty
        head = 0;
    }
    else {
        // equeue will not be emptied, so cope with loss of end
        tail->prev->next = 0;
    }
    tail = tail->prev;
    
    delete temp;    // free memory associated with the value
    
    return 1;
}

/***********************************************************************
 * void EQueue::empty()
 *
 * Delete all nodes in the equeue and return
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> void EQueue<T>::empty() {
    Node<T> * curr = head; // start from the beginning of the list
    head = 0;           // no need for the head pointer any more
    Node<T> * next;        // use this to not get lost in the list
    
    // start at the beginning of the list and delete to the end
    while (curr != 0) {     // note that while (curr) would also work here
        next = curr->next;  // figure out the next node
        delete curr;        // delete the current node
        curr = next;        // make the next node the current node
    }
    
    tail = 0;           // no need for the tail pointer, either
    
    return;
}

#endif