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