001// Exercise 1.4.31
002package algs14;
003import stdlib.*;
004import java.util.NoSuchElementException;
005import algs13.ResizingArrayStack;
006
007/*
008Here is the kind of output I get before fixing the move method.
009
010    4000     0.4   3.1
011    8000     1.5   4.1
012   16000     4.9   3.2
013   32000    21.6   4.4
014
015Here is the kind of output I get after fixing the move method.
016You can see that it is much faster, but not very consistent.
017This is due to garbage collection and other system effects.
018
019    4000     0.0   0.7
020    8000     0.0   1.2
021   16000     0.0   2.2
022   32000     0.0   0.2
023   64000     0.0   1.5
024  128000     0.0   5.7
025  256000     0.1   5.3
026  512000     0.2   2.1
027 1024000     0.4   1.9
028 2048000     0.7   2.0
029 4096000     2.5   3.6
030
031    4000     0.0   0.8
032    8000     0.0   1.6
033   16000     0.0   1.8
034   32000     0.0   0.1
035   64000     0.0   2.0
036  128000     0.0   4.5
037  256000     0.1   5.7
038  512000     0.2   1.8
039 1024000     0.3   1.8
040 2048000     0.7   2.1
041 4096000     3.7   5.1
042
043
044    4000     0.0   0.7
045    8000     0.0   2.0
046   16000     0.0   1.9
047   32000     0.0   0.2
048   64000     0.0   1.7
049  128000     0.0   4.4
050  256000     0.0   1.6
051  512000     0.1   2.3
052 1024000     0.1   0.6
053 2048000     0.1   2.0
054 4096000     0.2   2.4
055 */
056
057public class MyDequeUsingStacks<T> {
058        ResizingArrayStack<T> sl  = new ResizingArrayStack<>();
059        ResizingArrayStack<T> sr  = new ResizingArrayStack<>();
060        public boolean isEmpty ()      { return sl.isEmpty() && sr.isEmpty(); }
061        public int size ()             { return sl.size() + sr.size(); }
062        public void pushLeft (T item)  { sl.push (item); }
063        public void pushRight (T item) { sr.push (item); }
064
065        private void move (ResizingArrayStack<T> from, ResizingArrayStack<T> to) {
066                if (!to.isEmpty ()) throw new IllegalArgumentException();
067                if (from.isEmpty ()) throw new IllegalArgumentException();
068                while (!from.isEmpty ()) {
069                        to.push(from.pop()); 
070                }
071                // TODO: 
072                // Run the main method below.  
073                // Note that the execution is correct (that's the first part of the test).
074                // Note also that performance is terrible (that's the second part of the test).
075                // In particular, for N pops, the running time increases proportionally to N^2.
076                // So the amortized time for each pop is linear (proportional to N).
077                // 
078                // Your goal is to change this method so that overall performance of 
079                // the main method improves, by altering the number of elements moved 
080                // from "from" to "to".
081                //
082                // Your solution must continue to pass the correctness tests below.
083                // It must also have amortized constant time per pop.
084                // So for N pops, the running time should increase proportionally to N.
085                //
086                // You can use one temporary stack to help you:
087                //   ResizingArrayStack<T> tmp = new ResizingArrayStack<>();
088                // You may find it helpful to print the sizes while debugging:
089                //   StdOut.println ("from: " + from.size () + " to: " + to.size ());
090                // You can print out the content of the stacks by uncommenting the 
091                // lines in popLeft and popRight, below.
092        }
093
094        public T popLeft () {
095                if (isEmpty()) { throw new NoSuchElementException(); }
096                if (sl.isEmpty ()) { 
097                        //StdOut.println("r2l before: " + sl + ": " + sr);
098                        move (sr, sl); 
099                        //StdOut.println("r2l after:  " + sl + ": " + sr);
100                }
101                return sl.pop ();
102        }
103
104        public T popRight () {
105                if (isEmpty()) { throw new NoSuchElementException(); }
106                if (sr.isEmpty ()) { 
107                        //StdOut.println("l2r before: " + sl + ": " + sr);
108                        move (sl, sr); 
109                        //StdOut.println("l2r after:  " + sl + ": " + sr);
110                }
111                return sr.pop ();
112        }
113
114        public String toString () {
115                if (isEmpty ()) return "[ ]";
116
117                ResizingArrayStack<T> srBackwards = new ResizingArrayStack<>();
118                for (T item : sr)
119                        srBackwards.push (item);
120
121                StringBuilder sb = new StringBuilder ("[ ");
122                for (T item : sl) {
123                        sb.append (item);
124                        sb.append (" ");
125                }
126                for (T item : srBackwards) {
127                        sb.append (item);
128                        sb.append (" ");
129                }
130
131                sb.append ("]");
132                return sb.toString ();
133        }
134        private void check (String expected) {
135                if (expected != null) {
136                        if (!expected.equals (this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\"");
137                }
138                //StdOut.println (this);
139        }
140        private void check (T iExpected, T iActual, String expected) {
141                if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
142                check (expected);
143        }
144        private void check (T iExpected, T iActual) {
145                if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
146        }
147        private static void correctnessTest () {
148                MyDequeUsingStacks<Integer> d1 = new MyDequeUsingStacks<> ();
149                d1.pushLeft(0);
150                d1.pushLeft(1);
151                d1.pushLeft(2);
152                d1.pushLeft(3);
153                d1.check(0,d1.popRight());
154                d1.check(3,d1.popLeft());
155                d1.check(1,d1.popRight());
156                d1.check(2,d1.popLeft());
157                d1.pushRight(0);
158                d1.pushRight(1);
159                d1.pushRight(2);
160                d1.pushRight(3);
161                d1.check(0,d1.popLeft());
162                d1.check(3,d1.popRight());
163                d1.check(1,d1.popLeft());
164                d1.check(2,d1.popRight());
165
166                Integer k;
167
168                if (!d1.isEmpty ()) throw new Error();
169                d1.pushLeft (11);
170                d1.check ("[ 11 ]");
171                d1.pushLeft (12);
172                d1.check ("[ 12 11 ]");
173                k = d1.popLeft ();
174                d1.check (12, k, "[ 11 ]");
175                k = d1.popLeft ();
176                d1.check (11, k, "[ ]");
177
178                try {
179                        d1.popLeft ();
180                        throw new Error ("Expected exception");
181                } catch (NoSuchElementException e) {}
182
183                if (!d1.isEmpty ()) throw new Error();
184                for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
185                for (int i = 0; i < 20; i++) { d1.check (19-i, d1.popLeft ()); }
186
187                if (!d1.isEmpty ()) throw new Error();
188                for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
189                for (int i = 0; i < 20; i++) { d1.check (i, d1.popRight ()); }
190
191                if (!d1.isEmpty ()) throw new Error();
192                for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
193                for (int i = 0; i < 10; i++) { d1.check (i, d1.popRight ()); }
194                for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popLeft ()); }
195
196                if (!d1.isEmpty ()) throw new Error();
197                for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
198                for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popLeft ()); }
199                for (int i = 0; i < 10; i++) { d1.check (i, d1.popRight ()); }
200
201                if (!d1.isEmpty ()) throw new Error();
202                d1.pushRight (11);
203                d1.check ("[ 11 ]");
204                d1.pushRight (12);
205                d1.check ("[ 11 12 ]");
206                k = d1.popRight ();
207                d1.check (12, k, "[ 11 ]");
208                k = d1.popRight ();
209                d1.check (11, k, "[ ]");
210
211                if (!d1.isEmpty ()) throw new Error();
212                for (int i = 0; i < 20; i++) { d1.pushRight (i); }
213                for (int i = 0; i < 20; i++) { d1.check (19-i, d1.popRight ()); }
214
215                if (!d1.isEmpty ()) throw new Error();
216                for (int i = 0; i < 20; i++) { d1.pushRight (i); }
217                for (int i = 0; i < 20; i++) { d1.check (i, d1.popLeft ()); }
218
219                if (!d1.isEmpty ()) throw new Error();
220                for (int i = 0; i < 20; i++) { d1.pushRight (i); }
221                for (int i = 0; i < 10; i++) { d1.check (i, d1.popLeft ()); }
222                for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popRight ()); }
223
224                if (!d1.isEmpty ()) throw new Error();
225                for (int i = 0; i < 20; i++) { d1.pushRight (i); }
226                for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popRight ()); }
227                for (int i = 0; i < 10; i++) { d1.check (i, d1.popLeft ()); }
228
229                try {
230                        d1.popRight ();
231                        throw new Error ("Expected exception");
232                } catch (NoSuchElementException e) {}
233                
234                StdOut.println("Finished correctness test.");
235        }
236
237        private static void performanceTest() {
238                int MIN = 2000;
239                int MAX = 4096000;              
240                double prev = timeTrial(MIN);
241                for (int N = MIN*2; N<=MAX; N += N) {
242                        double time = timeTrial(N);
243                        StdOut.format("%8d %9.3f %5.1f\n", N, time, time/prev);
244                        prev = time;
245                }
246        }
247        private static double timeTrial(int N) {
248                int NUM_TRIALS = 1;
249                MyDequeUsingStacks<Integer> d1 = new MyDequeUsingStacks<> ();
250                Stopwatch sw = new Stopwatch ();
251                for (int trial=0; trial < NUM_TRIALS; trial++) {
252                        for (int i=0; i<2*N; i++) {
253                                d1.pushLeft (i);
254                        }
255                        for (int i=0; i<N; i++) {
256                                d1.popRight();
257                                d1.popLeft();
258                        }
259                }
260                return sw.elapsedTime ();
261        }
262
263
264        public static void main (String args[]) {
265                //Trace.drawStepsOfMethod ("correctnessTest");
266                //Trace.drawStepsOfMethod ("move");
267                //Trace.run ();
268                correctnessTest ();
269                performanceTest ();
270        }
271}