/*
   queued.h
   CIS 250
   March 24, 2008
   
   This program implements a templated queue class.
*/
#ifndef __QUEUED_H_
#define __QUEUED_H_
#include <cstdlib>

template <class T>
class queued {
private:
   struct Node {
      T data;
      Node* next;
   };
   Node* head;
public:
   queued();
   queued(const queued& q);
   ~queued();
   bool isEmpty() const;
   bool isFull() const;
   bool add(const T data);
   bool remove(T& data);
   queued& operator=(const queued& q);
};

template <class T>
queued<T>::queued() { head = NULL; }

template <class T>
queued<T>::queued(const queued& q) {
   Node* p = q.head;
   Node* prev = NULL;
   while (p != NULL) {
      // create new node
      Node* n = new Node();
      if (n == NULL) return; // unrecoverable error
      n->data = p->data;
      n->next = NULL;
      // set up pointers
      if (prev == NULL) head = n; // first node in stack/list
      else prev->next = n;
      // get ready for next pass
      prev = n;
      p = p->next;
   }
}
template <class T>
queued<T>& queued<T>::operator=(const queued<T>& q) {
   if (this == &q) return *this;
   T tmp;
   while (!isEmpty()) remove(tmp);
   Node* p = q.head;
   Node* prev = NULL;
   while (p != NULL) {
      // create new node
      Node* n = new Node();
      if (n == NULL) return *this; // unrecoverable error
      n->data = p->data;
      n->next = NULL;
      // set up pointers
      if (prev == NULL) head = n; // first node in stack/list
      else prev->next = n;
      // get ready for next pass
      prev = n;
      p = p->next;
   }
   return *this;
}

template <class T>
queued<T>::~queued() {
   T tmp;
   while (!isEmpty()) remove(tmp);
}

template <typename T>
bool queued<T>::isEmpty() const { return head==NULL; }

template <class T>
bool queued<T>::add(const T data) {
   Node* n = new Node();
   if (n==NULL) return false;
   n->data = data;
   n->next = NULL;
   if (head == NULL) head = n;
   else {
      Node* p = head;
      while (p->next != NULL) p = p->next;
      p->next = n;
   }
   return true;
}

template <class T>
bool queued<T>::remove(T& data) {
   if (isEmpty()) return false;
   Node* tmp = head;
   data = head->data;
   head = head->next;
   delete tmp;
   return true;
}

#endif