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}