001package algs13;
002import stdlib.*;
003import java.util.Iterator;
004import java.util.NoSuchElementException;
005/* ***********************************************************************
006 *  Compilation:  javac ResizingArrayStack.java
007 *  Execution:    java ResizingArrayStack < input.txt
008 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
009 *
010 *  Stack implementation with a resizing array.
011 *
012 *  % more tobe.txt
013 *  to be or not to - be - - that - - - is
014 *
015 *  % java ResizingArrayStack < tobe.txt
016 *  to be not that or be (2 left on stack)
017 *
018 *************************************************************************/
019public class ResizingArrayStack<T> implements Iterable<T> {
020        private T[] a;        // array of items
021        private int N;        // number of elements on stack
022
023        // create an empty stack
024        @SuppressWarnings("unchecked")
025        public ResizingArrayStack() {
026                this.a = (T[]) new Object[2];
027                this.N = 0;
028        }
029
030        public boolean isEmpty() { return N == 0; }
031        public int size()        { return N;      }
032
033
034        // resize the underlying array holding the elements
035        @SuppressWarnings("unchecked")
036        private void resize(int capacity) {
037                if (capacity <= N) throw new IllegalArgumentException ();
038                T[] temp = (T[]) new Object[capacity];
039                for (int i = 0; i < N; i++)
040                        temp[i] = a[i];
041                a = temp;
042        }
043
044        // push a new item onto the stack
045        public void push(T item) {
046                if (N == a.length) resize(2*N); // increase array size if necessary
047                //if (N == a.length) resize((int)Math.ceil (N*1.5));
048                a[N] = item;
049                N++;
050        }
051
052        // delete and return the item most recently added
053        public T pop() {
054                if (isEmpty()) { throw new Error("Stack underflow error"); }
055                N--;
056                T item = a[N];
057                a[N] = null; // to avoid loitering
058                if (N > 0 && N == a.length/4) resize(a.length/2); // shrink size of array if necessary
059                return item;
060        }
061
062        /**
063         * Return string representation.
064         */
065        public String toString() {
066                StringBuilder s = new StringBuilder();
067                for (T item : this)
068                        s.append(item + " ");
069                return s.toString();
070        }
071        
072        public Iterator<T> iterator()  { return new ReverseArrayIterator();  }
073
074        // an iterator, doesn't implement remove() since it's optional
075        private class ReverseArrayIterator implements Iterator<T> {
076                private int i = N;
077                public boolean hasNext()  { return i > 0;                               }
078                public void remove()      { throw new UnsupportedOperationException();  }
079
080                public T next() {
081                        if (!hasNext()) throw new NoSuchElementException();
082                        return a[--i];
083                }
084        }
085
086        /* *********************************************************************
087         * Test routine.
088         **********************************************************************/
089//      public static void bookMain(String[] args) {
090//              StdIn.fromString ("to be or not to - be - - that - - - is");
091//
092//              ResizingArrayStack<String> s = new ResizingArrayStack<>();
093//              while (!StdIn.isEmpty()) {
094//                      String item = StdIn.readString();
095//                      if (!item.equals("-")) s.push(item);
096//                      else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
097//              }
098//              StdOut.println("(" + s.size() + " left on stack)");
099//      }
100//
101        /* *********************************************************************
102         * Test routine.
103         **********************************************************************/
104        public static void main(String[] args) {
105                double prevTime = 1;
106                for (int i = 0, size = 20; i<19; i += 1, size *= 2) {
107                        Stopwatch s = new Stopwatch ();
108
109                        for (int k = 0; k < 1; k++) {
110                                ResizingArrayStack<Double> stack = new ResizingArrayStack<> ();
111                                for (int j = 0; j < size; j++) {
112                                        stack.push (1.2);
113                                }
114                        }
115
116                        double thisTime = s.elapsedTime ();
117                        StdOut.format ("size=%d thisTime=%f ratio=%f\n", size, thisTime, thisTime/prevTime);
118                        prevTime = thisTime;
119                }
120        }
121        public static void main2 (String[] args) {
122                //Trace.showObjectIdsRedundantly (true);
123                Trace.showBuiltInObjects (true);
124                //Trace.showBuiltInObjectsVerbose (true);
125                Trace.drawStepsOfMethod ("main");
126                Trace.drawStepsOfMethod ("resize");
127                Trace.run ();
128                
129                ResizingArrayStack<Integer> s1 = new ResizingArrayStack<> ();
130                ResizingArrayStack<String> s2 = new ResizingArrayStack<> ();
131                s1.push (11);
132                s1.push (21);
133                s1.push (31);
134
135                //s2.push (41);
136                s2.push ("duck");
137                s2.push ("goose");
138        }
139}