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}