#ifndef MTQUEUE_H
#define MTQUEUE_H
///////////////////////////////////////////////////////////////
//  mtqueue.h  -- template-based queue                       //
//  ver 3.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            //
///////////////////////////////////////////////////////////////
/*
  Typical Application:
  ====================
  The mtqueue class is intended to support communication between threads
  in a multi-threaded process.  A typical application would use mtqueue 
  to enqueue messages extracted from a socket by a socket server thread.  
  A message handler thread would then dequeue them for service by the 
  receiving process.

  Class Operation:
  ================
  The mtqueue 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.  
  
  Thread safety mechanisms have been, in this latest version, moved to a
  lockingPtr class, which you will find in the lockingPtr module, in the
  same directory as this file.  mtqueues may be used in multi-threaded 
  applications by declaring them volatile, and accessing them through a 
  locking pointer, provided in the lockingPtr module.  An example of how
  to use an object of the mtqueue class in a thread-safe way is given in
  the file queue.cpp, also stored in the directory where you find this 
  file.

  mtqueue 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(t) 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.

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

///////////////////////////////////////////////////////////////
//  Design Notes                                             //
///////////////////////////////////////////////////////////////
/*
    If you want to use this queue class in an application that will run
    for a long time, doing lots of enQ(val)s and deQ()s, you should 
    prevent the class from continuously newing and deleting nodes.  this 
    will cause the heap fragment and performance will suffer, possibly 
    failing due to memory allocation failures.

    The approach I've used is to keep a list of free nodes.  When deQuing,
    instead of deleting the node, I put it on a free list.  When enQing, I 
    check to see if the free list has any nodes before newing one.  This 
    way the queue will allocate nodes until the queue gets to its maximum 
    length.  Then as its length varies with time it will simply reuse 
    nodes on the free list.

    Note that, since mtqueue is based on a linked list, there is no maximum
    queue length.  An mtqueue will grow to whatever size is needed by the
    application.

    The free list is managed by a separate class nodePool.  By careful
    design of nodePool, the design of mtqueue was not affected at all.
*/


//

///////////////////////////////////////////////////////////////
//  Build Instructions                                       //
///////////////////////////////////////////////////////////////
//  Files Required:                                          //
//  - mtqueue.h, mtqueue.cpp, nodePool.h, nodePool.cpp       //
//                                                           //
//  Compiler Command:                                        //
//    cl -GX -DTEST_MTQUEUE mtqueue.cpp nodePool.cpp         //
///////////////////////////////////////////////////////////////
/*
    Maintenance History:
    ====================
    ver 3.1 : 09 Oct 2001
      - fixed  bug relating to the use of volatile.  After some
        thought and experimentation, I ripped out all of the self 
        synchronization, and provided a lockingPtr class, in a 
        module of that name.  You can see how to use mtqueues
        in a thread-safe way, using locking pointers, by looking
        at the queue.cpp file in this directory.
    ver 3.0 : 11 Mar 2001
      - added peekHead(), peekTail(), flushNP()
      - added node pool flush to mtqueue destructor
      - added nodeCount() member
    ver 2.1 : 08 Oct 2000
      - added synchronization of length
    ver 2.0 : 11 Feb 2000
      - added nodPool class to manage free list
      - provide
    ver 1.1 : 31 Jan 2000
      - moved using namespace std to implementation files
      - added private declarations for copy ctor and 
        assignment operator with no implementations so
        they can't be called
      - removed reference qualifier for node constructor,
        e.g., changed node<T>*& to node<T>*.  It wasn't needed.
    ver 1.0 : 14 Nov 1998
      - developed this first release by modifying
        queue.h and queue.cpp


*/

//

///////////////////////////////////////////////////////////////
//  declaration of mtqueue class                             //
///////////////////////////////////////////////////////////////

#include <iostream>
#include <windows.h>
#include <process.h>
#include "nodePool.h"

template <class T> class mtqueue {

  public:
    mtqueue();
    ~mtqueue();
    void enQ(const T &t) ;
       T deQ() ;
      T& peekHead() ;
      T& peekTail() ;
    void flush() ;
    void flushNP() ;
     int length() ;
     int freeLength() ;
     int nodeCount() ;

  private:
    mtqueue(const mtqueue<T> &mtq);
    mtqueue<T>& operator=(const mtqueue<T> &mtq);
    node<T>* head;
    node<T>* tail;
         int len;
    nodePool<T> np;
};

//----< return length of free list >---------------------------

template <class T> 
inline  int mtqueue<T>::freeLength()  { return np.size(); }

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

//

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

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

//----< return length of queue >-------------------------------

template <class T>  int mtqueue<T>::length()  { 

  int temp;
  temp = len;
  return temp;
}

//----< remove contents of queue >-----------------------------

template <class T> 
void mtqueue<T>::flush()  { while(length() > 0) deQ(); }

//----< remove contents of node pool >-------------------------

template <class T>
void mtqueue<T>::flushNP()  { np.flush(); }

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

  head = np.retrieveNode(t,head);
  if(!head)
    throw "\n  memory alloc failure in mtqueue<T>::enQ\n\n";
  if(tail != NULL) {                    // if there was a node in queue then
     node<T> *temp = head->next();
    temp->setPrev(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 mtqueue<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
    np.saveNode(tail->next());    // predecessor, return node to free pool
    tail->setNext(NULL);          // make new last node nextless
  }
  else {                          // otherwise this is only node so
    np.saveNode(tail);            // return node to free pool and make list
    head = tail = NULL;           // empty by nulling its head and tail
  }
  len--;
  return temp;
}

//----< peek at value in first node of queue >-----------------

template <class T> inline
T& mtqueue<T>::peekHead()  { return head->value(); }

//----< peek at value in last node of queue >------------------

template <class T> inline
T& mtqueue<T>::peekTail()  { return tail->value(); }

//----< return node count from queue and pool >----------------

template <class T> inline
 int mtqueue<T>::nodeCount()  { return length() + np.size(); }

#endif