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