001 /* Arrays.java -- Utility class with methods to operate on arrays 002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 003 Free Software Foundation, Inc. 004 005 This file is part of GNU Classpath. 006 007 GNU Classpath is free software; you can redistribute it and/or modify 008 it under the terms of the GNU General Public License as published by 009 the Free Software Foundation; either version 2, or (at your option) 010 any later version. 011 012 GNU Classpath is distributed in the hope that it will be useful, but 013 WITHOUT ANY WARRANTY; without even the implied warranty of 014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015 General Public License for more details. 016 017 You should have received a copy of the GNU General Public License 018 along with GNU Classpath; see the file COPYING. If not, write to the 019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 020 02110-1301 USA. 021 022 Linking this library statically or dynamically with other modules is 023 making a combined work based on this library. Thus, the terms and 024 conditions of the GNU General Public License cover the whole 025 combination. 026 027 As a special exception, the copyright holders of this library give you 028 permission to link this library with independent modules to produce an 029 executable, regardless of the license terms of these independent 030 modules, and to copy and distribute the resulting executable under 031 terms of your choice, provided that you also meet, for each linked 032 independent module, the terms and conditions of the license of that 033 module. An independent module is a module which is not derived from 034 or based on this library. If you modify this library, you may extend 035 this exception to your version of the library, but you are not 036 obligated to do so. If you do not wish to do so, delete this 037 exception statement from your version. */ 038 039 040 package java.util; 041 042 import java.io.Serializable; 043 import java.lang.reflect.Array; 044 045 /** 046 * This class contains various static utility methods performing operations on 047 * arrays, and a method to provide a List "view" of an array to facilitate 048 * using arrays with Collection-based APIs. All methods throw a 049 * {@link NullPointerException} if the parameter array is null. 050 * <p> 051 * 052 * Implementations may use their own algorithms, but must obey the general 053 * properties; for example, the sort must be stable and n*log(n) complexity. 054 * Sun's implementation of sort, and therefore ours, is a tuned quicksort, 055 * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort 056 * Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 057 * (November 1993). This algorithm offers n*log(n) performance on many data 058 * sets that cause other quicksorts to degrade to quadratic performance. 059 * 060 * @author Original author unknown 061 * @author Bryce McKinlay 062 * @author Eric Blake (ebb9@email.byu.edu) 063 * @see Comparable 064 * @see Comparator 065 * @since 1.2 066 * @status updated to 1.4 067 */ 068 public class Arrays 069 { 070 /** 071 * This class is non-instantiable. 072 */ 073 private Arrays() 074 { 075 } 076 077 078 // binarySearch 079 /** 080 * Perform a binary search of a byte array for a key. The array must be 081 * sorted (as by the sort() method) - if it is not, the behaviour of this 082 * method is undefined, and may be an infinite loop. If the array contains 083 * the key more than once, any one of them may be found. Note: although the 084 * specification allows for an infinite loop if the array is unsorted, it 085 * will not happen in this implementation. 086 * 087 * @param a the array to search (must be sorted) 088 * @param key the value to search for 089 * @return the index at which the key was found, or -n-1 if it was not 090 * found, where n is the index of the first value higher than key or 091 * a.length if there is no such value. 092 */ 093 public static int binarySearch(byte[] a, byte key) 094 { 095 if (a.length == 0) 096 return -1; 097 return binarySearch(a, 0, a.length - 1, key); 098 } 099 100 /** 101 * Perform a binary search of a range of a byte array for a key. The range 102 * must be sorted (as by the <code>sort(byte[], int, int)</code> method) - 103 * if it is not, the behaviour of this method is undefined, and may be an 104 * infinite loop. If the array contains the key more than once, any one of 105 * them may be found. Note: although the specification allows for an infinite 106 * loop if the array is unsorted, it will not happen in this implementation. 107 * 108 * @param a the array to search (must be sorted) 109 * @param low the lowest index to search from. 110 * @param hi the highest index to search to. 111 * @param key the value to search for 112 * @return the index at which the key was found, or -n-1 if it was not 113 * found, where n is the index of the first value higher than key or 114 * a.length if there is no such value. 115 * @throws IllegalArgumentException if <code>low > hi</code> 116 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 117 * <code>hi > a.length</code>. 118 */ 119 public static int binarySearch(byte[] a, int low, int hi, byte key) 120 { 121 if (low > hi) 122 throw new IllegalArgumentException("The start index is higher than " + 123 "the finish index."); 124 if (low < 0 || hi > a.length) 125 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 126 "of bounds."); 127 int mid = 0; 128 while (low <= hi) 129 { 130 mid = (low + hi) >>> 1; 131 final byte d = a[mid]; 132 if (d == key) 133 return mid; 134 else if (d > key) 135 hi = mid - 1; 136 else 137 // This gets the insertion point right on the last loop. 138 low = ++mid; 139 } 140 return -mid - 1; 141 } 142 143 /** 144 * Perform a binary search of a char array for a key. The array must be 145 * sorted (as by the sort() method) - if it is not, the behaviour of this 146 * method is undefined, and may be an infinite loop. If the array contains 147 * the key more than once, any one of them may be found. Note: although the 148 * specification allows for an infinite loop if the array is unsorted, it 149 * will not happen in this implementation. 150 * 151 * @param a the array to search (must be sorted) 152 * @param key the value to search for 153 * @return the index at which the key was found, or -n-1 if it was not 154 * found, where n is the index of the first value higher than key or 155 * a.length if there is no such value. 156 */ 157 public static int binarySearch(char[] a, char key) 158 { 159 if (a.length == 0) 160 return -1; 161 return binarySearch(a, 0, a.length - 1, key); 162 } 163 164 /** 165 * Perform a binary search of a range of a char array for a key. The range 166 * must be sorted (as by the <code>sort(char[], int, int)</code> method) - 167 * if it is not, the behaviour of this method is undefined, and may be an 168 * infinite loop. If the array contains the key more than once, any one of 169 * them may be found. Note: although the specification allows for an infinite 170 * loop if the array is unsorted, it will not happen in this implementation. 171 * 172 * @param a the array to search (must be sorted) 173 * @param low the lowest index to search from. 174 * @param hi the highest index to search to. 175 * @param key the value to search for 176 * @return the index at which the key was found, or -n-1 if it was not 177 * found, where n is the index of the first value higher than key or 178 * a.length if there is no such value. 179 * @throws IllegalArgumentException if <code>low > hi</code> 180 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 181 * <code>hi > a.length</code>. 182 */ 183 public static int binarySearch(char[] a, int low, int hi, char key) 184 { 185 if (low > hi) 186 throw new IllegalArgumentException("The start index is higher than " + 187 "the finish index."); 188 if (low < 0 || hi > a.length) 189 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 190 "of bounds."); 191 int mid = 0; 192 while (low <= hi) 193 { 194 mid = (low + hi) >>> 1; 195 final char d = a[mid]; 196 if (d == key) 197 return mid; 198 else if (d > key) 199 hi = mid - 1; 200 else 201 // This gets the insertion point right on the last loop. 202 low = ++mid; 203 } 204 return -mid - 1; 205 } 206 207 /** 208 * Perform a binary search of a short array for a key. The array must be 209 * sorted (as by the sort() method) - if it is not, the behaviour of this 210 * method is undefined, and may be an infinite loop. If the array contains 211 * the key more than once, any one of them may be found. Note: although the 212 * specification allows for an infinite loop if the array is unsorted, it 213 * will not happen in this implementation. 214 * 215 * @param a the array to search (must be sorted) 216 * @param key the value to search for 217 * @return the index at which the key was found, or -n-1 if it was not 218 * found, where n is the index of the first value higher than key or 219 * a.length if there is no such value. 220 */ 221 public static int binarySearch(short[] a, short key) 222 { 223 if (a.length == 0) 224 return -1; 225 return binarySearch(a, 0, a.length - 1, key); 226 } 227 228 /** 229 * Perform a binary search of a range of a short array for a key. The range 230 * must be sorted (as by the <code>sort(short[], int, int)</code> method) - 231 * if it is not, the behaviour of this method is undefined, and may be an 232 * infinite loop. If the array contains the key more than once, any one of 233 * them may be found. Note: although the specification allows for an infinite 234 * loop if the array is unsorted, it will not happen in this implementation. 235 * 236 * @param a the array to search (must be sorted) 237 * @param low the lowest index to search from. 238 * @param hi the highest index to search to. 239 * @param key the value to search for 240 * @return the index at which the key was found, or -n-1 if it was not 241 * found, where n is the index of the first value higher than key or 242 * a.length if there is no such value. 243 * @throws IllegalArgumentException if <code>low > hi</code> 244 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 245 * <code>hi > a.length</code>. 246 */ 247 public static int binarySearch(short[] a, int low, int hi, short key) 248 { 249 if (low > hi) 250 throw new IllegalArgumentException("The start index is higher than " + 251 "the finish index."); 252 if (low < 0 || hi > a.length) 253 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 254 "of bounds."); 255 int mid = 0; 256 while (low <= hi) 257 { 258 mid = (low + hi) >>> 1; 259 final short d = a[mid]; 260 if (d == key) 261 return mid; 262 else if (d > key) 263 hi = mid - 1; 264 else 265 // This gets the insertion point right on the last loop. 266 low = ++mid; 267 } 268 return -mid - 1; 269 } 270 271 /** 272 * Perform a binary search of an int array for a key. The array must be 273 * sorted (as by the sort() method) - if it is not, the behaviour of this 274 * method is undefined, and may be an infinite loop. If the array contains 275 * the key more than once, any one of them may be found. Note: although the 276 * specification allows for an infinite loop if the array is unsorted, it 277 * will not happen in this implementation. 278 * 279 * @param a the array to search (must be sorted) 280 * @param key the value to search for 281 * @return the index at which the key was found, or -n-1 if it was not 282 * found, where n is the index of the first value higher than key or 283 * a.length if there is no such value. 284 */ 285 public static int binarySearch(int[] a, int key) 286 { 287 if (a.length == 0) 288 return -1; 289 return binarySearch(a, 0, a.length - 1, key); 290 } 291 292 /** 293 * Perform a binary search of a range of an integer array for a key. The range 294 * must be sorted (as by the <code>sort(int[], int, int)</code> method) - 295 * if it is not, the behaviour of this method is undefined, and may be an 296 * infinite loop. If the array contains the key more than once, any one of 297 * them may be found. Note: although the specification allows for an infinite 298 * loop if the array is unsorted, it will not happen in this implementation. 299 * 300 * @param a the array to search (must be sorted) 301 * @param low the lowest index to search from. 302 * @param hi the highest index to search to. 303 * @param key the value to search for 304 * @return the index at which the key was found, or -n-1 if it was not 305 * found, where n is the index of the first value higher than key or 306 * a.length if there is no such value. 307 * @throws IllegalArgumentException if <code>low > hi</code> 308 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 309 * <code>hi > a.length</code>. 310 */ 311 public static int binarySearch(int[] a, int low, int hi, int key) 312 { 313 if (low > hi) 314 throw new IllegalArgumentException("The start index is higher than " + 315 "the finish index."); 316 if (low < 0 || hi > a.length) 317 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 318 "of bounds."); 319 int mid = 0; 320 while (low <= hi) 321 { 322 mid = (low + hi) >>> 1; 323 final int d = a[mid]; 324 if (d == key) 325 return mid; 326 else if (d > key) 327 hi = mid - 1; 328 else 329 // This gets the insertion point right on the last loop. 330 low = ++mid; 331 } 332 return -mid - 1; 333 } 334 335 /** 336 * Perform a binary search of a long array for a key. The array must be 337 * sorted (as by the sort() method) - if it is not, the behaviour of this 338 * method is undefined, and may be an infinite loop. If the array contains 339 * the key more than once, any one of them may be found. Note: although the 340 * specification allows for an infinite loop if the array is unsorted, it 341 * will not happen in this implementation. 342 * 343 * @param a the array to search (must be sorted) 344 * @param key the value to search for 345 * @return the index at which the key was found, or -n-1 if it was not 346 * found, where n is the index of the first value higher than key or 347 * a.length if there is no such value. 348 */ 349 public static int binarySearch(long[] a, long key) 350 { 351 if (a.length == 0) 352 return -1; 353 return binarySearch(a, 0, a.length - 1, key); 354 } 355 356 /** 357 * Perform a binary search of a range of a long array for a key. The range 358 * must be sorted (as by the <code>sort(long[], int, int)</code> method) - 359 * if it is not, the behaviour of this method is undefined, and may be an 360 * infinite loop. If the array contains the key more than once, any one of 361 * them may be found. Note: although the specification allows for an infinite 362 * loop if the array is unsorted, it will not happen in this implementation. 363 * 364 * @param a the array to search (must be sorted) 365 * @param low the lowest index to search from. 366 * @param hi the highest index to search to. 367 * @param key the value to search for 368 * @return the index at which the key was found, or -n-1 if it was not 369 * found, where n is the index of the first value higher than key or 370 * a.length if there is no such value. 371 * @throws IllegalArgumentException if <code>low > hi</code> 372 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 373 * <code>hi > a.length</code>. 374 */ 375 public static int binarySearch(long[] a, int low, int hi, long key) 376 { 377 if (low > hi) 378 throw new IllegalArgumentException("The start index is higher than " + 379 "the finish index."); 380 if (low < 0 || hi > a.length) 381 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 382 "of bounds."); 383 int mid = 0; 384 while (low <= hi) 385 { 386 mid = (low + hi) >>> 1; 387 final long d = a[mid]; 388 if (d == key) 389 return mid; 390 else if (d > key) 391 hi = mid - 1; 392 else 393 // This gets the insertion point right on the last loop. 394 low = ++mid; 395 } 396 return -mid - 1; 397 } 398 399 /** 400 * Perform a binary search of a float array for a key. The array must be 401 * sorted (as by the sort() method) - if it is not, the behaviour of this 402 * method is undefined, and may be an infinite loop. If the array contains 403 * the key more than once, any one of them may be found. Note: although the 404 * specification allows for an infinite loop if the array is unsorted, it 405 * will not happen in this implementation. 406 * 407 * @param a the array to search (must be sorted) 408 * @param key the value to search for 409 * @return the index at which the key was found, or -n-1 if it was not 410 * found, where n is the index of the first value higher than key or 411 * a.length if there is no such value. 412 */ 413 public static int binarySearch(float[] a, float key) 414 { 415 if (a.length == 0) 416 return -1; 417 return binarySearch(a, 0, a.length - 1, key); 418 } 419 420 /** 421 * Perform a binary search of a range of a float array for a key. The range 422 * must be sorted (as by the <code>sort(float[], int, int)</code> method) - 423 * if it is not, the behaviour of this method is undefined, and may be an 424 * infinite loop. If the array contains the key more than once, any one of 425 * them may be found. Note: although the specification allows for an infinite 426 * loop if the array is unsorted, it will not happen in this implementation. 427 * 428 * @param a the array to search (must be sorted) 429 * @param low the lowest index to search from. 430 * @param hi the highest index to search to. 431 * @param key the value to search for 432 * @return the index at which the key was found, or -n-1 if it was not 433 * found, where n is the index of the first value higher than key or 434 * a.length if there is no such value. 435 * @throws IllegalArgumentException if <code>low > hi</code> 436 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 437 * <code>hi > a.length</code>. 438 */ 439 public static int binarySearch(float[] a, int low, int hi, float key) 440 { 441 if (low > hi) 442 throw new IllegalArgumentException("The start index is higher than " + 443 "the finish index."); 444 if (low < 0 || hi > a.length) 445 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 446 "of bounds."); 447 // Must use Float.compare to take into account NaN, +-0. 448 int mid = 0; 449 while (low <= hi) 450 { 451 mid = (low + hi) >>> 1; 452 final int r = Float.compare(a[mid], key); 453 if (r == 0) 454 return mid; 455 else if (r > 0) 456 hi = mid - 1; 457 else 458 // This gets the insertion point right on the last loop 459 low = ++mid; 460 } 461 return -mid - 1; 462 } 463 464 /** 465 * Perform a binary search of a double array for a key. The array must be 466 * sorted (as by the sort() method) - if it is not, the behaviour of this 467 * method is undefined, and may be an infinite loop. If the array contains 468 * the key more than once, any one of them may be found. Note: although the 469 * specification allows for an infinite loop if the array is unsorted, it 470 * will not happen in this implementation. 471 * 472 * @param a the array to search (must be sorted) 473 * @param key the value to search for 474 * @return the index at which the key was found, or -n-1 if it was not 475 * found, where n is the index of the first value higher than key or 476 * a.length if there is no such value. 477 */ 478 public static int binarySearch(double[] a, double key) 479 { 480 if (a.length == 0) 481 return -1; 482 return binarySearch(a, 0, a.length - 1, key); 483 } 484 485 /** 486 * Perform a binary search of a range of a double array for a key. The range 487 * must be sorted (as by the <code>sort(double[], int, int)</code> method) - 488 * if it is not, the behaviour of this method is undefined, and may be an 489 * infinite loop. If the array contains the key more than once, any one of 490 * them may be found. Note: although the specification allows for an infinite 491 * loop if the array is unsorted, it will not happen in this implementation. 492 * 493 * @param a the array to search (must be sorted) 494 * @param low the lowest index to search from. 495 * @param hi the highest index to search to. 496 * @param key the value to search for 497 * @return the index at which the key was found, or -n-1 if it was not 498 * found, where n is the index of the first value higher than key or 499 * a.length if there is no such value. 500 * @throws IllegalArgumentException if <code>low > hi</code> 501 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 502 * <code>hi > a.length</code>. 503 */ 504 public static int binarySearch(double[] a, int low, int hi, double key) 505 { 506 if (low > hi) 507 throw new IllegalArgumentException("The start index is higher than " + 508 "the finish index."); 509 if (low < 0 || hi > a.length) 510 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 511 "of bounds."); 512 // Must use Double.compare to take into account NaN, +-0. 513 int mid = 0; 514 while (low <= hi) 515 { 516 mid = (low + hi) >>> 1; 517 final int r = Double.compare(a[mid], key); 518 if (r == 0) 519 return mid; 520 else if (r > 0) 521 hi = mid - 1; 522 else 523 // This gets the insertion point right on the last loop 524 low = ++mid; 525 } 526 return -mid - 1; 527 } 528 529 /** 530 * Perform a binary search of an Object array for a key, using the natural 531 * ordering of the elements. The array must be sorted (as by the sort() 532 * method) - if it is not, the behaviour of this method is undefined, and may 533 * be an infinite loop. Further, the key must be comparable with every item 534 * in the array. If the array contains the key more than once, any one of 535 * them may be found. Note: although the specification allows for an infinite 536 * loop if the array is unsorted, it will not happen in this (JCL) 537 * implementation. 538 * 539 * @param a the array to search (must be sorted) 540 * @param key the value to search for 541 * @return the index at which the key was found, or -n-1 if it was not 542 * found, where n is the index of the first value higher than key or 543 * a.length if there is no such value. 544 * @throws ClassCastException if key could not be compared with one of the 545 * elements of a 546 * @throws NullPointerException if a null element in a is compared 547 */ 548 public static int binarySearch(Object[] a, Object key) 549 { 550 if (a.length == 0) 551 return -1; 552 return binarySearch(a, key, null); 553 } 554 555 /** 556 * Perform a binary search of a range of an Object array for a key. The range 557 * must be sorted (as by the <code>sort(Object[], int, int)</code> method) - 558 * if it is not, the behaviour of this method is undefined, and may be an 559 * infinite loop. If the array contains the key more than once, any one of 560 * them may be found. Note: although the specification allows for an infinite 561 * loop if the array is unsorted, it will not happen in this implementation. 562 * 563 * @param a the array to search (must be sorted) 564 * @param low the lowest index to search from. 565 * @param hi the highest index to search to. 566 * @param key the value to search for 567 * @return the index at which the key was found, or -n-1 if it was not 568 * found, where n is the index of the first value higher than key or 569 * a.length if there is no such value. 570 */ 571 public static int binarySearch(Object[] a, int low, int hi, Object key) 572 { 573 return binarySearch(a, low, hi, key, null); 574 } 575 576 /** 577 * Perform a binary search of an Object array for a key, using a supplied 578 * Comparator. The array must be sorted (as by the sort() method with the 579 * same Comparator) - if it is not, the behaviour of this method is 580 * undefined, and may be an infinite loop. Further, the key must be 581 * comparable with every item in the array. If the array contains the key 582 * more than once, any one of them may be found. Note: although the 583 * specification allows for an infinite loop if the array is unsorted, it 584 * will not happen in this (JCL) implementation. 585 * 586 * @param a the array to search (must be sorted) 587 * @param key the value to search for 588 * @param c the comparator by which the array is sorted; or null to 589 * use the elements' natural order 590 * @return the index at which the key was found, or -n-1 if it was not 591 * found, where n is the index of the first value higher than key or 592 * a.length if there is no such value. 593 * @throws ClassCastException if key could not be compared with one of the 594 * elements of a 595 * @throws NullPointerException if a null element is compared with natural 596 * ordering (only possible when c is null) 597 */ 598 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) 599 { 600 if (a.length == 0) 601 return -1; 602 return binarySearch(a, 0, a.length - 1, key, c); 603 } 604 605 /** 606 * Perform a binary search of a range of an Object array for a key using 607 * a {@link Comparator}. The range must be sorted (as by the 608 * <code>sort(Object[], int, int)</code> method) - if it is not, the 609 * behaviour of this method is undefined, and may be an infinite loop. If 610 * the array contains the key more than once, any one of them may be found. 611 * Note: although the specification allows for an infinite loop if the array 612 * is unsorted, it will not happen in this implementation. 613 * 614 * @param a the array to search (must be sorted) 615 * @param low the lowest index to search from. 616 * @param hi the highest index to search to. 617 * @param key the value to search for 618 * @param c the comparator by which the array is sorted; or null to 619 * use the elements' natural order 620 * @return the index at which the key was found, or -n-1 if it was not 621 * found, where n is the index of the first value higher than key or 622 * a.length if there is no such value. 623 * @throws ClassCastException if key could not be compared with one of the 624 * elements of a 625 * @throws IllegalArgumentException if <code>low > hi</code> 626 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or 627 * <code>hi > a.length</code>. 628 */ 629 public static <T> int binarySearch(T[] a, int low, int hi, T key, 630 Comparator<? super T> c) 631 { 632 if (low > hi) 633 throw new IllegalArgumentException("The start index is higher than " + 634 "the finish index."); 635 if (low < 0 || hi > a.length) 636 throw new ArrayIndexOutOfBoundsException("One of the indices is out " + 637 "of bounds."); 638 int mid = 0; 639 while (low <= hi) 640 { 641 mid = (low + hi) >>> 1; 642 // NOTE: Please keep the order of a[mid] and key. Although 643 // not required by the specs, the RI has it in this order as 644 // well, and real programs (erroneously) depend on it. 645 final int d = Collections.compare(a[mid], key, c); 646 if (d == 0) 647 return mid; 648 else if (d > 0) 649 hi = mid - 1; 650 else 651 // This gets the insertion point right on the last loop 652 low = ++mid; 653 } 654 return -mid - 1; 655 } 656 657 658 // equals 659 /** 660 * Compare two boolean arrays for equality. 661 * 662 * @param a1 the first array to compare 663 * @param a2 the second array to compare 664 * @return true if a1 and a2 are both null, or if a2 is of the same length 665 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 666 */ 667 public static boolean equals(boolean[] a1, boolean[] a2) 668 { 669 // Quick test which saves comparing elements of the same array, and also 670 // catches the case that both are null. 671 if (a1 == a2) 672 return true; 673 674 if (null == a1 || null == a2) 675 return false; 676 677 // If they're the same length, test each element 678 if (a1.length == a2.length) 679 { 680 int i = a1.length; 681 while (--i >= 0) 682 if (a1[i] != a2[i]) 683 return false; 684 return true; 685 } 686 return false; 687 } 688 689 /** 690 * Compare two byte arrays for equality. 691 * 692 * @param a1 the first array to compare 693 * @param a2 the second array to compare 694 * @return true if a1 and a2 are both null, or if a2 is of the same length 695 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 696 */ 697 public static boolean equals(byte[] a1, byte[] a2) 698 { 699 // Quick test which saves comparing elements of the same array, and also 700 // catches the case that both are null. 701 if (a1 == a2) 702 return true; 703 704 if (null == a1 || null == a2) 705 return false; 706 707 // If they're the same length, test each element 708 if (a1.length == a2.length) 709 { 710 int i = a1.length; 711 while (--i >= 0) 712 if (a1[i] != a2[i]) 713 return false; 714 return true; 715 } 716 return false; 717 } 718 719 /** 720 * Compare two char arrays for equality. 721 * 722 * @param a1 the first array to compare 723 * @param a2 the second array to compare 724 * @return true if a1 and a2 are both null, or if a2 is of the same length 725 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 726 */ 727 public static boolean equals(char[] a1, char[] a2) 728 { 729 // Quick test which saves comparing elements of the same array, and also 730 // catches the case that both are null. 731 if (a1 == a2) 732 return true; 733 734 if (null == a1 || null == a2) 735 return false; 736 737 // If they're the same length, test each element 738 if (a1.length == a2.length) 739 { 740 int i = a1.length; 741 while (--i >= 0) 742 if (a1[i] != a2[i]) 743 return false; 744 return true; 745 } 746 return false; 747 } 748 749 /** 750 * Compare two short arrays for equality. 751 * 752 * @param a1 the first array to compare 753 * @param a2 the second array to compare 754 * @return true if a1 and a2 are both null, or if a2 is of the same length 755 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 756 */ 757 public static boolean equals(short[] a1, short[] a2) 758 { 759 // Quick test which saves comparing elements of the same array, and also 760 // catches the case that both are null. 761 if (a1 == a2) 762 return true; 763 764 if (null == a1 || null == a2) 765 return false; 766 767 // If they're the same length, test each element 768 if (a1.length == a2.length) 769 { 770 int i = a1.length; 771 while (--i >= 0) 772 if (a1[i] != a2[i]) 773 return false; 774 return true; 775 } 776 return false; 777 } 778 779 /** 780 * Compare two int arrays for equality. 781 * 782 * @param a1 the first array to compare 783 * @param a2 the second array to compare 784 * @return true if a1 and a2 are both null, or if a2 is of the same length 785 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 786 */ 787 public static boolean equals(int[] a1, int[] a2) 788 { 789 // Quick test which saves comparing elements of the same array, and also 790 // catches the case that both are null. 791 if (a1 == a2) 792 return true; 793 794 if (null == a1 || null == a2) 795 return false; 796 797 // If they're the same length, test each element 798 if (a1.length == a2.length) 799 { 800 int i = a1.length; 801 while (--i >= 0) 802 if (a1[i] != a2[i]) 803 return false; 804 return true; 805 } 806 return false; 807 } 808 809 /** 810 * Compare two long arrays for equality. 811 * 812 * @param a1 the first array to compare 813 * @param a2 the second array to compare 814 * @return true if a1 and a2 are both null, or if a2 is of the same length 815 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 816 */ 817 public static boolean equals(long[] a1, long[] a2) 818 { 819 // Quick test which saves comparing elements of the same array, and also 820 // catches the case that both are null. 821 if (a1 == a2) 822 return true; 823 824 if (null == a1 || null == a2) 825 return false; 826 827 // If they're the same length, test each element 828 if (a1.length == a2.length) 829 { 830 int i = a1.length; 831 while (--i >= 0) 832 if (a1[i] != a2[i]) 833 return false; 834 return true; 835 } 836 return false; 837 } 838 839 /** 840 * Compare two float arrays for equality. 841 * 842 * @param a1 the first array to compare 843 * @param a2 the second array to compare 844 * @return true if a1 and a2 are both null, or if a2 is of the same length 845 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 846 */ 847 public static boolean equals(float[] a1, float[] a2) 848 { 849 // Quick test which saves comparing elements of the same array, and also 850 // catches the case that both are null. 851 if (a1 == a2) 852 return true; 853 854 if (null == a1 || null == a2) 855 return false; 856 857 // Must use Float.compare to take into account NaN, +-0. 858 // If they're the same length, test each element 859 if (a1.length == a2.length) 860 { 861 int i = a1.length; 862 while (--i >= 0) 863 if (Float.compare(a1[i], a2[i]) != 0) 864 return false; 865 return true; 866 } 867 return false; 868 } 869 870 /** 871 * Compare two double arrays for equality. 872 * 873 * @param a1 the first array to compare 874 * @param a2 the second array to compare 875 * @return true if a1 and a2 are both null, or if a2 is of the same length 876 * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 877 */ 878 public static boolean equals(double[] a1, double[] a2) 879 { 880 // Quick test which saves comparing elements of the same array, and also 881 // catches the case that both are null. 882 if (a1 == a2) 883 return true; 884 885 if (null == a1 || null == a2) 886 return false; 887 888 // Must use Double.compare to take into account NaN, +-0. 889 // If they're the same length, test each element 890 if (a1.length == a2.length) 891 { 892 int i = a1.length; 893 while (--i >= 0) 894 if (Double.compare(a1[i], a2[i]) != 0) 895 return false; 896 return true; 897 } 898 return false; 899 } 900 901 /** 902 * Compare two Object arrays for equality. 903 * 904 * @param a1 the first array to compare 905 * @param a2 the second array to compare 906 * @return true if a1 and a2 are both null, or if a1 is of the same length 907 * as a2, and for each 0 <= i < a.length, a1[i] == null ? 908 * a2[i] == null : a1[i].equals(a2[i]). 909 */ 910 public static boolean equals(Object[] a1, Object[] a2) 911 { 912 // Quick test which saves comparing elements of the same array, and also 913 // catches the case that both are null. 914 if (a1 == a2) 915 return true; 916 917 if (null == a1 || null == a2) 918 return false; 919 920 // If they're the same length, test each element 921 if (a1.length == a2.length) 922 { 923 int i = a1.length; 924 while (--i >= 0) 925 if (! AbstractCollection.equals(a1[i], a2[i])) 926 return false; 927 return true; 928 } 929 return false; 930 } 931 932 933 // fill 934 /** 935 * Fill an array with a boolean value. 936 * 937 * @param a the array to fill 938 * @param val the value to fill it with 939 */ 940 public static void fill(boolean[] a, boolean val) 941 { 942 fill(a, 0, a.length, val); 943 } 944 945 /** 946 * Fill a range of an array with a boolean value. 947 * 948 * @param a the array to fill 949 * @param fromIndex the index to fill from, inclusive 950 * @param toIndex the index to fill to, exclusive 951 * @param val the value to fill with 952 * @throws IllegalArgumentException if fromIndex > toIndex 953 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 954 * || toIndex > a.length 955 */ 956 public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val) 957 { 958 if (fromIndex > toIndex) 959 throw new IllegalArgumentException(); 960 for (int i = fromIndex; i < toIndex; i++) 961 a[i] = val; 962 } 963 964 /** 965 * Fill an array with a byte value. 966 * 967 * @param a the array to fill 968 * @param val the value to fill it with 969 */ 970 public static void fill(byte[] a, byte val) 971 { 972 fill(a, 0, a.length, val); 973 } 974 975 /** 976 * Fill a range of an array with a byte value. 977 * 978 * @param a the array to fill 979 * @param fromIndex the index to fill from, inclusive 980 * @param toIndex the index to fill to, exclusive 981 * @param val the value to fill with 982 * @throws IllegalArgumentException if fromIndex > toIndex 983 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 984 * || toIndex > a.length 985 */ 986 public static void fill(byte[] a, int fromIndex, int toIndex, byte val) 987 { 988 if (fromIndex > toIndex) 989 throw new IllegalArgumentException(); 990 for (int i = fromIndex; i < toIndex; i++) 991 a[i] = val; 992 } 993 994 /** 995 * Fill an array with a char value. 996 * 997 * @param a the array to fill 998 * @param val the value to fill it with 999 */ 1000 public static void fill(char[] a, char val) 1001 { 1002 fill(a, 0, a.length, val); 1003 } 1004 1005 /** 1006 * Fill a range of an array with a char value. 1007 * 1008 * @param a the array to fill 1009 * @param fromIndex the index to fill from, inclusive 1010 * @param toIndex the index to fill to, exclusive 1011 * @param val the value to fill with 1012 * @throws IllegalArgumentException if fromIndex > toIndex 1013 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1014 * || toIndex > a.length 1015 */ 1016 public static void fill(char[] a, int fromIndex, int toIndex, char val) 1017 { 1018 if (fromIndex > toIndex) 1019 throw new IllegalArgumentException(); 1020 for (int i = fromIndex; i < toIndex; i++) 1021 a[i] = val; 1022 } 1023 1024 /** 1025 * Fill an array with a short value. 1026 * 1027 * @param a the array to fill 1028 * @param val the value to fill it with 1029 */ 1030 public static void fill(short[] a, short val) 1031 { 1032 fill(a, 0, a.length, val); 1033 } 1034 1035 /** 1036 * Fill a range of an array with a short value. 1037 * 1038 * @param a the array to fill 1039 * @param fromIndex the index to fill from, inclusive 1040 * @param toIndex the index to fill to, exclusive 1041 * @param val the value to fill with 1042 * @throws IllegalArgumentException if fromIndex > toIndex 1043 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1044 * || toIndex > a.length 1045 */ 1046 public static void fill(short[] a, int fromIndex, int toIndex, short val) 1047 { 1048 if (fromIndex > toIndex) 1049 throw new IllegalArgumentException(); 1050 for (int i = fromIndex; i < toIndex; i++) 1051 a[i] = val; 1052 } 1053 1054 /** 1055 * Fill an array with an int value. 1056 * 1057 * @param a the array to fill 1058 * @param val the value to fill it with 1059 */ 1060 public static void fill(int[] a, int val) 1061 { 1062 fill(a, 0, a.length, val); 1063 } 1064 1065 /** 1066 * Fill a range of an array with an int value. 1067 * 1068 * @param a the array to fill 1069 * @param fromIndex the index to fill from, inclusive 1070 * @param toIndex the index to fill to, exclusive 1071 * @param val the value to fill with 1072 * @throws IllegalArgumentException if fromIndex > toIndex 1073 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1074 * || toIndex > a.length 1075 */ 1076 public static void fill(int[] a, int fromIndex, int toIndex, int val) 1077 { 1078 if (fromIndex > toIndex) 1079 throw new IllegalArgumentException(); 1080 for (int i = fromIndex; i < toIndex; i++) 1081 a[i] = val; 1082 } 1083 1084 /** 1085 * Fill an array with a long value. 1086 * 1087 * @param a the array to fill 1088 * @param val the value to fill it with 1089 */ 1090 public static void fill(long[] a, long val) 1091 { 1092 fill(a, 0, a.length, val); 1093 } 1094 1095 /** 1096 * Fill a range of an array with a long value. 1097 * 1098 * @param a the array to fill 1099 * @param fromIndex the index to fill from, inclusive 1100 * @param toIndex the index to fill to, exclusive 1101 * @param val the value to fill with 1102 * @throws IllegalArgumentException if fromIndex > toIndex 1103 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1104 * || toIndex > a.length 1105 */ 1106 public static void fill(long[] a, int fromIndex, int toIndex, long val) 1107 { 1108 if (fromIndex > toIndex) 1109 throw new IllegalArgumentException(); 1110 for (int i = fromIndex; i < toIndex; i++) 1111 a[i] = val; 1112 } 1113 1114 /** 1115 * Fill an array with a float value. 1116 * 1117 * @param a the array to fill 1118 * @param val the value to fill it with 1119 */ 1120 public static void fill(float[] a, float val) 1121 { 1122 fill(a, 0, a.length, val); 1123 } 1124 1125 /** 1126 * Fill a range of an array with a float value. 1127 * 1128 * @param a the array to fill 1129 * @param fromIndex the index to fill from, inclusive 1130 * @param toIndex the index to fill to, exclusive 1131 * @param val the value to fill with 1132 * @throws IllegalArgumentException if fromIndex > toIndex 1133 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1134 * || toIndex > a.length 1135 */ 1136 public static void fill(float[] a, int fromIndex, int toIndex, float val) 1137 { 1138 if (fromIndex > toIndex) 1139 throw new IllegalArgumentException(); 1140 for (int i = fromIndex; i < toIndex; i++) 1141 a[i] = val; 1142 } 1143 1144 /** 1145 * Fill an array with a double value. 1146 * 1147 * @param a the array to fill 1148 * @param val the value to fill it with 1149 */ 1150 public static void fill(double[] a, double val) 1151 { 1152 fill(a, 0, a.length, val); 1153 } 1154 1155 /** 1156 * Fill a range of an array with a double value. 1157 * 1158 * @param a the array to fill 1159 * @param fromIndex the index to fill from, inclusive 1160 * @param toIndex the index to fill to, exclusive 1161 * @param val the value to fill with 1162 * @throws IllegalArgumentException if fromIndex > toIndex 1163 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1164 * || toIndex > a.length 1165 */ 1166 public static void fill(double[] a, int fromIndex, int toIndex, double val) 1167 { 1168 if (fromIndex > toIndex) 1169 throw new IllegalArgumentException(); 1170 for (int i = fromIndex; i < toIndex; i++) 1171 a[i] = val; 1172 } 1173 1174 /** 1175 * Fill an array with an Object value. 1176 * 1177 * @param a the array to fill 1178 * @param val the value to fill it with 1179 * @throws ClassCastException if val is not an instance of the element 1180 * type of a. 1181 */ 1182 public static void fill(Object[] a, Object val) 1183 { 1184 fill(a, 0, a.length, val); 1185 } 1186 1187 /** 1188 * Fill a range of an array with an Object value. 1189 * 1190 * @param a the array to fill 1191 * @param fromIndex the index to fill from, inclusive 1192 * @param toIndex the index to fill to, exclusive 1193 * @param val the value to fill with 1194 * @throws ClassCastException if val is not an instance of the element 1195 * type of a. 1196 * @throws IllegalArgumentException if fromIndex > toIndex 1197 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1198 * || toIndex > a.length 1199 */ 1200 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) 1201 { 1202 if (fromIndex > toIndex) 1203 throw new IllegalArgumentException(); 1204 for (int i = fromIndex; i < toIndex; i++) 1205 a[i] = val; 1206 } 1207 1208 1209 // sort 1210 // Thanks to Paul Fisher (rao@gnu.org) for finding this quicksort algorithm 1211 // as specified by Sun and porting it to Java. The algorithm is an optimised 1212 // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's 1213 // "Engineering a Sort Function", Software-Practice and Experience, Vol. 1214 // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n) 1215 // performance on many arrays that would take quadratic time with a standard 1216 // quicksort. 1217 1218 /** 1219 * Performs a stable sort on the elements, arranging them according to their 1220 * natural order. 1221 * 1222 * @param a the byte array to sort 1223 */ 1224 public static void sort(byte[] a) 1225 { 1226 qsort(a, 0, a.length); 1227 } 1228 1229 /** 1230 * Performs a stable sort on the elements, arranging them according to their 1231 * natural order. 1232 * 1233 * @param a the byte array to sort 1234 * @param fromIndex the first index to sort (inclusive) 1235 * @param toIndex the last index to sort (exclusive) 1236 * @throws IllegalArgumentException if fromIndex > toIndex 1237 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1238 * || toIndex > a.length 1239 */ 1240 public static void sort(byte[] a, int fromIndex, int toIndex) 1241 { 1242 if (fromIndex > toIndex) 1243 throw new IllegalArgumentException(); 1244 if (fromIndex < 0) 1245 throw new ArrayIndexOutOfBoundsException(); 1246 qsort(a, fromIndex, toIndex - fromIndex); 1247 } 1248 1249 /** 1250 * Finds the index of the median of three array elements. 1251 * 1252 * @param a the first index 1253 * @param b the second index 1254 * @param c the third index 1255 * @param d the array 1256 * @return the index (a, b, or c) which has the middle value of the three 1257 */ 1258 private static int med3(int a, int b, int c, byte[] d) 1259 { 1260 return (d[a] < d[b] 1261 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1262 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1263 } 1264 1265 /** 1266 * Swaps the elements at two locations of an array 1267 * 1268 * @param i the first index 1269 * @param j the second index 1270 * @param a the array 1271 */ 1272 private static void swap(int i, int j, byte[] a) 1273 { 1274 byte c = a[i]; 1275 a[i] = a[j]; 1276 a[j] = c; 1277 } 1278 1279 /** 1280 * Swaps two ranges of an array. 1281 * 1282 * @param i the first range start 1283 * @param j the second range start 1284 * @param n the element count 1285 * @param a the array 1286 */ 1287 private static void vecswap(int i, int j, int n, byte[] a) 1288 { 1289 for ( ; n > 0; i++, j++, n--) 1290 swap(i, j, a); 1291 } 1292 1293 /** 1294 * Performs a recursive modified quicksort. 1295 * 1296 * @param array the array to sort 1297 * @param from the start index (inclusive) 1298 * @param count the number of elements to sort 1299 */ 1300 private static void qsort(byte[] array, int from, int count) 1301 { 1302 // Use an insertion sort on small arrays. 1303 if (count <= 7) 1304 { 1305 for (int i = from + 1; i < from + count; i++) 1306 for (int j = i; j > from && array[j - 1] > array[j]; j--) 1307 swap(j, j - 1, array); 1308 return; 1309 } 1310 1311 // Determine a good median element. 1312 int mid = from + count / 2; 1313 int lo = from; 1314 int hi = from + count - 1; 1315 1316 if (count > 40) 1317 { // big arrays, pseudomedian of 9 1318 int s = count / 8; 1319 lo = med3(lo, lo + s, lo + 2 * s, array); 1320 mid = med3(mid - s, mid, mid + s, array); 1321 hi = med3(hi - 2 * s, hi - s, hi, array); 1322 } 1323 mid = med3(lo, mid, hi, array); 1324 1325 int a, b, c, d; 1326 int comp; 1327 1328 // Pull the median element out of the fray, and use it as a pivot. 1329 swap(from, mid, array); 1330 a = b = from; 1331 c = d = from + count - 1; 1332 1333 // Repeatedly move b and c to each other, swapping elements so 1334 // that all elements before index b are less than the pivot, and all 1335 // elements after index c are greater than the pivot. a and b track 1336 // the elements equal to the pivot. 1337 while (true) 1338 { 1339 while (b <= c && (comp = array[b] - array[from]) <= 0) 1340 { 1341 if (comp == 0) 1342 { 1343 swap(a, b, array); 1344 a++; 1345 } 1346 b++; 1347 } 1348 while (c >= b && (comp = array[c] - array[from]) >= 0) 1349 { 1350 if (comp == 0) 1351 { 1352 swap(c, d, array); 1353 d--; 1354 } 1355 c--; 1356 } 1357 if (b > c) 1358 break; 1359 swap(b, c, array); 1360 b++; 1361 c--; 1362 } 1363 1364 // Swap pivot(s) back in place, the recurse on left and right sections. 1365 hi = from + count; 1366 int span; 1367 span = Math.min(a - from, b - a); 1368 vecswap(from, b - span, span, array); 1369 1370 span = Math.min(d - c, hi - d - 1); 1371 vecswap(b, hi - span, span, array); 1372 1373 span = b - a; 1374 if (span > 1) 1375 qsort(array, from, span); 1376 1377 span = d - c; 1378 if (span > 1) 1379 qsort(array, hi - span, span); 1380 } 1381 1382 /** 1383 * Performs a stable sort on the elements, arranging them according to their 1384 * natural order. 1385 * 1386 * @param a the char array to sort 1387 */ 1388 public static void sort(char[] a) 1389 { 1390 qsort(a, 0, a.length); 1391 } 1392 1393 /** 1394 * Performs a stable sort on the elements, arranging them according to their 1395 * natural order. 1396 * 1397 * @param a the char array to sort 1398 * @param fromIndex the first index to sort (inclusive) 1399 * @param toIndex the last index to sort (exclusive) 1400 * @throws IllegalArgumentException if fromIndex > toIndex 1401 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1402 * || toIndex > a.length 1403 */ 1404 public static void sort(char[] a, int fromIndex, int toIndex) 1405 { 1406 if (fromIndex > toIndex) 1407 throw new IllegalArgumentException(); 1408 if (fromIndex < 0) 1409 throw new ArrayIndexOutOfBoundsException(); 1410 qsort(a, fromIndex, toIndex - fromIndex); 1411 } 1412 1413 /** 1414 * Finds the index of the median of three array elements. 1415 * 1416 * @param a the first index 1417 * @param b the second index 1418 * @param c the third index 1419 * @param d the array 1420 * @return the index (a, b, or c) which has the middle value of the three 1421 */ 1422 private static int med3(int a, int b, int c, char[] d) 1423 { 1424 return (d[a] < d[b] 1425 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1426 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1427 } 1428 1429 /** 1430 * Swaps the elements at two locations of an array 1431 * 1432 * @param i the first index 1433 * @param j the second index 1434 * @param a the array 1435 */ 1436 private static void swap(int i, int j, char[] a) 1437 { 1438 char c = a[i]; 1439 a[i] = a[j]; 1440 a[j] = c; 1441 } 1442 1443 /** 1444 * Swaps two ranges of an array. 1445 * 1446 * @param i the first range start 1447 * @param j the second range start 1448 * @param n the element count 1449 * @param a the array 1450 */ 1451 private static void vecswap(int i, int j, int n, char[] a) 1452 { 1453 for ( ; n > 0; i++, j++, n--) 1454 swap(i, j, a); 1455 } 1456 1457 /** 1458 * Performs a recursive modified quicksort. 1459 * 1460 * @param array the array to sort 1461 * @param from the start index (inclusive) 1462 * @param count the number of elements to sort 1463 */ 1464 private static void qsort(char[] array, int from, int count) 1465 { 1466 // Use an insertion sort on small arrays. 1467 if (count <= 7) 1468 { 1469 for (int i = from + 1; i < from + count; i++) 1470 for (int j = i; j > from && array[j - 1] > array[j]; j--) 1471 swap(j, j - 1, array); 1472 return; 1473 } 1474 1475 // Determine a good median element. 1476 int mid = from + count / 2; 1477 int lo = from; 1478 int hi = from + count - 1; 1479 1480 if (count > 40) 1481 { // big arrays, pseudomedian of 9 1482 int s = count / 8; 1483 lo = med3(lo, lo + s, lo + 2 * s, array); 1484 mid = med3(mid - s, mid, mid + s, array); 1485 hi = med3(hi - 2 * s, hi - s, hi, array); 1486 } 1487 mid = med3(lo, mid, hi, array); 1488 1489 int a, b, c, d; 1490 int comp; 1491 1492 // Pull the median element out of the fray, and use it as a pivot. 1493 swap(from, mid, array); 1494 a = b = from; 1495 c = d = from + count - 1; 1496 1497 // Repeatedly move b and c to each other, swapping elements so 1498 // that all elements before index b are less than the pivot, and all 1499 // elements after index c are greater than the pivot. a and b track 1500 // the elements equal to the pivot. 1501 while (true) 1502 { 1503 while (b <= c && (comp = array[b] - array[from]) <= 0) 1504 { 1505 if (comp == 0) 1506 { 1507 swap(a, b, array); 1508 a++; 1509 } 1510 b++; 1511 } 1512 while (c >= b && (comp = array[c] - array[from]) >= 0) 1513 { 1514 if (comp == 0) 1515 { 1516 swap(c, d, array); 1517 d--; 1518 } 1519 c--; 1520 } 1521 if (b > c) 1522 break; 1523 swap(b, c, array); 1524 b++; 1525 c--; 1526 } 1527 1528 // Swap pivot(s) back in place, the recurse on left and right sections. 1529 hi = from + count; 1530 int span; 1531 span = Math.min(a - from, b - a); 1532 vecswap(from, b - span, span, array); 1533 1534 span = Math.min(d - c, hi - d - 1); 1535 vecswap(b, hi - span, span, array); 1536 1537 span = b - a; 1538 if (span > 1) 1539 qsort(array, from, span); 1540 1541 span = d - c; 1542 if (span > 1) 1543 qsort(array, hi - span, span); 1544 } 1545 1546 /** 1547 * Performs a stable sort on the elements, arranging them according to their 1548 * natural order. 1549 * 1550 * @param a the short array to sort 1551 */ 1552 public static void sort(short[] a) 1553 { 1554 qsort(a, 0, a.length); 1555 } 1556 1557 /** 1558 * Performs a stable sort on the elements, arranging them according to their 1559 * natural order. 1560 * 1561 * @param a the short array to sort 1562 * @param fromIndex the first index to sort (inclusive) 1563 * @param toIndex the last index to sort (exclusive) 1564 * @throws IllegalArgumentException if fromIndex > toIndex 1565 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1566 * || toIndex > a.length 1567 */ 1568 public static void sort(short[] a, int fromIndex, int toIndex) 1569 { 1570 if (fromIndex > toIndex) 1571 throw new IllegalArgumentException(); 1572 if (fromIndex < 0) 1573 throw new ArrayIndexOutOfBoundsException(); 1574 qsort(a, fromIndex, toIndex - fromIndex); 1575 } 1576 1577 /** 1578 * Finds the index of the median of three array elements. 1579 * 1580 * @param a the first index 1581 * @param b the second index 1582 * @param c the third index 1583 * @param d the array 1584 * @return the index (a, b, or c) which has the middle value of the three 1585 */ 1586 private static int med3(int a, int b, int c, short[] d) 1587 { 1588 return (d[a] < d[b] 1589 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1590 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1591 } 1592 1593 /** 1594 * Swaps the elements at two locations of an array 1595 * 1596 * @param i the first index 1597 * @param j the second index 1598 * @param a the array 1599 */ 1600 private static void swap(int i, int j, short[] a) 1601 { 1602 short c = a[i]; 1603 a[i] = a[j]; 1604 a[j] = c; 1605 } 1606 1607 /** 1608 * Swaps two ranges of an array. 1609 * 1610 * @param i the first range start 1611 * @param j the second range start 1612 * @param n the element count 1613 * @param a the array 1614 */ 1615 private static void vecswap(int i, int j, int n, short[] a) 1616 { 1617 for ( ; n > 0; i++, j++, n--) 1618 swap(i, j, a); 1619 } 1620 1621 /** 1622 * Performs a recursive modified quicksort. 1623 * 1624 * @param array the array to sort 1625 * @param from the start index (inclusive) 1626 * @param count the number of elements to sort 1627 */ 1628 private static void qsort(short[] array, int from, int count) 1629 { 1630 // Use an insertion sort on small arrays. 1631 if (count <= 7) 1632 { 1633 for (int i = from + 1; i < from + count; i++) 1634 for (int j = i; j > from && array[j - 1] > array[j]; j--) 1635 swap(j, j - 1, array); 1636 return; 1637 } 1638 1639 // Determine a good median element. 1640 int mid = from + count / 2; 1641 int lo = from; 1642 int hi = from + count - 1; 1643 1644 if (count > 40) 1645 { // big arrays, pseudomedian of 9 1646 int s = count / 8; 1647 lo = med3(lo, lo + s, lo + 2 * s, array); 1648 mid = med3(mid - s, mid, mid + s, array); 1649 hi = med3(hi - 2 * s, hi - s, hi, array); 1650 } 1651 mid = med3(lo, mid, hi, array); 1652 1653 int a, b, c, d; 1654 int comp; 1655 1656 // Pull the median element out of the fray, and use it as a pivot. 1657 swap(from, mid, array); 1658 a = b = from; 1659 c = d = from + count - 1; 1660 1661 // Repeatedly move b and c to each other, swapping elements so 1662 // that all elements before index b are less than the pivot, and all 1663 // elements after index c are greater than the pivot. a and b track 1664 // the elements equal to the pivot. 1665 while (true) 1666 { 1667 while (b <= c && (comp = array[b] - array[from]) <= 0) 1668 { 1669 if (comp == 0) 1670 { 1671 swap(a, b, array); 1672 a++; 1673 } 1674 b++; 1675 } 1676 while (c >= b && (comp = array[c] - array[from]) >= 0) 1677 { 1678 if (comp == 0) 1679 { 1680 swap(c, d, array); 1681 d--; 1682 } 1683 c--; 1684 } 1685 if (b > c) 1686 break; 1687 swap(b, c, array); 1688 b++; 1689 c--; 1690 } 1691 1692 // Swap pivot(s) back in place, the recurse on left and right sections. 1693 hi = from + count; 1694 int span; 1695 span = Math.min(a - from, b - a); 1696 vecswap(from, b - span, span, array); 1697 1698 span = Math.min(d - c, hi - d - 1); 1699 vecswap(b, hi - span, span, array); 1700 1701 span = b - a; 1702 if (span > 1) 1703 qsort(array, from, span); 1704 1705 span = d - c; 1706 if (span > 1) 1707 qsort(array, hi - span, span); 1708 } 1709 1710 /** 1711 * Performs a stable sort on the elements, arranging them according to their 1712 * natural order. 1713 * 1714 * @param a the int array to sort 1715 */ 1716 public static void sort(int[] a) 1717 { 1718 qsort(a, 0, a.length); 1719 } 1720 1721 /** 1722 * Performs a stable sort on the elements, arranging them according to their 1723 * natural order. 1724 * 1725 * @param a the int array to sort 1726 * @param fromIndex the first index to sort (inclusive) 1727 * @param toIndex the last index to sort (exclusive) 1728 * @throws IllegalArgumentException if fromIndex > toIndex 1729 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1730 * || toIndex > a.length 1731 */ 1732 public static void sort(int[] a, int fromIndex, int toIndex) 1733 { 1734 if (fromIndex > toIndex) 1735 throw new IllegalArgumentException(); 1736 if (fromIndex < 0) 1737 throw new ArrayIndexOutOfBoundsException(); 1738 qsort(a, fromIndex, toIndex - fromIndex); 1739 } 1740 1741 /** 1742 * Finds the index of the median of three array elements. 1743 * 1744 * @param a the first index 1745 * @param b the second index 1746 * @param c the third index 1747 * @param d the array 1748 * @return the index (a, b, or c) which has the middle value of the three 1749 */ 1750 private static int med3(int a, int b, int c, int[] d) 1751 { 1752 return (d[a] < d[b] 1753 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1754 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1755 } 1756 1757 /** 1758 * Swaps the elements at two locations of an array 1759 * 1760 * @param i the first index 1761 * @param j the second index 1762 * @param a the array 1763 */ 1764 private static void swap(int i, int j, int[] a) 1765 { 1766 int c = a[i]; 1767 a[i] = a[j]; 1768 a[j] = c; 1769 } 1770 1771 /** 1772 * Swaps two ranges of an array. 1773 * 1774 * @param i the first range start 1775 * @param j the second range start 1776 * @param n the element count 1777 * @param a the array 1778 */ 1779 private static void vecswap(int i, int j, int n, int[] a) 1780 { 1781 for ( ; n > 0; i++, j++, n--) 1782 swap(i, j, a); 1783 } 1784 1785 /** 1786 * Compares two integers in natural order, since a - b is inadequate. 1787 * 1788 * @param a the first int 1789 * @param b the second int 1790 * @return < 0, 0, or > 0 accorting to the comparison 1791 */ 1792 private static int compare(int a, int b) 1793 { 1794 return a < b ? -1 : a == b ? 0 : 1; 1795 } 1796 1797 /** 1798 * Performs a recursive modified quicksort. 1799 * 1800 * @param array the array to sort 1801 * @param from the start index (inclusive) 1802 * @param count the number of elements to sort 1803 */ 1804 private static void qsort(int[] array, int from, int count) 1805 { 1806 // Use an insertion sort on small arrays. 1807 if (count <= 7) 1808 { 1809 for (int i = from + 1; i < from + count; i++) 1810 for (int j = i; j > from && array[j - 1] > array[j]; j--) 1811 swap(j, j - 1, array); 1812 return; 1813 } 1814 1815 // Determine a good median element. 1816 int mid = from + count / 2; 1817 int lo = from; 1818 int hi = from + count - 1; 1819 1820 if (count > 40) 1821 { // big arrays, pseudomedian of 9 1822 int s = count / 8; 1823 lo = med3(lo, lo + s, lo + 2 * s, array); 1824 mid = med3(mid - s, mid, mid + s, array); 1825 hi = med3(hi - 2 * s, hi - s, hi, array); 1826 } 1827 mid = med3(lo, mid, hi, array); 1828 1829 int a, b, c, d; 1830 int comp; 1831 1832 // Pull the median element out of the fray, and use it as a pivot. 1833 swap(from, mid, array); 1834 a = b = from; 1835 c = d = from + count - 1; 1836 1837 // Repeatedly move b and c to each other, swapping elements so 1838 // that all elements before index b are less than the pivot, and all 1839 // elements after index c are greater than the pivot. a and b track 1840 // the elements equal to the pivot. 1841 while (true) 1842 { 1843 while (b <= c && (comp = compare(array[b], array[from])) <= 0) 1844 { 1845 if (comp == 0) 1846 { 1847 swap(a, b, array); 1848 a++; 1849 } 1850 b++; 1851 } 1852 while (c >= b && (comp = compare(array[c], array[from])) >= 0) 1853 { 1854 if (comp == 0) 1855 { 1856 swap(c, d, array); 1857 d--; 1858 } 1859 c--; 1860 } 1861 if (b > c) 1862 break; 1863 swap(b, c, array); 1864 b++; 1865 c--; 1866 } 1867 1868 // Swap pivot(s) back in place, the recurse on left and right sections. 1869 hi = from + count; 1870 int span; 1871 span = Math.min(a - from, b - a); 1872 vecswap(from, b - span, span, array); 1873 1874 span = Math.min(d - c, hi - d - 1); 1875 vecswap(b, hi - span, span, array); 1876 1877 span = b - a; 1878 if (span > 1) 1879 qsort(array, from, span); 1880 1881 span = d - c; 1882 if (span > 1) 1883 qsort(array, hi - span, span); 1884 } 1885 1886 /** 1887 * Performs a stable sort on the elements, arranging them according to their 1888 * natural order. 1889 * 1890 * @param a the long array to sort 1891 */ 1892 public static void sort(long[] a) 1893 { 1894 qsort(a, 0, a.length); 1895 } 1896 1897 /** 1898 * Performs a stable sort on the elements, arranging them according to their 1899 * natural order. 1900 * 1901 * @param a the long array to sort 1902 * @param fromIndex the first index to sort (inclusive) 1903 * @param toIndex the last index to sort (exclusive) 1904 * @throws IllegalArgumentException if fromIndex > toIndex 1905 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1906 * || toIndex > a.length 1907 */ 1908 public static void sort(long[] a, int fromIndex, int toIndex) 1909 { 1910 if (fromIndex > toIndex) 1911 throw new IllegalArgumentException(); 1912 if (fromIndex < 0) 1913 throw new ArrayIndexOutOfBoundsException(); 1914 qsort(a, fromIndex, toIndex - fromIndex); 1915 } 1916 1917 /** 1918 * Finds the index of the median of three array elements. 1919 * 1920 * @param a the first index 1921 * @param b the second index 1922 * @param c the third index 1923 * @param d the array 1924 * @return the index (a, b, or c) which has the middle value of the three 1925 */ 1926 private static int med3(int a, int b, int c, long[] d) 1927 { 1928 return (d[a] < d[b] 1929 ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1930 : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1931 } 1932 1933 /** 1934 * Swaps the elements at two locations of an array 1935 * 1936 * @param i the first index 1937 * @param j the second index 1938 * @param a the array 1939 */ 1940 private static void swap(int i, int j, long[] a) 1941 { 1942 long c = a[i]; 1943 a[i] = a[j]; 1944 a[j] = c; 1945 } 1946 1947 /** 1948 * Swaps two ranges of an array. 1949 * 1950 * @param i the first range start 1951 * @param j the second range start 1952 * @param n the element count 1953 * @param a the array 1954 */ 1955 private static void vecswap(int i, int j, int n, long[] a) 1956 { 1957 for ( ; n > 0; i++, j++, n--) 1958 swap(i, j, a); 1959 } 1960 1961 /** 1962 * Compares two longs in natural order, since a - b is inadequate. 1963 * 1964 * @param a the first long 1965 * @param b the second long 1966 * @return < 0, 0, or > 0 accorting to the comparison 1967 */ 1968 private static int compare(long a, long b) 1969 { 1970 return a < b ? -1 : a == b ? 0 : 1; 1971 } 1972 1973 /** 1974 * Performs a recursive modified quicksort. 1975 * 1976 * @param array the array to sort 1977 * @param from the start index (inclusive) 1978 * @param count the number of elements to sort 1979 */ 1980 private static void qsort(long[] array, int from, int count) 1981 { 1982 // Use an insertion sort on small arrays. 1983 if (count <= 7) 1984 { 1985 for (int i = from + 1; i < from + count; i++) 1986 for (int j = i; j > from && array[j - 1] > array[j]; j--) 1987 swap(j, j - 1, array); 1988 return; 1989 } 1990 1991 // Determine a good median element. 1992 int mid = from + count / 2; 1993 int lo = from; 1994 int hi = from + count - 1; 1995 1996 if (count > 40) 1997 { // big arrays, pseudomedian of 9 1998 int s = count / 8; 1999 lo = med3(lo, lo + s, lo + 2 * s, array); 2000 mid = med3(mid - s, mid, mid + s, array); 2001 hi = med3(hi - 2 * s, hi - s, hi, array); 2002 } 2003 mid = med3(lo, mid, hi, array); 2004 2005 int a, b, c, d; 2006 int comp; 2007 2008 // Pull the median element out of the fray, and use it as a pivot. 2009 swap(from, mid, array); 2010 a = b = from; 2011 c = d = from + count - 1; 2012 2013 // Repeatedly move b and c to each other, swapping elements so 2014 // that all elements before index b are less than the pivot, and all 2015 // elements after index c are greater than the pivot. a and b track 2016 // the elements equal to the pivot. 2017 while (true) 2018 { 2019 while (b <= c && (comp = compare(array[b], array[from])) <= 0) 2020 { 2021 if (comp == 0) 2022 { 2023 swap(a, b, array); 2024 a++; 2025 } 2026 b++; 2027 } 2028 while (c >= b && (comp = compare(array[c], array[from])) >= 0) 2029 { 2030 if (comp == 0) 2031 { 2032 swap(c, d, array); 2033 d--; 2034 } 2035 c--; 2036 } 2037 if (b > c) 2038 break; 2039 swap(b, c, array); 2040 b++; 2041 c--; 2042 } 2043 2044 // Swap pivot(s) back in place, the recurse on left and right sections. 2045 hi = from + count; 2046 int span; 2047 span = Math.min(a - from, b - a); 2048 vecswap(from, b - span, span, array); 2049 2050 span = Math.min(d - c, hi - d - 1); 2051 vecswap(b, hi - span, span, array); 2052 2053 span = b - a; 2054 if (span > 1) 2055 qsort(array, from, span); 2056 2057 span = d - c; 2058 if (span > 1) 2059 qsort(array, hi - span, span); 2060 } 2061 2062 /** 2063 * Performs a stable sort on the elements, arranging them according to their 2064 * natural order. 2065 * 2066 * @param a the float array to sort 2067 */ 2068 public static void sort(float[] a) 2069 { 2070 qsort(a, 0, a.length); 2071 } 2072 2073 /** 2074 * Performs a stable sort on the elements, arranging them according to their 2075 * natural order. 2076 * 2077 * @param a the float array to sort 2078 * @param fromIndex the first index to sort (inclusive) 2079 * @param toIndex the last index to sort (exclusive) 2080 * @throws IllegalArgumentException if fromIndex > toIndex 2081 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 2082 * || toIndex > a.length 2083 */ 2084 public static void sort(float[] a, int fromIndex, int toIndex) 2085 { 2086 if (fromIndex > toIndex) 2087 throw new IllegalArgumentException(); 2088 if (fromIndex < 0) 2089 throw new ArrayIndexOutOfBoundsException(); 2090 qsort(a, fromIndex, toIndex - fromIndex); 2091 } 2092 2093 /** 2094 * Finds the index of the median of three array elements. 2095 * 2096 * @param a the first index 2097 * @param b the second index 2098 * @param c the third index 2099 * @param d the array 2100 * @return the index (a, b, or c) which has the middle value of the three 2101 */ 2102 private static int med3(int a, int b, int c, float[] d) 2103 { 2104 return (Float.compare(d[a], d[b]) < 0 2105 ? (Float.compare(d[b], d[c]) < 0 ? b 2106 : Float.compare(d[a], d[c]) < 0 ? c : a) 2107 : (Float.compare(d[b], d[c]) > 0 ? b 2108 : Float.compare(d[a], d[c]) > 0 ? c : a)); 2109 } 2110 2111 /** 2112 * Swaps the elements at two locations of an array 2113 * 2114 * @param i the first index 2115 * @param j the second index 2116 * @param a the array 2117 */ 2118 private static void swap(int i, int j, float[] a) 2119 { 2120 float c = a[i]; 2121 a[i] = a[j]; 2122 a[j] = c; 2123 } 2124 2125 /** 2126 * Swaps two ranges of an array. 2127 * 2128 * @param i the first range start 2129 * @param j the second range start 2130 * @param n the element count 2131 * @param a the array 2132 */ 2133 private static void vecswap(int i, int j, int n, float[] a) 2134 { 2135 for ( ; n > 0; i++, j++, n--) 2136 swap(i, j, a); 2137 } 2138 2139 /** 2140 * Performs a recursive modified quicksort. 2141 * 2142 * @param array the array to sort 2143 * @param from the start index (inclusive) 2144 * @param count the number of elements to sort 2145 */ 2146 private static void qsort(float[] array, int from, int count) 2147 { 2148 // Use an insertion sort on small arrays. 2149 if (count <= 7) 2150 { 2151 for (int i = from + 1; i < from + count; i++) 2152 for (int j = i; 2153 j > from && Float.compare(array[j - 1], array[j]) > 0; 2154 j--) 2155 { 2156 swap(j, j - 1, array); 2157 } 2158 return; 2159 } 2160 2161 // Determine a good median element. 2162 int mid = from + count / 2; 2163 int lo = from; 2164 int hi = from + count - 1; 2165 2166 if (count > 40) 2167 { // big arrays, pseudomedian of 9 2168 int s = count / 8; 2169 lo = med3(lo, lo + s, lo + 2 * s, array); 2170 mid = med3(mid - s, mid, mid + s, array); 2171 hi = med3(hi - 2 * s, hi - s, hi, array); 2172 } 2173 mid = med3(lo, mid, hi, array); 2174 2175 int a, b, c, d; 2176 int comp; 2177 2178 // Pull the median element out of the fray, and use it as a pivot. 2179 swap(from, mid, array); 2180 a = b = from; 2181 c = d = from + count - 1; 2182 2183 // Repeatedly move b and c to each other, swapping elements so 2184 // that all elements before index b are less than the pivot, and all 2185 // elements after index c are greater than the pivot. a and b track 2186 // the elements equal to the pivot. 2187 while (true) 2188 { 2189 while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0) 2190 { 2191 if (comp == 0) 2192 { 2193 swap(a, b, array); 2194 a++; 2195 } 2196 b++; 2197 } 2198 while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0) 2199 { 2200 if (comp == 0) 2201 { 2202 swap(c, d, array); 2203 d--; 2204 } 2205 c--; 2206 } 2207 if (b > c) 2208 break; 2209 swap(b, c, array); 2210 b++; 2211 c--; 2212 } 2213 2214 // Swap pivot(s) back in place, the recurse on left and right sections. 2215 hi = from + count; 2216 int span; 2217 span = Math.min(a - from, b - a); 2218 vecswap(from, b - span, span, array); 2219 2220 span = Math.min(d - c, hi - d - 1); 2221 vecswap(b, hi - span, span, array); 2222 2223 span = b - a; 2224 if (span > 1) 2225 qsort(array, from, span); 2226 2227 span = d - c; 2228 if (span > 1) 2229 qsort(array, hi - span, span); 2230 } 2231 2232 /** 2233 * Performs a stable sort on the elements, arranging them according to their 2234 * natural order. 2235 * 2236 * @param a the double array to sort 2237 */ 2238 public static void sort(double[] a) 2239 { 2240 qsort(a, 0, a.length); 2241 } 2242 2243 /** 2244 * Performs a stable sort on the elements, arranging them according to their 2245 * natural order. 2246 * 2247 * @param a the double array to sort 2248 * @param fromIndex the first index to sort (inclusive) 2249 * @param toIndex the last index to sort (exclusive) 2250 * @throws IllegalArgumentException if fromIndex > toIndex 2251 * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 2252 * || toIndex > a.length 2253 */ 2254 public static void sort(double[] a, int fromIndex, int toIndex) 2255 { 2256 if (fromIndex > toIndex) 2257 throw new IllegalArgumentException(); 2258 if (fromIndex < 0) 2259 throw new ArrayIndexOutOfBoundsException(); 2260 qsort(a, fromIndex, toIndex - fromIndex); 2261 } 2262 2263 /** 2264 * Finds the index of the median of three array elements. 2265 * 2266 * @param a the first index 2267 * @param b the second index 2268 * @param c the third index 2269 * @param d the array 2270 * @return the index (a, b, or c) which has the middle value of the three 2271 */ 2272 private static int med3(int a, int b, int c, double[] d) 2273 { 2274 return (Double.compare(d[a], d[b]) < 0 2275 ? (Double.compare(d[b], d[c]) < 0 ? b 2276 : Double.compare(d[a], d[c]) < 0 ? c : a) 2277 : (Double.compare(d[b], d[c]) > 0 ? b 2278 : Double.compare(d[a], d[c]) > 0 ? c : a)); 2279 } 2280 2281 /** 2282 * Swaps the elements at two locations of an array 2283 * 2284 * @param i the first index 2285 * @param j the second index 2286 * @param a the array 2287 */ 2288 private static void swap(int i, int j, double[] a) 2289 { 2290 double c = a[i]; 2291 a[i] = a[j]; 2292 a[j] = c; 2293 } 2294 2295 /** 2296 * Swaps two ranges of an array. 2297 * 2298 * @param i the first range start 2299 * @param j the second range start 2300 * @param n the element count 2301 * @param a the array 2302 */ 2303 private static void vecswap(int i, int j, int n, double[] a) 2304 { 2305 for ( ; n > 0; i++, j++, n--) 2306 swap(i, j, a); 2307 } 2308 2309 /** 2310 * Performs a recursive modified quicksort. 2311 * 2312 * @param array the array to sort 2313 * @param from the start index (inclusive) 2314 * @param count the number of elements to sort 2315 */ 2316 private static void qsort(double[] array, int from, int count) 2317 { 2318 // Use an insertion sort on small arrays. 2319 if (count <= 7) 2320 { 2321 for (int i = from + 1; i < from + count; i++) 2322 for (int j = i; 2323 j > from && Double.compare(array[j - 1], array[j]) > 0; 2324 j--) 2325 { 2326 swap(j, j - 1, array); 2327 } 2328 return; 2329 } 2330 2331 // Determine a good median element. 2332 int mid = from + count / 2; 2333 int lo = from; 2334 int hi = from + count - 1; 2335 2336 if (count > 40) 2337 { // big arrays, pseudomedian of 9 2338 int s = count / 8; 2339 lo = med3(lo, lo + s, lo + 2 * s, array); 2340 mid = med3(mid - s, mid, mid + s, array); 2341 hi = med3(hi - 2 * s, hi - s, hi, array); 2342 } 2343 mid = med3(lo, mid, hi, array); 2344 2345 int a, b, c, d; 2346 int comp; 2347 2348 // Pull the median element out of the fray, and use it as a pivot. 2349 swap(from, mid, array); 2350 a = b = from; 2351 c = d = from + count - 1; 2352 2353 // Repeatedly move b and c to each other, swapping elements so 2354 // that all elements before index b are less than the pivot, and all 2355 // elements after index c are greater than the pivot. a and b track 2356 // the elements equal to the pivot. 2357 while (true) 2358 { 2359 while (b <= c && (comp = Double.compare(array[b], array[from])) <= 0) 2360 { 2361 if (comp == 0) 2362 { 2363 swap(a, b, array); 2364 a++; 2365 } 2366 b++; 2367 } 2368 while (c >= b && (comp = Double.compare(array[c], array[from])) >= 0) 2369 { 2370 if (comp == 0) 2371 { 2372 swap(c, d, array); 2373 d--; 2374 } 2375 c--; 2376 } 2377 if (b > c) 2378 break; 2379 swap(b, c, array); 2380 b++; 2381 c--; 2382 } 2383 2384 // Swap pivot(s) back in place, the recurse on left and right sections. 2385 hi = from + count; 2386 int span; 2387 span = Math.min(a - from, b - a); 2388 vecswap(from, b - span, span, array); 2389 2390 span = Math.min(d - c, hi - d - 1); 2391 vecswap(b, hi - span, span, array); 2392 2393 span = b - a; 2394 if (span > 1) 2395 qsort(array, from, span); 2396 2397 span = d - c; 2398 if (span > 1) 2399 qsort(array, hi - span, span); 2400 } 2401 2402 /** 2403 * Sort an array of Objects according to their natural ordering. The sort is 2404 * guaranteed to be stable, that is, equal elements will not be reordered. 2405 * The sort algorithm is a mergesort with the merge omitted if the last 2406 * element of one half comes before the first element of the other half. This 2407 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2408 * copy of the array. 2409 * 2410 * @param a the array to be sorted 2411 * @throws ClassCastException if any two elements are not mutually 2412 * comparable 2413 * @throws NullPointerException if an element is null (since 2414 * null.compareTo cannot work) 2415 * @see Comparable 2416 */ 2417 public static void sort(Object[] a) 2418 { 2419 sort(a, 0, a.length, null); 2420 } 2421 2422 /** 2423 * Sort an array of Objects according to a Comparator. The sort is 2424 * guaranteed to be stable, that is, equal elements will not be reordered. 2425 * The sort algorithm is a mergesort with the merge omitted if the last 2426 * element of one half comes before the first element of the other half. This 2427 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2428 * copy of the array. 2429 * 2430 * @param a the array to be sorted 2431 * @param c a Comparator to use in sorting the array; or null to indicate 2432 * the elements' natural order 2433 * @throws ClassCastException if any two elements are not mutually 2434 * comparable by the Comparator provided 2435 * @throws NullPointerException if a null element is compared with natural 2436 * ordering (only possible when c is null) 2437 */ 2438 public static <T> void sort(T[] a, Comparator<? super T> c) 2439 { 2440 sort(a, 0, a.length, c); 2441 } 2442 2443 /** 2444 * Sort an array of Objects according to their natural ordering. The sort is 2445 * guaranteed to be stable, that is, equal elements will not be reordered. 2446 * The sort algorithm is a mergesort with the merge omitted if the last 2447 * element of one half comes before the first element of the other half. This 2448 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2449 * copy of the array. 2450 * 2451 * @param a the array to be sorted 2452 * @param fromIndex the index of the first element to be sorted 2453 * @param toIndex the index of the last element to be sorted plus one 2454 * @throws ClassCastException if any two elements are not mutually 2455 * comparable 2456 * @throws NullPointerException if an element is null (since 2457 * null.compareTo cannot work) 2458 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex 2459 * are not in range. 2460 * @throws IllegalArgumentException if fromIndex > toIndex 2461 */ 2462 public static void sort(Object[] a, int fromIndex, int toIndex) 2463 { 2464 sort(a, fromIndex, toIndex, null); 2465 } 2466 2467 /** 2468 * Sort an array of Objects according to a Comparator. The sort is 2469 * guaranteed to be stable, that is, equal elements will not be reordered. 2470 * The sort algorithm is a mergesort with the merge omitted if the last 2471 * element of one half comes before the first element of the other half. This 2472 * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2473 * copy of the array. 2474 * 2475 * @param a the array to be sorted 2476 * @param fromIndex the index of the first element to be sorted 2477 * @param toIndex the index of the last element to be sorted plus one 2478 * @param c a Comparator to use in sorting the array; or null to indicate 2479 * the elements' natural order 2480 * @throws ClassCastException if any two elements are not mutually 2481 * comparable by the Comparator provided 2482 * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex 2483 * are not in range. 2484 * @throws IllegalArgumentException if fromIndex > toIndex 2485 * @throws NullPointerException if a null element is compared with natural 2486 * ordering (only possible when c is null) 2487 */ 2488 public static <T> void sort(T[] a, int fromIndex, int toIndex, 2489 Comparator<? super T> c) 2490 { 2491 if (fromIndex > toIndex) 2492 throw new IllegalArgumentException("fromIndex " + fromIndex 2493 + " > toIndex " + toIndex); 2494 if (fromIndex < 0) 2495 throw new ArrayIndexOutOfBoundsException(); 2496 2497 // In general, the code attempts to be simple rather than fast, the 2498 // idea being that a good optimising JIT will be able to optimise it 2499 // better than I can, and if I try it will make it more confusing for 2500 // the JIT. First presort the array in chunks of length 6 with insertion 2501 // sort. A mergesort would give too much overhead for this length. 2502 for (int chunk = fromIndex; chunk < toIndex; chunk += 6) 2503 { 2504 int end = Math.min(chunk + 6, toIndex); 2505 for (int i = chunk + 1; i < end; i++) 2506 { 2507 if (Collections.compare(a[i - 1], a[i], c) > 0) 2508 { 2509 // not already sorted 2510 int j = i; 2511 T elem = a[j]; 2512 do 2513 { 2514 a[j] = a[j - 1]; 2515 j--; 2516 } 2517 while (j > chunk 2518 && Collections.compare(a[j - 1], elem, c) > 0); 2519 a[j] = elem; 2520 } 2521 } 2522 } 2523 2524 int len = toIndex - fromIndex; 2525 // If length is smaller or equal 6 we are done. 2526 if (len <= 6) 2527 return; 2528 2529 T[] src = a; 2530 T[] dest = (T[]) new Object[len]; 2531 T[] t = null; // t is used for swapping src and dest 2532 2533 // The difference of the fromIndex of the src and dest array. 2534 int srcDestDiff = -fromIndex; 2535 2536 // The merges are done in this loop 2537 for (int size = 6; size < len; size <<= 1) 2538 { 2539 for (int start = fromIndex; start < toIndex; start += size << 1) 2540 { 2541 // mid is the start of the second sublist; 2542 // end the start of the next sublist (or end of array). 2543 int mid = start + size; 2544 int end = Math.min(toIndex, mid + size); 2545 2546 // The second list is empty or the elements are already in 2547 // order - no need to merge 2548 if (mid >= end 2549 || Collections.compare(src[mid - 1], src[mid], c) <= 0) 2550 { 2551 System.arraycopy(src, start, 2552 dest, start + srcDestDiff, end - start); 2553 2554 // The two halves just need swapping - no need to merge 2555 } 2556 else if (Collections.compare(src[start], src[end - 1], c) > 0) 2557 { 2558 System.arraycopy(src, start, 2559 dest, end - size + srcDestDiff, size); 2560 System.arraycopy(src, mid, 2561 dest, start + srcDestDiff, end - mid); 2562 2563 } 2564 else 2565 { 2566 // Declare a lot of variables to save repeating 2567 // calculations. Hopefully a decent JIT will put these 2568 // in registers and make this fast 2569 int p1 = start; 2570 int p2 = mid; 2571 int i = start + srcDestDiff; 2572 2573 // The main merge loop; terminates as soon as either 2574 // half is ended 2575 while (p1 < mid && p2 < end) 2576 { 2577 dest[i++] = 2578 src[(Collections.compare(src[p1], src[p2], c) <= 0 2579 ? p1++ : p2++)]; 2580 } 2581 2582 // Finish up by copying the remainder of whichever half 2583 // wasn't finished. 2584 if (p1 < mid) 2585 System.arraycopy(src, p1, dest, i, mid - p1); 2586 else 2587 System.arraycopy(src, p2, dest, i, end - p2); 2588 } 2589 } 2590 // swap src and dest ready for the next merge 2591 t = src; 2592 src = dest; 2593 dest = t; 2594 fromIndex += srcDestDiff; 2595 toIndex += srcDestDiff; 2596 srcDestDiff = -srcDestDiff; 2597 } 2598 2599 // make sure the result ends up back in the right place. Note 2600 // that src and dest may have been swapped above, so src 2601 // contains the sorted array. 2602 if (src != a) 2603 { 2604 // Note that fromIndex == 0. 2605 System.arraycopy(src, 0, a, srcDestDiff, toIndex); 2606 } 2607 } 2608 2609 /** 2610 * Returns a list "view" of the specified array. This method is intended to 2611 * make it easy to use the Collections API with existing array-based APIs and 2612 * programs. Changes in the list or the array show up in both places. The 2613 * list does not support element addition or removal, but does permit 2614 * value modification. The returned list implements both Serializable and 2615 * RandomAccess. 2616 * 2617 * @param a the array to return a view of (<code>null</code> not permitted) 2618 * @return a fixed-size list, changes to which "write through" to the array 2619 * 2620 * @throws NullPointerException if <code>a</code> is <code>null</code>. 2621 * @see Serializable 2622 * @see RandomAccess 2623 * @see Arrays.ArrayList 2624 */ 2625 public static <T> List<T> asList(final T... a) 2626 { 2627 return new Arrays.ArrayList(a); 2628 } 2629 2630 /** 2631 * Returns the hashcode of an array of long numbers. If two arrays 2632 * are equal, according to <code>equals()</code>, they should have the 2633 * same hashcode. The hashcode returned by the method is equal to that 2634 * obtained by the corresponding <code>List</code> object. This has the same 2635 * data, but represents longs in their wrapper class, <code>Long</code>. 2636 * For <code>null</code>, 0 is returned. 2637 * 2638 * @param v an array of long numbers for which the hash code should be 2639 * computed. 2640 * @return the hash code of the array, or 0 if null was given. 2641 * @since 1.5 2642 */ 2643 public static int hashCode(long[] v) 2644 { 2645 if (v == null) 2646 return 0; 2647 int result = 1; 2648 for (int i = 0; i < v.length; ++i) 2649 { 2650 int elt = (int) (v[i] ^ (v[i] >>> 32)); 2651 result = 31 * result + elt; 2652 } 2653 return result; 2654 } 2655 2656 /** 2657 * Returns the hashcode of an array of integer numbers. If two arrays 2658 * are equal, according to <code>equals()</code>, they should have the 2659 * same hashcode. The hashcode returned by the method is equal to that 2660 * obtained by the corresponding <code>List</code> object. This has the same 2661 * data, but represents ints in their wrapper class, <code>Integer</code>. 2662 * For <code>null</code>, 0 is returned. 2663 * 2664 * @param v an array of integer numbers for which the hash code should be 2665 * computed. 2666 * @return the hash code of the array, or 0 if null was given. 2667 * @since 1.5 2668 */ 2669 public static int hashCode(int[] v) 2670 { 2671 if (v == null) 2672 return 0; 2673 int result = 1; 2674 for (int i = 0; i < v.length; ++i) 2675 result = 31 * result + v[i]; 2676 return result; 2677 } 2678 2679 /** 2680 * Returns the hashcode of an array of short numbers. If two arrays 2681 * are equal, according to <code>equals()</code>, they should have the 2682 * same hashcode. The hashcode returned by the method is equal to that 2683 * obtained by the corresponding <code>List</code> object. This has the same 2684 * data, but represents shorts in their wrapper class, <code>Short</code>. 2685 * For <code>null</code>, 0 is returned. 2686 * 2687 * @param v an array of short numbers for which the hash code should be 2688 * computed. 2689 * @return the hash code of the array, or 0 if null was given. 2690 * @since 1.5 2691 */ 2692 public static int hashCode(short[] v) 2693 { 2694 if (v == null) 2695 return 0; 2696 int result = 1; 2697 for (int i = 0; i < v.length; ++i) 2698 result = 31 * result + v[i]; 2699 return result; 2700 } 2701 2702 /** 2703 * Returns the hashcode of an array of characters. If two arrays 2704 * are equal, according to <code>equals()</code>, they should have the 2705 * same hashcode. The hashcode returned by the method is equal to that 2706 * obtained by the corresponding <code>List</code> object. This has the same 2707 * data, but represents chars in their wrapper class, <code>Character</code>. 2708 * For <code>null</code>, 0 is returned. 2709 * 2710 * @param v an array of characters for which the hash code should be 2711 * computed. 2712 * @return the hash code of the array, or 0 if null was given. 2713 * @since 1.5 2714 */ 2715 public static int hashCode(char[] v) 2716 { 2717 if (v == null) 2718 return 0; 2719 int result = 1; 2720 for (int i = 0; i < v.length; ++i) 2721 result = 31 * result + v[i]; 2722 return result; 2723 } 2724 2725 /** 2726 * Returns the hashcode of an array of bytes. If two arrays 2727 * are equal, according to <code>equals()</code>, they should have the 2728 * same hashcode. The hashcode returned by the method is equal to that 2729 * obtained by the corresponding <code>List</code> object. This has the same 2730 * data, but represents bytes in their wrapper class, <code>Byte</code>. 2731 * For <code>null</code>, 0 is returned. 2732 * 2733 * @param v an array of bytes for which the hash code should be 2734 * computed. 2735 * @return the hash code of the array, or 0 if null was given. 2736 * @since 1.5 2737 */ 2738 public static int hashCode(byte[] v) 2739 { 2740 if (v == null) 2741 return 0; 2742 int result = 1; 2743 for (int i = 0; i < v.length; ++i) 2744 result = 31 * result + v[i]; 2745 return result; 2746 } 2747 2748 /** 2749 * Returns the hashcode of an array of booleans. If two arrays 2750 * are equal, according to <code>equals()</code>, they should have the 2751 * same hashcode. The hashcode returned by the method is equal to that 2752 * obtained by the corresponding <code>List</code> object. This has the same 2753 * data, but represents booleans in their wrapper class, 2754 * <code>Boolean</code>. For <code>null</code>, 0 is returned. 2755 * 2756 * @param v an array of booleans for which the hash code should be 2757 * computed. 2758 * @return the hash code of the array, or 0 if null was given. 2759 * @since 1.5 2760 */ 2761 public static int hashCode(boolean[] v) 2762 { 2763 if (v == null) 2764 return 0; 2765 int result = 1; 2766 for (int i = 0; i < v.length; ++i) 2767 result = 31 * result + (v[i] ? 1231 : 1237); 2768 return result; 2769 } 2770 2771 /** 2772 * Returns the hashcode of an array of floats. If two arrays 2773 * are equal, according to <code>equals()</code>, they should have the 2774 * same hashcode. The hashcode returned by the method is equal to that 2775 * obtained by the corresponding <code>List</code> object. This has the same 2776 * data, but represents floats in their wrapper class, <code>Float</code>. 2777 * For <code>null</code>, 0 is returned. 2778 * 2779 * @param v an array of floats for which the hash code should be 2780 * computed. 2781 * @return the hash code of the array, or 0 if null was given. 2782 * @since 1.5 2783 */ 2784 public static int hashCode(float[] v) 2785 { 2786 if (v == null) 2787 return 0; 2788 int result = 1; 2789 for (int i = 0; i < v.length; ++i) 2790 result = 31 * result + Float.floatToIntBits(v[i]); 2791 return result; 2792 } 2793 2794 /** 2795 * Returns the hashcode of an array of doubles. If two arrays 2796 * are equal, according to <code>equals()</code>, they should have the 2797 * same hashcode. The hashcode returned by the method is equal to that 2798 * obtained by the corresponding <code>List</code> object. This has the same 2799 * data, but represents doubles in their wrapper class, <code>Double</code>. 2800 * For <code>null</code>, 0 is returned. 2801 * 2802 * @param v an array of doubles for which the hash code should be 2803 * computed. 2804 * @return the hash code of the array, or 0 if null was given. 2805 * @since 1.5 2806 */ 2807 public static int hashCode(double[] v) 2808 { 2809 if (v == null) 2810 return 0; 2811 int result = 1; 2812 for (int i = 0; i < v.length; ++i) 2813 { 2814 long l = Double.doubleToLongBits(v[i]); 2815 int elt = (int) (l ^ (l >>> 32)); 2816 result = 31 * result + elt; 2817 } 2818 return result; 2819 } 2820 2821 /** 2822 * Returns the hashcode of an array of objects. If two arrays 2823 * are equal, according to <code>equals()</code>, they should have the 2824 * same hashcode. The hashcode returned by the method is equal to that 2825 * obtained by the corresponding <code>List</code> object. 2826 * For <code>null</code>, 0 is returned. 2827 * 2828 * @param v an array of integer numbers for which the hash code should be 2829 * computed. 2830 * @return the hash code of the array, or 0 if null was given. 2831 * @since 1.5 2832 */ 2833 public static int hashCode(Object[] v) 2834 { 2835 if (v == null) 2836 return 0; 2837 int result = 1; 2838 for (int i = 0; i < v.length; ++i) 2839 { 2840 int elt = v[i] == null ? 0 : v[i].hashCode(); 2841 result = 31 * result + elt; 2842 } 2843 return result; 2844 } 2845 2846 public static int deepHashCode(Object[] v) 2847 { 2848 if (v == null) 2849 return 0; 2850 int result = 1; 2851 for (int i = 0; i < v.length; ++i) 2852 { 2853 int elt; 2854 if (v[i] == null) 2855 elt = 0; 2856 else if (v[i] instanceof boolean[]) 2857 elt = hashCode((boolean[]) v[i]); 2858 else if (v[i] instanceof byte[]) 2859 elt = hashCode((byte[]) v[i]); 2860 else if (v[i] instanceof char[]) 2861 elt = hashCode((char[]) v[i]); 2862 else if (v[i] instanceof short[]) 2863 elt = hashCode((short[]) v[i]); 2864 else if (v[i] instanceof int[]) 2865 elt = hashCode((int[]) v[i]); 2866 else if (v[i] instanceof long[]) 2867 elt = hashCode((long[]) v[i]); 2868 else if (v[i] instanceof float[]) 2869 elt = hashCode((float[]) v[i]); 2870 else if (v[i] instanceof double[]) 2871 elt = hashCode((double[]) v[i]); 2872 else if (v[i] instanceof Object[]) 2873 elt = hashCode((Object[]) v[i]); 2874 else 2875 elt = v[i].hashCode(); 2876 result = 31 * result + elt; 2877 } 2878 return result; 2879 } 2880 2881 /** @since 1.5 */ 2882 public static boolean deepEquals(Object[] v1, Object[] v2) 2883 { 2884 if (v1 == null) 2885 return v2 == null; 2886 if (v2 == null || v1.length != v2.length) 2887 return false; 2888 2889 for (int i = 0; i < v1.length; ++i) 2890 { 2891 Object e1 = v1[i]; 2892 Object e2 = v2[i]; 2893 2894 if (e1 == e2) 2895 continue; 2896 if (e1 == null || e2 == null) 2897 return false; 2898 2899 boolean check; 2900 if (e1 instanceof boolean[] && e2 instanceof boolean[]) 2901 check = equals((boolean[]) e1, (boolean[]) e2); 2902 else if (e1 instanceof byte[] && e2 instanceof byte[]) 2903 check = equals((byte[]) e1, (byte[]) e2); 2904 else if (e1 instanceof char[] && e2 instanceof char[]) 2905 check = equals((char[]) e1, (char[]) e2); 2906 else if (e1 instanceof short[] && e2 instanceof short[]) 2907 check = equals((short[]) e1, (short[]) e2); 2908 else if (e1 instanceof int[] && e2 instanceof int[]) 2909 check = equals((int[]) e1, (int[]) e2); 2910 else if (e1 instanceof long[] && e2 instanceof long[]) 2911 check = equals((long[]) e1, (long[]) e2); 2912 else if (e1 instanceof float[] && e2 instanceof float[]) 2913 check = equals((float[]) e1, (float[]) e2); 2914 else if (e1 instanceof double[] && e2 instanceof double[]) 2915 check = equals((double[]) e1, (double[]) e2); 2916 else if (e1 instanceof Object[] && e2 instanceof Object[]) 2917 check = equals((Object[]) e1, (Object[]) e2); 2918 else 2919 check = e1.equals(e2); 2920 if (! check) 2921 return false; 2922 } 2923 2924 return true; 2925 } 2926 2927 /** 2928 * Returns a String representation of the argument array. Returns "null" 2929 * if <code>a</code> is null. 2930 * @param v the array to represent 2931 * @return a String representing this array 2932 * @since 1.5 2933 */ 2934 public static String toString(boolean[] v) 2935 { 2936 if (v == null) 2937 return "null"; 2938 StringBuilder b = new StringBuilder("["); 2939 for (int i = 0; i < v.length; ++i) 2940 { 2941 if (i > 0) 2942 b.append(", "); 2943 b.append(v[i]); 2944 } 2945 b.append("]"); 2946 return b.toString(); 2947 } 2948 2949 /** 2950 * Returns a String representation of the argument array. Returns "null" 2951 * if <code>a</code> is null. 2952 * @param v the array to represent 2953 * @return a String representing this array 2954 * @since 1.5 2955 */ 2956 public static String toString(byte[] v) 2957 { 2958 if (v == null) 2959 return "null"; 2960 StringBuilder b = new StringBuilder("["); 2961 for (int i = 0; i < v.length; ++i) 2962 { 2963 if (i > 0) 2964 b.append(", "); 2965 b.append(v[i]); 2966 } 2967 b.append("]"); 2968 return b.toString(); 2969 } 2970 2971 /** 2972 * Returns a String representation of the argument array. Returns "null" 2973 * if <code>a</code> is null. 2974 * @param v the array to represent 2975 * @return a String representing this array 2976 * @since 1.5 2977 */ 2978 public static String toString(char[] v) 2979 { 2980 if (v == null) 2981 return "null"; 2982 StringBuilder b = new StringBuilder("["); 2983 for (int i = 0; i < v.length; ++i) 2984 { 2985 if (i > 0) 2986 b.append(", "); 2987 b.append(v[i]); 2988 } 2989 b.append("]"); 2990 return b.toString(); 2991 } 2992 2993 /** 2994 * Returns a String representation of the argument array. Returns "null" 2995 * if <code>a</code> is null. 2996 * @param v the array to represent 2997 * @return a String representing this array 2998 * @since 1.5 2999 */ 3000 public static String toString(short[] v) 3001 { 3002 if (v == null) 3003 return "null"; 3004 StringBuilder b = new StringBuilder("["); 3005 for (int i = 0; i < v.length; ++i) 3006 { 3007 if (i > 0) 3008 b.append(", "); 3009 b.append(v[i]); 3010 } 3011 b.append("]"); 3012 return b.toString(); 3013 } 3014 3015 /** 3016 * Returns a String representation of the argument array. Returns "null" 3017 * if <code>a</code> is null. 3018 * @param v the array to represent 3019 * @return a String representing this array 3020 * @since 1.5 3021 */ 3022 public static String toString(int[] v) 3023 { 3024 if (v == null) 3025 return "null"; 3026 StringBuilder b = new StringBuilder("["); 3027 for (int i = 0; i < v.length; ++i) 3028 { 3029 if (i > 0) 3030 b.append(", "); 3031 b.append(v[i]); 3032 } 3033 b.append("]"); 3034 return b.toString(); 3035 } 3036 3037 /** 3038 * Returns a String representation of the argument array. Returns "null" 3039 * if <code>a</code> is null. 3040 * @param v the array to represent 3041 * @return a String representing this array 3042 * @since 1.5 3043 */ 3044 public static String toString(long[] v) 3045 { 3046 if (v == null) 3047 return "null"; 3048 StringBuilder b = new StringBuilder("["); 3049 for (int i = 0; i < v.length; ++i) 3050 { 3051 if (i > 0) 3052 b.append(", "); 3053 b.append(v[i]); 3054 } 3055 b.append("]"); 3056 return b.toString(); 3057 } 3058 3059 /** 3060 * Returns a String representation of the argument array. Returns "null" 3061 * if <code>a</code> is null. 3062 * @param v the array to represent 3063 * @return a String representing this array 3064 * @since 1.5 3065 */ 3066 public static String toString(float[] v) 3067 { 3068 if (v == null) 3069 return "null"; 3070 StringBuilder b = new StringBuilder("["); 3071 for (int i = 0; i < v.length; ++i) 3072 { 3073 if (i > 0) 3074 b.append(", "); 3075 b.append(v[i]); 3076 } 3077 b.append("]"); 3078 return b.toString(); 3079 } 3080 3081 /** 3082 * Returns a String representation of the argument array. Returns "null" 3083 * if <code>a</code> is null. 3084 * @param v the array to represent 3085 * @return a String representing this array 3086 * @since 1.5 3087 */ 3088 public static String toString(double[] v) 3089 { 3090 if (v == null) 3091 return "null"; 3092 StringBuilder b = new StringBuilder("["); 3093 for (int i = 0; i < v.length; ++i) 3094 { 3095 if (i > 0) 3096 b.append(", "); 3097 b.append(v[i]); 3098 } 3099 b.append("]"); 3100 return b.toString(); 3101 } 3102 3103 /** 3104 * Returns a String representation of the argument array. Returns "null" 3105 * if <code>a</code> is null. 3106 * @param v the array to represent 3107 * @return a String representing this array 3108 * @since 1.5 3109 */ 3110 public static String toString(Object[] v) 3111 { 3112 if (v == null) 3113 return "null"; 3114 StringBuilder b = new StringBuilder("["); 3115 for (int i = 0; i < v.length; ++i) 3116 { 3117 if (i > 0) 3118 b.append(", "); 3119 b.append(v[i]); 3120 } 3121 b.append("]"); 3122 return b.toString(); 3123 } 3124 3125 private static void deepToString(Object[] v, StringBuilder b, HashSet seen) 3126 { 3127 b.append("["); 3128 for (int i = 0; i < v.length; ++i) 3129 { 3130 if (i > 0) 3131 b.append(", "); 3132 Object elt = v[i]; 3133 if (elt == null) 3134 b.append("null"); 3135 else if (elt instanceof boolean[]) 3136 b.append(toString((boolean[]) elt)); 3137 else if (elt instanceof byte[]) 3138 b.append(toString((byte[]) elt)); 3139 else if (elt instanceof char[]) 3140 b.append(toString((char[]) elt)); 3141 else if (elt instanceof short[]) 3142 b.append(toString((short[]) elt)); 3143 else if (elt instanceof int[]) 3144 b.append(toString((int[]) elt)); 3145 else if (elt instanceof long[]) 3146 b.append(toString((long[]) elt)); 3147 else if (elt instanceof float[]) 3148 b.append(toString((float[]) elt)); 3149 else if (elt instanceof double[]) 3150 b.append(toString((double[]) elt)); 3151 else if (elt instanceof Object[]) 3152 { 3153 Object[] os = (Object[]) elt; 3154 if (seen.contains(os)) 3155 b.append("[...]"); 3156 else 3157 { 3158 seen.add(os); 3159 deepToString(os, b, seen); 3160 } 3161 } 3162 else 3163 b.append(elt); 3164 } 3165 b.append("]"); 3166 } 3167 3168 /** @since 1.5 */ 3169 public static String deepToString(Object[] v) 3170 { 3171 if (v == null) 3172 return "null"; 3173 HashSet seen = new HashSet(); 3174 StringBuilder b = new StringBuilder(); 3175 deepToString(v, b, seen); 3176 return b.toString(); 3177 } 3178 3179 /** 3180 * Inner class used by {@link #asList(Object[])} to provide a list interface 3181 * to an array. The name, though it clashes with java.util.ArrayList, is 3182 * Sun's choice for Serialization purposes. Element addition and removal 3183 * is prohibited, but values can be modified. 3184 * 3185 * @author Eric Blake (ebb9@email.byu.edu) 3186 * @status updated to 1.4 3187 */ 3188 private static final class ArrayList<E> extends AbstractList<E> 3189 implements Serializable, RandomAccess 3190 { 3191 // We override the necessary methods, plus others which will be much 3192 // more efficient with direct iteration rather than relying on iterator(). 3193 3194 /** 3195 * Compatible with JDK 1.4. 3196 */ 3197 private static final long serialVersionUID = -2764017481108945198L; 3198 3199 /** 3200 * The array we are viewing. 3201 * @serial the array 3202 */ 3203 private final E[] a; 3204 3205 /** 3206 * Construct a list view of the array. 3207 * @param a the array to view 3208 * @throws NullPointerException if a is null 3209 */ 3210 ArrayList(E[] a) 3211 { 3212 // We have to explicitly check. 3213 if (a == null) 3214 throw new NullPointerException(); 3215 this.a = a; 3216 } 3217 3218 /** 3219 * Returns the object at the specified index in 3220 * the array. 3221 * 3222 * @param index The index to retrieve an object from. 3223 * @return The object at the array index specified. 3224 */ 3225 public E get(int index) 3226 { 3227 return a[index]; 3228 } 3229 3230 /** 3231 * Returns the size of the array. 3232 * 3233 * @return The size. 3234 */ 3235 public int size() 3236 { 3237 return a.length; 3238 } 3239 3240 /** 3241 * Replaces the object at the specified index 3242 * with the supplied element. 3243 * 3244 * @param index The index at which to place the new object. 3245 * @param element The new object. 3246 * @return The object replaced by this operation. 3247 */ 3248 public E set(int index, E element) 3249 { 3250 E old = a[index]; 3251 a[index] = element; 3252 return old; 3253 } 3254 3255 /** 3256 * Returns true if the array contains the 3257 * supplied object. 3258 * 3259 * @param o The object to look for. 3260 * @return True if the object was found. 3261 */ 3262 public boolean contains(Object o) 3263 { 3264 return lastIndexOf(o) >= 0; 3265 } 3266 3267 /** 3268 * Returns the first index at which the 3269 * object, o, occurs in the array. 3270 * 3271 * @param o The object to search for. 3272 * @return The first relevant index. 3273 */ 3274 public int indexOf(Object o) 3275 { 3276 int size = a.length; 3277 for (int i = 0; i < size; i++) 3278 if (ArrayList.equals(o, a[i])) 3279 return i; 3280 return -1; 3281 } 3282 3283 /** 3284 * Returns the last index at which the 3285 * object, o, occurs in the array. 3286 * 3287 * @param o The object to search for. 3288 * @return The last relevant index. 3289 */ 3290 public int lastIndexOf(Object o) 3291 { 3292 int i = a.length; 3293 while (--i >= 0) 3294 if (ArrayList.equals(o, a[i])) 3295 return i; 3296 return -1; 3297 } 3298 3299 /** 3300 * Transforms the list into an array of 3301 * objects, by simplying cloning the array 3302 * wrapped by this list. 3303 * 3304 * @return A clone of the internal array. 3305 */ 3306 public Object[] toArray() 3307 { 3308 return (Object[]) a.clone(); 3309 } 3310 3311 /** 3312 * Copies the objects from this list into 3313 * the supplied array. The supplied array 3314 * is shrunk or enlarged to the size of the 3315 * internal array, and filled with its objects. 3316 * 3317 * @param array The array to fill with the objects in this list. 3318 * @return The array containing the objects in this list, 3319 * which may or may not be == to array. 3320 */ 3321 public <T> T[] toArray(T[] array) 3322 { 3323 int size = a.length; 3324 if (array.length < size) 3325 array = (T[]) Array.newInstance(array.getClass().getComponentType(), 3326 size); 3327 else if (array.length > size) 3328 array[size] = null; 3329 3330 System.arraycopy(a, 0, array, 0, size); 3331 return array; 3332 } 3333 } 3334 3335 /** 3336 * Returns a copy of the supplied array, truncating or padding as 3337 * necessary with <code>false</code> to obtain the specified length. 3338 * Indices that are valid for both arrays will return the same value. 3339 * Indices that only exist in the returned array (due to the new length 3340 * being greater than the original length) will return <code>false</code>. 3341 * This is equivalent to calling 3342 * <code>copyOfRange(original, 0, newLength)</code>. 3343 * 3344 * @param original the original array to be copied. 3345 * @param newLength the length of the returned array. 3346 * @return a copy of the original array, truncated or padded with 3347 * <code>false</code> to obtain the required length. 3348 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3349 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3350 * @since 1.6 3351 * @see #copyOfRange(boolean[],int,int) 3352 */ 3353 public static boolean[] copyOf(boolean[] original, int newLength) 3354 { 3355 if (newLength < 0) 3356 throw new NegativeArraySizeException("The array size is negative."); 3357 return copyOfRange(original, 0, newLength); 3358 } 3359 3360 /** 3361 * Copies the specified range of the supplied array to a new 3362 * array, padding as necessary with <code>false</code> 3363 * if <code>to</code> is greater than the length of the original 3364 * array. <code>from</code> must be in the range zero to 3365 * <code>original.length</code> and can not be greater than 3366 * <code>to</code>. The initial element of the 3367 * returned array will be equal to <code>original[from]</code>, 3368 * except where <code>from</code> is equal to <code>to</code> 3369 * (where a zero-length array will be returned) or <code> 3370 * <code>from</code> is equal to <code>original.length</code> 3371 * (where an array padded with <code>false</code> will be 3372 * returned). The returned array is always of length 3373 * <code>to - from</code>. 3374 * 3375 * @param original the array from which to copy. 3376 * @param from the initial index of the range, inclusive. 3377 * @param to the final index of the range, exclusive. 3378 * @return a copy of the specified range, with padding to 3379 * obtain the required length. 3380 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3381 * or <code>from > original.length</code> 3382 * @throws IllegalArgumentException if <code>from > to</code> 3383 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3384 * @since 1.6 3385 * @see #copyOf(boolean[],int) 3386 */ 3387 public static boolean[] copyOfRange(boolean[] original, int from, int to) 3388 { 3389 if (from > to) 3390 throw new IllegalArgumentException("The initial index is after " + 3391 "the final index."); 3392 boolean[] newArray = new boolean[to - from]; 3393 if (to > original.length) 3394 { 3395 System.arraycopy(original, from, newArray, 0, 3396 original.length - from); 3397 fill(newArray, original.length, newArray.length, false); 3398 } 3399 else 3400 System.arraycopy(original, from, newArray, 0, to - from); 3401 return newArray; 3402 } 3403 3404 /** 3405 * Returns a copy of the supplied array, truncating or padding as 3406 * necessary with <code>(byte)0</code> to obtain the specified length. 3407 * Indices that are valid for both arrays will return the same value. 3408 * Indices that only exist in the returned array (due to the new length 3409 * being greater than the original length) will return <code>(byte)0</code>. 3410 * This is equivalent to calling 3411 * <code>copyOfRange(original, 0, newLength)</code>. 3412 * 3413 * @param original the original array to be copied. 3414 * @param newLength the length of the returned array. 3415 * @return a copy of the original array, truncated or padded with 3416 * <code>(byte)0</code> to obtain the required length. 3417 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3418 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3419 * @since 1.6 3420 * @see #copyOfRange(byte[],int,int) 3421 */ 3422 public static byte[] copyOf(byte[] original, int newLength) 3423 { 3424 if (newLength < 0) 3425 throw new NegativeArraySizeException("The array size is negative."); 3426 return copyOfRange(original, 0, newLength); 3427 } 3428 3429 /** 3430 * Copies the specified range of the supplied array to a new 3431 * array, padding as necessary with <code>(byte)0</code> 3432 * if <code>to</code> is greater than the length of the original 3433 * array. <code>from</code> must be in the range zero to 3434 * <code>original.length</code> and can not be greater than 3435 * <code>to</code>. The initial element of the 3436 * returned array will be equal to <code>original[from]</code>, 3437 * except where <code>from</code> is equal to <code>to</code> 3438 * (where a zero-length array will be returned) or <code> 3439 * <code>from</code> is equal to <code>original.length</code> 3440 * (where an array padded with <code>(byte)0</code> will be 3441 * returned). The returned array is always of length 3442 * <code>to - from</code>. 3443 * 3444 * @param original the array from which to copy. 3445 * @param from the initial index of the range, inclusive. 3446 * @param to the final index of the range, exclusive. 3447 * @return a copy of the specified range, with padding to 3448 * obtain the required length. 3449 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3450 * or <code>from > original.length</code> 3451 * @throws IllegalArgumentException if <code>from > to</code> 3452 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3453 * @since 1.6 3454 * @see #copyOf(byte[],int) 3455 */ 3456 public static byte[] copyOfRange(byte[] original, int from, int to) 3457 { 3458 if (from > to) 3459 throw new IllegalArgumentException("The initial index is after " + 3460 "the final index."); 3461 byte[] newArray = new byte[to - from]; 3462 if (to > original.length) 3463 { 3464 System.arraycopy(original, from, newArray, 0, 3465 original.length - from); 3466 fill(newArray, original.length, newArray.length, (byte)0); 3467 } 3468 else 3469 System.arraycopy(original, from, newArray, 0, to - from); 3470 return newArray; 3471 } 3472 3473 /** 3474 * Returns a copy of the supplied array, truncating or padding as 3475 * necessary with <code>'\0'</code> to obtain the specified length. 3476 * Indices that are valid for both arrays will return the same value. 3477 * Indices that only exist in the returned array (due to the new length 3478 * being greater than the original length) will return <code>'\0'</code>. 3479 * This is equivalent to calling 3480 * <code>copyOfRange(original, 0, newLength)</code>. 3481 * 3482 * @param original the original array to be copied. 3483 * @param newLength the length of the returned array. 3484 * @return a copy of the original array, truncated or padded with 3485 * <code>'\0'</code> to obtain the required length. 3486 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3487 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3488 * @since 1.6 3489 * @see #copyOfRange(char[],int,int) 3490 */ 3491 public static char[] copyOf(char[] original, int newLength) 3492 { 3493 if (newLength < 0) 3494 throw new NegativeArraySizeException("The array size is negative."); 3495 return copyOfRange(original, 0, newLength); 3496 } 3497 3498 /** 3499 * Copies the specified range of the supplied array to a new 3500 * array, padding as necessary with <code>'\0'</code> 3501 * if <code>to</code> is greater than the length of the original 3502 * array. <code>from</code> must be in the range zero to 3503 * <code>original.length</code> and can not be greater than 3504 * <code>to</code>. The initial element of the 3505 * returned array will be equal to <code>original[from]</code>, 3506 * except where <code>from</code> is equal to <code>to</code> 3507 * (where a zero-length array will be returned) or <code> 3508 * <code>from</code> is equal to <code>original.length</code> 3509 * (where an array padded with <code>'\0'</code> will be 3510 * returned). The returned array is always of length 3511 * <code>to - from</code>. 3512 * 3513 * @param original the array from which to copy. 3514 * @param from the initial index of the range, inclusive. 3515 * @param to the final index of the range, exclusive. 3516 * @return a copy of the specified range, with padding to 3517 * obtain the required length. 3518 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3519 * or <code>from > original.length</code> 3520 * @throws IllegalArgumentException if <code>from > to</code> 3521 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3522 * @since 1.6 3523 * @see #copyOf(char[],int) 3524 */ 3525 public static char[] copyOfRange(char[] original, int from, int to) 3526 { 3527 if (from > to) 3528 throw new IllegalArgumentException("The initial index is after " + 3529 "the final index."); 3530 char[] newArray = new char[to - from]; 3531 if (to > original.length) 3532 { 3533 System.arraycopy(original, from, newArray, 0, 3534 original.length - from); 3535 fill(newArray, original.length, newArray.length, '\0'); 3536 } 3537 else 3538 System.arraycopy(original, from, newArray, 0, to - from); 3539 return newArray; 3540 } 3541 3542 /** 3543 * Returns a copy of the supplied array, truncating or padding as 3544 * necessary with <code>0d</code> to obtain the specified length. 3545 * Indices that are valid for both arrays will return the same value. 3546 * Indices that only exist in the returned array (due to the new length 3547 * being greater than the original length) will return <code>0d</code>. 3548 * This is equivalent to calling 3549 * <code>copyOfRange(original, 0, newLength)</code>. 3550 * 3551 * @param original the original array to be copied. 3552 * @param newLength the length of the returned array. 3553 * @return a copy of the original array, truncated or padded with 3554 * <code>0d</code> to obtain the required length. 3555 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3556 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3557 * @since 1.6 3558 * @see #copyOfRange(double[],int,int) 3559 */ 3560 public static double[] copyOf(double[] original, int newLength) 3561 { 3562 if (newLength < 0) 3563 throw new NegativeArraySizeException("The array size is negative."); 3564 return copyOfRange(original, 0, newLength); 3565 } 3566 3567 /** 3568 * Copies the specified range of the supplied array to a new 3569 * array, padding as necessary with <code>0d</code> 3570 * if <code>to</code> is greater than the length of the original 3571 * array. <code>from</code> must be in the range zero to 3572 * <code>original.length</code> and can not be greater than 3573 * <code>to</code>. The initial element of the 3574 * returned array will be equal to <code>original[from]</code>, 3575 * except where <code>from</code> is equal to <code>to</code> 3576 * (where a zero-length array will be returned) or <code> 3577 * <code>from</code> is equal to <code>original.length</code> 3578 * (where an array padded with <code>0d</code> will be 3579 * returned). The returned array is always of length 3580 * <code>to - from</code>. 3581 * 3582 * @param original the array from which to copy. 3583 * @param from the initial index of the range, inclusive. 3584 * @param to the final index of the range, exclusive. 3585 * @return a copy of the specified range, with padding to 3586 * obtain the required length. 3587 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3588 * or <code>from > original.length</code> 3589 * @throws IllegalArgumentException if <code>from > to</code> 3590 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3591 * @since 1.6 3592 * @see #copyOf(double[],int) 3593 */ 3594 public static double[] copyOfRange(double[] original, int from, int to) 3595 { 3596 if (from > to) 3597 throw new IllegalArgumentException("The initial index is after " + 3598 "the final index."); 3599 double[] newArray = new double[to - from]; 3600 if (to > original.length) 3601 { 3602 System.arraycopy(original, from, newArray, 0, 3603 original.length - from); 3604 fill(newArray, original.length, newArray.length, 0d); 3605 } 3606 else 3607 System.arraycopy(original, from, newArray, 0, to - from); 3608 return newArray; 3609 } 3610 3611 /** 3612 * Returns a copy of the supplied array, truncating or padding as 3613 * necessary with <code>0f</code> to obtain the specified length. 3614 * Indices that are valid for both arrays will return the same value. 3615 * Indices that only exist in the returned array (due to the new length 3616 * being greater than the original length) will return <code>0f</code>. 3617 * This is equivalent to calling 3618 * <code>copyOfRange(original, 0, newLength)</code>. 3619 * 3620 * @param original the original array to be copied. 3621 * @param newLength the length of the returned array. 3622 * @return a copy of the original array, truncated or padded with 3623 * <code>0f</code> to obtain the required length. 3624 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3625 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3626 * @since 1.6 3627 * @see #copyOfRange(float[],int,int) 3628 */ 3629 public static float[] copyOf(float[] original, int newLength) 3630 { 3631 if (newLength < 0) 3632 throw new NegativeArraySizeException("The array size is negative."); 3633 return copyOfRange(original, 0, newLength); 3634 } 3635 3636 /** 3637 * Copies the specified range of the supplied array to a new 3638 * array, padding as necessary with <code>0f</code> 3639 * if <code>to</code> is greater than the length of the original 3640 * array. <code>from</code> must be in the range zero to 3641 * <code>original.length</code> and can not be greater than 3642 * <code>to</code>. The initial element of the 3643 * returned array will be equal to <code>original[from]</code>, 3644 * except where <code>from</code> is equal to <code>to</code> 3645 * (where a zero-length array will be returned) or <code> 3646 * <code>from</code> is equal to <code>original.length</code> 3647 * (where an array padded with <code>0f</code> will be 3648 * returned). The returned array is always of length 3649 * <code>to - from</code>. 3650 * 3651 * @param original the array from which to copy. 3652 * @param from the initial index of the range, inclusive. 3653 * @param to the final index of the range, exclusive. 3654 * @return a copy of the specified range, with padding to 3655 * obtain the required length. 3656 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3657 * or <code>from > original.length</code> 3658 * @throws IllegalArgumentException if <code>from > to</code> 3659 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3660 * @since 1.6 3661 * @see #copyOf(float[],int) 3662 */ 3663 public static float[] copyOfRange(float[] original, int from, int to) 3664 { 3665 if (from > to) 3666 throw new IllegalArgumentException("The initial index is after " + 3667 "the final index."); 3668 float[] newArray = new float[to - from]; 3669 if (to > original.length) 3670 { 3671 System.arraycopy(original, from, newArray, 0, 3672 original.length - from); 3673 fill(newArray, original.length, newArray.length, 0f); 3674 } 3675 else 3676 System.arraycopy(original, from, newArray, 0, to - from); 3677 return newArray; 3678 } 3679 3680 /** 3681 * Returns a copy of the supplied array, truncating or padding as 3682 * necessary with <code>0</code> to obtain the specified length. 3683 * Indices that are valid for both arrays will return the same value. 3684 * Indices that only exist in the returned array (due to the new length 3685 * being greater than the original length) will return <code>0</code>. 3686 * This is equivalent to calling 3687 * <code>copyOfRange(original, 0, newLength)</code>. 3688 * 3689 * @param original the original array to be copied. 3690 * @param newLength the length of the returned array. 3691 * @return a copy of the original array, truncated or padded with 3692 * <code>0</code> to obtain the required length. 3693 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3694 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3695 * @since 1.6 3696 * @see #copyOfRange(int[],int,int) 3697 */ 3698 public static int[] copyOf(int[] original, int newLength) 3699 { 3700 if (newLength < 0) 3701 throw new NegativeArraySizeException("The array size is negative."); 3702 return copyOfRange(original, 0, newLength); 3703 } 3704 3705 /** 3706 * Copies the specified range of the supplied array to a new 3707 * array, padding as necessary with <code>0</code> 3708 * if <code>to</code> is greater than the length of the original 3709 * array. <code>from</code> must be in the range zero to 3710 * <code>original.length</code> and can not be greater than 3711 * <code>to</code>. The initial element of the 3712 * returned array will be equal to <code>original[from]</code>, 3713 * except where <code>from</code> is equal to <code>to</code> 3714 * (where a zero-length array will be returned) or <code> 3715 * <code>from</code> is equal to <code>original.length</code> 3716 * (where an array padded with <code>0</code> will be 3717 * returned). The returned array is always of length 3718 * <code>to - from</code>. 3719 * 3720 * @param original the array from which to copy. 3721 * @param from the initial index of the range, inclusive. 3722 * @param to the final index of the range, exclusive. 3723 * @return a copy of the specified range, with padding to 3724 * obtain the required length. 3725 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3726 * or <code>from > original.length</code> 3727 * @throws IllegalArgumentException if <code>from > to</code> 3728 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3729 * @since 1.6 3730 * @see #copyOf(int[],int) 3731 */ 3732 public static int[] copyOfRange(int[] original, int from, int to) 3733 { 3734 if (from > to) 3735 throw new IllegalArgumentException("The initial index is after " + 3736 "the final index."); 3737 int[] newArray = new int[to - from]; 3738 if (to > original.length) 3739 { 3740 System.arraycopy(original, from, newArray, 0, 3741 original.length - from); 3742 fill(newArray, original.length, newArray.length, 0); 3743 } 3744 else 3745 System.arraycopy(original, from, newArray, 0, to - from); 3746 return newArray; 3747 } 3748 3749 /** 3750 * Returns a copy of the supplied array, truncating or padding as 3751 * necessary with <code>0L</code> to obtain the specified length. 3752 * Indices that are valid for both arrays will return the same value. 3753 * Indices that only exist in the returned array (due to the new length 3754 * being greater than the original length) will return <code>0L</code>. 3755 * This is equivalent to calling 3756 * <code>copyOfRange(original, 0, newLength)</code>. 3757 * 3758 * @param original the original array to be copied. 3759 * @param newLength the length of the returned array. 3760 * @return a copy of the original array, truncated or padded with 3761 * <code>0L</code> to obtain the required length. 3762 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3763 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3764 * @since 1.6 3765 * @see #copyOfRange(long[],int,int) 3766 */ 3767 public static long[] copyOf(long[] original, int newLength) 3768 { 3769 if (newLength < 0) 3770 throw new NegativeArraySizeException("The array size is negative."); 3771 return copyOfRange(original, 0, newLength); 3772 } 3773 3774 /** 3775 * Copies the specified range of the supplied array to a new 3776 * array, padding as necessary with <code>0L</code> 3777 * if <code>to</code> is greater than the length of the original 3778 * array. <code>from</code> must be in the range zero to 3779 * <code>original.length</code> and can not be greater than 3780 * <code>to</code>. The initial element of the 3781 * returned array will be equal to <code>original[from]</code>, 3782 * except where <code>from</code> is equal to <code>to</code> 3783 * (where a zero-length array will be returned) or <code> 3784 * <code>from</code> is equal to <code>original.length</code> 3785 * (where an array padded with <code>0L</code> will be 3786 * returned). The returned array is always of length 3787 * <code>to - from</code>. 3788 * 3789 * @param original the array from which to copy. 3790 * @param from the initial index of the range, inclusive. 3791 * @param to the final index of the range, exclusive. 3792 * @return a copy of the specified range, with padding to 3793 * obtain the required length. 3794 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3795 * or <code>from > original.length</code> 3796 * @throws IllegalArgumentException if <code>from > to</code> 3797 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3798 * @since 1.6 3799 * @see #copyOf(long[],int) 3800 */ 3801 public static long[] copyOfRange(long[] original, int from, int to) 3802 { 3803 if (from > to) 3804 throw new IllegalArgumentException("The initial index is after " + 3805 "the final index."); 3806 long[] newArray = new long[to - from]; 3807 if (to > original.length) 3808 { 3809 System.arraycopy(original, from, newArray, 0, 3810 original.length - from); 3811 fill(newArray, original.length, newArray.length, 0L); 3812 } 3813 else 3814 System.arraycopy(original, from, newArray, 0, to - from); 3815 return newArray; 3816 } 3817 3818 /** 3819 * Returns a copy of the supplied array, truncating or padding as 3820 * necessary with <code>(short)0</code> to obtain the specified length. 3821 * Indices that are valid for both arrays will return the same value. 3822 * Indices that only exist in the returned array (due to the new length 3823 * being greater than the original length) will return <code>(short)0</code>. 3824 * This is equivalent to calling 3825 * <code>copyOfRange(original, 0, newLength)</code>. 3826 * 3827 * @param original the original array to be copied. 3828 * @param newLength the length of the returned array. 3829 * @return a copy of the original array, truncated or padded with 3830 * <code>(short)0</code> to obtain the required length. 3831 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3832 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3833 * @since 1.6 3834 * @see #copyOfRange(short[],int,int) 3835 */ 3836 public static short[] copyOf(short[] original, int newLength) 3837 { 3838 if (newLength < 0) 3839 throw new NegativeArraySizeException("The array size is negative."); 3840 return copyOfRange(original, 0, newLength); 3841 } 3842 3843 /** 3844 * Copies the specified range of the supplied array to a new 3845 * array, padding as necessary with <code>(short)0</code> 3846 * if <code>to</code> is greater than the length of the original 3847 * array. <code>from</code> must be in the range zero to 3848 * <code>original.length</code> and can not be greater than 3849 * <code>to</code>. The initial element of the 3850 * returned array will be equal to <code>original[from]</code>, 3851 * except where <code>from</code> is equal to <code>to</code> 3852 * (where a zero-length array will be returned) or <code> 3853 * <code>from</code> is equal to <code>original.length</code> 3854 * (where an array padded with <code>(short)0</code> will be 3855 * returned). The returned array is always of length 3856 * <code>to - from</code>. 3857 * 3858 * @param original the array from which to copy. 3859 * @param from the initial index of the range, inclusive. 3860 * @param to the final index of the range, exclusive. 3861 * @return a copy of the specified range, with padding to 3862 * obtain the required length. 3863 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3864 * or <code>from > original.length</code> 3865 * @throws IllegalArgumentException if <code>from > to</code> 3866 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3867 * @since 1.6 3868 * @see #copyOf(short[],int) 3869 */ 3870 public static short[] copyOfRange(short[] original, int from, int to) 3871 { 3872 if (from > to) 3873 throw new IllegalArgumentException("The initial index is after " + 3874 "the final index."); 3875 short[] newArray = new short[to - from]; 3876 if (to > original.length) 3877 { 3878 System.arraycopy(original, from, newArray, 0, 3879 original.length - from); 3880 fill(newArray, original.length, newArray.length, (short)0); 3881 } 3882 else 3883 System.arraycopy(original, from, newArray, 0, to - from); 3884 return newArray; 3885 } 3886 3887 /** 3888 * Returns a copy of the supplied array, truncating or padding as 3889 * necessary with <code>null</code> to obtain the specified length. 3890 * Indices that are valid for both arrays will return the same value. 3891 * Indices that only exist in the returned array (due to the new length 3892 * being greater than the original length) will return <code>null</code>. 3893 * This is equivalent to calling 3894 * <code>copyOfRange(original, 0, newLength)</code>. 3895 * 3896 * @param original the original array to be copied. 3897 * @param newLength the length of the returned array. 3898 * @return a copy of the original array, truncated or padded with 3899 * <code>null</code> to obtain the required length. 3900 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3901 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3902 * @since 1.6 3903 * @see #copyOfRange(T[],int,int) 3904 */ 3905 public static <T> T[] copyOf(T[] original, int newLength) 3906 { 3907 if (newLength < 0) 3908 throw new NegativeArraySizeException("The array size is negative."); 3909 return copyOfRange(original, 0, newLength); 3910 } 3911 3912 /** 3913 * Copies the specified range of the supplied array to a new 3914 * array, padding as necessary with <code>null</code> 3915 * if <code>to</code> is greater than the length of the original 3916 * array. <code>from</code> must be in the range zero to 3917 * <code>original.length</code> and can not be greater than 3918 * <code>to</code>. The initial element of the 3919 * returned array will be equal to <code>original[from]</code>, 3920 * except where <code>from</code> is equal to <code>to</code> 3921 * (where a zero-length array will be returned) or <code> 3922 * <code>from</code> is equal to <code>original.length</code> 3923 * (where an array padded with <code>null</code> will be 3924 * returned). The returned array is always of length 3925 * <code>to - from</code>. 3926 * 3927 * @param original the array from which to copy. 3928 * @param from the initial index of the range, inclusive. 3929 * @param to the final index of the range, exclusive. 3930 * @return a copy of the specified range, with padding to 3931 * obtain the required length. 3932 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 3933 * or <code>from > original.length</code> 3934 * @throws IllegalArgumentException if <code>from > to</code> 3935 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3936 * @since 1.6 3937 * @see #copyOf(T[],int) 3938 */ 3939 public static <T> T[] copyOfRange(T[] original, int from, int to) 3940 { 3941 if (from > to) 3942 throw new IllegalArgumentException("The initial index is after " + 3943 "the final index."); 3944 Class elemType = original.getClass().getComponentType(); 3945 T[] newArray = (T[]) Array.newInstance(elemType, to - from); 3946 if (to > original.length) 3947 { 3948 System.arraycopy(original, from, newArray, 0, 3949 original.length - from); 3950 fill(newArray, original.length, newArray.length, null); 3951 } 3952 else 3953 System.arraycopy(original, from, newArray, 0, to - from); 3954 return newArray; 3955 } 3956 3957 /** 3958 * Returns a copy of the supplied array, truncating or padding as 3959 * necessary with <code>null</code> to obtain the specified length. 3960 * Indices that are valid for both arrays will return the same value. 3961 * Indices that only exist in the returned array (due to the new length 3962 * being greater than the original length) will return <code>null</code>. 3963 * This is equivalent to calling 3964 * <code>copyOfRange(original, 0, newLength, newType)</code>. The returned 3965 * array will be of the specified type, <code>newType</code>. 3966 * 3967 * @param original the original array to be copied. 3968 * @param newLength the length of the returned array. 3969 * @param newType the type of the returned array. 3970 * @return a copy of the original array, truncated or padded with 3971 * <code>null</code> to obtain the required length. 3972 * @throws NegativeArraySizeException if <code>newLength</code> is negative. 3973 * @throws NullPointerException if <code>original</code> is <code>null</code>. 3974 * @since 1.6 3975 * @see #copyOfRange(U[],int,int,Class) 3976 */ 3977 public static <T,U> T[] copyOf(U[] original, int newLength, 3978 Class<? extends T[]> newType) 3979 { 3980 if (newLength < 0) 3981 throw new NegativeArraySizeException("The array size is negative."); 3982 return copyOfRange(original, 0, newLength, newType); 3983 } 3984 3985 /** 3986 * Copies the specified range of the supplied array to a new 3987 * array, padding as necessary with <code>null</code> 3988 * if <code>to</code> is greater than the length of the original 3989 * array. <code>from</code> must be in the range zero to 3990 * <code>original.length</code> and can not be greater than 3991 * <code>to</code>. The initial element of the 3992 * returned array will be equal to <code>original[from]</code>, 3993 * except where <code>from</code> is equal to <code>to</code> 3994 * (where a zero-length array will be returned) or <code> 3995 * <code>from</code> is equal to <code>original.length</code> 3996 * (where an array padded with <code>null</code> will be 3997 * returned). The returned array is always of length 3998 * <code>to - from</code> and will be of the specified type, 3999 * <code>newType</code>. 4000 * 4001 * @param original the array from which to copy. 4002 * @param from the initial index of the range, inclusive. 4003 * @param to the final index of the range, exclusive. 4004 * @param newType the type of the returned array. 4005 * @return a copy of the specified range, with padding to 4006 * obtain the required length. 4007 * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code> 4008 * or <code>from > original.length</code> 4009 * @throws IllegalArgumentException if <code>from > to</code> 4010 * @throws NullPointerException if <code>original</code> is <code>null</code>. 4011 * @since 1.6 4012 * @see #copyOf(T[],int) 4013 */ 4014 public static <T,U> T[] copyOfRange(U[] original, int from, int to, 4015 Class<? extends T[]> newType) 4016 { 4017 if (from > to) 4018 throw new IllegalArgumentException("The initial index is after " + 4019 "the final index."); 4020 T[] newArray = (T[]) Array.newInstance(newType.getComponentType(), 4021 to - from); 4022 if (to > original.length) 4023 { 4024 System.arraycopy(original, from, newArray, 0, 4025 original.length - from); 4026 fill(newArray, original.length, newArray.length, null); 4027 } 4028 else 4029 System.arraycopy(original, from, newArray, 0, to - from); 4030 return newArray; 4031 } 4032 }