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