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 may NOT change method or field names. 033 * You do NOT need to use recursion for this homework. 034 * You can use loops in each problem. 035 */ 036public class MyLinked2 { 037 static class Node { 038 public Node (double item, Node next) { this.item = item; this.next = next; } 039 public double item; 040 public Node next; 041 } 042 int N; 043 Node first; 044 045 // delete the kth element (where k is between 0 and N-1 inclusive) 046 public void delete (int k) { 047 if (k < 0 || k >= N) throw new IllegalArgumentException (); 048 // TODO 049 } 050 051 // reverse the list "in place"... 052 public void reverse () { 053 // TODO 054 } 055 056 // remove all occurrences of item from the list 057 public void remove (double item) { 058 // TODO 059 } 060 061 public static void main (String args[]) { 062 //mainDebug (); 063 mainRunTests (); 064 } 065 private static void mainDebug () { 066 // Use this for debugging! 067 // Add the names of helper functions if you use them. 068 Trace.drawStepsOfMethod ("delete"); 069 Trace.drawStepsOfMethod ("reverse"); 070 Trace.drawStepsOfMethod ("remove"); 071 Trace.showObjectIdsRedundantly(true); 072 Trace.run (); 073 // TODO: Put the test here you want to debug: 074 testReverse ("11 21 31 41", "[ 41 31 21 11 ]"); 075 StdOut.println ("Finished tests"); 076 } 077 private static void mainRunTests () { 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 from(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 int num = 0; 175 Node firstInCycle = null; 176 { 177 java.util.HashSet<Node> visited = new java.util.HashSet<>(); 178 for (Node x = list.first; x!=null; x=x.next) { 179 if (visited.contains(x)) { 180 firstInCycle = x; 181 break; 182 } 183 visited.add(x); 184 num++; 185 } 186 } 187 if (firstInCycle != null) { 188 showError (String.format ("For %s: Node list has cycle.\n" 189 + "Cycle starts at Node with item=%f.\n" 190 + "Refusing to run any more tests until the cycle is removed.\n" 191 + "Uncomment Trace.run() in main to see a picture.\n", message, firstInCycle.item)); 192 System.exit(1); 193 } 194 if (num != list.N) { 195 showError (String.format ("%s: N=%d, but there are %d Nodes.", message, list.N, num)); 196 } 197 } 198 private static void check (String message, MyLinked2 actual, String expected) { 199 checkInvariants (message, actual); 200 if (!expected.equals (actual.toString ())) { 201 showError (String.format ("%s: expected=%s, actual=%s", message, expected, actual.toString ())); 202 } 203 } 204 private static void testDelete (int k, String list, String expected) { 205 MyLinked2 actual = MyLinked2.from (list); 206 String message = String.format ("[ %s ].delete( %d )", list, k); 207 try { 208 actual.delete (k); 209 } catch (Throwable e) { 210 String exception = e.getClass ().getName (); 211 if (! exception.equals (expected)) { 212 e.printStackTrace (); // for debugging 213 showError (String.format ("%s: expected=%s, actual=%s", message, expected, exception)); 214 } 215 return; 216 } 217 check (message, actual, expected); 218 } 219 private static void testReverse (String list, String expected) { 220 MyLinked2 actual = MyLinked2.from (list); 221 actual.reverse (); 222 String message = String.format ("[ %s ].reverse( )", list); 223 check (message, actual, expected); 224 } 225 private static void testRemove (double item, String list, String expected) { 226 MyLinked2 actual = MyLinked2.from (list); 227 actual.remove (item); 228 String message = String.format ("[ %s ].remove( %.2f )", list, item); 229 check (message, actual, expected); 230 } 231}