package algs13;
import  stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
 *  Compilation:  javac Stack.java
 *  Execution:    java Stack < input.txt
 *
 *  A generic stack, implemented using a linked list. Each stack
 *  element is of type Item.
 *
 *  % more tobe.txt
 *  to be or not to - be - - that - - - is
 *
 *  % java Stack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

/**
 *  The {@code Stack} class represents a last-in-first-out (LIFO) stack of generic items.
 *  It supports the usual <em>push</em> and <em>pop</em> operations, along with methods
 *  for peeking at the top item, testing if the stack is empty, and iterating through
 *  the items in LIFO order.
 *  <p>
 *  All stack operations except iteration are constant time.
 *  <p>
 *  For additional documentation, see <a href="/algs4/13stacks">Section 1.3</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 */
public class Stack<T> implements Iterable<T> {
  private int N;          // size of the stack
  private Node<T> first;  // top of stack

  // helper linked list class
  private static class Node<T> {
    public Node () { }
    public T item;
    public Node<T> next;
  }

  /**
   * Create an empty stack.
   */
  public Stack() {
    this.first = null;
    this.N = 0;
  }

  /**
   * Is the stack empty?
   */
  public boolean isEmpty() {
    return first == null;
  }

  /**
   * Return the number of items in the stack.
   */
  public int size() {
    return N;
  }

  /**
   * Add the item to the stack.
   */
  public void push(T item) {
    Node<T> oldfirst = first;
    first = new Node<>();
    first.item = item;
    first.next = oldfirst;
    N++;
  }

  /**
   * Delete and return the item most recently added to the stack.
   * @throws java.util.NoSuchElementException if stack is empty.
   */
  public T pop() {
    if (isEmpty()) throw new NoSuchElementException("Stack underflow");
    T item = first.item;        // save item to return
    first = first.next;            // delete first node
    N--;
    return item;                   // return the saved item
  }


  /**
   * Return the item most recently added to the stack.
   * @throws java.util.NoSuchElementException if stack is empty.
   */
  public T peek() {
    if (isEmpty()) throw new NoSuchElementException("Stack underflow");
    return first.item;
  }

  /**
   * Return string representation.
   */
  public String toString() {
    StringBuilder s = new StringBuilder();
    for (T item : this)
      s.append(item + " ");
    return s.toString();
  }


  // check internal invariants
  private static <T> boolean check(Stack<T> that) {
    int N = that.N;
    Stack.Node<T> first = that.first;
    if (N == 0) {
      if (first != null) return false;
    }
    else if (N == 1) {
      if (first == null)      return false;
      if (first.next != null) return false;
    }
    else {
      if (first.next == null) return false;
    }

    // check internal consistency of instance variable N
    int numberOfNodes = 0;
    for (Stack.Node<T> x = first; x != null; x = x.next) {
      numberOfNodes++;
    }
    if (numberOfNodes != N) return false;

    return true;
  }


  /**
   * Return an iterator to the stack that iterates through the items in LIFO order.
   */
  public Iterator<T> iterator()  { return new ListIterator();  }

  // an iterator, doesn't implement remove() since it's optional
  private class ListIterator implements Iterator<T> {
    private Node<T> current = first;
    public void remove() { throw new UnsupportedOperationException(); }
    public boolean hasNext() { return current != null; }
    //public ListIterator () { TraceGraph.draw (); }
    public T next() {
      if (!hasNext()) throw new NoSuchElementException();
      T item = current.item;
      current = current.next;
      return item;
    }
  }

  /**
   * A test client.
   */
  public static void main(String[] args) {
    StdIn.fromString ("to be or not to - be - - that - - - is");
    //StdIn.fromString ("0 - 1 2 3 4 5 6 7 8 9 - -");
    Stack<String> stack = new Stack<>();
    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) stack.push(item);
      else if (!stack.isEmpty()) StdOut.print(stack.pop() + " ");
    }
    StdOut.println();
    StdOut.println(stack.size() + " left on stack:");
    for (String s : stack) {
      StdOut.print (s + " ");
    }
    StdOut.println ();
  }
  public static void main1(String[] args) {
    //Trace.showBuiltInObjectsVerbose (true);
    Trace.drawStepsOfMethod ("main");
    Trace.run ();
    Integer r1 = null;
    Stack<Integer> s1 = new Stack<>();
    s1.push (11);
    s1.push (21);
    s1.push (31);
    s1.push (41);
    s1.push (51);
    r1 = s1.pop ();
    r1 = s1.pop ();
    r1 = s1.pop ();
    r1 = null;
    s1.push (61);
    s1.push (71);
    
    String r2 = null;
    Stack<String> s2 = new Stack<>();   
    s2.push ("a");
    s2.push ("b");
    s2.push ("c");
    s2.push ("d");
    s2.push ("e");
    r2 = s2.pop ();
    r2 = s2.pop ();
    r2 = s2.pop ();
    r2 = null;
    s2.push ("f");
    s2.push ("g");
    s2.push ("h");
  }
  public static void main2(String[] args) {
    Trace.drawStepsOfMethod ("main");
    Trace.run ();
    Stack<Integer> s1 = new Stack<>();
    s1.push (300);
    Stack<String> s2 = new Stack<>();
    s2.push ("duck");
    s2.push ("goose");
  }
}