001package algs13;
002import java.text.DecimalFormat;
003import stdlib.*;
004
005/* 
006 * Complete the methods below.
007 * All of these methods modify the list.
008 * Use the function checkInvariants to ensure that your list is well-formed after you modify it.
009 * Note that this list keeps track of the number of elements N.
010 * It is important that N accurately reflect the length of 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 objects objects.
015 * For example, you may not create a new Node, new Stack, or new ArrayList.
016 * 
017 *    new Node (...)  // Forbidden: create a new Node object.
018 *    
019 * You *may* declare variables of type Node.
020 *    
021 *    Node x = first; // Allowed: declare variable of type Node.
022 *  
023 * You may not change the item value of any existing node, only change the next pointer.
024 * 
025 *    x.item = ... // Forbidden
026 *    x.next = ... // Allowed
027 *    first  = ... // Allowed
028 *
029 * Each function must be independent.  
030 * For example, you cannot call delete to implement remove.
031 * You MAY add private methods to the list class (helper functions for the recursion). 
032 * You do NOT need to use recursion for this homework.
033 * You can use loops in each problem.
034 */
035public class MyLinked2 {
036        static class Node {
037                public Node (double item, Node next) { this.item = item; this.next = next; }
038                public double item;
039                public Node next;
040        }
041        int N;
042        Node first;
043
044        // delete the kth element (where k is between 0 and N-1 inclusive)
045        public void delete (int k) {
046                if (k < 0 || k >= N) throw new IllegalArgumentException ();
047                // TODO 
048        }
049
050        // reverse the list "in place"... 
051        public void reverse () {
052                // TODO 
053        }
054
055        // remove all occurrences of item from the list 
056        public void remove (double item) {
057                // TODO
058        }
059
060        public static void main (String args[]) {
061                //mainDebug ();
062                mainRunTests ();
063        }
064        private static void mainDebug () {
065                // Use this for debugging!
066                // Add the names of helper functions if you use them.
067                Trace.drawStepsOfMethod ("delete");
068                Trace.drawStepsOfMethod ("reverse");
069                Trace.drawStepsOfMethod ("remove");
070                Trace.showObjectIdsRedundantly(true);
071                Trace.run (); 
072                // TODO:  Put the test here you want to debug:
073                testReverse ("11 21 31 41", "[ 41 31 21 11 ]");
074                StdOut.println ("Finished tests");
075        }
076        private static void mainRunTests () {
077                // Trace.run (); // uncomment this to get drawings in showError
078                testDelete (1, "11 21 31 41", "[ 11 31 41 ]");
079                testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
080                testDelete (3, "11 21 31 41", "[ 11 21 31 ]");
081                testDelete (1, "11 21 31 41 51", "[ 11 31 41 51 ]");
082                testDelete (2, "11 21 31 41 51", "[ 11 21 41 51 ]");
083                testDelete (3, "11 21 31 41 51", "[ 11 21 31 51 ]");
084                testDelete (4, "11 21 31 41 51", "[ 11 21 31 41 ]");
085                testDelete (0, "11 21 31 41 51", "[ 21 31 41 51 ]");
086                testDelete (0, "11", "[ ]");
087                testDelete (0, "11 21 31 41", "[ 21 31 41 ]");
088                testDelete (0, "", "java.lang.IllegalArgumentException");
089                testDelete(-1, "11 21 31", "java.lang.IllegalArgumentException");
090                testDelete (3, "11 21 31", "java.lang.IllegalArgumentException");
091
092                testReverse ("11 21 31 41", "[ 41 31 21 11 ]");
093                testReverse ("11 21 31 41 51", "[ 51 41 31 21 11 ]");
094                testReverse ("11 21", "[ 21 11 ]");
095                testReverse ("11 21 31", "[ 31 21 11 ]");
096                testReverse ("11", "[ 11 ]");
097                testReverse ("", "[ ]");
098
099                testRemove (5, "8 11 5 5 21 31 5 5 5 41", "[ 8 11 21 31 41 ]");
100                testRemove (5, "11 5 5 21 5 31 5 5 41 8", "[ 11 21 31 41 8 ]");
101                testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]");
102                testRemove (5, "11 21 31 5 41", "[ 11 21 31 41 ]");
103                testRemove (5, "11 5 21 31 41", "[ 11 21 31 41 ]");
104                testRemove (5, "11 5 5 21 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]");
105                testRemove (5, "11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]");
106                testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
107                testRemove (5, "11 5 21 5 31 5 41", "[ 11 21 31 41 ]");
108                testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]");
109                testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]");
110                testRemove (5, "11 5 5 21 31 41", "[ 11 21 31 41 ]");
111                testRemove (5, "11 5 5 5 21 31 41", "[ 11 21 31 41 ]");
112                testRemove (5, "11 21 31 5 5 41", "[ 11 21 31 41 ]");
113                testRemove (5, "11 21 31 5 5 5 41", "[ 11 21 31 41 ]");
114                testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
115                testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]");
116                testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]");
117                testRemove (5, "5 5 11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]");
118                testRemove (5, "5 5 5 11 5 5 5 21 31 5 5 41 5 5", "[ 11 21 31 41 ]");
119                testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]");
120                testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]");
121                testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]");
122                testRemove (5, "11", "[ 11 ]");
123                testRemove (5, "11 21", "[ 11 21 ]");
124                testRemove (5, "11 21 31", "[ 11 21 31 ]");
125                testRemove (5, "5 5 5", "[ ]");
126                testRemove (5, "5 5", "[ ]");
127                testRemove (5, "5", "[ ]");
128                testRemove (5, "", "[ ]");
129                testRemove (5.1, "5.1 5.1 5.1 5 11 5.1 5.1 21 5.1 31 5.1 5.1 41 5.1 5.1 5.1", "[ 5 11 21 31 41 ]");
130                StdOut.println ("Finished tests");
131        }
132
133        /* ToString method to print */
134        public String toString () { 
135                // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes
136                DecimalFormat format = new DecimalFormat ("#.###");
137                StringBuilder result = new StringBuilder ("[ ");
138                for (Node x = first; x != null; x = x.next) {
139                        result.append (format.format (x.item));
140                        result.append (" ");
141                }
142                result.append ("]");
143                return result.toString ();
144        }
145
146        /* Method to create lists */
147        public static MyLinked2 of(String s) {
148                MyLinked2 result = new MyLinked2 ();
149                if ("".equals (s)) return result;
150
151                int N = 0;
152                Node first = null;
153                String[] nums = s.split (" ");
154                for (int i = nums.length-1; i >= 0; i--) {
155                        try { 
156                                double num = Double.parseDouble (nums[i]); 
157                                first = new Node (num, first);  
158                                N++;
159                        } catch (NumberFormatException e) {
160                                throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
161                        }
162                }
163                result.first = first;
164                result.N = N;
165                return result;
166        }
167
168        static void showError (String message) {
169                Trace.draw ();
170                StdOut.println (message);
171                //throw new Error (); // stops execution
172        }
173        private static void checkInvariants (String message, MyLinked2 list) {
174                java.util.HashSet<Node> visited = new java.util.HashSet<>();                            
175                int num = 0;
176                for (Node x = list.first; x!=null; x=x.next) {
177                        if (visited.contains(x)) {
178                                showError (String.format ("%s: Node list has cycle, starting at Node with item=%f", message, x.item));
179                                showError ("Refusing to run any more tests until the cycle is removed.");
180                                System.exit(1);
181                        }
182                        visited.add(x);
183                        num++;                  
184                }
185                if (num != list.N) {
186                        showError (String.format ("%s: N=%d, but there are %d Nodes.", message, list.N, num));
187                }
188        }
189        private static void check (String message, MyLinked2 actual, String expected) {
190                checkInvariants (message, actual);
191                if (!expected.equals (actual.toString ())) {
192                        showError (String.format ("%s: expected=%s, actual=%s", message, expected, actual.toString ()));
193                }
194        }
195        private static void testDelete (int k, String list, String expected) {
196                MyLinked2 actual = MyLinked2.of (list);
197                String message = String.format ("[ %s ].delete( %d )", list, k);
198                try {
199                        actual.delete (k);
200                } catch (Throwable e) {
201                        String exception = e.getClass ().getName ();
202                        if (! exception.equals (expected)) {
203                                e.printStackTrace (); // for debugging
204                                showError (String.format ("%s: expected=%s, actual=%s", message, expected, exception));
205                        }
206                        return;
207                }
208                check (message, actual, expected);
209        }
210        private static void testReverse (String list, String expected) {
211                MyLinked2 actual = MyLinked2.of (list);
212                actual.reverse ();
213                String message = String.format ("[ %s ].reverse( )", list);
214                check (message, actual, expected);
215        }
216        private static void testRemove (double item, String list, String expected) {
217                MyLinked2 actual = MyLinked2.of (list);
218                actual.remove (item);
219                String message = String.format ("[ %s ].remove( %.2f )", list, item);
220                check (message, actual, expected);
221        }
222}