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