001package algs13;
002import stdlib.*;
003
004public class MyLinked3 {
005        static class Node {
006                public Node() { }
007                public double item;
008                public Node next;
009        }
010
011        int N;
012        Node first;
013
014        public MyLinked3 () {
015                first = null;
016                N = 0;
017                checkInvariants ();
018        }
019
020        private void myassert (String s, boolean b) { if (!b) throw new Error ("Assertion failed: " + s); }
021        private void checkInvariants() {
022                myassert("Empty <==> first==null", (N == 0) == (first == null));
023                Node x = first;
024                for (int i = 0; i < N; i++) {
025                        if (x==null) {
026                                throw new Error ("List too short!");
027                        }
028                        x = x.next;
029                }
030                myassert("EndOfList == null", x == null);
031        }
032
033        public boolean isEmpty () { return first == null; }
034        public int size () { return N; }
035        public void add (double item) {
036                Node newfirst = new Node ();
037                newfirst.item = item;
038                newfirst.next = first;
039                first = newfirst;
040                N++;
041        }
042
043        // return Double.NEGATIVE_INFINITY if the linked list is empty
044        public double sum () { return sum (first); }
045        private static double sum (Node x) {
046                double result = 0;
047                while (x != null) {
048                        result = result + x.item;
049                        x = x.next;
050                }
051                return result;
052        }
053        
054        // return Double.NEGATIVE_INFINITY if the linked list is empty
055        public double max () { 
056                // TODO
057                return Double.NEGATIVE_INFINITY;
058        }
059
060        // return Double.NEGATIVE_INFINITY if the linked list is empty
061        public double maxRecursive () { 
062                // TODO
063                return Double.NEGATIVE_INFINITY;
064        }
065
066        // delete the kth element
067        public void delete (int k) {
068                if (k < 0 || k >= N) throw new IllegalArgumentException ();
069                // TODO 1.3.20
070                checkInvariants ();
071        }
072
073        // reverse the list "in place"... without creating any new nodes
074        public void reverse () {
075                // TODO 1.3.30
076                checkInvariants ();
077        }
078
079        // remove
080        public void remove (double item) {
081                // TODO 1.3.26
082                checkInvariants ();
083        }
084
085
086        private static void print (String s, MyLinked3 b) {
087                StdOut.print (s + ": ");
088                for (Node x = b.first; x != null; x = x.next)
089                        StdOut.print (x.item + " ");
090                StdOut.println ();
091        }
092        private static void print (String s, MyLinked3 b, double i) {
093                StdOut.print (s + ": ");
094                for (Node x = b.first; x != null; x = x.next)
095                        StdOut.print (x.item + " ");
096                StdOut.println (": " + i);
097        }
098        public static MyLinked3 listFromString (String s) {
099                MyLinked3 list = new MyLinked3 ();
100                String[] nums = s.split (" ");
101                for (int i = nums.length-1; i >= 0; i--) {
102                        try { list.add (Integer.parseInt (nums[i])); } catch (NumberFormatException e) {}
103                }
104                return list;
105        }
106        private static void testMax () {
107                MyLinked3 b = new MyLinked3 ();
108                print ("empty", b, b.max());
109                b.add (-1);
110                print ("singleton", b, b.max());
111                b.add (-2);
112                b.add (-3);
113                b.add (-4);
114                print ("at end", b, b.max());
115                b.add (5);
116                print ("at beginning", b, b.max());
117                b.add (3);
118                b.add (2);
119                b.add (4);
120                print ("in the middle", b, b.max());
121        }
122        private static void testMaxRecursive () {
123                MyLinked3 b = new MyLinked3 ();
124                print ("empty", b, b.maxRecursive());
125                b.add (-1);
126                print ("singleton", b, b.maxRecursive());
127                b.add (-2);
128                b.add (-3);
129                b.add (-4);
130                print ("at end", b, b.maxRecursive());
131                b.add (5);
132                print ("at beginning", b, b.maxRecursive());
133                b.add (3);
134                b.add (2);
135                b.add (4);
136                print ("in the middle", b, b.maxRecursive());
137        }
138        private static void testDelete () {
139                MyLinked3 b = new MyLinked3 ();
140                b.add (1);
141                print ("singleton", b);
142                b.delete (0);
143                print ("deleted", b);
144                for (double i = 1; i < 13; i++) {
145                        b.add (i);
146                }
147                print ("bigger list", b);
148                b.delete (0);
149                print ("deleted at beginning", b);
150                b.delete (10);
151                print ("deleted at end", b);
152                b.delete (4);
153                print ("deleted in middle", b);
154        }
155        private static void testReverse () {
156                MyLinked3 b = new MyLinked3 ();
157                b.reverse ();
158                print ("reverse empty", b);
159                b.add (1);
160                print ("singleton", b);
161                b.reverse ();
162                print ("reverse singleton", b);
163                b.add (2);
164                print ("two", b);
165                b.reverse ();
166                print ("reverse two", b);
167                b.reverse ();
168                print ("reverse again", b);
169                for (double i = 3; i < 7; i++) {
170                        b.add (i);
171                        b.add (i);
172                }
173                print ("bigger list", b);
174                b.reverse ();
175                print ("reversed", b);
176        }
177        private static void testRemove () {
178                MyLinked3 b = new MyLinked3 ();
179                b.remove (4);
180                print ("removed 4 from empty", b);
181                b.add (1);
182                b.remove (4);
183                print ("removed 4 from singelton", b);
184                b.remove (1);
185                print ("removed 1 from singelton", b);
186                for (double i = 1; i < 5; i++) {
187                        b.add (i);
188                        b.add (i);
189                }
190                for (double i = 1; i < 5; i++) {
191                        b.add (i);
192                        b.add (i);
193                        b.add (i);
194                        b.add (i);
195                        b.add (i);
196                }
197                print ("longer list", b);
198                b.remove (9);
199                print ("removed all 9s", b); // does nothing
200                b.remove (3);
201                print ("removed all 3s", b);
202                b.remove (1);
203                print ("removed all 1s", b);
204                b.remove (4);
205                print ("removed all 4s", b);
206                b.remove (2);
207                print ("removed all 2s", b); // should be empty
208        }
209
210        public static void main (String args[]) {
211                testMax ();
212                //        testMaxRecursive ();
213                //        testDelete ();
214                //        testReverse ();
215                //        testRemove ();
216        }
217}
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250