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.run (); 
071                // TODO:  Put the test here you want to debug:
072                testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
073                StdOut.println ("Finished tests");
074        }
075        private static void mainRunTests () {
076                // Trace.run (); // uncomment this to get drawings in showError
077                testDelete (1, "11 21 31 41", "[ 11 31 41 ]");
078                testDelete (2, "11 21 31 41", "[ 11 21 41 ]");
079                testDelete (3, "11 21 31 41", "[ 11 21 31 ]");
080                testDelete (1, "11 21 31 41 51", "[ 11 31 41 51 ]");
081                testDelete (2, "11 21 31 41 51", "[ 11 21 41 51 ]");
082                testDelete (3, "11 21 31 41 51", "[ 11 21 31 51 ]");
083                testDelete (4, "11 21 31 41 51", "[ 11 21 31 41 ]");
084                testDelete (0, "11 21 31 41 51", "[ 21 31 41 51 ]");
085                testDelete (0, "11", "[ ]");
086                testDelete (0, "11 21 31 41", "[ 21 31 41 ]");
087                testDelete (0, "", "java.lang.IllegalArgumentException");
088                testDelete(-1, "11 21 31", "java.lang.IllegalArgumentException");
089                testDelete (3, "11 21 31", "java.lang.IllegalArgumentException");
090
091                testReverse ("11 21 31 41", "[ 41 31 21 11 ]");
092                testReverse ("11 21 31 41 51", "[ 51 41 31 21 11 ]");
093                testReverse ("11 21", "[ 21 11 ]");
094                testReverse ("11 21 31", "[ 31 21 11 ]");
095                testReverse ("11", "[ 11 ]");
096                testReverse ("", "[ ]");
097
098                testRemove (5, "8 11 5 5 21 31 5 5 5 41", "[ 8 11 21 31 41 ]");
099                testRemove (5, "11 5 5 21 5 31 5 5 41 8", "[ 11 21 31 41 8 ]");
100                testRemove (5, "11 21 5 31 41", "[ 11 21 31 41 ]");
101                testRemove (5, "11 21 31 5 41", "[ 11 21 31 41 ]");
102                testRemove (5, "11 5 21 31 41", "[ 11 21 31 41 ]");
103                testRemove (5, "11 5 5 21 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]");
104                testRemove (5, "11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]");
105                testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
106                testRemove (5, "11 5 21 5 31 5 41", "[ 11 21 31 41 ]");
107                testRemove (5, "11 21 5 5 31 41", "[ 11 21 31 41 ]");
108                testRemove (5, "11 21 5 5 5 31 41", "[ 11 21 31 41 ]");
109                testRemove (5, "11 5 5 21 31 41", "[ 11 21 31 41 ]");
110                testRemove (5, "11 5 5 5 21 31 41", "[ 11 21 31 41 ]");
111                testRemove (5, "11 21 31 5 5 41", "[ 11 21 31 41 ]");
112                testRemove (5, "11 21 31 5 5 5 41", "[ 11 21 31 41 ]");
113                testRemove (5, "11 21 31 41 5", "[ 11 21 31 41 ]");
114                testRemove (5, "11 21 31 41 5 5", "[ 11 21 31 41 ]");
115                testRemove (5, "11 21 31 41 5 5 5", "[ 11 21 31 41 ]");
116                testRemove (5, "5 5 11 5 5 21 5 31 5 5 5 41 5 5 5", "[ 11 21 31 41 ]");
117                testRemove (5, "5 5 5 11 5 5 5 21 31 5 5 41 5 5", "[ 11 21 31 41 ]");
118                testRemove (5, "5 11 21 31 41", "[ 11 21 31 41 ]");
119                testRemove (5, "5 5 11 21 31 41", "[ 11 21 31 41 ]");
120                testRemove (5, "5 5 5 11 21 31 41", "[ 11 21 31 41 ]");
121                testRemove (5, "11", "[ 11 ]");
122                testRemove (5, "11 21", "[ 11 21 ]");
123                testRemove (5, "11 21 31", "[ 11 21 31 ]");
124                testRemove (5, "5 5 5", "[ ]");
125                testRemove (5, "5 5", "[ ]");
126                testRemove (5, "5", "[ ]");
127                testRemove (5, "", "[ ]");
128                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 ]");
129                StdOut.println ("Finished tests");
130        }
131
132        /* ToString method to print */
133        public String toString () { 
134                // Use DecimalFormat #.### rather than String.format 0.3f to leave off trailing zeroes
135                DecimalFormat format = new DecimalFormat ("#.###");
136                StringBuilder result = new StringBuilder ("[ ");
137                for (Node x = first; x != null; x = x.next) {
138                        result.append (format.format (x.item));
139                        result.append (" ");
140                }
141                result.append ("]");
142                return result.toString ();
143        }
144
145        /* Method to create lists */
146        public static MyLinked2 of(String s) {
147                MyLinked2 result = new MyLinked2 ();
148                if ("".equals (s)) return result;
149
150                int N = 0;
151                Node first = null;
152                String[] nums = s.split (" ");
153                for (int i = nums.length-1; i >= 0; i--) {
154                        try { 
155                                double num = Double.parseDouble (nums[i]); 
156                                first = new Node (num, first);  
157                                N++;
158                        } catch (NumberFormatException e) {
159                                throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
160                        }
161                }
162                result.first = first;
163                result.N = N;
164                return result;
165        }
166
167        static void showError (String message) {
168                Trace.draw ();
169                StdOut.println (message);
170                //throw new Error (); // stops execution
171        }
172        private static void checkInvariants (String message, MyLinked2 list) {
173                java.util.HashSet<Node> visited = new java.util.HashSet<>();                            
174                int num = 0;
175                for (Node x = list.first; x!=null; x=x.next) {
176                        if (visited.contains(x)) {
177                                showError (String.format ("%s: Node list has cycle, starting at Node with item=%f", message, x.item));
178                                showError ("Refusing to run any more tests until the cycle is removed.");
179                                System.exit(1);
180                        }
181                        visited.add(x);
182                        num++;                  
183                }
184                if (num != list.N) {
185                        showError (String.format ("%s: N=%d, but there are %d Nodes.", message, list.N, num));
186                }
187        }
188        private static void check (String message, MyLinked2 actual, String expected) {
189                checkInvariants (message, actual);
190                if (!expected.equals (actual.toString ())) {
191                        showError (String.format ("%s: expected=%s, actual=%s", message, expected, actual.toString ()));
192                }
193        }
194        private static void testDelete (int k, String list, String expected) {
195                MyLinked2 actual = MyLinked2.of (list);
196                String message = String.format ("[ %s ].delete( %d )", list, k);
197                try {
198                        actual.delete (k);
199                } catch (Throwable e) {
200                        String exception = e.getClass ().getName ();
201                        if (! exception.equals (expected)) {
202                                e.printStackTrace (); // for debugging
203                                showError (String.format ("%s: expected=%s, actual=%s", message, expected, exception));
204                        }
205                        return;
206                }
207                check (message, actual, expected);
208        }
209        private static void testReverse (String list, String expected) {
210                MyLinked2 actual = MyLinked2.of (list);
211                actual.reverse ();
212                String message = String.format ("[ %s ].reverse( )", list);
213                check (message, actual, expected);
214        }
215        private static void testRemove (double item, String list, String expected) {
216                MyLinked2 actual = MyLinked2.of (list);
217                actual.remove (item);
218                String message = String.format ("[ %s ].remove( %.2f )", list, item);
219                check (message, actual, expected);
220        }
221}