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