This is the test program that will grading the assignment:

CS 143 Assignment 4 Improving DoublyLinkedList (DLList) DUE on Tuesday, February 19 at 11:59 PM Your assignment is to improve the DoublyLinkedList class we wrote in class. Please start with the version uploaded to Canvas called DLList (abbreviated version shown on the back of this page) to make sure there is a common starting point, but it should be equivalent to what we wrote in class. (This version includes generics and an iterator.) descendinglterator method and Backward Conductor (20 points) Implement a new inner BackwardConductor class that implements Iterator and the method public Iterator implements Iterable{ | private static class Node @param i Zero-based index of element @return element i (throws if invalid i) public Node prev, next; public T data; public Node(Node prev, T data, public T get(int i) ( Node next) ( this . prev prev; this.next next; this.data-data; if (i current head; for (int j-e; current!-null && j *Get and remove element i from the list implements Iterator car; // Next node to visit public Conductor(DLList list) @param i Zero-based index of element @return element i (throws if invalid i) car-list.head; /7 Begin at head public T remove(int i)( if (i (null, data, null); tail-head; else // Put new node after tail tail.next new Node(tail, data,null); tail-tail.next; //New node is now last // The Conductor object can walk this list // forward, front to back. Each time /I .next() is called, the Conductor // produces one more piece of data, // starting with head and ending with tail return new Conductor (this); Page 2 of2 1 import java.util.Iterator; 3 public class DLListTest 5 public static String ordinal(int x) int one-x%10; if (one 1) if (one 2) if (one 3) return x + "th"; return x "st"; return x + "nd" return x + "rd"; 10 12 13 14 15 16 17 18 19 20 21 22 public static boolean verifyCDLList list, int n) 23 24 25 26 27 28 29 30 31 32 public static int verifyCalls 0; public static int verifySize 0; public static int verifyRev0 public static long verifyTime ; verifyCalls lterator> f-list.iterator(); int count 0 int hash-0 int hash2 -0; int hash3a -1 int hash3b -0 int hash3c 0; int hash3d -1 int bcount -0; int bhash -0; int bhash2 -0; int bhash3a 1; int bhash3b0; int bhash3c0; int bhash3d 1; while (f.hasNextO) f 34 35 36 37 38 39 40 int hc-f.nextO.hashCodeO 41 hash + hc; hash2 (hash2 65537) + hc; int hca-(hc & 0xFF) 1103515245 0x55555555; int hcb-(Chc >> 8) & xFF) * 1103515245 A 0x55555555; int hcc-(Chc>>16) & 0xFF) * 1103515245 A 0x55555555; int hcd-(Chc>> 24) & xFF) * 1103515245 A 0x55555555; int a hash3a * hca + hash3b * hcc; int b hash3a *hcb + hash3b *hcd int c hash3c * hca + hash3d* hcc; int d hash3c * hcb + hash3d * hcd; 43 45 46 47 48 49 50 52 53 54 hash3b-b; hash3c c hash3dd; count++; if (count > 10000000) [ System.out.println("Your list appears to contain a loop which causes it to iterate forward forever!"; 57 58 59 first -f.nextO; String out - first.toStringO); T nextf.nextO; while C!next.equals(first)) [ 61 63 65 out +", " + next; next f.nextO System.out.println("Loop value(s):" +out) return false; 67 68 69 70 71 72 Iterator blist.descendingIteratorO; while (b.hasNext(O) int hcb.nextO.hashCodeO bhash += hc; bhash2 (bhash2 65537) + hc; 74 75 76 int hca-(hc & 0xFF) 1103515245 0x55555555; int hcb-(Chc >> 8) & xFF) * 1103515245 A 0x55555555; int hcc-(Chc>>16) & 0xFF) * 1103515245 A 0x55555555; int hcd-(Chc>> 24) & xFF) * 1103515245 A 0x55555555; int ba-hca bhash3a + hcb bhash3c 79 80 81 82 83 84 85 86 int bb-hca* bhash3b +hcb *bhash3d int bc-hcc* bhash3a + hcd * bhash3c int bd hcc * bhash3b +hcd * bhash3d; bhash3aba; bhash3b-bb; bhash3c-bc; bhash3d-bd; bcount++ if (bcount > 10000000) i 89 90 91 92 93 94 95 96 97 98 System.out.printlnC"Your list appears to contain a loop which causes it to iterate backward forever!"; first f.nextO; String out - first.toStringO); T next-f.nextO; while C!next.equals(first)) [ out ", " + next; next -f.nextO; System.out.printlnC"Loop value(s): " + out); return false; 100 101 102 103 104 105 106 107 108 109 110 if (countbcount) System.out.println "Forward iteration counted " count + " elements but backward iterator counted"bcount); else if (hash !- bhash) System.out.printlnC" Forward iteration saw the same count but a different set of element values!" System.out.printlnC"Backard iteration saw the same elements in the same order as forward!"; System.out.printlnC"Backward iterator did not see the reverse of forward's elements!"); else if (hash2bhash2 && count > 1) } else if (hash3a != bhash3a II hash3b !-bhash3b II hash3c != bhash3c II hash3d != bhash3d) { t else 112 113 114 115 116 verifyRev++; long start System.nanoTime); int size -list.sizeO); long end System.nanoTime); verifyTime + (end start); if (ncount 11 count!- size) 118 System.out.println("There should be""elements, forward iteration counted " count 119 +" elements, size method says there are"size); } else 121 122 123 124 125 126 1278 128 verifySizet+; return true; return false; public static void main(String[] args) { int iterScore 0, sizeScore, getScore 0, revScore 0, addScore0 try f System.out.printlnC"First, making sure add, get, forward iterator work."); for (int z -0; z(); if (z1) 135 verify(a, 0); 137 138 139 140 141 142 143 144 145 146 147 148 149 for (inti 0; i ilist - new DLListo; boolean ilistoK true; try System.out.println("Creating a list by adding the numbers 50 through 99."); for (int i -50; i -1; i--) f ilist.add(0, i); if (verifyCilist, 50 +26 - i)) vscore++ System.out.printlnC"Trying to get them all..."); for (int 1-0; i (); for (inti -0; i - 0; i--) f 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 System.out.printlnC" Complained when adding" C-i -1)+ " to index " + i); break int saw-list.get(i) if (saw !-- 1) [ System.out.println "Insert at index"++"did not place "+ (-i -1)+"there instead, saw +saw); break; if(1-0){ addScore 10; } catch (Exception e) [ System.out.printlnC"Your code caused an exception when adding in the medium sized list." e.printStackTrace System.out.printlnC"Now testing reverse."; boolean reverseOK true; try f DLList ilist2 new DLListo; for (inti-0; i- 0; i--) [ int ir - ilist.remove(i); if Cir!- 99 ) System.out.println "removeC"+i+ ") should have returned"+ (99 ) " but instead returned "+ir); System.out.printlnC"There may be a problem with backwards remove!"; break if (!verify(ilist, i 1)) break if (ilist.remove(0) !- 1) 1 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 System.out.println("Removing final element didn't get 1"); verify(ilist, 0); catch (Exception e) System.out.printlnC"Your code caused an exception with reversing and removing from the 1-99 list."; e.printStackTrace; ilistoK-false; reverseOK false; J else l System.out.printlnC"Skipping reversing and removing elements from the 1-99 list due to earlier problems in your code."); System.out.printlnC Testing backwards get on a large list..."; try f DLListInteger ilist3 = new DLList(); int m - (int) (Math.random) * 10) + 1; int N 1000000; for (int 1-0; i 181 verifyRev> verifyCalls) System.out.printlnC"Somehow, too many calls to verify are being made for reversal..."); iterScore -20; iterScore verifyRev 20/verifyCalls; System.out.printlnC"Notice there were some errors in your code. It's possible that after fixing those errors, problems with your descendingIteratorO else if (verifyRev-verifyCalls && verifyCalls > 0) else if (verifyCalls >) if (verifyRev 181 verifySize verifyCalls) System.out.printlnC"Somehow, too many calls to verify are being made for size..."); sizescore -l; sizeScore-verifySize 10/verifyCalls; else if (verifySizeverifyCalls && verifyCalls>0) else if verifycalls > ) if (verifySize -5) { 548 549 550 551 552 553 554 sizeScore - 10; } else if (sizeScore boolean compare(DLList