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