// stack.h -- John Valois (valoisj@cs.rpi.edu)

// Simple fixed-size stack class.


#ifndef STACK_H
#define STACK_H

#include <algorithm>
#include <cassert>


// Exceptions that can be thrown.
class stack_full {};
class stack_empty {};

// T is the type of data stored in the stack.
template <class T>
class stack
{
public:

  // Constant time.
  stack() : data(new T[default_size]), next(data), end(data + default_size) {
    assert(size() == 0);
    assert(max_size() == default_size);
    assert(invariant());
  }

  // Constant time.
  explicit stack(unsigned sz) : data(new T[sz]), next(data), end(data + sz) {
    assert(size() == 0);
    assert(max_size() == sz);
    assert(invariant());
  }

  // Linear in number of elements on stack.
  ~stack() { 
    assert(invariant());
    delete[] data;
  }

  // Linear in number of elements on argument.
  stack(const stack & s) { 
    assert(s.invariant());
    copy_stack(s); 
    assert(invariant());
    assert(size() == s.size());
    assert(max_size() == s.max_size());
    assert(std::equal(data, end, s.data));
  }

  // Linear in number of elements on argument.
  stack & operator=(const stack & s) { 
    assert(invariant());
    assert(s.invariant());
    if (&s != this) 
      copy_stack(s);
    assert(invariant());
    assert(size() == s.size());
    assert(max_size() == s.max_size());
    assert(std::equal(data, end, s.data));
    return *this;
  }

  // Linear in number of elements on each stack if same;
  // otherwise constant time.
  // Also constant time for special case of s == s.
  bool operator==(const stack & s) const {
    assert(invariant());
    assert(s.invariant());
    if (&s == this)
      return true;
    else if (s.size() != size())
      return false;
    else
      return std::equal(data, end, s.data);
  }
  bool operator!=(const stack & s) const { return !operator==(s); }

  // Add a new element to the stack.
  // Constant time.
  void push(const T & x) {
    assert(invariant());
    if (full())
      throw stack_full();
    *next = x;
    ++next;
    assert(invariant());
    assert(top() == x);
    assert("popping top element restores old value of stack");
    assert("size of stack increased by one");
  }
  
  // Remove top element from stack.
  // Constant time.
  void pop() {
    assert(invariant());
    if (empty())
      throw stack_empty();
    --next;
    assert(invariant());
    assert("size of stack decreased by one");
  }

  // Return top element on stack.
  // Constant time.
  const T & top() const {
    assert(invariant());
    if (empty())
      throw stack_empty();
    return *(next - 1);
  }

  // Return max. number of elements stack can hold.
  unsigned max_size() const { 
    assert(invariant());
    return end - data; 
  }

  // Return current number of elements on stack.
  unsigned size() const { 
    assert(invariant());
    return next - data ; 
  }

  // Is the stack empty?
  bool empty() const {
    assert(invariant());
    return next == data; 
  }

  // Is the stack full?
  bool full() const {
    assert(invariant());
    return next == end; 
  }

  // Constant time.
  void swap(stack & s) {
    assert(invariant());
    assert(s.invariant());
    std::swap(data, s.data);
    std::swap(next, s.next);
    std::swap(end, s.end);
    assert(invariant());
    assert(s.invariant());
    assert("s equals old value of this");
    assert("this equals old value of s");
  }
    
private:
  /* The variable 'data' points to a dynamically allocated array where
     we store the elements on the stack.  One past the end of this array
     is pointed at by 'end', and 'next' points to the next available space
     to place new data.

     The capacity of the stack cannot be changed.
   */
  T * data;
  T * next;
  T * end;

  // Default size of data area.
  static const unsigned default_size;

  /* Copy one stack to another by deallocating the data array, allocating 
     a new one of the proper size, copying the data, and setting the
     end and next pointers appropriately.
   */
  void copy_stack(const stack & s) {
    delete[] data;
    unsigned new_size = s.end - s.data;
    data = new T[new_size];
    std::copy(s.data, s.end, data);
    end = data + new_size;
    next = data + (s.next - s.data);
  }

  bool invariant() const {
    assert(next >= data);
    assert(next <= end);
    return true;
  }
};

template <class T>
const unsigned stack<T>::default_size = 10;

#endif