/******************************************************************************

  *  Compilation:  javac ResizingArrayStackWithReflection.java

  *  Execution:    java ResizingArrayStackWithReflection < input.txt

  *  Dependencies: StdIn.java StdOut.java

  *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt

  *

  *  Stack implementation with a resizing array.

  *

  *  % more tobe.txt

  *  to be or not to - be - - that - - - is

  *

  *  % java ResizingArrayStackWithReflection < tobe.txt

  *  to be not that or be (2 left on stack)

  *

  *  Written by Bruno Lehouque.

  *

  ******************************************************************************/

 import java.lang.reflect.Array;

 import java.util.Iterator;

 import java.util.NoSuchElementException;

 /**

  * A LIFO Stack using a resizeable array.

  */

 public class ResizingArrayStackWithReflection<Item> implements Iterable<Item> {

     private Class<Item[]> itemArrayClass;

     private Item[] array;

     private int N = 0;

     public ResizingArrayStackWithReflection(Class<Item[]> itemArrayClass) {

         this.itemArrayClass = itemArrayClass;

         array = itemArrayClass.cast(Array.newInstance(itemArrayClass.getComponentType(), 1));

     }

     /**

      * Adds a non-{@code null} element on top of the Stack.

      *

      * @param item

      *      the element which is to be added to the Stack

      *

      * @throws IllegalArgumentException if {@code item} is {@code null}.

      */

     public void push(Item item) {

         if (item == null)

             throw new IllegalArgumentException("Cannot add null item.");

         if (N == array.length)

             resize(array.length * 2);

         array[N++] = item;

     }

     /**

      * Removes and returns the top element of the Stack.

      *

      * @return the top element of the Stack

      *

      * @throws NoSuchElementException if the Stack is empty

      */

     public Item pop() {

         if (isEmpty())

             throw new NoSuchElementException();

         Item item = array[--N];

         array[N] = null;

         if ((N > 0) && (N <= array.length / 4))

             resize(array.length / 2);

         return item;

     }

     /**

      * Returns, but doesn't remove, the top element of the Stack.

      *

      * @return the top element of the Stack

      *

      * @throws NoSuchElementException if the Stack is empty

      */

     public Item peek() {

         if (isEmpty())

             throw new NoSuchElementException();

         return array[N - 1];

     }

     /**

      * Returns {@code true} if the Stack is empty.

      *

      * @return {@code true} if the Stack is empty

      */

     public boolean isEmpty() {

         return N == 0;

     }

     /**

      * Returns the size of the Stack.

      *

      * @return the size of the Stack

      */

     public int size() {

         return N;

     }

     /**

      * Returns an iterator which iterates over the Stack from the top element

      * to the bottom element.

      *

      * @return an iterator which iterates over the Stack from the top element

      * to the bottom element

      */

     public Iterator<Item> iterator() {

         return new ReverseArrayIterator();

     }

     private void resize(int size) {

         Item[] newarray = itemArrayClass.cast(Array.newInstance(itemArrayClass.getComponentType(), size));

         for (int i = 0; i < N; i++)

             newarray[i] = array[i];

         array = newarray;

     }

     private class ReverseArrayIterator implements Iterator<Item> {

         private int i = N-1;

         @Override

         public boolean hasNext() {

             return i >= 0;

         }

         @Override

         public Item next() {

             if (!hasNext())

                 throw new NoSuchElementException();

             return array[i--];

         }

         @Override

         public void remove() {

             throw new UnsupportedOperationException("Not supported.");

         }

     }

     /**

      * Test client (copied from ResizingArrayStack).

      */

     public static void main(String[] args) {

         ResizingArrayStackWithReflection<String> s = new ResizingArrayStackWithReflection<String>(String[].class);

         while (!StdIn.isEmpty()) {

             String item = StdIn.readString();

             if (!item.equals("-")) s.push(item);

             else if (!s.isEmpty()) StdOut.print(s.pop() + " ");

         }

         StdOut.println("(" + s.size() + " left on stack)");

     }

 }

 /******************************************************************************

  *  Compilation:  javac ResizingArrayStack.java

  *  Execution:    java ResizingArrayStack < input.txt

  *  Dependencies: StdIn.java StdOut.java

  *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt

  *

  *  Stack implementation with a resizing array.

  *

  *  % more tobe.txt

  *  to be or not to - be - - that - - - is

  *

  *  % java ResizingArrayStack < tobe.txt

  *  to be not that or be (2 left on stack)

  *

  ******************************************************************************/

 import java.util.Iterator;

 import java.util.NoSuchElementException;

 /**

  *  The <tt>ResizingArrayStack</tt> 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>

  *  This implementation uses a resizing array, which double the underlying array

  *  when it is full and halves the underlying array when it is one-quarter full.

  *  The <em>push</em> and <em>pop</em> operations take constant amortized time.

  *  The <em>size</em>, <em>peek</em>, and <em>is-empty</em> operations takes

  *  constant time in the worst case.

  *  <p>

  *  For additional documentation,

  *  see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of

  *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.

  *

  *  @author Robert Sedgewick

  *  @author Kevin Wayne

  */

 public class ResizingArrayStack<Item> implements Iterable<Item> {

     private Item[] a;         // array of items

     private int N;            // number of elements on stack

     /**

      * Initializes an empty stack.

      */

     public ResizingArrayStack() {

         a = (Item[]) new Object[2];

         N = 0;

     }

     /**

      * Is this stack empty?

      * @return true if this stack is empty; false otherwise

      */

     public boolean isEmpty() {

         return N == 0;

     }

     /**

      * Returns the number of items in the stack.

      * @return the number of items in the stack

      */

     public int size() {

         return N;

     }

     // resize the underlying array holding the elements

     private void resize(int capacity) {

         assert capacity >= N;

         Item[] temp = (Item[]) new Object[capacity];

         for (int i = 0; i < N; i++) {

             temp[i] = a[i];

         }

         a = temp;

     }

     /**

      * Adds the item to this stack.

      * @param item the item to add

      */

     public void push(Item item) {

         if (N == a.length) resize(2*a.length);    // double size of array if necessary

         a[N++] = item;                            // add item

     }

     /**

      * Removes and returns the item most recently added to this stack.

      * @return the item most recently added

      * @throws java.util.NoSuchElementException if this stack is empty

      */

     public Item pop() {

         if (isEmpty()) throw new NoSuchElementException("Stack underflow");

         Item item = a[N-1];

         a[N-1] = null;                              // to avoid loitering

         N--;

         // shrink size of array if necessary

         if (N > 0 && N == a.length/4) resize(a.length/2);

         return item;

     }

     /**

      * Returns (but does not remove) the item most recently added to this stack.

      * @return the item most recently added to this stack

      * @throws java.util.NoSuchElementException if this stack is empty

      */

     public Item peek() {

         if (isEmpty()) throw new NoSuchElementException("Stack underflow");

         return a[N-1];

     }

     /**

      * Returns an iterator to this stack that iterates through the items in LIFO order.

      * @return an iterator to this stack that iterates through the items in LIFO order.

      */

     public Iterator<Item> iterator() {

         return new ReverseArrayIterator();

     }

     // an iterator, doesn't implement remove() since it's optional

     private class ReverseArrayIterator implements Iterator<Item> {

         private int i;

         public ReverseArrayIterator() {

             i = N-1;

         }

         public boolean hasNext() {

             return i >= 0;

         }

         public void remove() {

             throw new UnsupportedOperationException();

         }

         public Item next() {

             if (!hasNext()) throw new NoSuchElementException();

             return a[i--];

         }

     }

     /**

      * Unit tests the <tt>Stack</tt> data type.

      */

     public static void main(String[] args) {

         ResizingArrayStack<String> s = new ResizingArrayStack<String>();

         while (!StdIn.isEmpty()) {

             String item = StdIn.readString();

             if (!item.equals("-")) s.push(item);

             else if (!s.isEmpty()) StdOut.print(s.pop() + " ");

         }

         StdOut.println("(" + s.size() + " left on stack)");

     }

 }