/* reverse2.cpp -- Matt Mahoney, mmahoney@cs.fit.edu  10/21/2002

ANALYSIS

This program reverses a text file line by line from standard input
to standard output, e.g.

  reverse2 <input.txt >output.txt

If input.txt is

  This
  is a
  test.

then output.txt is

  test.
  is a
  This

DESIGN

The program reads lines of input, pushes them onto a Stack<string>,
then iterates through the stack to print them out.

The program defines a class Stack<T> with the following interface:

  Stack<T> st;          // Defines a stack holding items of type T
  st.push(x);           // Push x onto stack
  st.pop();             // Remove and return the last item pushed
  st.empty();           // true if there is at least one item on stack
  st.begin();           // Iterator pointing to top
  st.end()              // Iterator pointing to bottom
  Stack<T>::iterator    // Type returned by begin(), end()
  Stack<T>::const_iterator  // Type returned if st is const

If the stack is empty, then st.pop() returns the default value for T,
which is 0 for numeric types.

Stack<T>::iterator and Stack<T>::const_iterator are forward iterators.
They support operators *, ->, ++, ==, != and assignment with their usual
meanings.  If p is a const_iterator, then *p and p->m (where m is a member
of T) are read-only, otherwise they may be modified.  iterator may be
converted to const_iterator but not the other way around.

A stack is implemented as a linked list with the top at the start
of the list.  const_iterator is a public nested class of Stack and
is implemented as a pointer to the current node on the list or 0 to
represent the end.  iterator is derived from const_iterator in order
to inherit the data representation, operators == and !=, and to allow
conversion from iterator to const_iterator.
*/
#include <iterator>

template <class T> class Stack {
private:
  struct Stacknode {  // Node of a linked list
    T item;
    Stacknode* next;  // Points to item below, or 0 at bottom
    Stacknode(const T& x, Stacknode* p): item(x), next(p) {}
  } *start;  // Points to front of list (top of stack)
  void destroy();  // Delete the linked list
  void copy(const Stack& st);  // Copy linked list
public:
  Stack(): start(0) {}
  bool empty() const {return start==0;}
  void push(const T& x) {start=new Stacknode(x, start);}
  T pop() {
    T result=T();
    if (!empty()) {
      result=start->item;
      Stacknode* p=start->next;
      delete start;
      start=p;
    }
    return result;
  }

  // Pointer to a const element
  class const_iterator {
    friend class Stack;
  protected:
    Stacknode* ptr;  // Pointer to current node, 0 represents the end
    const_iterator(Stacknode* p): ptr(p) {}  // Used by begin()
  public:
    typedef std::forward_iterator_tag iterator_category;
      // or input_, output_, bidirectional_, or random_access_iterator_tag
    typedef T value_type;         // Type of element
    typedef ptrdiff_t difference_type; // Type returned by iterator subtraction
    typedef const T* pointer;     // Type returned by operator->()
    typedef const T& reference;   // Type returned by operator*()
    const_iterator(): ptr(0) {}
    const_iterator& operator++() {ptr=ptr->next; return *this;}  // prefix ++
    const_iterator operator++(int dummy) {  // postfix ++, return original
      const_iterator result=*this;
      ptr=ptr->next;
      return result;
    }
    pointer operator->() const {return &ptr->item;}
    reference operator*() const {return ptr->item;}
    bool operator==(const_iterator i) const {return ptr==i.ptr;}
    bool operator!=(const_iterator i) const {return ptr!=i.ptr;}
  };

  // Pointer to non-const element, inherits ptr, ==, !=, and some typedefs
  class iterator: public const_iterator {
    friend class Stack;
  private:
    iterator(Stacknode* p): const_iterator(p) {}
  public:
    typedef T* pointer;
    typedef T& reference;
    iterator(): const_iterator(0) {}
    iterator& operator++() {ptr=ptr->next; return *this;}
    iterator operator++(int dummy) {
      iterator result=*this;
      ptr=ptr->next;
      return result;
    }
    pointer operator->() const {return &ptr->item;}
    reference operator*() const {return ptr->item;}
  };

  const_iterator begin() const {return const_iterator(start);}
  iterator begin() {return iterator(start);}
  const_iterator end() const {return const_iterator();}
  iterator end() {return iterator();}

  // Deep copy requires the rule of 3
  ~Stack() {destroy();}
  Stack(const Stack& st): start(0) {copy(st);}
  Stack& operator=(const Stack& st) {
    if (&st!=this) {
      destroy();
      copy(st);
    }
    return *this;
  }
};

// Delete linked list
template<class T> void Stack<T>::destroy() {
  while (start) {
    Stacknode* p=start->next;
    delete start;
    start=p;
  }
}

// Copy linked list from st to start
template<class T> void Stack<T>::copy(const Stack<T>& st) {
  Stacknode** p=&start;
  for (Stack<T>::const_iterator i=st.begin(); i!=st.end(); ++i) {
    *p=new Stacknode(*i, 0);
    p=&((*p)->next);
  }
}

// Test program, reverse stdin to stdout
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
  Stack<string> st;
  string s;
  while (getline(cin, s))
    st.push(s);
  for (Stack<string>::const_iterator p=st.begin(); p!=st.end(); ++p)
    cout << *p << "\n";
  return 0;
}