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}