Source code

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