Source code

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 may NOT change method or field names.
033 * You do NOT need to use recursion for this homework.
034 * You can use loops in each problem.
035 */
036public class MyLinked2 {
037        static class Node {
038                public Node (double item, Node next) { this.item = item; this.next = next; }
039                public double item;
040                public Node next;
041        }
042        int N;
043        Node first;
044
045        // delete the kth element (where k is between 0 and N-1 inclusive)
046        public void delete (int k) {
047                if (k < 0 || k >= N) throw new IllegalArgumentException ();
048                // TODO 
049        }
050
051        // reverse the list "in place"... 
052        public void reverse () {
053                // TODO 
054        }
055
056        // remove all occurrences of item from the list 
057        public void remove (double item) {
058                // TODO
059        }
060
061        public static void main (String args[]) {
062                //mainDebug ();
063                mainRunTests ();
064        }
065        private static void mainDebug () {
066                // Use this for debugging!
067                // Add the names of helper functions if you use them.
068                Trace.drawStepsOfMethod ("delete");
069                Trace.drawStepsOfMethod ("reverse");
070                Trace.drawStepsOfMethod ("remove");
071                Trace.showObjectIdsRedundantly(true);
072                Trace.run (); 
073                // TODO:  Put the test here you want to debug:
074                testReverse ("11 21 31 41", "[ 41 31 21 11 ]");
075                StdOut.println ("Finished tests");
076        }
077        private static void mainRunTests () {
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 from(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                int num = 0;
175                Node firstInCycle = null;
176                {
177                        java.util.HashSet<Node> visited = new java.util.HashSet<>();                            
178                        for (Node x = list.first; x!=null; x=x.next) {
179                                if (visited.contains(x)) {
180                                        firstInCycle = x;
181                                        break;
182                                }
183                                visited.add(x);
184                                num++;                  
185                        }
186                }
187                if (firstInCycle != null) {
188                        showError (String.format ("For %s: Node list has cycle.\n"
189                                + "Cycle starts at Node with item=%f.\n"
190                                + "Refusing to run any more tests until the cycle is removed.\n"
191                                + "Uncomment Trace.run() in main to see a picture.\n", message, firstInCycle.item));
192                        System.exit(1);
193                }
194                if (num != list.N) {
195                        showError (String.format ("%s: N=%d, but there are %d Nodes.", message, list.N, num));
196                }
197        }
198        private static void check (String message, MyLinked2 actual, String expected) {
199                checkInvariants (message, actual);
200                if (!expected.equals (actual.toString ())) {
201                        showError (String.format ("%s: expected=%s, actual=%s", message, expected, actual.toString ()));
202                }
203        }
204        private static void testDelete (int k, String list, String expected) {
205                MyLinked2 actual = MyLinked2.from (list);
206                String message = String.format ("[ %s ].delete( %d )", list, k);
207                try {
208                        actual.delete (k);
209                } catch (Throwable e) {
210                        String exception = e.getClass ().getName ();
211                        if (! exception.equals (expected)) {
212                                e.printStackTrace (); // for debugging
213                                showError (String.format ("%s: expected=%s, actual=%s", message, expected, exception));
214                        }
215                        return;
216                }
217                check (message, actual, expected);
218        }
219        private static void testReverse (String list, String expected) {
220                MyLinked2 actual = MyLinked2.from (list);
221                actual.reverse ();
222                String message = String.format ("[ %s ].reverse( )", list);
223                check (message, actual, expected);
224        }
225        private static void testRemove (double item, String list, String expected) {
226                MyLinked2 actual = MyLinked2.from (list);
227                actual.remove (item);
228                String message = String.format ("[ %s ].remove( %.2f )", list, item);
229                check (message, actual, expected);
230        }
231}