001package algs13;
002import stdlib.*;
003import java.text.DecimalFormat;
004import java.util.NoSuchElementException;
005
006/**
007 * This is a skeleton file for your homework.
008 * Complete the functions below. 
009 * You may also edit the function "main" to test your code.
010 * 
011 * You should not use any loops or recursions, except in "delete"
012 * Delete may use one loop or recursive helper.
013 *
014 * You must not add fields or static variables.
015 * As always, you must not change the declaration of any method.
016 * Do not change any of the methods I have provided, such as "toString" and "check".
017 */
018
019public class MyDeque {
020        Node first = null;
021        Node last = null;
022        int N = 0;
023
024        static class Node {
025                public Node (double item) { this.item = item; }
026                public double item;
027                public Node next;
028                public Node prev;
029        }
030
031        public MyDeque ()         { };
032        public boolean isEmpty () { return N == 0; }
033        public int size ()        { return N; }
034
035        public void pushLeft (double item) {
036                // TODO
037        }
038
039        public double popLeft () {
040                if (N == 0) throw new NoSuchElementException ();
041                return StdRandom.uniform ();
042                // TODO
043        }
044
045        public void pushRight (double item) {
046                // TODO
047        }
048        
049        public double popRight () {
050                if (N == 0) throw new NoSuchElementException ();
051                return StdRandom.uniform ();
052                // TODO
053        }
054
055        /* The concat method should take the Nodes from "that" and add them to "this"
056         * After execution, "that" should be empty.
057         * See the tests in the main program.
058         *
059         * Do not use a loop or a recursive definition.
060         * This method can declare Node variables, but may not create new node objects (using "new").
061         * Therefore the method should not call pushLeft or pushRight (which use create new objects).
062         */
063        public void concat (MyDeque that) {
064                // TODO
065        }
066
067        /* Delete should delete and return the kth element from the left (where k is between 0 and N-1).
068         * See the tests in the main program.
069         *
070         * You may use a loop or a recursive definition here.
071         * This method can declare Node variables, but may not create new node objects (using "new").
072         * Therefore the method should not call pushLeft or pushRight (which use create new objects).
073         */
074        public double delete (int k) {
075                if (k < 0 || k >= N) throw new IllegalArgumentException ();
076                return StdRandom.uniform ();
077                // TODO 
078        }
079
080
081        public static void main (String args[]) {
082                // TODO: Uncomment these lines to use the visual debugger
083                // Note, however, that this will substantially slow things down
084                // So you should leave these commented unless you are using the debugger
085                //
086                // Trace.drawStepsOfMethod ("main");
087                // Trace.drawStepsOfMethod ("pushLeft");
088                // Trace.run ();
089
090                // Here are some tests to get you started.
091                // You can edit this all you like.
092                MyDeque d1, d2, d3;
093                double k;
094
095                ////////////////////////////////////////////////////////////////////
096                // push/pop tests
097                ////////////////////////////////////////////////////////////////////
098                d1 = new MyDeque ();
099                d1.pushLeft (11);
100                check ("left1", d1, "[ 11 ]");
101                d1.pushLeft (12);
102                check ("left2", d1, "[ 12 11 ]");
103                d1.pushLeft (13);
104                check ("left3", d1, "[ 13 12 11 ]");
105                k = d1.popLeft ();
106                check ("left4", d1, "[ 12 11 ]", k, 13);
107                k = d1.popLeft ();
108                check ("left5", d1, "[ 11 ]", k, 12);
109                k = d1.popLeft ();
110                check ("left6", d1, "[ ]", k, 11);
111
112                d1 = new MyDeque ();
113                d1.pushRight (11);
114                check ("right1", d1, "[ 11 ]");
115                d1.pushRight (12);
116                check ("right2", d1, "[ 11 12 ]");
117                d1.pushRight (13);
118                check ("right3", d1, "[ 11 12 13 ]");
119                k = d1.popRight ();
120                check ("right4", d1, "[ 11 12 ]", k, 13);
121                k = d1.popRight ();
122                check ("right5", d1, "[ 11 ]", k, 12);
123                k = d1.popRight ();
124                check ("right6", d1, "[ ]", k, 11);
125
126                d1 = new MyDeque ();
127                d1.pushLeft (11);
128                check ("left/right1", d1, "[ 11 ]");
129                d1.pushRight (21);
130                check ("left/right2", d1, "[ 11 21 ]");
131                d1.pushLeft (12);
132                check ("left/right3", d1, "[ 12 11 21 ]");
133                d1.pushRight (22);
134                check ("left/right4", d1, "[ 12 11 21 22 ]");
135                k = d1.popLeft ();
136                check ("left/right5", d1, "[ 11 21 22 ]", k, 12);
137                k = d1.popLeft ();
138                check ("left/right6", d1, "[ 21 22 ]", k, 11);
139                k = d1.popLeft ();
140                check ("left/right7", d1, "[ 22 ]", k, 21);
141                k = d1.popLeft ();
142                check ("left/right8", d1, "[ ]", k, 22);
143
144                d1 = new MyDeque ();
145                d1.pushLeft (11);
146                check ("left/right10", d1, "[ 11 ]");
147                d1.pushRight (21);
148                check ("left/right11", d1, "[ 11 21 ]");
149                d1.pushLeft (12);
150                check ("left/right12", d1, "[ 12 11 21 ]");
151                d1.pushRight (22);
152                check ("left/right13", d1, "[ 12 11 21 22 ]");
153                k = d1.popRight ();
154                check ("left/right14", d1, "[ 12 11 21 ]", k, 22);
155                k = d1.popRight ();
156                check ("left/right15", d1, "[ 12 11 ]", k, 21);
157                k = d1.popRight ();
158                check ("left/right16", d1, "[ 12 ]", k, 11);
159                k = d1.popRight ();
160                check ("left/right17", d1, "[ ]", k, 12);
161
162                ////////////////////////////////////////////////////////////////////
163                //  test exceptions
164                ////////////////////////////////////////////////////////////////////
165                try {
166                        d1.popLeft ();
167                        showError ("Expected exception1");
168                } catch (NoSuchElementException e) {}
169                try {
170                        d1.popRight ();
171                        showError ("Expected exception2");
172                } catch (NoSuchElementException e) {}
173
174                ////////////////////////////////////////////////////////////////////
175                // concat tests (and more push/pop tests)
176                ////////////////////////////////////////////////////////////////////
177                d1 = new MyDeque ();
178                d1.concat (new MyDeque ());
179                check ("concat1", d1, "[ ]");
180                d1.pushLeft (11);
181                d1.concat (new MyDeque ());
182                check ("concat2", d1, "[ 11 ]");
183
184                d1 = new MyDeque ();
185                d2 = new MyDeque ();
186                d2.pushLeft (11);
187                d1.concat (d2);
188                check ("concat3a", d1, "[ 11 ]");
189                check ("concat3b", d2, "[ ]");
190
191                d1 = new MyDeque ();
192                d2 = new MyDeque ();
193                d1.pushLeft (11);
194                d1.pushLeft (12);
195                d2.pushLeft (21);
196                d2.pushLeft (22);
197                d1.concat (d2);
198                check ("concat4a", d1, "[ 12 11 22 21 ]");
199                check ("concat4b", d2, "[ ]");
200                d2.concat (d1);
201                check ("concat5a", d2, "[ 12 11 22 21 ]");
202                check ("concat5b", d1, "[ ]");
203
204                d1 = new MyDeque ();
205                for (int i = 10; i < 13; i++) { d1.pushLeft (i); checkInvariants ("left1", d1); }
206                for (int i = 20; i < 23; i++) { d1.pushRight (i); checkInvariants ("right2", d1); }
207                check ("concat6", d1, "[ 12 11 10 20 21 22 ]");
208                d2 = new MyDeque ();
209                d1.concat (d2);
210                check ("concat7a", d1, "[ 12 11 10 20 21 22 ]");
211                check ("concat7b", d2, "[ ]");
212
213                for (int i = 30; i < 33; i++) { d2.pushLeft (i); checkInvariants ("left3", d2); }
214                for (int i = 40; i < 43; i++) { d2.pushRight (i); checkInvariants ("right4", d2); }
215                check ("concat9", d2, "[ 32 31 30 40 41 42 ]");
216
217                d3 = new MyDeque ();
218                d2.concat (d3);
219                check ("concat10", d2, "[ 32 31 30 40 41 42 ]");
220                check ("concat11", d3, "[ ]");
221
222                d1.concat (d2);
223                check ("concat12", d1, "[ 12 11 10 20 21 22 32 31 30 40 41 42 ]");
224                check ("concat13", d2, "[ ]");
225                for (int i = 0; i < 12; i++) { d1.popLeft (); checkInvariants ("left5", d1); }
226                ////////////////////////////////////////////////////////////////////
227                // delete tests
228                ////////////////////////////////////////////////////////////////////
229                d1 = new MyDeque ();
230                d1.pushLeft (11);
231                k = d1.delete (0);
232                check ("delete1", d1, "[ ]", k, 11);
233                for (int i = 10; i < 20; i++) { d1.pushRight (i); checkInvariants ("right6", d1); }
234                k = d1.delete (0);
235                check ("delete2", d1, "[ 11 12 13 14 15 16 17 18 19 ]", k, 10);
236                k = d1.delete (8);
237                check ("delete3", d1, "[ 11 12 13 14 15 16 17 18 ]", k, 19);
238                k = d1.delete (4);
239                check ("delete4", d1, "[ 11 12 13 14 16 17 18 ]", k, 15);
240                k = d1.delete (3);
241                check ("delete5", d1, "[ 11 12 13 16 17 18 ]", k, 14);
242                k = d1.delete (0);
243                check ("delete6", d1, "[ 12 13 16 17 18 ]", k, 11);
244                k = d1.delete (4);
245                check ("delete7", d1, "[ 12 13 16 17 ]", k, 18);
246                k = d1.delete (3);
247                check ("delete8", d1, "[ 12 13 16 ]", k, 17);
248                k = d1.delete (1);
249                check ("delete9", d1, "[ 12 16 ]", k, 13);
250                k = d1.delete (1);
251                check ("delete10", d1, "[ 12 ]", k, 16);
252                k = d1.delete (0);
253                check ("delete10", d1, "[ ]", k, 12);
254                
255                ////////////////////////////////////////////////////////////////////
256                // More push/pop
257                ////////////////////////////////////////////////////////////////////
258                d1 = new MyDeque();
259                d1.pushRight(21);
260                check("left/right20", d1, "[ 21 ]");
261                d1.pushLeft(11);
262                check("left/right21", d1, "[ 11 21 ]");
263                k = d1.popLeft();
264                check("left/right22", d1, "[ 21 ]", k, 11);
265                d1.pushRight(22);
266                check("left/right23", d1, "[ 21 22 ]");
267
268                d1 = new MyDeque();
269                d1.pushRight(21);
270                check("left/right30", d1, "[ 21 ]");
271                d1.pushRight(22);
272                check("left/right31", d1, "[ 21 22 ]");
273                d1.pushLeft(11);
274                check("left/right32", d1, "[ 11 21 22 ]");
275                k = d1.popLeft();
276                check("left/right33", d1, "[ 21 22 ]", k, 11);
277                k = d1.popLeft();
278                check("left/right34", d1, "[ 22 ]", k, 21);
279                d1.pushLeft(12);
280                check("left/right35", d1, "[ 12 22 ]");
281                StdOut.println ("Finished tests");
282        }
283        
284        public MyDeque (String s) {
285                String[] nums = s.split (" ");
286                for (int i = nums.length-1; i >= 0; i--) {
287                        try { 
288                                pushLeft (Double.parseDouble (nums[i]));                        
289                        } catch (NumberFormatException e) {     }
290                }
291        }
292        public String toString () { 
293                DecimalFormat format = new DecimalFormat ("#.###");
294                StringBuilder result = new StringBuilder ("[ ");
295                for (Node x = first; x != null; x = x.next) {
296                        result.append (format.format (x.item));
297                        result.append (" ");
298                }
299                result.append ("]");
300                return result.toString ();
301        }
302
303
304        private static void checkInvariants (String message, MyDeque that) {
305                int N = that.N;
306                MyDeque.Node first = that.first;
307                MyDeque.Node last = that.last;
308
309                if (N < 0) throw new Error ();
310                if (N == 0) {
311                        if (first != null) {
312                                showError (String.format ("%s: N==0, Expected first == null.", message));
313                        }
314                        if (last != null) {
315                                showError (String.format ("%s: N==0, Expected last == null.", message));
316                        }
317                } else {
318                        if (first == null) {
319                                showError (String.format ("%s: N!=0, Expected first != null.", message));
320                        }
321                        if (last == null) {
322                                showError (String.format ("%s: N!=0, Expected last != null.", message));
323                        }
324                }
325                if (N > 0) {
326                        MyDeque.Node prev = null;
327                        MyDeque.Node current = first;
328                        for (int i = 0; i < N; i++) {
329                                if (current == null) {
330                                        showError (String.format ("%s: N==%d, Expected %d next nodes, but got less.", message, N, N));
331                                        return;
332                                }
333                                if (current.prev != prev) { 
334                                        showError (String.format ("%s: i=%d, Broken prev link.", message, i));
335                                        return;
336                                }
337                                prev = current;
338                                current = current.next;
339                        }
340                        if (current != null) {
341                                showError (String.format ("%s: N==%d, Expected %d next nodes, but got more.", message, N, N));
342                                return;
343                        }
344                        MyDeque.Node next = null;
345                        current = last;
346                        for (int i = 0; i < N; i++) {
347                                if (current == null) {
348                                        showError (String.format ("%s: N==%d, Expected %d prev nodes, but got less.", message, N, N));
349                                        return;
350                                }
351                                if (current.next != next) {
352                                        showError (String.format ("%s: i=%d, Broken next link.", message, i));
353                                        return;
354                                }
355                                next = current;
356                                current = current.prev;
357                        }
358                        if (current != null) {
359                                showError (String.format ("%s: N==%d, Expected %d prev nodes, but got more.", message, N, N));
360                                return;
361                        }
362                }
363        }
364        private static void check (String message, MyDeque actual, String expected) {
365                checkInvariants (message, actual);
366                if (expected != null) {
367                        if (!expected.equals (actual.toString ())) {
368                                showError ("Expected \"" + expected + "\", got \"" + actual + "\"");
369                                return;
370                        }
371                }
372        }
373        private static void check (String message, MyDeque actual, String expected, double dActual, double dExpected) {
374                if (dExpected != dActual) {
375                        showError ("Expected \"" + dExpected + "\", got \"" + dActual + "\"");
376                        return;
377                }
378                check (message, actual, expected);
379        }
380
381        private static void showError (String message) {
382                Trace.draw ();
383                StdOut.println (message);
384                throw new Error (); // stops execution
385        }
386}