/*
 * Stack class with Iterator
 *
 */

template <class T>
class Stack {

  private:
    // Define elements/nodes in the stack (unidirectional linked list)
    class StackElement {
      protected:
        T value;
        StackElement* next;
      public:
        StackElement(T value, StackElement* next) : value(value), next(next) { }

        ~StackElement() { ; } // nothing to be done
      friend Stack<T>;
    };

    // Pointer to the top of the stack
    StackElement* top;

    // height of the stack
    int size;

    StackElement* recursiveCopy(StackElement* current) {
      if ( current->next == 0 ) {
        return new StackElement(current->value, 0);
      }
      return new StackElement(current, recursiveCopy(current->next) );
    }

  public:
    // Define Iterator for the stack    
    // The iterator allows the following code to traverse Stack s
    // for (Stack::Iterator si = s.begin() ; si != s.end() ; si++ ) {
    //   si.value().do_stuff();
    // } 
    class Iterator {
    private:
      StackElement* current;
      Stack<T>* my_stack;
 
    public:
      Iterator( Stack<T>* my_stack )
        : current(my_stack->top)
        , my_stack(my_stack)
        {}

      Iterator( const Iterator &that ) 
        : current(that.current)
        , my_stack(that.my_stack)
        {}

      // Constructor for Iterator at end
      Iterator( Stack<T>* my_stack, bool end )
        : current(0)
        , my_stack(my_stack)
        {}
     
      ~Iterator() { ; } // nothing to do, does not own pointers
 
      // Overload operators
      // Equality ==
      inline bool operator==(const Iterator &rhs) {
        if ( this->my_stack == rhs.my_stack && this->current == rhs.current ) {
          return true;
        }
        else {
          return false;
        }
      }

      // Inequlaity !=
      inline bool operator!=(const Iterator &rhs) { return !(*this == rhs); }

      // Increment ++
      inline Iterator &operator++(int) {
        current = current->next;
        return *this;
      }
 
      // Move the iterator to the top of the stack
      void begin() { current = my_stack->top; }

      // Move the iterator forward      
      void advance() { current = current->next; }

      // Get the value of the element the iterator is pointing at
      T value() { return current->value; }

    }; 


  public:

    // Constructor: empty stack
    Stack<T>() : top(0), size(0) { }

    // Constructor: copy constructor
    Stack<T>(const Stack<T> &that) {
      if ( that.top == 0 ) {
        top = 0;
        size = 0;
      }
      else {
        top = recursiveCopy(that.top);
        size = that.size();
      }
    }

    // Destructor
    ~Stack<T>() {
       while(top != 0) {
         StackElement* temp = top; 
         top = top->next;
         delete temp;
       }
    }

    // Push an element onto the stack 
    void push(T value) {
      StackElement* element = new StackElement(value,top);
      top = element;
      size++;
    }

    // Pop an element off the stack
    // Assert: stack not empty
    T pop() {
      StackElement* popped = top;
      T return_value = popped->value;
      top = top->next;
      size--;
      delete popped;
      return return_value;
    }

    // Peek at the top element without popping it
    T peek() {
      return top->value;
    } 
      

    // return true if stack size = 0
    bool empty() {
      if ( size == 0 ) { return true; }
      return false;
    }

    // return the height of the stack
    int height() { return size; } 
   
    // return an Iterator to the top of the stack 
    Iterator begin() { return Iterator(this); }

    // return an Iterator to the element past the end of the stack (null)
    Iterator end() { return Iterator(this, true); }
};