// ---------------------------------------------------------------------------
// SimpleUnboundedQueue.h
//
// A generic unbounded queue class.  (There is already a queue class in the 
// Standard C++ Library; this class is just an illustration of how such a
// class is written from scratch!)  Copying and assignment are prohibited 
// because this is just a simple example.  A real class would have copy
// constructors and an assignment operator defined.
//
//   Queue()       Constructor: makes an empty queue.
//   ~Queue()      Destructor.
//   q.getSize()   Returns the number of elements in the queue.
//   q.isEmpty()   Returns whether the queue is empty.
//   q.enqueue(x)  Adds x to the back of q.   Will throw a bad_alloc if there
//                 is no memory available to add the element (but note that
//                 many compilers do not implement the C++ Standard correctly
//                 and with one of these the behavior is undefined is there
//                 is no memory).
//   q.dequeue()   If not empty, removes the front element and returns it,
//                 else throws a standard underflow_error.
//   q.peek()      If not empty, returns the front element, else throws
//                 a standard underflow_error.
// ---------------------------------------------------------------------------

#ifndef _SIMPLE_UNBOUNDED_QUEUE_H
#define _SIMPLE_UNBOUNDED_QUEUE_H

#include <stdexcept>
using namespace std;

// A queue object is represented as a singly-linked list of nodes, from the
// head to the tail.  The queue itself maintains pointer to the head and the
// tail nodes.

template<class T>
class Queue {

// A private local class for the nodes that are linked together.
private:
  class Node {
  public:
    T data;
    Node* next;
    Node(T data, Node* next): data(data), next(next) {}
  };

// The queue itself maintains pointers to the head node and tail node.
private:
  Node* head;
  Node* tail;

// A private helper function to delete all the nodes in the queue.
// It is inefficient but it looks cool.  It deletes all nodes
// from its argument onward.
private:
  static void clear(Node* n) {if (n != 0) {clear(n->next); delete n;}}

// Constructors and Destructors
public:

  // Constructor ensures that the queue is empty upon creation.
  Queue(): head(0), tail(0) {}

  // Destructor uses the helper to delete all the nodes.
  ~Queue() {clear(head);}

// Behavior
public:

  // The size of the queue is determined by mindless counting of nodes.
  int getSize() {
    int count = 0;
    for (Node* n = head; n != 0; n = n->next) count++;
    return count;
  }

  // A queue is empty when its head and tail pointers are both null.  Since
  // the implementation maintains this consistency requirement, it suffices
  // to simply check one or the other to determine emptiness.
  bool isEmpty() {return head == 0;}

  // To add an element we make a new node, attach it after the current tail
  // node, and update the queue's tail filed to point to this new node.  One
  // special case is when the queue is initially empty: in this case the
  // new node becomes both the head and the tail.
  void enqueue(T x) {
    if (tail == 0)
      head = tail = new Node(x, 0);
    else
      tail = tail->next = new Node(x, 0);
  }

  // Removing from a queue is taking the head element out.  First of all if
  // there are no elements we have to throw an error because there is nothing
  // to remove.  If there is, we save the head element to return later as
  // well as a pointer to the head node to delete later.  We "detach" the node
  // by moving the queue's head pointer past it.  Note the special case here!
  // If this was the last node, we have to update the queue's tail node field!
  // After all this, we can delete the node and return the value we saved up.
  T dequeue() {
    if (isEmpty()) throw underflow_error("cannot remove from empty queue");
    Node* nodeToDelete = head;
    T valueToReturn = head->data;
    head = head->next;
    if (head == 0) tail = 0;
    delete nodeToDelete;
    return valueToReturn;
  }

  // Peek just returns the head element, if there is one.
  T peek() {
    if (head == 0) throw underflow_error("Cannot peek into empty queue");
    return head->data;
  }

// Prohibit copying and assignment
private:
  Queue(Queue&);
  Queue& operator=(Queue&);
};

#endif

// ---------------------------------------------------------------------------
// testunboundedqueue.cpp                                                                 
//                                                                           
// A test script for the SimpleUnboundedQueue class.
// ---------------------------------------------------------------------------

#include <iostream>
#include <cassert>
#include <stdexcept>
using namespace std;

#include "SimpleUnboundedQueue.h"

int main(int argc, char** argv) {

  // Test an integer queue of testSize 200 for empty, getSize, and that
  // enqueing then dequeueing produces predicatble (FIFO) results.
  
  const int testSize = 8;
  Queue<int> q;

  assert(q.isEmpty() && q.getSize() == 0);
  q.enqueue(0);
  assert(!q.isEmpty() && q.getSize() == 1);
  for (int i = 1; i < testSize; i++) {
    q.enqueue(i);
  }
  assert(!q.isEmpty() && q.getSize() == testSize);
  for (int i = 0; i < testSize; i++) {
    assert(q.peek() == i);
    assert(q.dequeue() == i);
  }

  // Test underflow_errors are properly thrown on dequeues and peeks
  // when empty.  Also test that if an underflow is thrown, the queue
  // is not disturbed, i.e., it remains empty.
  
  assert(q.isEmpty());
  bool underflowHappened = false;
  try {
    q.dequeue();
  } 
  catch (underflow_error e) {
    underflowHappened = true;
  }
  assert(underflowHappened);
  assert(q.isEmpty());
  underflowHappened = false;
  try {
    q.peek();
  } 
  catch (underflow_error e) {
    underflowHappened = true;
  }
  assert(underflowHappened);
  
  cout << "All tests have passed\n";
  return 0;
}