#ifndef QUEUE_H
#define QUEUE_H
///////////////////////////////////////////////////////////////
//  queue.h    -- template-based queue                       //
//  ver 1.1                                                  //
//  Language:     Visual C++, ver 6.0                        //
//  Platform:     Micron Dual Pentium Pro 200, Win NT 4.0    //
//  Application:  CSE691 - Project #3 prototype              //
//  Author:       Jim Fawcett, CST 2-187, Syracuse Univ      //
//                (315) 443-3948, fawcett@syr.edu            //
///////////////////////////////////////////////////////////////
/*
  Class Operation
  ===============
  The queue class accepts messages with an enQ(m) command where
  m is the message to be queued.  It destructively returns the
  message with deQ().  deQ() returns messages in the order they
  were enqueued.

  Queue is implemented with a doubly linked list of nodes.  Each
  node holds pointers to its predecessor and successor, and a
  message value, so the queue is simply a class holding head and 
  tail pointers, used by enQ(...) and deQ().
    
                                       tail
    arrival      +------+      +------+  |   +------+   server
      end        |node 1|      |node 2|  |   |node 3|    end
                 +------+      +------+  +-->+------+
      head ----->| next |----->| next |----->| next |----+
            +----| prev |<-----| prev |<-----| prev |    |
            |    |  t1  |      |  t2  |      |  t3  |   \ /
           \ /   +------+      +------+      +------+


  enQ(...) adds a node to the head of the list, logically equivalent
  to adding an element to the end of the queue.  deQ() removes an
  element from the tail of the list, logically equivalent to removing
  an element from the beginning of the queue.

    queue<string> sq;     // make a queue to hold string messages
    sq.enQ(s);            // enqueues a message m
    string s = sq.deQ();  // dequeues a message

*/
///////////////////////////////////////////////////////////////
//  Build Instructions                                       //
///////////////////////////////////////////////////////////////
//  Files Required:                                          //
//    queue.h, queue.cpp                                     //
//  Compiler Command:                                        //
//    cl -GX -DTEST_QUEUE queue.cpp                          //
///////////////////////////////////////////////////////////////
/*
    Maintenance History
    ===================
    ver 1.1 : 14 November 1998
      - moved template member functions to the header file
        where they belong
    ver 1.0 : 28 October 1998
      - first release
*/

//

#include <iostream>

using namespace std;


template <class T> class node {

  public:
    node(const T &t, node<T> *&link);
    ~node();
    T& value();
    node<T>*& prev();   // read or write prev pointer
    node<T>*& next();   // read or write next pointer

  private:
    node<T> *_prev;
    node<T> *_next;
    T _t;
};

template <class T> inline node<T>::~node() { }

template <class T> inline T& node<T>::value() { return _t; }

template <class T> inline node<T>*& node<T>::prev() { return _prev; }

template <class T> inline node<T>*& node<T>::next() { return _next; }


template <class T> class queue {

  public:
    queue();
    ~queue();
    void enQ(const T &t);
    T deQ();
    int length();

  private:
    node<T> *head;
    node<T> *tail;
    int len;
};

template <class T> inline int queue<T>::length() { return len; }


//----< node constructor >-------------------------------------
//
//  construct node, give it a value, and link to
//  head of the list
//
template <class T> node<T>::node(const T &t, node<T> *&link) {

  _t = t;         // store value
  _prev = NULL;   // this is at head of list so there is no prev
  _next = link;   // link to old first node
}

//

//----< queue constructor >------------------------------------
//
//  construct queue by setting both head and tail to null
//  signifying an empty queue
//
template <class T> queue<T>::queue() : head(NULL), tail(NULL), len(0) { }

//----< queue destructor >-------------------------------------
//
//  walk down list and delete each node
//
template <class T> queue<T>::~queue() {

  while(head != NULL) {
    node<T> *temp = head;
    head = head->next();
    delete temp;
  }
  head = tail = NULL;
}

//----< add element to back of queue >-------------------------
//
//  create node and link to the head of queue list
//
template <class T> void queue<T>::enQ(const T &t) {

  head = new node<T>(t,head);     // create node pointing to old head
  if(tail != NULL)                // if there was a node in queue then
    head->next()->prev() = head;  //   make new node its predecessor
  else                            // otherwise this is the first node
    tail = head;                  //   so make tail point to it
  len++;
}

//----< remove element from front of queue >-------------------
//
//  retrieve value of last node on list, e.g., first in queue
//  and eliminate node
//
template <class T> T queue<T>::deQ() {

  static T safe;
  if(tail == NULL)                // empty queue so return safe
    return safe;
  T temp = tail->value();         // retrieve last node's value
  if(tail != head) {              // if this is not the only node
    tail = tail->prev();          //   make new tail pointing to its
    delete tail->next();          //   predecessor and delete node,
    tail->next() = NULL;          //   make new last node nextless
  }
  else {                          // otherwise this is only node
    delete tail;                  //   delete node and make list empty
    head = tail = NULL;           //   by nulling its head and tail
  }
  len--;
  return temp;
}

#endif