001// Exercise 1.1.28
002package algs11;
003import stdlib.*;
004import java.util.Arrays;
005
006/*
007   1.1.28 Remove duplicates.
008   Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort.
009
010   Hint: For this problem, you will need to create a second array that is
011   smaller than the original whitelist.  You need to go through the
012   original whitelist twice.  The first time, you need to determine the number
013   of unique items in the whitelist; use this as the size of the second array,
014   which you create.  The second time, copy the unique items to the new
015   array.
016 */
017public class MyBinarySearchRemoveDuplicates {
018
019        // precondition: array a[] is sorted
020        public static int rank (int key, int[] a) {
021                int lo = 0;
022                int hi = a.length - 1;
023                while (lo <= hi) {
024                        // key is in a[lo..hi] or not present.
025                        int mid = lo + (hi - lo) / 2;
026                        if (key < a[mid]) hi = mid - 1;
027                        else if (key > a[mid]) lo = mid + 1;
028                        else return mid;
029                }
030                return -1;
031        }
032
033        // precondition: array a[] is sorted
034        public static int[] removeDuplicates (int[] a) {
035                int N = a.length;
036                if (N < 1) return a;
037
038                // determine number of unique elements
039                // TODO
040
041                // copy from a to new array
042                // TODO
043                return null;
044        }
045
046        public static void printRemoveDuplicates (int[] a) {
047                //StdOut.println (Arrays.toString (a));
048                StdOut.println (Arrays.toString (removeDuplicates (a)));
049        }
050
051        public static void testRemoveDuplicates () {
052                printRemoveDuplicates (new int[] {});
053                printRemoveDuplicates (new int[] {10});
054                printRemoveDuplicates (new int[] {10, 10});
055                printRemoveDuplicates (new int[] {10, 20});
056                printRemoveDuplicates (new int[] {10, 10, 20, 30});
057                printRemoveDuplicates (new int[] {10, 10, 10, 20, 30});
058                printRemoveDuplicates (new int[] {10, 20, 20, 30});
059                printRemoveDuplicates (new int[] {10, 20, 20, 20, 30});
060                printRemoveDuplicates (new int[] {10, 20, 30, 30});
061                printRemoveDuplicates (new int[] {10, 20, 30, 30, 30});
062                printRemoveDuplicates (new int[] {10, 10, 10, 10, 10, 10, 20, 20, 20, 30});
063        }
064
065        public static void main (String[] args) {
066                testRemoveDuplicates ();
067                //        args = new String[] { "data/tinyW.txt" };
068                //        StdIn.fromFile ("data/tinyT.txt");
069                //        int[] whitelist = new In (args[0]).readAllInts();
070                //
071                //        Arrays.sort (whitelist);
072                //        whitelist = removeDuplicates (whitelist);
073                //
074                //        // read key; print if not in whitelist
075                //        while (!StdIn.isEmpty ()) {
076                //            int key = StdIn.readInt ();
077                //            if (BinarySearch.rank (key, whitelist) == -1) StdOut.println (key);
078                //        }
079        }
080}