001package stdlib;
002
003/**
004 * Provides methods to generate arrays of Integer objects,
005 * arrays of doubles in [0.0,1.0), and arrays of characters.
006 */
007public class ArrayGenerator {
008        /**
009         * Generate an array of strings from a string.  Each array element will be a string of length one.
010         * For example
011         * <pre>
012         *   fromString("DOG") generates the array { "D", "O", "G" }
013         * </pre>
014         *
015         * @see In#readAllStrings()
016         * @see StdIn#readAllStrings()
017         */
018        public static String[] fromString (String s) {
019                int N = s.length();
020                String[] a = new String[N];
021                for (int i = 0; i < N; i++)
022                        a[i] = s.substring(i, i+1);
023                return a;
024        }
025        /** 
026         * Generate an array of doubles from a string.  The string should include a list of numbers, separated by single spaces. 
027         * For example
028         * <pre>
029         *   doublesFromString("10.3 -Infinity 11)" generates the array { 10.3, -Infinity, 11.0 }
030         * </pre>
031         * 
032         * @see java.lang.Double#parseDouble(java.lang.String)
033         */
034        public static double[] doublesFromString (String s) {
035                if ("".equals (s)) return new double[0]; // empty array is a special case
036                String[] nums = s.split (" ");
037                double[] result = new double[nums.length];
038                for (int i = nums.length - 1; i >= 0; i--) {
039                        try {
040                                result[i] = Double.parseDouble (nums[i]);
041                        } catch (NumberFormatException e) {
042                                throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
043                        }
044                }
045                return result;
046        }
047        /** 
048         * Generate an array of ints from a string.  The string should include a list of numbers, separated by single spaces. 
049         * For example
050         * <pre>
051         *   doublesFromString("10 11)" generates the array { 10, 11.0 }
052         * </pre>
053         * 
054         * @see java.lang.Integer#parseInt(java.lang.String)
055         */
056        public static int[] intsFromString (String s) {
057                if ("".equals (s)) return new int[0]; // empty array is a special case
058                String[] nums = s.split (" ");
059                int[] result = new int[nums.length];
060                for (int i = nums.length - 1; i >= 0; i--) {
061                        try {
062                                result[i] = Integer.parseInt (nums[i]);
063                        } catch (NumberFormatException e) {
064                                throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a int", s, nums[i]));
065                        }
066                }
067                return result;
068        }       
069        /**
070         * Generate an array of length N whose values are chosen uniformly from the range [minValue,maxValue).
071         */
072        public static int[] intRandom (int N, int minValue, int maxValue) {
073                if (N < 0) throw new IllegalArgumentException ();
074                int[] a = new int[N];
075                for (int i = 0; i < N; i++) {
076                        a[i] = StdRandom.uniform (minValue, maxValue);
077                }
078                return a;
079        }
080        /**
081         * Generate an array of length N whose values are chosen uniformly from the range [0,numValues).
082         */
083        public static int[] intRandom (int N, int numValues) {
084                if (N < 0) throw new IllegalArgumentException ();
085                int[] a = new int[N];
086                for (int i = 0; i < N; i++) {
087                        a[i] = StdRandom.uniform (numValues);
088                }
089                return a;
090        }
091        /**
092         * Generate an array of length N with values 0, 1, ..., N-1.
093         */
094        public static int[] intSortedUnique (int N) {
095                if (N < 0) throw new IllegalArgumentException ();
096                int[] a = new int[N];
097                for (int i = 0; i < N; i++) {
098                        a[i] = i;
099                }
100                return a;
101        }
102        /**
103         * Generate an array of length N with values N-1, N-2, ... 0.
104         */
105        public static int[] intReverseSortedUnique (int N) {
106                if (N < 0) throw new IllegalArgumentException ();
107                int[] a = new int[N];
108                for (int i = 0; i < N; i++) {
109                        a[i] = N - 1 - i;
110                }
111                return a;
112        }
113        /**
114         * Generate a shuffled array of length N with unique values 0, 1, ... N-1
115         */
116        public static int[] intRandomUnique (int N) {
117                int[] a = intSortedUnique (N);
118                StdRandom.shuffle (a);
119                return a;
120        }
121        /**
122         * Generate a partially sorted array with unique elements.
123         * The number of inversions will be between N and 2N.
124         * This algorithm moves random elements an arbitrary amount until the threshold is achieved.
125         */
126        public static int[] intPartiallySortedUnique (int N) {
127                if (N < 6) throw new IllegalArgumentException ("array too small");
128                int[] a = intSortedUnique (N);
129                int totalDistance = 0; // this is an approximation of the number of inversions
130                int range = (int) (Math.sqrt (N));
131                while (totalDistance < N) {
132                        int i = StdRandom.uniform (N);
133                        int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
134                        totalDistance += Math.abs (i - r);
135                        int temp = a[i];
136                        a[i] = a[r];
137                        a[r] = temp;
138                }
139                return a;
140        }
141        /**
142         * Generate a partially sorted array with unique elements.
143         * The number of inversions will be between N and 2N.
144         * This algorithm moves all elements a small amount.
145         */
146        public static int[] intPartiallySortedUnique2 (int N) {
147                if (N < 6) throw new IllegalArgumentException ("array too small");
148                int[] a = intSortedUnique (N);
149                int range = 4;
150                for (int i=0; i<N; i++) {
151                        int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
152                        int temp = a[i];
153                        a[i] = a[r];
154                        a[r] = temp;
155                }
156                return a;
157        }
158
159        /**
160         * Generate an array of length N whose values are chosen uniformly from the range [minValue,maxValue).
161         */
162        public static Integer[] integerRandom (int N, int minValue, int maxValue) {
163                if (N < 0) throw new IllegalArgumentException ();
164                Integer[] a = new Integer[N];
165                for (int i = 0; i < N; i++) {
166                        a[i] = StdRandom.uniform (minValue, maxValue);
167                }
168                return a;
169        }
170        /**
171         * Generate an array of length N whose values are chosen uniformly from the range [0,numValues).
172         */
173        public static Integer[] integerRandom (int N, int numValues) {
174                if (N < 0) throw new IllegalArgumentException ();
175                Integer[] a = new Integer[N];
176                for (int i = 0; i < N; i++) {
177                        a[i] = StdRandom.uniform (numValues);
178                }
179                return a;
180        }
181        /**
182         * Generate an array of length N with values 0, 1, ..., N-1.
183         */
184        public static Integer[] integerSortedUnique (int N) {
185                if (N < 0) throw new IllegalArgumentException ();
186                Integer[] a = new Integer[N];
187                for (int i = 0; i < N; i++) {
188                        a[i] = i;
189                }
190                return a;
191        }
192        /**
193         * Generate an array of length N with values N-1, N-2, ... 0.
194         */
195        public static Integer[] integerReverseSortedUnique (int N) {
196                if (N < 0) throw new IllegalArgumentException ();
197                Integer[] a = new Integer[N];
198                for (int i = 0; i < N; i++) {
199                        a[i] = N - 1 - i;
200                }
201                return a;
202        }
203        /**
204         * Generate a shuffled array of length N with unique values 0, 1, ... N-1
205         */
206        public static Integer[] integerRandomUnique (int N) {
207                Integer[] a = integerSortedUnique (N);
208                StdRandom.shuffle (a);
209                return a;
210        }
211        /**
212         * Generate a partially sorted array with unique elements.
213         * The number of inversions will be between N and 2N.
214         * This algorithm moves random elements an arbitrary amount until the threshold is achieved.
215         */
216        public static Integer[] integerPartiallySortedUnique (int N) {
217                if (N < 6) throw new IllegalArgumentException ("array too small");
218                Integer[] a = integerSortedUnique (N);
219                int totalDistance = 0; // this is an approximation of the number of inversions
220                int range = (int) (Math.sqrt (N));
221                while (totalDistance < N) {
222                        int i = StdRandom.uniform (N);
223                        int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
224                        totalDistance += Math.abs (i - r);
225                        Integer temp = a[i];
226                        a[i] = a[r];
227                        a[r] = temp;
228                }
229                return a;
230        }
231        /**
232         * Generate a partially sorted array with unique elements.
233         * The number of inversions will be between N and 2N.
234         * This algorithm moves all elements a small amount.
235         */
236        public static Integer[] integerPartiallySortedUnique2 (int N) {
237                if (N < 6) throw new IllegalArgumentException ("array too small");
238                Integer[] a = integerSortedUnique (N);
239                int range = 4;
240                for (int i=0; i<N; i++) {
241                        int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
242                        Integer temp = a[i];
243                        a[i] = a[r];
244                        a[r] = temp;
245                }
246                return a;
247        }
248
249        //    public static void main (String[] args) {
250        //        StdOut.println (java.util.Arrays.toString (integerRandom (20, 1)));
251        //        StdOut.println (java.util.Arrays.toString (integerRandom (20, 2)));
252        //        StdOut.println (java.util.Arrays.toString (integerRandom (20, 4)));
253        //
254        //        // This is a unit test for partiallySortedUnique, to ensure that the result has inversions between N and 2N.
255        //        int N = 80;
256        //        for (int i = 0; i < 100; i++) {
257        //            Integer[] a = integerPartiallySortedUnique2 (N);
258        //            Integer[] b = integerRandomUnique (N);
259        //            StdOut.format ("N = %3d, partiallySorted = %3d, random = %3d\n", N, algs22.XInversions.count (a), algs22.XInversions.count (b));
260        //        }
261        //        for (int j = 0; j < 12; j++) {
262        //            N = N*2;
263        //            for (int i = 0; i < 100; i++) {
264        //                Integer[] a = integerPartiallySortedUnique2 (N);
265        //                int inversions = algs22.XInversions.count (a);
266        //                if (inversions < N || inversions > 2*N)
267        //                    StdOut.format ("N = %3d, partiallySorted = %3d\n", N, inversions);
268        //            }
269        //        }
270        //    }
271
272        /**
273         * Generate an array of length N whose values are chosen uniformly from the range [0,numValues).
274         */
275        public static double[] doubleRandom (int N, int numValues) {
276                if (N < 0) throw new IllegalArgumentException ();
277                double[] a = new double[N];
278                for (int i = 0; i < N; i++) {
279                        a[i] = Math.random ();
280                }
281                return a;
282        }
283        /**
284         * Generate an array of length N with values 0, 1, ..., N-1.
285         */
286        public static double[] doubleSortedUnique (int N) {
287                if (N < 0) throw new IllegalArgumentException ();
288                double[] a = new double[N];
289                for (int i = 0; i < N; i++) {
290                        a[i] = i;
291                }
292                return a;
293        }
294        /**
295         * Generate an array of length N with values N-1, N-2, ... 0.
296         */
297        public static double[] doubleReverseSortedUnique (int N) {
298                if (N < 0) throw new IllegalArgumentException ();
299                double[] a = new double[N];
300                for (int i = 0; i < N; i++) {
301                        a[i] = N - 1 - i;
302                }
303                return a;
304        }
305        /**
306         * Generate a shuffled array of length N with unique values 0, 1, ... N-1
307         */
308        public static double[] doubleRandomUnique (int N) {
309                double[] a = doubleSortedUnique (N);
310                StdRandom.shuffle (a);
311                return a;
312        }
313        /**
314         * Generate a partially sorted array with unique elements.
315         * The number of inversions will be between N and 2N.
316         * This algorithm moves random elements an arbitrary amount until the threshold is achieved.
317         */
318        public static double[] doublePartiallySortedUnique (int N) {
319                if (N < 6) throw new IllegalArgumentException ("array too small");
320                double[] a = doubleSortedUnique (N);
321                int totalDistance = 0; // this is an approximation of the number of inversions
322                int range = (int) (Math.sqrt (N));
323                while (totalDistance < N) {
324                        int i = StdRandom.uniform (N);
325                        int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
326                        totalDistance += Math.abs (i - r);
327                        double temp = a[i];
328                        a[i] = a[r];
329                        a[r] = temp;
330                }
331                return a;
332        }
333        /**
334         * Generate a partially sorted array with unique elements.
335         * The number of inversions will be between N and 2N.
336         * This algorithm moves all elements a small amount.
337         */
338        public static double[] doublePartiallySortedUnique2 (int N) {
339                if (N < 6) throw new IllegalArgumentException ("array too small");
340                double[] a = doubleSortedUnique (N);
341                int range = 4;
342                for (int i=0; i<N; i++) {
343                        int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
344                        double temp = a[i];
345                        a[i] = a[r];
346                        a[r] = temp;
347                }
348                return a;
349        }
350
351        /**
352         * Read in and return an array of Strings from fileName.  Input must begin with dimensions.
353         *
354         * @see In#readAllStrings()
355         * @see StdIn#readAllStrings()
356         */
357        public static String[] readString1D(String fileName) {
358                return readString1D (new In(fileName));
359        }
360        /**
361         * Read in and return an array of Strings from in. Input must begin with dimensions.
362         *
363         * @see In#readAllStrings()
364         * @see StdIn#readAllStrings()
365         */
366        public static String[] readString1D(In in) {
367                int N = in.readInt();
368                String[] a = new String[N];
369                for (int i = 0; i < N; i++) {
370                        a[i] = in.readString();
371                }
372                return a;
373        }
374
375        /**
376         * Print an array of Strings to standard output.
377         */
378        public static void print(Object[] a) {
379                int N = a.length;
380                StdOut.println(N);
381                for (int i = 0; i < N; i++) {
382                        StdOut.format("%s ", a[i]);
383                }
384                StdOut.println();
385        }
386
387        /**
388         * Read in and return an M-by-N array of Strings from fileName. Input must begin with dimensions.
389         */
390        public static String[][] readString2D(String fileName) {
391                return readString2D (new In(fileName));
392        }
393        /**
394         * Read in and return an M-by-N array of Strings from in. Input must begin with dimensions.
395         */
396        public static String[][] readString2D(In in) {
397                int M = in.readInt();
398                int N = in.readInt();
399                String[][] a = new String[M][N];
400                for (int i = 0; i < M; i++) {
401                        for (int j = 0; j < N; j++) {
402                                a[i][j] = in.readString();
403                        }
404                }
405                return a;
406        }
407
408        /**
409         * Print the M-by-N array of Strings to standard output.
410         */
411        public static void print(Object[][] a) {
412                int M = a.length;
413                int N = a[0].length;
414                StdOut.println(M + " " + N);
415                for (int i = 0; i < M; i++) {
416                        for (int j = 0; j < N; j++) {
417                                StdOut.format("%s ", a[i][j]);
418                        }
419                        StdOut.println();
420                }
421        }
422
423        /**
424         * Read in and return an array of doubles from fileName. Input must begin with dimensions.
425         *
426         * @see In#readAllDoubles()
427         * @see StdIn#readAllDoubles()
428         */
429        public static double[] readDouble1D(String fileName) {
430                return readDouble1D (new In(fileName));
431        }
432        /**
433         * Read in and return an array of doubles from in. Input must begin with dimensions.
434         *
435         * @see In#readAllDoubles()
436         * @see StdIn#readAllDoubles()
437         */
438        public static double[] readDouble1D(In in) {
439                int N = in.readInt();
440                double[] a = new double[N];
441                for (int i = 0; i < N; i++) {
442                        a[i] = in.readDouble();
443                }
444                return a;
445        }
446
447        /**
448         * Print an array of doubles to standard output.
449         */
450        public static void print(double[] a) {
451                int N = a.length;
452                StdOut.println(N);
453                for (int i = 0; i < N; i++) {
454                        StdOut.format("%9.5f ", a[i]);
455                }
456                StdOut.println();
457        }
458
459
460        /**
461         * Read in and return an M-by-N array of doubles from fileName. Input must begin with dimensions.
462         */
463        public static double[][] readDouble2D(String fileName) {
464                return readDouble2D (new In(fileName));
465        }
466        /**
467         * Read in and return an M-by-N array of doubles from in. Input must begin with dimensions.
468         */
469        public static double[][] readDouble2D(In in) {
470                int M = in.readInt();
471                int N = in.readInt();
472                double[][] a = new double[M][N];
473                for (int i = 0; i < M; i++) {
474                        for (int j = 0; j < N; j++) {
475                                a[i][j] = in.readDouble();
476                        }
477                }
478                return a;
479        }
480
481        /**
482         * Print the M-by-N array of doubles to standard output.
483         */
484        public static void print(double[][] a) {
485                int M = a.length;
486                int N = a[0].length;
487                StdOut.println(M + " " + N);
488                for (int i = 0; i < M; i++) {
489                        for (int j = 0; j < N; j++) {
490                                StdOut.format("%9.5f ", a[i][j]);
491                        }
492                        StdOut.println();
493                }
494        }
495
496
497        /**
498         * Read in and return an array of ints from fileName. Input must begin with dimensions.
499         *
500         * @see In#readAllInts()
501         * @see StdIn#readAllInts()
502         */
503        public static int[] readInt1D(String fileName) {
504                return readInt1D (new In(fileName));
505        }
506        /**
507         * Read in and return an array of ints from in. Input must begin with dimensions.
508         *
509         * @see In#readAllInts()
510         * @see StdIn#readAllInts()
511         */
512        public static int[] readInt1D(In in) {
513                int N = in.readInt();
514                int[] a = new int[N];
515                for (int i = 0; i < N; i++) {
516                        a[i] = in.readInt();
517                }
518                return a;
519        }
520
521        /**
522         * Print an array of ints to standard output.
523         */
524        public static void print(int[] a) {
525                int N = a.length;
526                StdOut.println(N);
527                for (int i = 0; i < N; i++) {
528                        StdOut.format("%9d ", a[i]);
529                }
530                StdOut.println();
531        }
532
533
534        /**
535         * Read in and return an M-by-N array of ints from fileName. Input must begin with dimensions.
536         */
537        public static int[][] readInt2D(String fileName) {
538                return readInt2D (new In(fileName));
539        }
540        /**
541         * Read in and return an M-by-N array of ints from in. Input must begin with dimensions.
542         */
543        public static int[][] readInt2D(In in) {
544                int M = in.readInt();
545                int N = in.readInt();
546                int[][] a = new int[M][N];
547                for (int i = 0; i < M; i++) {
548                        for (int j = 0; j < N; j++) {
549                                a[i][j] = in.readInt();
550                        }
551                }
552                return a;
553        }
554
555        /**
556         * Print the M-by-N array of ints to standard output.
557         */
558        public static void print(int[][] a) {
559                int M = a.length;
560                int N = a[0].length;
561                StdOut.println(M + " " + N);
562                for (int i = 0; i < M; i++) {
563                        for (int j = 0; j < N; j++) {
564                                StdOut.format("%9d ", a[i][j]);
565                        }
566                        StdOut.println();
567                }
568        }
569
570
571        /**
572         * Read in and return an array of booleans from fileName. Input must begin with dimensions.
573         */
574        public static boolean[] readBoolean1D(String fileName) {
575                return readBoolean1D (new In(fileName));
576        }
577        /**
578         * Read in and return an array of booleans from in. Input must begin with dimensions.
579         */
580        public static boolean[] readBoolean1D(In in) {
581                int N = in.readInt();
582                boolean[] a = new boolean[N];
583                for (int i = 0; i < N; i++) {
584                        a[i] = in.readBoolean();
585                }
586                return a;
587        }
588
589        /**
590         * Print an array of booleans to standard output.
591         */
592        public static void print(boolean[] a) {
593                int N = a.length;
594                StdOut.println(N);
595                for (int i = 0; i < N; i++) {
596                        if (a[i]) StdOut.print("1 ");
597                        else      StdOut.print("0 ");
598                }
599                StdOut.println();
600        }
601
602        /**
603         * Read in and return an M-by-N array of booleans from fileName. Input must begin with dimensions.
604         */
605        public static boolean[][] readBoolean2D(String fileName) {
606                return readBoolean2D (new In(fileName));
607        }
608        /**
609         * Read in and return an M-by-N array of booleans from in. Input must begin with dimensions.
610         */
611        public static boolean[][] readBoolean2D(In in) {
612                int M = in.readInt();
613                int N = in.readInt();
614                boolean[][] a = new boolean[M][N];
615                for (int i = 0; i < M; i++) {
616                        for (int j = 0; j < N; j++) {
617                                a[i][j] = in.readBoolean();
618                        }
619                }
620                return a;
621        }
622
623        /**
624         * Print the  M-by-N array of booleans to standard output.
625         */
626        public static void print(boolean[][] a) {
627                int M = a.length;
628                int N = a[0].length;
629                StdOut.println(M + " " + N);
630                for (int i = 0; i < M; i++) {
631                        for (int j = 0; j < N; j++) {
632                                if (a[i][j]) StdOut.print("1 ");
633                                else         StdOut.print("0 ");
634                        }
635                        StdOut.println();
636                }
637        }
638}