// ---------------------------------------------------------------------------
// SimpleUnboundedStack.h
//
// A generic unbounded stack class.  (There is already a stack 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.
//
//   Stack()       Constructor: declares a stack and initializes it to empty.
//   ~Stack()      Destructor.
//   s.size()      Returns the number of elements in the stack.
//   s.isEmpty()   Returns whether the stack is empty.
//   s.push(x)     Pushes x.   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).
//   s.pop()       If not empty, pops and returns the element that was
//                 popped, else throws a standard underflow_error.
//   s.peek()      If not empty, returns the top element, else throws a
//                 standard underflow_error.
// ---------------------------------------------------------------------------

#ifndef _SIMPLE_UNBOUNDED_STACK_H
#define _SIMPLE_UNBOUNDED_STACK_H

#include <stdexcept>
using namespace std;

// A stack object is represented as a singly-linked list of nodes.  The top
// of the stack is the first node.

template<class T>
class Stack {

// A private nested class of nodes, and a neat little routine
// that recursively blows away a whole linked chain of nodes.
private:
  class Node {
  public:
    T data;
    Node* next;
    Node(T data, Node* next): data(data), next(next) {}
  };
  static void clear(Node* n) {if (n != 0) {clear(n->next); delete n;}}
  
// Representation.  A single pointer field:  
private:
  Node* head;
  
// Constructors and Destructors
public:
  Stack(): head(0) {}
  ~Stack() {clear(head);}
  
// Behavior
public:
  int getSize() {
    int count = 0;
    for (Node* n = head; n != 0; n = n->next) count++;
    return count;
  }
  
  bool isEmpty() {
    return head == 0;
  }
  
  void push(T x) {
    head = new Node(x, head);
  }
  
  T pop() {
    if (head == 0) throw underflow_error("Cannot pop from empty stack");
    Node* nodeToDelete = head;
    T valueToReturn = head->data;
    head = head->next;
    delete nodeToDelete;
    return valueToReturn;
  }
  
  T peek() {
    if (head == 0) throw underflow_error("Cannot peek into empty stack");
    return head->data;
  }
  
// Prohibit copying and assignment
private:
  Stack(Stack&);
  Stack& operator=(Stack&);
};

#endif

// ---------------------------------------------------------------------------
// testunboundedstack.cpp                                                                 
//                                                                           
// A test script for the SimpleUnboundedStack class.
// ---------------------------------------------------------------------------

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

#include "SimpleUnboundedStack.h"

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

  // Test an integer stack of testSize 8 for empty, full, and that
  // enqueing then dequeueing produces predicatble (LIFO) results.
  
  const int testSize = 100;
  Stack<int> s;

  assert(s.isEmpty() && s.getSize() == 0);
  s.push(0);
  assert(!s.isEmpty() && s.getSize() == 1);
  for (int i = 1; i < testSize; i++) {
    s.push(i);
  }
  assert(!s.isEmpty() && s.getSize() == testSize);
  for (int i = testSize - 1; i >= 0; i--) {
    assert(s.peek() == i);
    assert(s.pop() == i);
  }

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