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}