001package algs13; 002import java.text.DecimalFormat; 003import stdlib.*; 004 005/* 006 * Complete the methods below. 007 * See the tests in main for examples of what each function should do. 008 * 009 * deleteFirst should modify the list. 010 * None of the other methods should modify 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 change method or field names. 015 * You may not create any new node objects or other objects. 016 * For example, you cannot create a new Stack or ArrayList. 017 * 018 * Each function must be independent: you cannot call one solution function from the other. 019 * You MAY add private methods to the list class 020 * (helper functions for recursion, if you chose to use it). 021 */ 022public class MyLinked0 { 023 static class Node { 024 public Node (double item, Node next) { this.item = item; this.next = next; } 025 public double item; 026 public Node next; 027 } 028 Node first; 029 030 // Return the size of the list 031 // See the tests for more... 032 public int size () { 033 return StdRandom.uniform (100); //TODO 034 } 035 036 // Return the sum of the positive elements of the list 037 // See the tests for more... 038 public double sumPositiveElements () { 039 return StdRandom.random (); //TODO 040 } 041 042 // Return the length of the common prefix for this and that 043 // See the tests for more... 044 public int lengthOfCommonPrefix (MyLinked0 that) { 045 return StdRandom.uniform (100); //TODO 046 } 047 048 // Return true if the elements are strictly increasing 049 // See the tests for more... 050 public boolean isIncreasing () { 051 return StdRandom.bernoulli(); //TODO 052 } 053 054 // Return true if the even indexed elements are strictly increasing 055 // See the tests for more... 056 public boolean evenIndicesIncreasing () { 057 return StdRandom.bernoulli(); //TODO 058 } 059 060 // Delete the first element from this list, if it exists 061 // Do nothing if the list is empty 062 // This is similar to Stack.pop 063 public void deleteFirst () { 064 // TODO 065 } 066 067 public static void main (String args[]) { 068 //mainDebug (); 069 mainRunTests (); 070 } 071 private static void mainDebug () { 072 // Use this for debugging! 073 // Uncomment the call in main to use this. 074 // Add the names of helper functions if you use them. 075 Trace.drawStepsOfMethod ("size"); 076 Trace.drawStepsOfMethod ("sumPositiveElements"); 077 Trace.drawStepsOfMethod ("lengthOfCommonPrefix"); 078 Trace.drawStepsOfMethod ("isIncreasing"); 079 Trace.drawStepsOfMethod ("evenIndicesIncreasing"); 080 Trace.drawStepsOfMethod ("deleteFirst"); 081 //Trace.showObjectIdsRedundantly(true); 082 Trace.run (); 083 // TODO: Put the test here you want to debug: 084 //testSumPositiveElements (104, "11 -3 -4 21 31 41 -1"); 085 //testLengthOfCommonPrefix (3, "11 21 31 41 41", "11 21 31 5 41"); 086 //testIsIncreasing(true, "11 21 31 41"); 087 //testEvenIndicesIncreasing(true, "11 0 21 11 31 0 41"); 088 //testDeleteFirst ("21 31", "11 21 31"); 089 StdOut.println ("Finished tests"); 090 } 091 private static void mainRunTests () { 092 testSize (2, "11 21"); 093 testSize (4, "11 -21.2 31 41"); 094 testSize (1, "11"); 095 testSize (0, ""); 096 097 testSumPositiveElements (104, "11 -3 -4 21 31 41 -1"); 098 testSumPositiveElements (104, "11 -3 -4 21 31 -1 41"); 099 testSumPositiveElements (0, "-11.2"); 100 testSumPositiveElements (52, "11 -21 -31 41"); 101 testSumPositiveElements (0, ""); 102 testSumPositiveElements (11, "11"); 103 104 testLengthOfCommonPrefix (3, "11 21 31 41 41", "11 21 31 5 41"); 105 testLengthOfCommonPrefix (3, "11 21 31 41 41 51", "11 21 31 5 41 51"); 106 testLengthOfCommonPrefix (3, "11 21 31 41 5", "11 21 31 5 41"); 107 testLengthOfCommonPrefix (3, "11 21 31 5 41", "11 21 31 41 5"); 108 testLengthOfCommonPrefix (2, "11 21 31 41 5", "11 21 5 31 41"); 109 testLengthOfCommonPrefix (2, "11 21 5 31 41", "11 21 31 41 5"); 110 testLengthOfCommonPrefix (1, "11 21 31 41 5", "11 5 21 31 41"); 111 testLengthOfCommonPrefix (1, "11 5 21 31 41", "11 21 31 41"); 112 testLengthOfCommonPrefix (0, "11 21 31 41", "5 11 21 31 41"); 113 testLengthOfCommonPrefix (0, "5 11 21 31 41", "11 21 31 41"); 114 testLengthOfCommonPrefix (3, "11 21 31 41", "11 21 31 5 41"); 115 testLengthOfCommonPrefix (3, "11 21 31", "11 21 31"); 116 testLengthOfCommonPrefix (3, "11 21 31", "11 21 31 41"); 117 testLengthOfCommonPrefix (2, "11 21 31 41", "11 21"); 118 testLengthOfCommonPrefix (1, "11", "11 21 31 41"); 119 testLengthOfCommonPrefix (1, "11", "11"); 120 testLengthOfCommonPrefix (0, "11", "5"); 121 testLengthOfCommonPrefix (0, "11 21 31 41", ""); 122 testLengthOfCommonPrefix (0, "", "11 21 31 41"); 123 testLengthOfCommonPrefix (0, "", ""); 124 125 testIsIncreasing(true, "11 21 31 41"); 126 testIsIncreasing(true, "11 21 31 41 51"); 127 testIsIncreasing(false, "11 21 21 31 41 51"); 128 testIsIncreasing(false, "11 21 5 31 41 51"); 129 testIsIncreasing(false, "11 21 5 31 41 51"); 130 testIsIncreasing(false, "11 21 31 5 41 51"); 131 testIsIncreasing(false, "11 21 31 41 5 51"); 132 testIsIncreasing(false, "11 21 31 41 51 5"); 133 testIsIncreasing(false, "11 21 5 31 41"); 134 testIsIncreasing(false, "11 5 21 31 41"); 135 testIsIncreasing(false, "11 21 31 5 41"); 136 testIsIncreasing(false, "11 21 31 41 5"); 137 testIsIncreasing(false, "11 5"); 138 testIsIncreasing(true, "11 21"); 139 testIsIncreasing(true, "11"); 140 testIsIncreasing(true, ""); 141 142 testEvenIndicesIncreasing(true, "11 0 21 11 31 0 41 0"); 143 testEvenIndicesIncreasing(true, "11 0 21 11 31 0 41"); 144 testEvenIndicesIncreasing(true, "-41 0 -31 11 -21 0 -11"); 145 testEvenIndicesIncreasing(false, "11 0 21 0 5 11 31 0 41"); 146 testEvenIndicesIncreasing(false, "11 0 21 0 21 11 31 0 41"); 147 testEvenIndicesIncreasing(false, "-41 0 -31 11 21 0 -11"); 148 testEvenIndicesIncreasing(true, "-21 -11 31"); 149 testEvenIndicesIncreasing(false, "11 -3 -4 21 31 41 -1"); 150 testEvenIndicesIncreasing(false, "11 -21 -31 41"); 151 testEvenIndicesIncreasing(false, "11 -3 -4 21 31 -1 41"); 152 testEvenIndicesIncreasing(true, "11 1 21 -2 31 -3"); 153 testEvenIndicesIncreasing(false, "11 1 21 -2 31 -3 5"); 154 testEvenIndicesIncreasing(true, "11 1 21 -2 31"); 155 testEvenIndicesIncreasing(false, "11 1 21 -2 5 -3"); 156 testEvenIndicesIncreasing(true, "11 1 21 -2"); 157 testEvenIndicesIncreasing(true, "11 1 21"); 158 testEvenIndicesIncreasing(true, "11 1"); 159 testEvenIndicesIncreasing(true, "11"); 160 testEvenIndicesIncreasing(true, "-11"); 161 testEvenIndicesIncreasing(true, ""); 162 163 testDeleteFirst ("21 31", "11 21 31"); 164 testDeleteFirst ("21 11", "31 21 11"); 165 testDeleteFirst ("21", "11 21"); 166 testDeleteFirst ("", "11"); 167 testDeleteFirst ("", ""); 168 169 StdOut.println ("Finished tests"); 170 } 171 172 173 /* ToString method to print */ 174 public String toString () { 175 // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes 176 DecimalFormat format = new DecimalFormat ("#.###"); 177 StringBuilder result = new StringBuilder ("[ "); 178 for (Node x = first; x != null; x = x.next) { 179 result.append (format.format (x.item)); 180 result.append (" "); 181 } 182 result.append ("]"); 183 return result.toString (); 184 } 185 public String toStringWithQuadraticPerformance () { 186 // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes 187 DecimalFormat format = new DecimalFormat ("#.###"); 188 String result = ""; 189 for (Node x = first; x != null; x = x.next) { 190 result += format.format (x.item); 191 result += " "; 192 } 193 result += "]"; 194 return result; 195 } 196 197 /* Method to create lists */ 198 public static MyLinked0 from(String s) { 199 var result = new MyLinked0 (); 200 if ("".equals (s)) return result; 201 202 Node first = null; 203 String[] nums = s.split (" "); 204 for (int i = nums.length-1; i >= 0; i--) { 205 try { 206 double num = Double.parseDouble (nums[i]); 207 first = new Node (num, first); 208 } catch (NumberFormatException e) { 209 throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 210 } 211 } 212 result.first = first; 213 return result; 214 } 215 216 // lots of copy and paste in these test! 217 private static void testSize (int expected, String sList) { 218 var list = MyLinked0.from (sList); 219 String sStart = list.toString (); 220 int actual = list.size(); 221 if (expected != actual) { 222 StdOut.format ("Failed %s.size(): Expecting (%d) Actual (%d)\n", sStart, expected, actual); 223 } 224 String sEnd = list.toString (); 225 if (! sStart.equals (sEnd)) { 226 StdOut.format ("Failed %s.size(): List changed to %s\n", sStart, sEnd); 227 } 228 } 229 private static void testSumPositiveElements (double expected, String sList) { 230 var list = MyLinked0.from (sList); 231 String sStart = list.toString (); 232 double actual = list.sumPositiveElements (); 233 if (expected != actual) { 234 StdOut.format ("Failed %s.sumPositiveElements(): Expecting (%f) Actual (%f)\n", sStart, expected, actual); 235 } 236 String sEnd = list.toString (); 237 if (!sStart.equals (sEnd)) { 238 StdOut.format ("Failed %s.sumPositiveElements(): List changed to %s\n", sStart, sEnd); 239 } 240 } 241 private static void testDeleteFirst (String expected, String sList) { 242 String sExpected = MyLinked0.from (expected).toString (); 243 var list = MyLinked0.from (sList); 244 String sStart = list.toString (); 245 list.deleteFirst (); 246 String sEnd = list.toString (); 247 if (! sExpected.equals (sEnd)) { 248 StdOut.format ("Failed %s.deleteFirst(): Expecting %s Actual %s\n", sStart, sExpected, sEnd); 249 } 250 } 251 private static void testIsIncreasing(boolean expected, String sList) { 252 var list = MyLinked0.from (sList); 253 String sStart = list.toString (); 254 boolean actual = list.isIncreasing (); 255 if (expected != actual) { 256 StdOut.format ("Failed %s.isIncreasing(): Expecting (%b) Actual (%b)\n", sStart, expected, actual); 257 } 258 String sEnd = list.toString (); 259 if (!sStart.equals (sEnd)) { 260 StdOut.format ("Failed %s.isIncreasing(): List changed to %s\n", sStart, sEnd); 261 } 262 } 263 private static void testEvenIndicesIncreasing(boolean expected, String sList) { 264 var list = MyLinked0.from (sList); 265 String sStart = list.toString (); 266 boolean actual = list.evenIndicesIncreasing (); 267 if (expected != actual) { 268 StdOut.format ("Failed %s.evenIndicesIncreasing(): Expecting (%b) Actual (%b)\n", sStart, expected, actual); 269 } 270 String sEnd = list.toString (); 271 if (!sStart.equals (sEnd)) { 272 StdOut.format ("Failed %s.evenIndicesIncreasing(): List changed to %s\n", sStart, sEnd); 273 } 274 } 275 private static void testLengthOfCommonPrefix(int expected, String sList1, String sList2) { 276 var list1 = MyLinked0.from (sList1); 277 var list2 = MyLinked0.from (sList2); 278 String sStart1 = list1.toString (); 279 String sStart2 = list2.toString (); 280 int actual = list1.lengthOfCommonPrefix(list2); 281 if (expected != actual) { 282 StdOut.format ("Failed %s.lengthOfCommonPrefix(%s): Expecting (%d) Actual (%d)\n", sStart1, sStart2, expected, actual); 283 } 284 String sEnd1 = list1.toString (); 285 if (!sStart1.equals (sEnd1)) { 286 StdOut.format ("Failed %s.lengthOfCommonPrefix(%s): List changed to %s\n", sStart1, sStart2, sEnd1); 287 } 288 String sEnd2 = list2.toString (); 289 if (!sStart2.equals (sEnd2)) { 290 StdOut.format ("Failed %s.lengthOfCommonPrefix(%s): List changed to %s\n", sStart1, sStart2, sEnd2); 291 } 292 } 293}