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}