// ---------------------------------------------------------------------------
// SimpleBoundedStack.h
//
// A generic bounded 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(n)      Constructor: declares a stack with room for n elements;
//                 default size is 256 elements.  Throws a bad_alloc if there
//                 is not enough memory to construct the stack.  Note: many
//                 compilers do not correctly implement Standard C++ and if
//                 you build this class with a non-standard compiler then the
//                 behavior is undefined if there is not enough memory for
//                 the stack.
//   ~Stack()      Destructor.
//   s.size()      Returns the number of elements in the stack.
//   s.isEmpty()   Returns whether the stack is empty.
//   s.isFull()    Returns whether the stack is full.
//   s.push(x)     If not full, pushes x, else throws a standard
//                 overflow_error.
//   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 overflow_error.
// ---------------------------------------------------------------------------

#ifndef _SIMPLE_BOUNDED_STACK_H
#define _SIMPLE_BOUNDED_STACK_H

#include <stdexcept>
using namespace std;

// A stack object wraps a low-level array indexed from 0 to capacity-1 where
// the bottommost element (if it exists) will be in slot 0.  The member top is
// the index of the slot above the top element, i.e. the next available slot
// that an element can go into.  Therefore if top==0 the stack is empty and
// if top==capacity it is full.

template<class T>
class Stack {
  T* data;
  int capacity;
  int top;
  
// Constructors and Destructors
public:
  explicit Stack(int n = 256): top(0), data(new T[n]), capacity(n) {}
  ~Stack() {delete[] data;}

// Behavior
public:
  int getSize() {return top;}
  bool isEmpty() {return top == 0;}
  bool isFull() {return top == capacity;}
  
  void push(T x) {
    if (isFull()) throw overflow_error("cannot push on full stack");
    data[top++] = x;
  }
  
  T pop() {
    if (isEmpty()) throw underflow_error("cannot pop from empty stack");
    return data[--top];
  }
  
  T peek() {
    if (isEmpty()) throw underflow_error("cannot peek into empty stack");
    return data[top - 1];
  }
  
// Prohibit copying and assignment
private:
  Stack(Stack&);
  Stack& operator=(Stack&);
};

#endif

// ---------------------------------------------------------------------------
// testboundedstack.cpp                                                                 
//                                                                           
// A test script for the SimpleBoundedStack class.
// ---------------------------------------------------------------------------

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

#include "SimpleBoundedStack.h"

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

  // Test that the default stack has capacity 256, is created empty,
  // fills after 256, and overflow_errors are thrown correctly.
  
  Stack<char> s1;
  assert(s1.isEmpty() && !s1.isFull() && s1.getSize() == 0);
  for (int i = 0; i < 256; i++) {
    s1.push('*');
  }
  assert(!s1.isEmpty() && s1.isFull());
  
  bool overflowHappened = false;
  try {
    s1.push('@');
  } 
  catch (overflow_error e) {
    overflowHappened = true;
  }
  assert(overflowHappened);

  // Test an integer stack of capacity 8 for empty, full, and that
  // pushing then popping produces predicatble (LIFO) results.
  
  const int capacity = 8;
  Stack<int> s2(capacity);

  assert(s2.isEmpty() && !s2.isFull());
  s2.push(0);
  assert(!s2.isEmpty() && !s2.isFull() && s2.getSize() == 1);
  for (int i = 1; i < capacity; i++) {
    s2.push(i);
  }
  assert(!s2.isEmpty() && s2.isFull() && s2.getSize() == capacity);
  for (int i = capacity - 1; i >= 0; i--) {
    assert(s2.peek() == i);
    assert(s2.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(s2.isEmpty());
  bool underflowHappened = false;
  try {
    s2.pop();
  } 
  catch (underflow_error e) {
    underflowHappened = true;
  }
  assert(underflowHappened);
  assert(s2.isEmpty());
  underflowHappened = false;
  try {
    s2.peek();
  } 
  catch (underflow_error e) {
    underflowHappened = true;
  }
  assert(underflowHappened);
  
  cout << "All tests have passed\n";
  return 0;
}