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 (helper functions for the recursion). 020 */ 021public class MyLinked1 { 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 030 // write a function to compute the size of the list, using a loop 031 // empty list has size 0 032 public int sizeLoop () { 033 return StdRandom.uniform (100); //TODO: fix this 034 } 035 036 // write a function to compute the size of the list, using a forward recursion 037 // empty list has size 0 038 public int sizeForward () { 039 return StdRandom.uniform (100); //TODO: fix this 040 } 041 042 // write a function to compute the size of the list, using a backward recursion 043 // empty list has size 0 044 public int sizeBackward () { 045 return StdRandom.uniform (100); //TODO: fix this 046 } 047 048 // delete the first element of this list 049 public void deleteFirst () { 050 // TODO 051 } 052 053 // compute the position of the first 5.0 in the list, counting as an offset from the beginning. 054 // if 5.0 is the FIRST element, the position is 0 055 // if 5.0 does not appear, return a negative number 056 // you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper 057 // I would expect 058 // [0,1,2,5,5,5,5,5,8,9].positionOfFirstFiveFromBeginning() == 3 059 // [0,1,2,5,5,5,5,5,8,9].positionOfLastFiveFromEnd() == 2 060 public int positionOfFirstFiveFromBeginning () { 061 return StdRandom.uniform (100); //TODO: fix this 062 } 063 064 // compute the position of the last 5.0 in the list, counting as an offset from the end. 065 // if 5.0 is the LAST element, the position is 0 066 // if 5.0 does not appear, return a negative number 067 // you can write this using a loop or recursion, in any style, but you should only have one loop or recursive helper 068 // Hint: One way to do this is to use a backwards recursion. 069 // If the number does appear return a non-negative number. 070 // If the number does not appear, return the distance to the END of the list as a NEGATIVE number. 071 // For example: 072 // [].positionOfLastFiveFromEnd() == -1 073 // [41].positionOfLastFiveFromEnd() == -2 074 // [31 41].positionOfLastFiveFromEnd() == -3 075 // [21 31 41].positionOfLastFiveFromEnd() == -4 076 // [11 21 31 41].positionOfLastFiveFromEnd() == -5 077 // [5 11 21 31 41].positionOfLastFiveFromEnd() == 4 078 // [5 5 11 21 31 41].positionOfLastFiveFromEnd() == 4 079 // [1 5 5 11 21 31 41].positionOfLastFiveFromEnd() == 4 080 // 081 // [].positionOfLastFiveFromEnd() == -1 082 // [5].positionOfLastFiveFromEnd() == 0 083 // 084 // [].positionOfLastFiveFromEnd() == -1 085 // [41].positionOfLastFiveFromEnd() == -2 086 // [31 41].positionOfLastFiveFromEnd() == -3 087 // [5 31 41].positionOfLastFiveFromEnd() == 2 088 // [21 5 31 41].positionOfLastFiveFromEnd() == 2 089 // [5 21 5 31 41].positionOfLastFiveFromEnd() == 2 090 public int positionOfLastFiveFromEnd () { 091 return StdRandom.uniform (100); //TODO: fix this 092 } 093 094 public static void main (String args[]) { 095 //mainDebug (); 096 mainRunTests (); 097 } 098 private static void mainDebug () { 099 // Use this for debugging! 100 // Uncomment the call in main to use this. 101 // Add the names of helper functions if you use them. 102 Trace.drawStepsOfMethod ("sizeLoop"); 103 Trace.drawStepsOfMethod ("sizeForward"); 104 Trace.drawStepsOfMethod ("sizeBackward"); 105 Trace.drawStepsOfMethod ("positionOfFirstFiveFromBeginning"); 106 Trace.drawStepsOfMethod ("positionOfLastFiveFromEnd"); 107 Trace.drawStepsOfMethod ("deleteFirst"); 108 Trace.run (); 109 // TODO: Put the test here you want to debug: 110 testSizeLoop (4, "11 -21.2 31 41"); 111 } 112 private static void mainRunTests () { 113 testSizeLoop (2, "11 21"); 114 testSizeLoop (4, "11 -21.2 31 41"); 115 testSizeLoop (1, "11"); 116 testSizeLoop (0, ""); 117 118 testSizeForward (2, "11 21"); 119 testSizeForward (4, "11 -21.2 31 41"); 120 testSizeForward (1, "11"); 121 testSizeForward (0, ""); 122 123 testSizeBackward (2, "11 21"); 124 testSizeBackward (4, "11 -21.2 31 41"); 125 testSizeBackward (1, "11"); 126 testSizeBackward (0, ""); 127 128 testPositionOfFirstFiveFromBeginning (1, "11 5 21 31 41"); 129 testPositionOfFirstFiveFromBeginning (2, "11 21 5 31 41"); 130 testPositionOfFirstFiveFromBeginning (3, "11 21 31 5 41"); 131 testPositionOfFirstFiveFromBeginning (4, "11 21 31 41 5"); 132 testPositionOfFirstFiveFromBeginning (0, "5 11 21 31 41"); 133 testPositionOfFirstFiveFromBeginning (3, "0 1 2 5 5 5 5 5 8 9"); 134 testPositionOfFirstFiveFromBeginning (-1, "11 21 31 41"); 135 testPositionOfFirstFiveFromBeginning (-1, "11"); 136 testPositionOfFirstFiveFromBeginning (-1, ""); 137 138 testPositionOfLastFiveFromEnd (3, "11 5 21 31 41"); 139 testPositionOfLastFiveFromEnd (2, "11 21 5 31 41"); 140 testPositionOfLastFiveFromEnd (1, "11 21 31 5 41"); 141 testPositionOfLastFiveFromEnd (0, "11 21 31 41 5"); 142 testPositionOfLastFiveFromEnd (4, "5 11 21 31 41"); 143 testPositionOfLastFiveFromEnd (2, "0 1 2 5 5 5 5 5 8 9"); 144 testPositionOfLastFiveFromEnd (2, "0 1 2 5 5 5 5 5 5 8 9"); 145 testPositionOfLastFiveFromEnd (-5, "11 21 31 41"); 146 testPositionOfLastFiveFromEnd (-2, "11"); 147 testPositionOfLastFiveFromEnd (-1, ""); 148 149 testDeleteFirst ("21 31", "11 21 31"); 150 testDeleteFirst ("21 11", "31 21 11"); 151 testDeleteFirst ("21", "11 21"); 152 testDeleteFirst ("", "11"); 153 StdOut.println ("Finished tests"); 154 } 155 156 157 /* ToString method to print */ 158 public String toString () { 159 // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes 160 DecimalFormat format = new DecimalFormat ("#.###"); 161 StringBuilder result = new StringBuilder ("[ "); 162 for (Node x = first; x != null; x = x.next) { 163 result.append (format.format (x.item)); 164 result.append (" "); 165 } 166 result.append ("]"); 167 return result.toString (); 168 } 169 170 /* Method to create lists */ 171 public static MyLinked1 from(String s) { 172 MyLinked1 result = new MyLinked1 (); 173 if ("".equals (s)) return result; 174 175 Node first = null; 176 String[] nums = s.split (" "); 177 for (int i = nums.length-1; i >= 0; i--) { 178 try { 179 double num = Double.parseDouble (nums[i]); 180 first = new Node (num, first); 181 } catch (NumberFormatException e) { 182 throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 183 } 184 } 185 result.first = first; 186 return result; 187 } 188 189 // lots of copy and paste in these test! 190 private static void testSizeLoop (int expected, String sList) { 191 MyLinked1 list = MyLinked1.from (sList); 192 String sStart = list.toString (); 193 int actual = list.sizeLoop(); 194 if (expected != actual) { 195 StdOut.format ("Failed %s.sizeLoop(): Expecting (%d) Actual (%d)\n", sStart, expected, actual); 196 } 197 String sEnd = list.toString (); 198 if (! sStart.equals (sEnd)) { 199 StdOut.format ("Failed %s.sizeLoop(): List changed to %s\n", sStart, sEnd); 200 } 201 } 202 private static void testSizeForward (int expected, String sList) { 203 MyLinked1 list = MyLinked1.from (sList); 204 String sStart = list.toString (); 205 int actual = list.sizeForward (); 206 if (expected != actual) { 207 StdOut.format ("Failed %s.sizeForward(): Expecting (%d) Actual (%d)\n", sStart, expected, actual); 208 } 209 String sEnd = list.toString (); 210 if (! sStart.equals (sEnd)) { 211 StdOut.format ("Failed %s.sizeForward(): List changed to %s\n", sStart, sEnd); 212 } 213 } 214 private static void testSizeBackward (int expected, String sList) { 215 MyLinked1 list = MyLinked1.from (sList); 216 String sStart = list.toString (); 217 int actual = list.sizeBackward (); 218 if (expected != actual) { 219 StdOut.format ("Failed %s.sizeBackward(): Expecting (%d) Actual (%d)\n", sStart, expected, actual); 220 } 221 String sEnd = list.toString (); 222 if (! sStart.equals (sEnd)) { 223 StdOut.format ("Failed %s.sizeBackward(): List changed to %s\n", sStart, sEnd); 224 } 225 } 226 private static void testPositionOfFirstFiveFromBeginning (int expected, String sList) { 227 MyLinked1 list = MyLinked1.from (sList); 228 String sStart = list.toString (); 229 int actual = list.positionOfFirstFiveFromBeginning (); 230 //if ((expected >= 0 && expected != actual) || (expected < 0 && actual > 0)) { 231 if (expected != actual) { 232 StdOut.format ("Failed %s.positionOfFirstFiveFromBeginning(): Expecting (%d) Actual (%d)\n", sStart, expected, actual); 233 } 234 String sEnd = list.toString (); 235 if (! sStart.equals (sEnd)) { 236 StdOut.format ("Failed %s.positionOfFirstFiveFromBeginning(): List changed to %s\n", sStart, sEnd); 237 } 238 } 239 private static void testPositionOfLastFiveFromEnd (int expected, String sList) { 240 MyLinked1 list = MyLinked1.from (sList); 241 String sStart = list.toString (); 242 int actual = list.positionOfLastFiveFromEnd (); 243 //if ((expected >= 0 && expected != actual) || (expected < 0 && actual > 0)) { 244 if (expected != actual) { 245 StdOut.format ("Failed %s.testPositionOfLastFiveFromEnd(): Expecting (%d) Actual (%d)\n", sStart, expected, actual); 246 } 247 String sEnd = list.toString (); 248 if (! sStart.equals (sEnd)) { 249 StdOut.format ("Failed %s.testPositionOfLastFiveFromEnd(): List changed to %s\n", sStart, sEnd); 250 } 251 } 252 private static void testDeleteFirst (String expected, String sList) { 253 String sExpected = MyLinked1.from (expected).toString (); 254 MyLinked1 list = MyLinked1.from (sList); 255 String sStart = list.toString (); 256 list.deleteFirst (); 257 String sEnd = list.toString (); 258 if (! sExpected.equals (sEnd)) { 259 StdOut.format ("Failed %s.deleteFirst(): Expecting %s Actual %s\n", sStart, sExpected, sEnd); 260 } 261 } 262}