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