001package algs13; 002import java.text.DecimalFormat; 003import stdlib.*; 004 005/* 006 * Complete the methods below. 007 * All of these methods modify the list. 008 * Use the function checkInvariants to ensure that your list is well-formed after you modify it. 009 * Note that this list keeps track of the number of elements N. 010 * It is important that N accurately reflect the length of the list. 011 * 012 * You may not add any fields to the node or list classes. 013 * You may not add any methods to the node class. 014 * You may not create any new objects objects. 015 * For example, you may not create a new Node, new Stack, or new ArrayList. 016 * 017 * new Node (...) // Forbidden: create a new Node object. 018 * 019 * You *may* declare variables of type Node. 020 * 021 * Node x = first; // Allowed: declare variable of type Node. 022 * 023 * You may not change the item value of any existing node, only change the next pointer. 024 * 025 * x.item = ... // Forbidden 026 * x.next = ... // Allowed 027 * first = ... // Allowed 028 * 029 * Each function must be independent. 030 * For example, you cannot call delete to implement remove. 031 * You MAY add private methods to the list class (helper functions for the recursion). 032 * You do NOT need to use recursion for this homework. 033 * You can use loops in each problem. 034 */ 035public class MyLinked2 { 036 static class Node { 037 public Node (double item, Node next) { this.item = item; this.next = next; } 038 public double item; 039 public Node next; 040 } 041 int N; 042 Node first; 043 044 // delete the kth element (where k is between 0 and N-1 inclusive) 045 public void delete (int k) { 046 if (k < 0 || k >= N) throw new IllegalArgumentException (); 047 // TODO 048 } 049 050 // reverse the list "in place"... 051 public void reverse () { 052 // TODO 053 } 054 055 // remove all occurrences of item from the list 056 public void remove (double item) { 057 // TODO 058 } 059 060 public static void main (String args[]) { 061 //mainDebug (); 062 mainRunTests (); 063 } 064 private static void mainDebug () { 065 // Use this for debugging! 066 // Add the names of helper functions if you use them. 067 Trace.drawStepsOfMethod ("delete"); 068 Trace.drawStepsOfMethod ("reverse"); 069 Trace.drawStepsOfMethod ("remove"); 070 Trace.showObjectIdsRedundantly(true); 071 Trace.run (); 072 // TODO: Put the test here you want to debug: 073 testReverse ("11 21 31 41", "[ 41 31 21 11 ]"); 074 StdOut.println ("Finished tests"); 075 } 076 private static void mainRunTests () { 077 // Trace.run (); // uncomment this to get drawings in showError 078 testDelete (1, "11 21 31 41", "[ 11 31 41 ]"); 079 testDelete (2, "11 21 31 41", "[ 11 21 41 ]"); 080 testDelete (3, "11 21 31 41", "[ 11 21 31 ]"); 081 testDelete (1, "11 21 31 41 51", "[ 11 31 41 51 ]"); 082 testDelete (2, "11 21 31 41 51", "[ 11 21 41 51 ]"); 083 testDelete (3, "11 21 31 41 51", "[ 11 21 31 51 ]"); 084 testDelete (4, "11 21 31 41 51", "[ 11 21 31 41 ]"); 085 testDelete (0, "11 21 31 41 51", "[ 21 31 41 51 ]"); 086 testDelete (0, "11", "[ ]"); 087 testDelete (0, "11 21 31 41", "[ 21 31 41 ]"); 088 testDelete (0, "", "java.lang.IllegalArgumentException"); 089 testDelete(-1, "11 21 31", "java.lang.IllegalArgumentException"); 090 testDelete (3, "11 21 31", "java.lang.IllegalArgumentException"); 091 092 testReverse ("11 21 31 41", "[ 41 31 21 11 ]"); 093 testReverse ("11 21 31 41 51", "[ 51 41 31 21 11 ]"); 094 testReverse ("11 21", "[ 21 11 ]"); 095 testReverse ("11 21 31", "[ 31 21 11 ]"); 096 testReverse ("11", "[ 11 ]"); 097 testReverse ("", "[ ]"); 098 099 testRemove (5, "8 11 5 5 21 31 5 5 5 41", "[ 8 11 21 31 41 ]"); 100 testRemove (5, "11 5 5 21 5 31 5 5 41 8", "[ 11 21 31 41 8 ]"); 101 testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]"); 102 testRemove (5, "11 21 31 5 41", "[ 11 21 31 41 ]"); 103 testRemove (5, "11 5 21 31 41", "[ 11 21 31 41 ]"); 104 testRemove (5, "11 5 5 21 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]"); 105 testRemove (5, "11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]"); 106 testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]"); 107 testRemove (5, "11 5 21 5 31 5 41", "[ 11 21 31 41 ]"); 108 testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]"); 109 testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]"); 110 testRemove (5, "11 5 5 21 31 41", "[ 11 21 31 41 ]"); 111 testRemove (5, "11 5 5 5 21 31 41", "[ 11 21 31 41 ]"); 112 testRemove (5, "11 21 31 5 5 41", "[ 11 21 31 41 ]"); 113 testRemove (5, "11 21 31 5 5 5 41", "[ 11 21 31 41 ]"); 114 testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]"); 115 testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]"); 116 testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]"); 117 testRemove (5, "5 5 11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]"); 118 testRemove (5, "5 5 5 11 5 5 5 21 31 5 5 41 5 5", "[ 11 21 31 41 ]"); 119 testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]"); 120 testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]"); 121 testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]"); 122 testRemove (5, "11", "[ 11 ]"); 123 testRemove (5, "11 21", "[ 11 21 ]"); 124 testRemove (5, "11 21 31", "[ 11 21 31 ]"); 125 testRemove (5, "5 5 5", "[ ]"); 126 testRemove (5, "5 5", "[ ]"); 127 testRemove (5, "5", "[ ]"); 128 testRemove (5, "", "[ ]"); 129 testRemove (5.1, "5.1 5.1 5.1 5 11 5.1 5.1 21 5.1 31 5.1 5.1 41 5.1 5.1 5.1", "[ 5 11 21 31 41 ]"); 130 StdOut.println ("Finished tests"); 131 } 132 133 /* ToString method to print */ 134 public String toString () { 135 // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes 136 DecimalFormat format = new DecimalFormat ("#.###"); 137 StringBuilder result = new StringBuilder ("[ "); 138 for (Node x = first; x != null; x = x.next) { 139 result.append (format.format (x.item)); 140 result.append (" "); 141 } 142 result.append ("]"); 143 return result.toString (); 144 } 145 146 /* Method to create lists */ 147 public static MyLinked2 of(String s) { 148 MyLinked2 result = new MyLinked2 (); 149 if ("".equals (s)) return result; 150 151 int N = 0; 152 Node first = null; 153 String[] nums = s.split (" "); 154 for (int i = nums.length-1; i >= 0; i--) { 155 try { 156 double num = Double.parseDouble (nums[i]); 157 first = new Node (num, first); 158 N++; 159 } catch (NumberFormatException e) { 160 throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 161 } 162 } 163 result.first = first; 164 result.N = N; 165 return result; 166 } 167 168 static void showError (String message) { 169 Trace.draw (); 170 StdOut.println (message); 171 //throw new Error (); // stops execution 172 } 173 private static void checkInvariants (String message, MyLinked2 list) { 174 java.util.HashSet<Node> visited = new java.util.HashSet<>(); 175 int num = 0; 176 for (Node x = list.first; x!=null; x=x.next) { 177 if (visited.contains(x)) { 178 showError (String.format ("%s: Node list has cycle, starting at Node with item=%f", message, x.item)); 179 showError ("Refusing to run any more tests until the cycle is removed."); 180 System.exit(1); 181 } 182 visited.add(x); 183 num++; 184 } 185 if (num != list.N) { 186 showError (String.format ("%s: N=%d, but there are %d Nodes.", message, list.N, num)); 187 } 188 } 189 private static void check (String message, MyLinked2 actual, String expected) { 190 checkInvariants (message, actual); 191 if (!expected.equals (actual.toString ())) { 192 showError (String.format ("%s: expected=%s, actual=%s", message, expected, actual.toString ())); 193 } 194 } 195 private static void testDelete (int k, String list, String expected) { 196 MyLinked2 actual = MyLinked2.of (list); 197 String message = String.format ("[ %s ].delete( %d )", list, k); 198 try { 199 actual.delete (k); 200 } catch (Throwable e) { 201 String exception = e.getClass ().getName (); 202 if (! exception.equals (expected)) { 203 e.printStackTrace (); // for debugging 204 showError (String.format ("%s: expected=%s, actual=%s", message, expected, exception)); 205 } 206 return; 207 } 208 check (message, actual, expected); 209 } 210 private static void testReverse (String list, String expected) { 211 MyLinked2 actual = MyLinked2.of (list); 212 actual.reverse (); 213 String message = String.format ("[ %s ].reverse( )", list); 214 check (message, actual, expected); 215 } 216 private static void testRemove (double item, String list, String expected) { 217 MyLinked2 actual = MyLinked2.of (list); 218 actual.remove (item); 219 String message = String.format ("[ %s ].remove( %.2f )", list, item); 220 check (message, actual, expected); 221 } 222}