001package algs11;
002
003import java.util.Arrays;
004import stdlib.*;
005
006/**
007 * This is a skeleton file for your homework. Edit the sections marked TODO. You
008 * may also edit the function "main" to test your code.
009 *
010 * You must not change the declaration of any method. This will be true of every
011 * skeleton file I give you.
012 *
013 * For example, you will get zero points if you change the line
014 * 
015 * <pre>
016 *     public static double minValue (double[] list) {
017 * </pre>
018 * 
019 * to something like
020 * 
021 * <pre>
022 *     public static void minValue (double[] list) {
023 * </pre>
024 * 
025 * or
026 * 
027 * <pre>
028 *     public static double minValue (double[] list, int i) {
029 * </pre>
030 * 
031 * Each of the functions below is meant to be SELF CONTAINED. This means that
032 * you should use no other functions or classes. You should not use any HashSets
033 * or ArrayLists, or anything else! In addition, each of your functions should
034 * go through the argument array at most once. The only exception to this
035 * removeDuplicates, which is allowed to call numUnique and then go through the
036 * array once after that.
037 */
038public class MyFirstHomeworkFor300PartTwo {
039
040        /**
041         * allSame returns true if all of the elements in list have the same value.
042         * allSame returns false if any two elements in list have different values. The
043         * array may be empty and it may contain duplicate values.
044         *
045         * Your solution should contain at most one loop. You may not use recursion.
046         * Your solution must not call any other functions. Here are some examples
047         * (using "==" informally):
048         *
049         * <pre>
050         *     true  == allSame(new double[] { })
051         *     true  == allSame(new double[] { 11 })
052         *     true  == allSame(new double[] { 11, 11, 11, 11 })
053         *     false == allSame(new double[] { 11, 11, 11, 22 })
054         *     false == allSame(new double[] { 11, 11, 22, 11 })
055         *     true  == allSame(new double[] { 22, 22, 22, 22 })
056         * </pre>
057         */
058        public static boolean allSame(double[] list) {
059                return StdRandom.bernoulli(); // TODO: fix this
060        }
061
062        /**
063         * numUnique returns the number of unique values in a sorted array of doubles.
064         * The array may be empty and it may contain duplicate values. Assume that the
065         * list array is sorted.
066         *
067         * Your solution should contain at most one loop. You may not use recursion.
068         * Your solution must not call any other functions. Here are some examples
069         * (using "==" informally):
070         *
071         * <pre>
072         *     0 == numUnique(new double[] { })
073         *     1 == numUnique(new double[] { 11 })
074         *     1 == numUnique(new double[] { 11, 11, 11, 11 })
075         *     8 == numUnique(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 })
076         *     8 == numUnique(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 })
077         * </pre>
078         */
079        public static int numUnique(double[] list) {
080                return StdRandom.uniform (100); //TODO: fix this
081        }
082
083        /**
084         * removeDuplicates returns a new array containing the unique values in the
085         * sorted argument array, in the same order that they were found in the original
086         * array. There should not be any extra space in the array --- there should be
087         * exactly one space for each unique element (Hint: numUnique tells you how big
088         * the array should be).
089         * 
090         * Assume that the list array is sorted, as you did for numUnique.
091         *
092         * Your solution should contain at most one loop. You may not use recursion.
093         * Your solution must not call any other functions, except numUnique. Here are
094         * some examples (using "==" informally):
095         *
096         * <pre>
097         *   new double[] { }
098         *     == removeDuplicates(new double[] { })
099         *   new double[] { 11 }
100         *     == removeDuplicates(new double[] { 11 })
101         *     == removeDuplicates(new double[] { 11, 11, 11, 11 })
102         *   new double[] { 11, 22, 33, 44, 55, 66, 77, 88 }
103         *     == removeDuplicates(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 })
104         *     == removeDuplicates(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 })
105         * </pre>
106         */
107        public static double[] removeDuplicates(double[] list) {
108                int resultLength = numUnique(list);
109                double[] result = new double[resultLength];
110                // TODO: fix this
111                return result;
112        }
113
114        /*
115         * A main function for debugging -- change the name to "main" to run it (and
116         * rename the existing main method to something else). Change the test as
117         * appropriate.
118         */
119        public static void main2(String[] args) {
120                Trace.drawStepsOfMethod("removeDuplicates");
121                Trace.run();
122                testRemoveDuplicates("11 21 31 41", "11 21 31 41");
123                testRemoveDuplicates("11 21", "11 11 21");
124        }
125
126        /**
127         * A test program, using private helper functions. See below. To make typing
128         * tests a little easier, I've written a function to convert strings to arrays.
129         * See below.
130         */
131        public static void main(String[] args) {
132                testAllSame(true, "11 11 11 11");
133                testAllSame(true, "5 5 5");
134                testAllSame(false, "11 5 11 11");
135                testAllSame(false, "11 11 5 11");
136                testAllSame(false, "11 11 11 5");
137                testAllSame(false, "5 11 11 11");
138                testAllSame(false, "11 5 5 11 11");
139                testAllSame(false, "11 11 5 5 11");
140                testAllSame(false, "11 11 5 11 5");
141                testAllSame(false, "5 5 11 11 11");
142                testAllSame(false, "11 11 11 5 5");
143                testAllSame(true, "11");
144                testAllSame(true, "2");
145                testAllSame(true, "");
146
147                // for numUnique: array must be sorted
148                testNumUnique(4, "11 21 21 21 31 41 41 41 41");
149                testNumUnique(1, "11 11 11 11");
150                testNumUnique(4, "11 21 31 41");
151                testNumUnique(4, "11 11 11 21 31 31 31 31 41");
152                testNumUnique(4, "11 11 21 21 21 31 31 41 41 41 41");
153                testNumUnique(8, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81");
154                testNumUnique(8, "11 21 31 41 41 41 41 41 51 51 61 71 81");
155                testNumUnique(7, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71");
156                testNumUnique(7, "11 21 31 41 41 41 41 41 51 51 61 71");
157                testNumUnique(8, "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11");
158                testNumUnique(3, "-11 -11 -11 0 0 11 11 11");
159                testNumUnique(2, "0 11 11 11");
160                testNumUnique(2, "-Infinity 11 11 11");
161                testNumUnique(2, "11 11 11 Infinity");
162                testNumUnique(1, "11 11");
163                testNumUnique(1, "11");
164                testNumUnique(0, "");
165
166                // for removeDuplicates: array must be sorted
167                testRemoveDuplicates("11", "11 11 11 11");
168                testRemoveDuplicates("11 21", "11 11 21");
169                testRemoveDuplicates("11 21 31 41", "11 21 31 41");
170                testRemoveDuplicates("11 21 31 41", "11 11 11 21 31 31 31 31 41");
171                testRemoveDuplicates("11 21 31 41", "11 21 21 21 31 41 41 41 41");
172                testRemoveDuplicates("11 21 31 41", "11 11 21 21 21 31 31 41 41 41 41");
173                testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81");
174                testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 21 31 41 41 41 41 41 51 51 61 71 81");
175                testRemoveDuplicates("11 21 31 41 51 61 71", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71");
176                testRemoveDuplicates("11 21 31 41 51 61 71", "11 21 31 41 41 41 41 41 51 51 61 71");
177                testRemoveDuplicates("-81 -71 -61 -51 -41 -31 -21 -11", "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11");
178                testRemoveDuplicates("-11 0 11", "-11 -11 -11 0 0 11 11 11");
179                testRemoveDuplicates("0 11", "0 11 11 11");
180                testRemoveDuplicates("-Infinity 11", "-Infinity 11 11 11");
181                testRemoveDuplicates("Infinity 11", "Infinity 11 11 11");
182                testRemoveDuplicates("11", "11 11");
183                testRemoveDuplicates("11", "11");
184                testRemoveDuplicates("", "");
185                StdOut.println("Finished tests");
186        }
187
188        private static void testAllSame(boolean expected, String list) {
189                double[] aList = doublesFromString(list);
190                boolean actual = allSame(aList);
191                if (!Arrays.equals(aList, doublesFromString(list))) {
192                        StdOut.format("Failed allSame([%s]): Array modified\n", list);
193                }
194                if (expected != actual) {
195                        StdOut.format("Failed allSame([%s]): Expecting (%b) Actual (%b)\n", list, expected, actual);
196                }
197        }
198
199        private static void testNumUnique(int expected, String list) {
200                double[] aList = doublesFromString(list);
201                int actual = numUnique(aList);
202                if (!Arrays.equals(aList, doublesFromString(list))) {
203                        StdOut.format("Failed numUnique([%s]): Array modified\n", list);
204                }
205                if (expected != actual) {
206                        StdOut.format("Failed numUnique([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual);
207                }
208        }
209
210        private static void testRemoveDuplicates(String expected, String list) {
211                double[] aList = doublesFromString(list);
212                double[] actual = removeDuplicates(aList);
213                if (!Arrays.equals(aList, doublesFromString(list))) {
214                        StdOut.format("Failed removeDuplicates([%s]): Array modified\n", list);
215                }
216                double[] aExpected = doublesFromString(expected);
217                // != does not do what we want on arrays
218                if (!Arrays.equals(aExpected, actual)) {
219                        StdOut.format("Failed removeDuplicates([%s]): Expecting (%s) Actual (%s)\n", list,
220                                        Arrays.toString(aExpected), Arrays.toString(actual));
221                }
222        }
223
224        /* A utility function to create an array of doubles from a string. */
225        // The string should include a list of numbers, separated by single spaces.
226        private static double[] doublesFromString(String s) {
227                if ("".equals(s))
228                        return new double[0]; // empty array is a special case
229                String[] nums = s.split(" ");
230                double[] result = new double[nums.length];
231                for (int i = nums.length - 1; i >= 0; i--) {
232                        try {
233                                result[i] = Double.parseDouble(nums[i]);
234                        } catch (NumberFormatException e) {
235                                throw new IllegalArgumentException(
236                                                String.format("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
237                        }
238                }
239                return result;
240        }
241}