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.run (); 071 // TODO: Put the test here you want to debug: 072 testDelete (2, "11 21 31 41", "[ 11 21 41 ]"); 073 StdOut.println ("Finished tests"); 074 } 075 private static void mainRunTests () { 076 // Trace.run (); // uncomment this to get drawings in showError 077 testDelete (1, "11 21 31 41", "[ 11 31 41 ]"); 078 testDelete (2, "11 21 31 41", "[ 11 21 41 ]"); 079 testDelete (3, "11 21 31 41", "[ 11 21 31 ]"); 080 testDelete (1, "11 21 31 41 51", "[ 11 31 41 51 ]"); 081 testDelete (2, "11 21 31 41 51", "[ 11 21 41 51 ]"); 082 testDelete (3, "11 21 31 41 51", "[ 11 21 31 51 ]"); 083 testDelete (4, "11 21 31 41 51", "[ 11 21 31 41 ]"); 084 testDelete (0, "11 21 31 41 51", "[ 21 31 41 51 ]"); 085 testDelete (0, "11", "[ ]"); 086 testDelete (0, "11 21 31 41", "[ 21 31 41 ]"); 087 testDelete (0, "", "java.lang.IllegalArgumentException"); 088 testDelete(-1, "11 21 31", "java.lang.IllegalArgumentException"); 089 testDelete (3, "11 21 31", "java.lang.IllegalArgumentException"); 090 091 testReverse ("11 21 31 41", "[ 41 31 21 11 ]"); 092 testReverse ("11 21 31 41 51", "[ 51 41 31 21 11 ]"); 093 testReverse ("11 21", "[ 21 11 ]"); 094 testReverse ("11 21 31", "[ 31 21 11 ]"); 095 testReverse ("11", "[ 11 ]"); 096 testReverse ("", "[ ]"); 097 098 testRemove (5, "8 11 5 5 21 31 5 5 5 41", "[ 8 11 21 31 41 ]"); 099 testRemove (5, "11 5 5 21 5 31 5 5 41 8", "[ 11 21 31 41 8 ]"); 100 testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]"); 101 testRemove (5, "11 21 31 5 41", "[ 11 21 31 41 ]"); 102 testRemove (5, "11 5 21 31 41", "[ 11 21 31 41 ]"); 103 testRemove (5, "11 5 5 21 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]"); 104 testRemove (5, "11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]"); 105 testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]"); 106 testRemove (5, "11 5 21 5 31 5 41", "[ 11 21 31 41 ]"); 107 testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]"); 108 testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]"); 109 testRemove (5, "11 5 5 21 31 41", "[ 11 21 31 41 ]"); 110 testRemove (5, "11 5 5 5 21 31 41", "[ 11 21 31 41 ]"); 111 testRemove (5, "11 21 31 5 5 41", "[ 11 21 31 41 ]"); 112 testRemove (5, "11 21 31 5 5 5 41", "[ 11 21 31 41 ]"); 113 testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]"); 114 testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]"); 115 testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]"); 116 testRemove (5, "5 5 11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]"); 117 testRemove (5, "5 5 5 11 5 5 5 21 31 5 5 41 5 5", "[ 11 21 31 41 ]"); 118 testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]"); 119 testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]"); 120 testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]"); 121 testRemove (5, "11", "[ 11 ]"); 122 testRemove (5, "11 21", "[ 11 21 ]"); 123 testRemove (5, "11 21 31", "[ 11 21 31 ]"); 124 testRemove (5, "5 5 5", "[ ]"); 125 testRemove (5, "5 5", "[ ]"); 126 testRemove (5, "5", "[ ]"); 127 testRemove (5, "", "[ ]"); 128 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 ]"); 129 StdOut.println ("Finished tests"); 130 } 131 132 /* ToString method to print */ 133 public String toString () { 134 // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes 135 DecimalFormat format = new DecimalFormat ("#.###"); 136 StringBuilder result = new StringBuilder ("[ "); 137 for (Node x = first; x != null; x = x.next) { 138 result.append (format.format (x.item)); 139 result.append (" "); 140 } 141 result.append ("]"); 142 return result.toString (); 143 } 144 145 /* Method to create lists */ 146 public static MyLinked2 of(String s) { 147 MyLinked2 result = new MyLinked2 (); 148 if ("".equals (s)) return result; 149 150 int N = 0; 151 Node first = null; 152 String[] nums = s.split (" "); 153 for (int i = nums.length-1; i >= 0; i--) { 154 try { 155 double num = Double.parseDouble (nums[i]); 156 first = new Node (num, first); 157 N++; 158 } catch (NumberFormatException e) { 159 throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 160 } 161 } 162 result.first = first; 163 result.N = N; 164 return result; 165 } 166 167 static void showError (String message) { 168 Trace.draw (); 169 StdOut.println (message); 170 //throw new Error (); // stops execution 171 } 172 private static void checkInvariants (String message, MyLinked2 list) { 173 java.util.HashSet<Node> visited = new java.util.HashSet<>(); 174 int num = 0; 175 for (Node x = list.first; x!=null; x=x.next) { 176 if (visited.contains(x)) { 177 showError (String.format ("%s: Node list has cycle, starting at Node with item=%f", message, x.item)); 178 showError ("Refusing to run any more tests until the cycle is removed."); 179 System.exit(1); 180 } 181 visited.add(x); 182 num++; 183 } 184 if (num != list.N) { 185 showError (String.format ("%s: N=%d, but there are %d Nodes.", message, list.N, num)); 186 } 187 } 188 private static void check (String message, MyLinked2 actual, String expected) { 189 checkInvariants (message, actual); 190 if (!expected.equals (actual.toString ())) { 191 showError (String.format ("%s: expected=%s, actual=%s", message, expected, actual.toString ())); 192 } 193 } 194 private static void testDelete (int k, String list, String expected) { 195 MyLinked2 actual = MyLinked2.of (list); 196 String message = String.format ("[ %s ].delete( %d )", list, k); 197 try { 198 actual.delete (k); 199 } catch (Throwable e) { 200 String exception = e.getClass ().getName (); 201 if (! exception.equals (expected)) { 202 e.printStackTrace (); // for debugging 203 showError (String.format ("%s: expected=%s, actual=%s", message, expected, exception)); 204 } 205 return; 206 } 207 check (message, actual, expected); 208 } 209 private static void testReverse (String list, String expected) { 210 MyLinked2 actual = MyLinked2.of (list); 211 actual.reverse (); 212 String message = String.format ("[ %s ].reverse( )", list); 213 check (message, actual, expected); 214 } 215 private static void testRemove (double item, String list, String expected) { 216 MyLinked2 actual = MyLinked2.of (list); 217 actual.remove (item); 218 String message = String.format ("[ %s ].remove( %.2f )", list, item); 219 check (message, actual, expected); 220 } 221}