GNU Classpath (0.20) | |
Frames | No Frames |
1: /* Arrays.java -- Utility class with methods to operate on arrays 2: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 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: int low = 0; 96: int hi = a.length - 1; 97: int mid = 0; 98: while (low <= hi) 99: { 100: mid = (low + hi) >> 1; 101: final byte d = a[mid]; 102: if (d == key) 103: return mid; 104: else if (d > key) 105: hi = mid - 1; 106: else 107: // This gets the insertion point right on the last loop. 108: low = ++mid; 109: } 110: return -mid - 1; 111: } 112: 113: /** 114: * Perform a binary search of a char array for a key. The array must be 115: * sorted (as by the sort() method) - if it is not, the behaviour of this 116: * method is undefined, and may be an infinite loop. If the array contains 117: * the key more than once, any one of them may be found. Note: although the 118: * specification allows for an infinite loop if the array is unsorted, it 119: * will not happen in this implementation. 120: * 121: * @param a the array to search (must be sorted) 122: * @param key the value to search for 123: * @return the index at which the key was found, or -n-1 if it was not 124: * found, where n is the index of the first value higher than key or 125: * a.length if there is no such value. 126: */ 127: public static int binarySearch(char[] a, char key) 128: { 129: int low = 0; 130: int hi = a.length - 1; 131: int mid = 0; 132: while (low <= hi) 133: { 134: mid = (low + hi) >> 1; 135: final char d = a[mid]; 136: if (d == key) 137: return mid; 138: else if (d > key) 139: hi = mid - 1; 140: else 141: // This gets the insertion point right on the last loop. 142: low = ++mid; 143: } 144: return -mid - 1; 145: } 146: 147: /** 148: * Perform a binary search of a short array for a key. The array must be 149: * sorted (as by the sort() method) - if it is not, the behaviour of this 150: * method is undefined, and may be an infinite loop. If the array contains 151: * the key more than once, any one of them may be found. Note: although the 152: * specification allows for an infinite loop if the array is unsorted, it 153: * will not happen in this implementation. 154: * 155: * @param a the array to search (must be sorted) 156: * @param key the value to search for 157: * @return the index at which the key was found, or -n-1 if it was not 158: * found, where n is the index of the first value higher than key or 159: * a.length if there is no such value. 160: */ 161: public static int binarySearch(short[] a, short key) 162: { 163: int low = 0; 164: int hi = a.length - 1; 165: int mid = 0; 166: while (low <= hi) 167: { 168: mid = (low + hi) >> 1; 169: final short d = a[mid]; 170: if (d == key) 171: return mid; 172: else if (d > key) 173: hi = mid - 1; 174: else 175: // This gets the insertion point right on the last loop. 176: low = ++mid; 177: } 178: return -mid - 1; 179: } 180: 181: /** 182: * Perform a binary search of an int array for a key. The array must be 183: * sorted (as by the sort() method) - if it is not, the behaviour of this 184: * method is undefined, and may be an infinite loop. If the array contains 185: * the key more than once, any one of them may be found. Note: although the 186: * specification allows for an infinite loop if the array is unsorted, it 187: * will not happen in this implementation. 188: * 189: * @param a the array to search (must be sorted) 190: * @param key the value to search for 191: * @return the index at which the key was found, or -n-1 if it was not 192: * found, where n is the index of the first value higher than key or 193: * a.length if there is no such value. 194: */ 195: public static int binarySearch(int[] a, int key) 196: { 197: int low = 0; 198: int hi = a.length - 1; 199: int mid = 0; 200: while (low <= hi) 201: { 202: mid = (low + hi) >> 1; 203: final int d = a[mid]; 204: if (d == key) 205: return mid; 206: else if (d > key) 207: hi = mid - 1; 208: else 209: // This gets the insertion point right on the last loop. 210: low = ++mid; 211: } 212: return -mid - 1; 213: } 214: 215: /** 216: * Perform a binary search of a long array for a key. The array must be 217: * sorted (as by the sort() method) - if it is not, the behaviour of this 218: * method is undefined, and may be an infinite loop. If the array contains 219: * the key more than once, any one of them may be found. Note: although the 220: * specification allows for an infinite loop if the array is unsorted, it 221: * will not happen in this implementation. 222: * 223: * @param a the array to search (must be sorted) 224: * @param key the value to search for 225: * @return the index at which the key was found, or -n-1 if it was not 226: * found, where n is the index of the first value higher than key or 227: * a.length if there is no such value. 228: */ 229: public static int binarySearch(long[] a, long key) 230: { 231: int low = 0; 232: int hi = a.length - 1; 233: int mid = 0; 234: while (low <= hi) 235: { 236: mid = (low + hi) >> 1; 237: final long d = a[mid]; 238: if (d == key) 239: return mid; 240: else if (d > key) 241: hi = mid - 1; 242: else 243: // This gets the insertion point right on the last loop. 244: low = ++mid; 245: } 246: return -mid - 1; 247: } 248: 249: /** 250: * Perform a binary search of a float array for a key. The array must be 251: * sorted (as by the sort() method) - if it is not, the behaviour of this 252: * method is undefined, and may be an infinite loop. If the array contains 253: * the key more than once, any one of them may be found. Note: although the 254: * specification allows for an infinite loop if the array is unsorted, it 255: * will not happen in this implementation. 256: * 257: * @param a the array to search (must be sorted) 258: * @param key the value to search for 259: * @return the index at which the key was found, or -n-1 if it was not 260: * found, where n is the index of the first value higher than key or 261: * a.length if there is no such value. 262: */ 263: public static int binarySearch(float[] a, float key) 264: { 265: // Must use Float.compare to take into account NaN, +-0. 266: int low = 0; 267: int hi = a.length - 1; 268: int mid = 0; 269: while (low <= hi) 270: { 271: mid = (low + hi) >> 1; 272: final int r = Float.compare(a[mid], key); 273: if (r == 0) 274: return mid; 275: else if (r > 0) 276: hi = mid - 1; 277: else 278: // This gets the insertion point right on the last loop 279: low = ++mid; 280: } 281: return -mid - 1; 282: } 283: 284: /** 285: * Perform a binary search of a double array for a key. The array must be 286: * sorted (as by the sort() method) - if it is not, the behaviour of this 287: * method is undefined, and may be an infinite loop. If the array contains 288: * the key more than once, any one of them may be found. Note: although the 289: * specification allows for an infinite loop if the array is unsorted, it 290: * will not happen in this implementation. 291: * 292: * @param a the array to search (must be sorted) 293: * @param key the value to search for 294: * @return the index at which the key was found, or -n-1 if it was not 295: * found, where n is the index of the first value higher than key or 296: * a.length if there is no such value. 297: */ 298: public static int binarySearch(double[] a, double key) 299: { 300: // Must use Double.compare to take into account NaN, +-0. 301: int low = 0; 302: int hi = a.length - 1; 303: int mid = 0; 304: while (low <= hi) 305: { 306: mid = (low + hi) >> 1; 307: final int r = Double.compare(a[mid], key); 308: if (r == 0) 309: return mid; 310: else if (r > 0) 311: hi = mid - 1; 312: else 313: // This gets the insertion point right on the last loop 314: low = ++mid; 315: } 316: return -mid - 1; 317: } 318: 319: /** 320: * Perform a binary search of an Object array for a key, using the natural 321: * ordering of the elements. The array must be sorted (as by the sort() 322: * method) - if it is not, the behaviour of this method is undefined, and may 323: * be an infinite loop. Further, the key must be comparable with every item 324: * in the array. If the array contains the key more than once, any one of 325: * them may be found. Note: although the specification allows for an infinite 326: * loop if the array is unsorted, it will not happen in this (JCL) 327: * implementation. 328: * 329: * @param a the array to search (must be sorted) 330: * @param key the value to search for 331: * @return the index at which the key was found, or -n-1 if it was not 332: * found, where n is the index of the first value higher than key or 333: * a.length if there is no such value. 334: * @throws ClassCastException if key could not be compared with one of the 335: * elements of a 336: * @throws NullPointerException if a null element in a is compared 337: */ 338: public static int binarySearch(Object[] a, Object key) 339: { 340: return binarySearch(a, key, null); 341: } 342: 343: /** 344: * Perform a binary search of an Object array for a key, using a supplied 345: * Comparator. The array must be sorted (as by the sort() method with the 346: * same Comparator) - if it is not, the behaviour of this method is 347: * undefined, and may be an infinite loop. Further, the key must be 348: * comparable with every item in the array. If the array contains the key 349: * more than once, any one of them may be found. Note: although the 350: * specification allows for an infinite loop if the array is unsorted, it 351: * will not happen in this (JCL) implementation. 352: * 353: * @param a the array to search (must be sorted) 354: * @param key the value to search for 355: * @param c the comparator by which the array is sorted; or null to 356: * use the elements' natural order 357: * @return the index at which the key was found, or -n-1 if it was not 358: * found, where n is the index of the first value higher than key or 359: * a.length if there is no such value. 360: * @throws ClassCastException if key could not be compared with one of the 361: * elements of a 362: * @throws NullPointerException if a null element is compared with natural 363: * ordering (only possible when c is null) 364: */ 365: public static int binarySearch(Object[] a, Object key, Comparator c) 366: { 367: int low = 0; 368: int hi = a.length - 1; 369: int mid = 0; 370: while (low <= hi) 371: { 372: mid = (low + hi) >> 1; 373: final int d = Collections.compare(key, a[mid], c); 374: if (d == 0) 375: return mid; 376: else if (d < 0) 377: hi = mid - 1; 378: else 379: // This gets the insertion point right on the last loop 380: low = ++mid; 381: } 382: return -mid - 1; 383: } 384: 385: 386: // equals 387: /** 388: * Compare two boolean arrays for equality. 389: * 390: * @param a1 the first array to compare 391: * @param a2 the second array to compare 392: * @return true if a1 and a2 are both null, or if a2 is of the same length 393: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 394: */ 395: public static boolean equals(boolean[] a1, boolean[] a2) 396: { 397: // Quick test which saves comparing elements of the same array, and also 398: // catches the case that both are null. 399: if (a1 == a2) 400: return true; 401: 402: if (null == a1 || null == a2) 403: return false; 404: 405: // If they're the same length, test each element 406: if (a1.length == a2.length) 407: { 408: int i = a1.length; 409: while (--i >= 0) 410: if (a1[i] != a2[i]) 411: return false; 412: return true; 413: } 414: return false; 415: } 416: 417: /** 418: * Compare two byte arrays for equality. 419: * 420: * @param a1 the first array to compare 421: * @param a2 the second array to compare 422: * @return true if a1 and a2 are both null, or if a2 is of the same length 423: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 424: */ 425: public static boolean equals(byte[] a1, byte[] a2) 426: { 427: // Quick test which saves comparing elements of the same array, and also 428: // catches the case that both are null. 429: if (a1 == a2) 430: return true; 431: 432: if (null == a1 || null == a2) 433: return false; 434: 435: // If they're the same length, test each element 436: if (a1.length == a2.length) 437: { 438: int i = a1.length; 439: while (--i >= 0) 440: if (a1[i] != a2[i]) 441: return false; 442: return true; 443: } 444: return false; 445: } 446: 447: /** 448: * Compare two char arrays for equality. 449: * 450: * @param a1 the first array to compare 451: * @param a2 the second array to compare 452: * @return true if a1 and a2 are both null, or if a2 is of the same length 453: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 454: */ 455: public static boolean equals(char[] a1, char[] a2) 456: { 457: // Quick test which saves comparing elements of the same array, and also 458: // catches the case that both are null. 459: if (a1 == a2) 460: return true; 461: 462: if (null == a1 || null == a2) 463: return false; 464: 465: // If they're the same length, test each element 466: if (a1.length == a2.length) 467: { 468: int i = a1.length; 469: while (--i >= 0) 470: if (a1[i] != a2[i]) 471: return false; 472: return true; 473: } 474: return false; 475: } 476: 477: /** 478: * Compare two short arrays for equality. 479: * 480: * @param a1 the first array to compare 481: * @param a2 the second array to compare 482: * @return true if a1 and a2 are both null, or if a2 is of the same length 483: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 484: */ 485: public static boolean equals(short[] a1, short[] a2) 486: { 487: // Quick test which saves comparing elements of the same array, and also 488: // catches the case that both are null. 489: if (a1 == a2) 490: return true; 491: 492: if (null == a1 || null == a2) 493: return false; 494: 495: // If they're the same length, test each element 496: if (a1.length == a2.length) 497: { 498: int i = a1.length; 499: while (--i >= 0) 500: if (a1[i] != a2[i]) 501: return false; 502: return true; 503: } 504: return false; 505: } 506: 507: /** 508: * Compare two int arrays for equality. 509: * 510: * @param a1 the first array to compare 511: * @param a2 the second array to compare 512: * @return true if a1 and a2 are both null, or if a2 is of the same length 513: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 514: */ 515: public static boolean equals(int[] a1, int[] a2) 516: { 517: // Quick test which saves comparing elements of the same array, and also 518: // catches the case that both are null. 519: if (a1 == a2) 520: return true; 521: 522: if (null == a1 || null == a2) 523: return false; 524: 525: // If they're the same length, test each element 526: if (a1.length == a2.length) 527: { 528: int i = a1.length; 529: while (--i >= 0) 530: if (a1[i] != a2[i]) 531: return false; 532: return true; 533: } 534: return false; 535: } 536: 537: /** 538: * Compare two long arrays for equality. 539: * 540: * @param a1 the first array to compare 541: * @param a2 the second array to compare 542: * @return true if a1 and a2 are both null, or if a2 is of the same length 543: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 544: */ 545: public static boolean equals(long[] a1, long[] a2) 546: { 547: // Quick test which saves comparing elements of the same array, and also 548: // catches the case that both are null. 549: if (a1 == a2) 550: return true; 551: 552: if (null == a1 || null == a2) 553: return false; 554: 555: // If they're the same length, test each element 556: if (a1.length == a2.length) 557: { 558: int i = a1.length; 559: while (--i >= 0) 560: if (a1[i] != a2[i]) 561: return false; 562: return true; 563: } 564: return false; 565: } 566: 567: /** 568: * Compare two float arrays for equality. 569: * 570: * @param a1 the first array to compare 571: * @param a2 the second array to compare 572: * @return true if a1 and a2 are both null, or if a2 is of the same length 573: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 574: */ 575: public static boolean equals(float[] a1, float[] a2) 576: { 577: // Quick test which saves comparing elements of the same array, and also 578: // catches the case that both are null. 579: if (a1 == a2) 580: return true; 581: 582: if (null == a1 || null == a2) 583: return false; 584: 585: // Must use Float.compare to take into account NaN, +-0. 586: // If they're the same length, test each element 587: if (a1.length == a2.length) 588: { 589: int i = a1.length; 590: while (--i >= 0) 591: if (Float.compare(a1[i], a2[i]) != 0) 592: return false; 593: return true; 594: } 595: return false; 596: } 597: 598: /** 599: * Compare two double arrays for equality. 600: * 601: * @param a1 the first array to compare 602: * @param a2 the second array to compare 603: * @return true if a1 and a2 are both null, or if a2 is of the same length 604: * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] 605: */ 606: public static boolean equals(double[] a1, double[] a2) 607: { 608: // Quick test which saves comparing elements of the same array, and also 609: // catches the case that both are null. 610: if (a1 == a2) 611: return true; 612: 613: if (null == a1 || null == a2) 614: return false; 615: 616: // Must use Double.compare to take into account NaN, +-0. 617: // If they're the same length, test each element 618: if (a1.length == a2.length) 619: { 620: int i = a1.length; 621: while (--i >= 0) 622: if (Double.compare(a1[i], a2[i]) != 0) 623: return false; 624: return true; 625: } 626: return false; 627: } 628: 629: /** 630: * Compare two Object arrays for equality. 631: * 632: * @param a1 the first array to compare 633: * @param a2 the second array to compare 634: * @return true if a1 and a2 are both null, or if a1 is of the same length 635: * as a2, and for each 0 <= i < a.length, a1[i] == null ? 636: * a2[i] == null : a1[i].equals(a2[i]). 637: */ 638: public static boolean equals(Object[] a1, Object[] a2) 639: { 640: // Quick test which saves comparing elements of the same array, and also 641: // catches the case that both are null. 642: if (a1 == a2) 643: return true; 644: 645: if (null == a1 || null == a2) 646: return false; 647: 648: // If they're the same length, test each element 649: if (a1.length == a2.length) 650: { 651: int i = a1.length; 652: while (--i >= 0) 653: if (! AbstractCollection.equals(a1[i], a2[i])) 654: return false; 655: return true; 656: } 657: return false; 658: } 659: 660: 661: // fill 662: /** 663: * Fill an array with a boolean value. 664: * 665: * @param a the array to fill 666: * @param val the value to fill it with 667: */ 668: public static void fill(boolean[] a, boolean val) 669: { 670: fill(a, 0, a.length, val); 671: } 672: 673: /** 674: * Fill a range of an array with a boolean value. 675: * 676: * @param a the array to fill 677: * @param fromIndex the index to fill from, inclusive 678: * @param toIndex the index to fill to, exclusive 679: * @param val the value to fill with 680: * @throws IllegalArgumentException if fromIndex > toIndex 681: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 682: * || toIndex > a.length 683: */ 684: public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val) 685: { 686: if (fromIndex > toIndex) 687: throw new IllegalArgumentException(); 688: for (int i = fromIndex; i < toIndex; i++) 689: a[i] = val; 690: } 691: 692: /** 693: * Fill an array with a byte value. 694: * 695: * @param a the array to fill 696: * @param val the value to fill it with 697: */ 698: public static void fill(byte[] a, byte val) 699: { 700: fill(a, 0, a.length, val); 701: } 702: 703: /** 704: * Fill a range of an array with a byte value. 705: * 706: * @param a the array to fill 707: * @param fromIndex the index to fill from, inclusive 708: * @param toIndex the index to fill to, exclusive 709: * @param val the value to fill with 710: * @throws IllegalArgumentException if fromIndex > toIndex 711: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 712: * || toIndex > a.length 713: */ 714: public static void fill(byte[] a, int fromIndex, int toIndex, byte val) 715: { 716: if (fromIndex > toIndex) 717: throw new IllegalArgumentException(); 718: for (int i = fromIndex; i < toIndex; i++) 719: a[i] = val; 720: } 721: 722: /** 723: * Fill an array with a char value. 724: * 725: * @param a the array to fill 726: * @param val the value to fill it with 727: */ 728: public static void fill(char[] a, char val) 729: { 730: fill(a, 0, a.length, val); 731: } 732: 733: /** 734: * Fill a range of an array with a char value. 735: * 736: * @param a the array to fill 737: * @param fromIndex the index to fill from, inclusive 738: * @param toIndex the index to fill to, exclusive 739: * @param val the value to fill with 740: * @throws IllegalArgumentException if fromIndex > toIndex 741: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 742: * || toIndex > a.length 743: */ 744: public static void fill(char[] a, int fromIndex, int toIndex, char val) 745: { 746: if (fromIndex > toIndex) 747: throw new IllegalArgumentException(); 748: for (int i = fromIndex; i < toIndex; i++) 749: a[i] = val; 750: } 751: 752: /** 753: * Fill an array with a short value. 754: * 755: * @param a the array to fill 756: * @param val the value to fill it with 757: */ 758: public static void fill(short[] a, short val) 759: { 760: fill(a, 0, a.length, val); 761: } 762: 763: /** 764: * Fill a range of an array with a short value. 765: * 766: * @param a the array to fill 767: * @param fromIndex the index to fill from, inclusive 768: * @param toIndex the index to fill to, exclusive 769: * @param val the value to fill with 770: * @throws IllegalArgumentException if fromIndex > toIndex 771: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 772: * || toIndex > a.length 773: */ 774: public static void fill(short[] a, int fromIndex, int toIndex, short val) 775: { 776: if (fromIndex > toIndex) 777: throw new IllegalArgumentException(); 778: for (int i = fromIndex; i < toIndex; i++) 779: a[i] = val; 780: } 781: 782: /** 783: * Fill an array with an int value. 784: * 785: * @param a the array to fill 786: * @param val the value to fill it with 787: */ 788: public static void fill(int[] a, int val) 789: { 790: fill(a, 0, a.length, val); 791: } 792: 793: /** 794: * Fill a range of an array with an int value. 795: * 796: * @param a the array to fill 797: * @param fromIndex the index to fill from, inclusive 798: * @param toIndex the index to fill to, exclusive 799: * @param val the value to fill with 800: * @throws IllegalArgumentException if fromIndex > toIndex 801: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 802: * || toIndex > a.length 803: */ 804: public static void fill(int[] a, int fromIndex, int toIndex, int val) 805: { 806: if (fromIndex > toIndex) 807: throw new IllegalArgumentException(); 808: for (int i = fromIndex; i < toIndex; i++) 809: a[i] = val; 810: } 811: 812: /** 813: * Fill an array with a long value. 814: * 815: * @param a the array to fill 816: * @param val the value to fill it with 817: */ 818: public static void fill(long[] a, long val) 819: { 820: fill(a, 0, a.length, val); 821: } 822: 823: /** 824: * Fill a range of an array with a long value. 825: * 826: * @param a the array to fill 827: * @param fromIndex the index to fill from, inclusive 828: * @param toIndex the index to fill to, exclusive 829: * @param val the value to fill with 830: * @throws IllegalArgumentException if fromIndex > toIndex 831: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 832: * || toIndex > a.length 833: */ 834: public static void fill(long[] a, int fromIndex, int toIndex, long val) 835: { 836: if (fromIndex > toIndex) 837: throw new IllegalArgumentException(); 838: for (int i = fromIndex; i < toIndex; i++) 839: a[i] = val; 840: } 841: 842: /** 843: * Fill an array with a float value. 844: * 845: * @param a the array to fill 846: * @param val the value to fill it with 847: */ 848: public static void fill(float[] a, float val) 849: { 850: fill(a, 0, a.length, val); 851: } 852: 853: /** 854: * Fill a range of an array with a float value. 855: * 856: * @param a the array to fill 857: * @param fromIndex the index to fill from, inclusive 858: * @param toIndex the index to fill to, exclusive 859: * @param val the value to fill with 860: * @throws IllegalArgumentException if fromIndex > toIndex 861: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 862: * || toIndex > a.length 863: */ 864: public static void fill(float[] a, int fromIndex, int toIndex, float val) 865: { 866: if (fromIndex > toIndex) 867: throw new IllegalArgumentException(); 868: for (int i = fromIndex; i < toIndex; i++) 869: a[i] = val; 870: } 871: 872: /** 873: * Fill an array with a double value. 874: * 875: * @param a the array to fill 876: * @param val the value to fill it with 877: */ 878: public static void fill(double[] a, double val) 879: { 880: fill(a, 0, a.length, val); 881: } 882: 883: /** 884: * Fill a range of an array with a double value. 885: * 886: * @param a the array to fill 887: * @param fromIndex the index to fill from, inclusive 888: * @param toIndex the index to fill to, exclusive 889: * @param val the value to fill with 890: * @throws IllegalArgumentException if fromIndex > toIndex 891: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 892: * || toIndex > a.length 893: */ 894: public static void fill(double[] a, int fromIndex, int toIndex, double val) 895: { 896: if (fromIndex > toIndex) 897: throw new IllegalArgumentException(); 898: for (int i = fromIndex; i < toIndex; i++) 899: a[i] = val; 900: } 901: 902: /** 903: * Fill an array with an Object value. 904: * 905: * @param a the array to fill 906: * @param val the value to fill it with 907: * @throws ClassCastException if val is not an instance of the element 908: * type of a. 909: */ 910: public static void fill(Object[] a, Object val) 911: { 912: fill(a, 0, a.length, val); 913: } 914: 915: /** 916: * Fill a range of an array with an Object value. 917: * 918: * @param a the array to fill 919: * @param fromIndex the index to fill from, inclusive 920: * @param toIndex the index to fill to, exclusive 921: * @param val the value to fill with 922: * @throws ClassCastException if val is not an instance of the element 923: * type of a. 924: * @throws IllegalArgumentException if fromIndex > toIndex 925: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 926: * || toIndex > a.length 927: */ 928: public static void fill(Object[] a, int fromIndex, int toIndex, Object val) 929: { 930: if (fromIndex > toIndex) 931: throw new IllegalArgumentException(); 932: for (int i = fromIndex; i < toIndex; i++) 933: a[i] = val; 934: } 935: 936: 937: // sort 938: // Thanks to Paul Fisher (rao@gnu.org) for finding this quicksort algorithm 939: // as specified by Sun and porting it to Java. The algorithm is an optimised 940: // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's 941: // "Engineering a Sort Function", Software-Practice and Experience, Vol. 942: // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n) 943: // performance on many arrays that would take quadratic time with a standard 944: // quicksort. 945: 946: /** 947: * Performs a stable sort on the elements, arranging them according to their 948: * natural order. 949: * 950: * @param a the byte array to sort 951: */ 952: public static void sort(byte[] a) 953: { 954: qsort(a, 0, a.length); 955: } 956: 957: /** 958: * Performs a stable sort on the elements, arranging them according to their 959: * natural order. 960: * 961: * @param a the byte array to sort 962: * @param fromIndex the first index to sort (inclusive) 963: * @param toIndex the last index to sort (exclusive) 964: * @throws IllegalArgumentException if fromIndex > toIndex 965: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 966: * || toIndex > a.length 967: */ 968: public static void sort(byte[] a, int fromIndex, int toIndex) 969: { 970: if (fromIndex > toIndex) 971: throw new IllegalArgumentException(); 972: if (fromIndex < 0) 973: throw new ArrayIndexOutOfBoundsException(); 974: qsort(a, fromIndex, toIndex - fromIndex); 975: } 976: 977: /** 978: * Finds the index of the median of three array elements. 979: * 980: * @param a the first index 981: * @param b the second index 982: * @param c the third index 983: * @param d the array 984: * @return the index (a, b, or c) which has the middle value of the three 985: */ 986: private static int med3(int a, int b, int c, byte[] d) 987: { 988: return (d[a] < d[b] 989: ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 990: : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 991: } 992: 993: /** 994: * Swaps the elements at two locations of an array 995: * 996: * @param i the first index 997: * @param j the second index 998: * @param a the array 999: */ 1000: private static void swap(int i, int j, byte[] a) 1001: { 1002: byte c = a[i]; 1003: a[i] = a[j]; 1004: a[j] = c; 1005: } 1006: 1007: /** 1008: * Swaps two ranges of an array. 1009: * 1010: * @param i the first range start 1011: * @param j the second range start 1012: * @param n the element count 1013: * @param a the array 1014: */ 1015: private static void vecswap(int i, int j, int n, byte[] a) 1016: { 1017: for ( ; n > 0; i++, j++, n--) 1018: swap(i, j, a); 1019: } 1020: 1021: /** 1022: * Performs a recursive modified quicksort. 1023: * 1024: * @param array the array to sort 1025: * @param from the start index (inclusive) 1026: * @param count the number of elements to sort 1027: */ 1028: private static void qsort(byte[] array, int from, int count) 1029: { 1030: // Use an insertion sort on small arrays. 1031: if (count <= 7) 1032: { 1033: for (int i = from + 1; i < from + count; i++) 1034: for (int j = i; j > from && array[j - 1] > array[j]; j--) 1035: swap(j, j - 1, array); 1036: return; 1037: } 1038: 1039: // Determine a good median element. 1040: int mid = count / 2; 1041: int lo = from; 1042: int hi = from + count - 1; 1043: 1044: if (count > 40) 1045: { // big arrays, pseudomedian of 9 1046: int s = count / 8; 1047: lo = med3(lo, lo + s, lo + 2 * s, array); 1048: mid = med3(mid - s, mid, mid + s, array); 1049: hi = med3(hi - 2 * s, hi - s, hi, array); 1050: } 1051: mid = med3(lo, mid, hi, array); 1052: 1053: int a, b, c, d; 1054: int comp; 1055: 1056: // Pull the median element out of the fray, and use it as a pivot. 1057: swap(from, mid, array); 1058: a = b = from; 1059: c = d = from + count - 1; 1060: 1061: // Repeatedly move b and c to each other, swapping elements so 1062: // that all elements before index b are less than the pivot, and all 1063: // elements after index c are greater than the pivot. a and b track 1064: // the elements equal to the pivot. 1065: while (true) 1066: { 1067: while (b <= c && (comp = array[b] - array[from]) <= 0) 1068: { 1069: if (comp == 0) 1070: { 1071: swap(a, b, array); 1072: a++; 1073: } 1074: b++; 1075: } 1076: while (c >= b && (comp = array[c] - array[from]) >= 0) 1077: { 1078: if (comp == 0) 1079: { 1080: swap(c, d, array); 1081: d--; 1082: } 1083: c--; 1084: } 1085: if (b > c) 1086: break; 1087: swap(b, c, array); 1088: b++; 1089: c--; 1090: } 1091: 1092: // Swap pivot(s) back in place, the recurse on left and right sections. 1093: hi = from + count; 1094: int span; 1095: span = Math.min(a - from, b - a); 1096: vecswap(from, b - span, span, array); 1097: 1098: span = Math.min(d - c, hi - d - 1); 1099: vecswap(b, hi - span, span, array); 1100: 1101: span = b - a; 1102: if (span > 1) 1103: qsort(array, from, span); 1104: 1105: span = d - c; 1106: if (span > 1) 1107: qsort(array, hi - span, span); 1108: } 1109: 1110: /** 1111: * Performs a stable sort on the elements, arranging them according to their 1112: * natural order. 1113: * 1114: * @param a the char array to sort 1115: */ 1116: public static void sort(char[] a) 1117: { 1118: qsort(a, 0, a.length); 1119: } 1120: 1121: /** 1122: * Performs a stable sort on the elements, arranging them according to their 1123: * natural order. 1124: * 1125: * @param a the char array to sort 1126: * @param fromIndex the first index to sort (inclusive) 1127: * @param toIndex the last index to sort (exclusive) 1128: * @throws IllegalArgumentException if fromIndex > toIndex 1129: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1130: * || toIndex > a.length 1131: */ 1132: public static void sort(char[] a, int fromIndex, int toIndex) 1133: { 1134: if (fromIndex > toIndex) 1135: throw new IllegalArgumentException(); 1136: if (fromIndex < 0) 1137: throw new ArrayIndexOutOfBoundsException(); 1138: qsort(a, fromIndex, toIndex - fromIndex); 1139: } 1140: 1141: /** 1142: * Finds the index of the median of three array elements. 1143: * 1144: * @param a the first index 1145: * @param b the second index 1146: * @param c the third index 1147: * @param d the array 1148: * @return the index (a, b, or c) which has the middle value of the three 1149: */ 1150: private static int med3(int a, int b, int c, char[] d) 1151: { 1152: return (d[a] < d[b] 1153: ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1154: : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1155: } 1156: 1157: /** 1158: * Swaps the elements at two locations of an array 1159: * 1160: * @param i the first index 1161: * @param j the second index 1162: * @param a the array 1163: */ 1164: private static void swap(int i, int j, char[] a) 1165: { 1166: char c = a[i]; 1167: a[i] = a[j]; 1168: a[j] = c; 1169: } 1170: 1171: /** 1172: * Swaps two ranges of an array. 1173: * 1174: * @param i the first range start 1175: * @param j the second range start 1176: * @param n the element count 1177: * @param a the array 1178: */ 1179: private static void vecswap(int i, int j, int n, char[] a) 1180: { 1181: for ( ; n > 0; i++, j++, n--) 1182: swap(i, j, a); 1183: } 1184: 1185: /** 1186: * Performs a recursive modified quicksort. 1187: * 1188: * @param array the array to sort 1189: * @param from the start index (inclusive) 1190: * @param count the number of elements to sort 1191: */ 1192: private static void qsort(char[] array, int from, int count) 1193: { 1194: // Use an insertion sort on small arrays. 1195: if (count <= 7) 1196: { 1197: for (int i = from + 1; i < from + count; i++) 1198: for (int j = i; j > from && array[j - 1] > array[j]; j--) 1199: swap(j, j - 1, array); 1200: return; 1201: } 1202: 1203: // Determine a good median element. 1204: int mid = count / 2; 1205: int lo = from; 1206: int hi = from + count - 1; 1207: 1208: if (count > 40) 1209: { // big arrays, pseudomedian of 9 1210: int s = count / 8; 1211: lo = med3(lo, lo + s, lo + 2 * s, array); 1212: mid = med3(mid - s, mid, mid + s, array); 1213: hi = med3(hi - 2 * s, hi - s, hi, array); 1214: } 1215: mid = med3(lo, mid, hi, array); 1216: 1217: int a, b, c, d; 1218: int comp; 1219: 1220: // Pull the median element out of the fray, and use it as a pivot. 1221: swap(from, mid, array); 1222: a = b = from; 1223: c = d = from + count - 1; 1224: 1225: // Repeatedly move b and c to each other, swapping elements so 1226: // that all elements before index b are less than the pivot, and all 1227: // elements after index c are greater than the pivot. a and b track 1228: // the elements equal to the pivot. 1229: while (true) 1230: { 1231: while (b <= c && (comp = array[b] - array[from]) <= 0) 1232: { 1233: if (comp == 0) 1234: { 1235: swap(a, b, array); 1236: a++; 1237: } 1238: b++; 1239: } 1240: while (c >= b && (comp = array[c] - array[from]) >= 0) 1241: { 1242: if (comp == 0) 1243: { 1244: swap(c, d, array); 1245: d--; 1246: } 1247: c--; 1248: } 1249: if (b > c) 1250: break; 1251: swap(b, c, array); 1252: b++; 1253: c--; 1254: } 1255: 1256: // Swap pivot(s) back in place, the recurse on left and right sections. 1257: hi = from + count; 1258: int span; 1259: span = Math.min(a - from, b - a); 1260: vecswap(from, b - span, span, array); 1261: 1262: span = Math.min(d - c, hi - d - 1); 1263: vecswap(b, hi - span, span, array); 1264: 1265: span = b - a; 1266: if (span > 1) 1267: qsort(array, from, span); 1268: 1269: span = d - c; 1270: if (span > 1) 1271: qsort(array, hi - span, span); 1272: } 1273: 1274: /** 1275: * Performs a stable sort on the elements, arranging them according to their 1276: * natural order. 1277: * 1278: * @param a the short array to sort 1279: */ 1280: public static void sort(short[] a) 1281: { 1282: qsort(a, 0, a.length); 1283: } 1284: 1285: /** 1286: * Performs a stable sort on the elements, arranging them according to their 1287: * natural order. 1288: * 1289: * @param a the short array to sort 1290: * @param fromIndex the first index to sort (inclusive) 1291: * @param toIndex the last index to sort (exclusive) 1292: * @throws IllegalArgumentException if fromIndex > toIndex 1293: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1294: * || toIndex > a.length 1295: */ 1296: public static void sort(short[] a, int fromIndex, int toIndex) 1297: { 1298: if (fromIndex > toIndex) 1299: throw new IllegalArgumentException(); 1300: if (fromIndex < 0) 1301: throw new ArrayIndexOutOfBoundsException(); 1302: qsort(a, fromIndex, toIndex - fromIndex); 1303: } 1304: 1305: /** 1306: * Finds the index of the median of three array elements. 1307: * 1308: * @param a the first index 1309: * @param b the second index 1310: * @param c the third index 1311: * @param d the array 1312: * @return the index (a, b, or c) which has the middle value of the three 1313: */ 1314: private static int med3(int a, int b, int c, short[] d) 1315: { 1316: return (d[a] < d[b] 1317: ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1318: : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1319: } 1320: 1321: /** 1322: * Swaps the elements at two locations of an array 1323: * 1324: * @param i the first index 1325: * @param j the second index 1326: * @param a the array 1327: */ 1328: private static void swap(int i, int j, short[] a) 1329: { 1330: short c = a[i]; 1331: a[i] = a[j]; 1332: a[j] = c; 1333: } 1334: 1335: /** 1336: * Swaps two ranges of an array. 1337: * 1338: * @param i the first range start 1339: * @param j the second range start 1340: * @param n the element count 1341: * @param a the array 1342: */ 1343: private static void vecswap(int i, int j, int n, short[] a) 1344: { 1345: for ( ; n > 0; i++, j++, n--) 1346: swap(i, j, a); 1347: } 1348: 1349: /** 1350: * Performs a recursive modified quicksort. 1351: * 1352: * @param array the array to sort 1353: * @param from the start index (inclusive) 1354: * @param count the number of elements to sort 1355: */ 1356: private static void qsort(short[] array, int from, int count) 1357: { 1358: // Use an insertion sort on small arrays. 1359: if (count <= 7) 1360: { 1361: for (int i = from + 1; i < from + count; i++) 1362: for (int j = i; j > from && array[j - 1] > array[j]; j--) 1363: swap(j, j - 1, array); 1364: return; 1365: } 1366: 1367: // Determine a good median element. 1368: int mid = count / 2; 1369: int lo = from; 1370: int hi = from + count - 1; 1371: 1372: if (count > 40) 1373: { // big arrays, pseudomedian of 9 1374: int s = count / 8; 1375: lo = med3(lo, lo + s, lo + 2 * s, array); 1376: mid = med3(mid - s, mid, mid + s, array); 1377: hi = med3(hi - 2 * s, hi - s, hi, array); 1378: } 1379: mid = med3(lo, mid, hi, array); 1380: 1381: int a, b, c, d; 1382: int comp; 1383: 1384: // Pull the median element out of the fray, and use it as a pivot. 1385: swap(from, mid, array); 1386: a = b = from; 1387: c = d = from + count - 1; 1388: 1389: // Repeatedly move b and c to each other, swapping elements so 1390: // that all elements before index b are less than the pivot, and all 1391: // elements after index c are greater than the pivot. a and b track 1392: // the elements equal to the pivot. 1393: while (true) 1394: { 1395: while (b <= c && (comp = array[b] - array[from]) <= 0) 1396: { 1397: if (comp == 0) 1398: { 1399: swap(a, b, array); 1400: a++; 1401: } 1402: b++; 1403: } 1404: while (c >= b && (comp = array[c] - array[from]) >= 0) 1405: { 1406: if (comp == 0) 1407: { 1408: swap(c, d, array); 1409: d--; 1410: } 1411: c--; 1412: } 1413: if (b > c) 1414: break; 1415: swap(b, c, array); 1416: b++; 1417: c--; 1418: } 1419: 1420: // Swap pivot(s) back in place, the recurse on left and right sections. 1421: hi = from + count; 1422: int span; 1423: span = Math.min(a - from, b - a); 1424: vecswap(from, b - span, span, array); 1425: 1426: span = Math.min(d - c, hi - d - 1); 1427: vecswap(b, hi - span, span, array); 1428: 1429: span = b - a; 1430: if (span > 1) 1431: qsort(array, from, span); 1432: 1433: span = d - c; 1434: if (span > 1) 1435: qsort(array, hi - span, span); 1436: } 1437: 1438: /** 1439: * Performs a stable sort on the elements, arranging them according to their 1440: * natural order. 1441: * 1442: * @param a the int array to sort 1443: */ 1444: public static void sort(int[] a) 1445: { 1446: qsort(a, 0, a.length); 1447: } 1448: 1449: /** 1450: * Performs a stable sort on the elements, arranging them according to their 1451: * natural order. 1452: * 1453: * @param a the int array to sort 1454: * @param fromIndex the first index to sort (inclusive) 1455: * @param toIndex the last index to sort (exclusive) 1456: * @throws IllegalArgumentException if fromIndex > toIndex 1457: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1458: * || toIndex > a.length 1459: */ 1460: public static void sort(int[] a, int fromIndex, int toIndex) 1461: { 1462: if (fromIndex > toIndex) 1463: throw new IllegalArgumentException(); 1464: if (fromIndex < 0) 1465: throw new ArrayIndexOutOfBoundsException(); 1466: qsort(a, fromIndex, toIndex - fromIndex); 1467: } 1468: 1469: /** 1470: * Finds the index of the median of three array elements. 1471: * 1472: * @param a the first index 1473: * @param b the second index 1474: * @param c the third index 1475: * @param d the array 1476: * @return the index (a, b, or c) which has the middle value of the three 1477: */ 1478: private static int med3(int a, int b, int c, int[] d) 1479: { 1480: return (d[a] < d[b] 1481: ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1482: : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1483: } 1484: 1485: /** 1486: * Swaps the elements at two locations of an array 1487: * 1488: * @param i the first index 1489: * @param j the second index 1490: * @param a the array 1491: */ 1492: private static void swap(int i, int j, int[] a) 1493: { 1494: int c = a[i]; 1495: a[i] = a[j]; 1496: a[j] = c; 1497: } 1498: 1499: /** 1500: * Swaps two ranges of an array. 1501: * 1502: * @param i the first range start 1503: * @param j the second range start 1504: * @param n the element count 1505: * @param a the array 1506: */ 1507: private static void vecswap(int i, int j, int n, int[] a) 1508: { 1509: for ( ; n > 0; i++, j++, n--) 1510: swap(i, j, a); 1511: } 1512: 1513: /** 1514: * Compares two integers in natural order, since a - b is inadequate. 1515: * 1516: * @param a the first int 1517: * @param b the second int 1518: * @return < 0, 0, or > 0 accorting to the comparison 1519: */ 1520: private static int compare(int a, int b) 1521: { 1522: return a < b ? -1 : a == b ? 0 : 1; 1523: } 1524: 1525: /** 1526: * Performs a recursive modified quicksort. 1527: * 1528: * @param array the array to sort 1529: * @param from the start index (inclusive) 1530: * @param count the number of elements to sort 1531: */ 1532: private static void qsort(int[] array, int from, int count) 1533: { 1534: // Use an insertion sort on small arrays. 1535: if (count <= 7) 1536: { 1537: for (int i = from + 1; i < from + count; i++) 1538: for (int j = i; j > from && array[j - 1] > array[j]; j--) 1539: swap(j, j - 1, array); 1540: return; 1541: } 1542: 1543: // Determine a good median element. 1544: int mid = count / 2; 1545: int lo = from; 1546: int hi = from + count - 1; 1547: 1548: if (count > 40) 1549: { // big arrays, pseudomedian of 9 1550: int s = count / 8; 1551: lo = med3(lo, lo + s, lo + 2 * s, array); 1552: mid = med3(mid - s, mid, mid + s, array); 1553: hi = med3(hi - 2 * s, hi - s, hi, array); 1554: } 1555: mid = med3(lo, mid, hi, array); 1556: 1557: int a, b, c, d; 1558: int comp; 1559: 1560: // Pull the median element out of the fray, and use it as a pivot. 1561: swap(from, mid, array); 1562: a = b = from; 1563: c = d = from + count - 1; 1564: 1565: // Repeatedly move b and c to each other, swapping elements so 1566: // that all elements before index b are less than the pivot, and all 1567: // elements after index c are greater than the pivot. a and b track 1568: // the elements equal to the pivot. 1569: while (true) 1570: { 1571: while (b <= c && (comp = compare(array[b], array[from])) <= 0) 1572: { 1573: if (comp == 0) 1574: { 1575: swap(a, b, array); 1576: a++; 1577: } 1578: b++; 1579: } 1580: while (c >= b && (comp = compare(array[c], array[from])) >= 0) 1581: { 1582: if (comp == 0) 1583: { 1584: swap(c, d, array); 1585: d--; 1586: } 1587: c--; 1588: } 1589: if (b > c) 1590: break; 1591: swap(b, c, array); 1592: b++; 1593: c--; 1594: } 1595: 1596: // Swap pivot(s) back in place, the recurse on left and right sections. 1597: hi = from + count; 1598: int span; 1599: span = Math.min(a - from, b - a); 1600: vecswap(from, b - span, span, array); 1601: 1602: span = Math.min(d - c, hi - d - 1); 1603: vecswap(b, hi - span, span, array); 1604: 1605: span = b - a; 1606: if (span > 1) 1607: qsort(array, from, span); 1608: 1609: span = d - c; 1610: if (span > 1) 1611: qsort(array, hi - span, span); 1612: } 1613: 1614: /** 1615: * Performs a stable sort on the elements, arranging them according to their 1616: * natural order. 1617: * 1618: * @param a the long array to sort 1619: */ 1620: public static void sort(long[] a) 1621: { 1622: qsort(a, 0, a.length); 1623: } 1624: 1625: /** 1626: * Performs a stable sort on the elements, arranging them according to their 1627: * natural order. 1628: * 1629: * @param a the long array to sort 1630: * @param fromIndex the first index to sort (inclusive) 1631: * @param toIndex the last index to sort (exclusive) 1632: * @throws IllegalArgumentException if fromIndex > toIndex 1633: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1634: * || toIndex > a.length 1635: */ 1636: public static void sort(long[] a, int fromIndex, int toIndex) 1637: { 1638: if (fromIndex > toIndex) 1639: throw new IllegalArgumentException(); 1640: if (fromIndex < 0) 1641: throw new ArrayIndexOutOfBoundsException(); 1642: qsort(a, fromIndex, toIndex - fromIndex); 1643: } 1644: 1645: /** 1646: * Finds the index of the median of three array elements. 1647: * 1648: * @param a the first index 1649: * @param b the second index 1650: * @param c the third index 1651: * @param d the array 1652: * @return the index (a, b, or c) which has the middle value of the three 1653: */ 1654: private static int med3(int a, int b, int c, long[] d) 1655: { 1656: return (d[a] < d[b] 1657: ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a) 1658: : (d[b] > d[c] ? b : d[a] > d[c] ? c : a)); 1659: } 1660: 1661: /** 1662: * Swaps the elements at two locations of an array 1663: * 1664: * @param i the first index 1665: * @param j the second index 1666: * @param a the array 1667: */ 1668: private static void swap(int i, int j, long[] a) 1669: { 1670: long c = a[i]; 1671: a[i] = a[j]; 1672: a[j] = c; 1673: } 1674: 1675: /** 1676: * Swaps two ranges of an array. 1677: * 1678: * @param i the first range start 1679: * @param j the second range start 1680: * @param n the element count 1681: * @param a the array 1682: */ 1683: private static void vecswap(int i, int j, int n, long[] a) 1684: { 1685: for ( ; n > 0; i++, j++, n--) 1686: swap(i, j, a); 1687: } 1688: 1689: /** 1690: * Compares two longs in natural order, since a - b is inadequate. 1691: * 1692: * @param a the first long 1693: * @param b the second long 1694: * @return < 0, 0, or > 0 accorting to the comparison 1695: */ 1696: private static int compare(long a, long b) 1697: { 1698: return a < b ? -1 : a == b ? 0 : 1; 1699: } 1700: 1701: /** 1702: * Performs a recursive modified quicksort. 1703: * 1704: * @param array the array to sort 1705: * @param from the start index (inclusive) 1706: * @param count the number of elements to sort 1707: */ 1708: private static void qsort(long[] array, int from, int count) 1709: { 1710: // Use an insertion sort on small arrays. 1711: if (count <= 7) 1712: { 1713: for (int i = from + 1; i < from + count; i++) 1714: for (int j = i; j > from && array[j - 1] > array[j]; j--) 1715: swap(j, j - 1, array); 1716: return; 1717: } 1718: 1719: // Determine a good median element. 1720: int mid = count / 2; 1721: int lo = from; 1722: int hi = from + count - 1; 1723: 1724: if (count > 40) 1725: { // big arrays, pseudomedian of 9 1726: int s = count / 8; 1727: lo = med3(lo, lo + s, lo + 2 * s, array); 1728: mid = med3(mid - s, mid, mid + s, array); 1729: hi = med3(hi - 2 * s, hi - s, hi, array); 1730: } 1731: mid = med3(lo, mid, hi, array); 1732: 1733: int a, b, c, d; 1734: int comp; 1735: 1736: // Pull the median element out of the fray, and use it as a pivot. 1737: swap(from, mid, array); 1738: a = b = from; 1739: c = d = from + count - 1; 1740: 1741: // Repeatedly move b and c to each other, swapping elements so 1742: // that all elements before index b are less than the pivot, and all 1743: // elements after index c are greater than the pivot. a and b track 1744: // the elements equal to the pivot. 1745: while (true) 1746: { 1747: while (b <= c && (comp = compare(array[b], array[from])) <= 0) 1748: { 1749: if (comp == 0) 1750: { 1751: swap(a, b, array); 1752: a++; 1753: } 1754: b++; 1755: } 1756: while (c >= b && (comp = compare(array[c], array[from])) >= 0) 1757: { 1758: if (comp == 0) 1759: { 1760: swap(c, d, array); 1761: d--; 1762: } 1763: c--; 1764: } 1765: if (b > c) 1766: break; 1767: swap(b, c, array); 1768: b++; 1769: c--; 1770: } 1771: 1772: // Swap pivot(s) back in place, the recurse on left and right sections. 1773: hi = from + count; 1774: int span; 1775: span = Math.min(a - from, b - a); 1776: vecswap(from, b - span, span, array); 1777: 1778: span = Math.min(d - c, hi - d - 1); 1779: vecswap(b, hi - span, span, array); 1780: 1781: span = b - a; 1782: if (span > 1) 1783: qsort(array, from, span); 1784: 1785: span = d - c; 1786: if (span > 1) 1787: qsort(array, hi - span, span); 1788: } 1789: 1790: /** 1791: * Performs a stable sort on the elements, arranging them according to their 1792: * natural order. 1793: * 1794: * @param a the float array to sort 1795: */ 1796: public static void sort(float[] a) 1797: { 1798: qsort(a, 0, a.length); 1799: } 1800: 1801: /** 1802: * Performs a stable sort on the elements, arranging them according to their 1803: * natural order. 1804: * 1805: * @param a the float array to sort 1806: * @param fromIndex the first index to sort (inclusive) 1807: * @param toIndex the last index to sort (exclusive) 1808: * @throws IllegalArgumentException if fromIndex > toIndex 1809: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1810: * || toIndex > a.length 1811: */ 1812: public static void sort(float[] a, int fromIndex, int toIndex) 1813: { 1814: if (fromIndex > toIndex) 1815: throw new IllegalArgumentException(); 1816: if (fromIndex < 0) 1817: throw new ArrayIndexOutOfBoundsException(); 1818: qsort(a, fromIndex, toIndex - fromIndex); 1819: } 1820: 1821: /** 1822: * Finds the index of the median of three array elements. 1823: * 1824: * @param a the first index 1825: * @param b the second index 1826: * @param c the third index 1827: * @param d the array 1828: * @return the index (a, b, or c) which has the middle value of the three 1829: */ 1830: private static int med3(int a, int b, int c, float[] d) 1831: { 1832: return (Float.compare(d[a], d[b]) < 0 1833: ? (Float.compare(d[b], d[c]) < 0 ? b 1834: : Float.compare(d[a], d[c]) < 0 ? c : a) 1835: : (Float.compare(d[b], d[c]) > 0 ? b 1836: : Float.compare(d[a], d[c]) > 0 ? c : a)); 1837: } 1838: 1839: /** 1840: * Swaps the elements at two locations of an array 1841: * 1842: * @param i the first index 1843: * @param j the second index 1844: * @param a the array 1845: */ 1846: private static void swap(int i, int j, float[] a) 1847: { 1848: float c = a[i]; 1849: a[i] = a[j]; 1850: a[j] = c; 1851: } 1852: 1853: /** 1854: * Swaps two ranges of an array. 1855: * 1856: * @param i the first range start 1857: * @param j the second range start 1858: * @param n the element count 1859: * @param a the array 1860: */ 1861: private static void vecswap(int i, int j, int n, float[] a) 1862: { 1863: for ( ; n > 0; i++, j++, n--) 1864: swap(i, j, a); 1865: } 1866: 1867: /** 1868: * Performs a recursive modified quicksort. 1869: * 1870: * @param array the array to sort 1871: * @param from the start index (inclusive) 1872: * @param count the number of elements to sort 1873: */ 1874: private static void qsort(float[] array, int from, int count) 1875: { 1876: // Use an insertion sort on small arrays. 1877: if (count <= 7) 1878: { 1879: for (int i = from + 1; i < from + count; i++) 1880: for (int j = i; 1881: j > from && Float.compare(array[j - 1], array[j]) > 0; 1882: j--) 1883: { 1884: swap(j, j - 1, array); 1885: } 1886: return; 1887: } 1888: 1889: // Determine a good median element. 1890: int mid = count / 2; 1891: int lo = from; 1892: int hi = from + count - 1; 1893: 1894: if (count > 40) 1895: { // big arrays, pseudomedian of 9 1896: int s = count / 8; 1897: lo = med3(lo, lo + s, lo + 2 * s, array); 1898: mid = med3(mid - s, mid, mid + s, array); 1899: hi = med3(hi - 2 * s, hi - s, hi, array); 1900: } 1901: mid = med3(lo, mid, hi, array); 1902: 1903: int a, b, c, d; 1904: int comp; 1905: 1906: // Pull the median element out of the fray, and use it as a pivot. 1907: swap(from, mid, array); 1908: a = b = from; 1909: c = d = from + count - 1; 1910: 1911: // Repeatedly move b and c to each other, swapping elements so 1912: // that all elements before index b are less than the pivot, and all 1913: // elements after index c are greater than the pivot. a and b track 1914: // the elements equal to the pivot. 1915: while (true) 1916: { 1917: while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0) 1918: { 1919: if (comp == 0) 1920: { 1921: swap(a, b, array); 1922: a++; 1923: } 1924: b++; 1925: } 1926: while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0) 1927: { 1928: if (comp == 0) 1929: { 1930: swap(c, d, array); 1931: d--; 1932: } 1933: c--; 1934: } 1935: if (b > c) 1936: break; 1937: swap(b, c, array); 1938: b++; 1939: c--; 1940: } 1941: 1942: // Swap pivot(s) back in place, the recurse on left and right sections. 1943: hi = from + count; 1944: int span; 1945: span = Math.min(a - from, b - a); 1946: vecswap(from, b - span, span, array); 1947: 1948: span = Math.min(d - c, hi - d - 1); 1949: vecswap(b, hi - span, span, array); 1950: 1951: span = b - a; 1952: if (span > 1) 1953: qsort(array, from, span); 1954: 1955: span = d - c; 1956: if (span > 1) 1957: qsort(array, hi - span, span); 1958: } 1959: 1960: /** 1961: * Performs a stable sort on the elements, arranging them according to their 1962: * natural order. 1963: * 1964: * @param a the double array to sort 1965: */ 1966: public static void sort(double[] a) 1967: { 1968: qsort(a, 0, a.length); 1969: } 1970: 1971: /** 1972: * Performs a stable sort on the elements, arranging them according to their 1973: * natural order. 1974: * 1975: * @param a the double array to sort 1976: * @param fromIndex the first index to sort (inclusive) 1977: * @param toIndex the last index to sort (exclusive) 1978: * @throws IllegalArgumentException if fromIndex > toIndex 1979: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 1980: * || toIndex > a.length 1981: */ 1982: public static void sort(double[] a, int fromIndex, int toIndex) 1983: { 1984: if (fromIndex > toIndex) 1985: throw new IllegalArgumentException(); 1986: if (fromIndex < 0) 1987: throw new ArrayIndexOutOfBoundsException(); 1988: qsort(a, fromIndex, toIndex - fromIndex); 1989: } 1990: 1991: /** 1992: * Finds the index of the median of three array elements. 1993: * 1994: * @param a the first index 1995: * @param b the second index 1996: * @param c the third index 1997: * @param d the array 1998: * @return the index (a, b, or c) which has the middle value of the three 1999: */ 2000: private static int med3(int a, int b, int c, double[] d) 2001: { 2002: return (Double.compare(d[a], d[b]) < 0 2003: ? (Double.compare(d[b], d[c]) < 0 ? b 2004: : Double.compare(d[a], d[c]) < 0 ? c : a) 2005: : (Double.compare(d[b], d[c]) > 0 ? b 2006: : Double.compare(d[a], d[c]) > 0 ? c : a)); 2007: } 2008: 2009: /** 2010: * Swaps the elements at two locations of an array 2011: * 2012: * @param i the first index 2013: * @param j the second index 2014: * @param a the array 2015: */ 2016: private static void swap(int i, int j, double[] a) 2017: { 2018: double c = a[i]; 2019: a[i] = a[j]; 2020: a[j] = c; 2021: } 2022: 2023: /** 2024: * Swaps two ranges of an array. 2025: * 2026: * @param i the first range start 2027: * @param j the second range start 2028: * @param n the element count 2029: * @param a the array 2030: */ 2031: private static void vecswap(int i, int j, int n, double[] a) 2032: { 2033: for ( ; n > 0; i++, j++, n--) 2034: swap(i, j, a); 2035: } 2036: 2037: /** 2038: * Performs a recursive modified quicksort. 2039: * 2040: * @param array the array to sort 2041: * @param from the start index (inclusive) 2042: * @param count the number of elements to sort 2043: */ 2044: private static void qsort(double[] array, int from, int count) 2045: { 2046: // Use an insertion sort on small arrays. 2047: if (count <= 7) 2048: { 2049: for (int i = from + 1; i < from + count; i++) 2050: for (int j = i; 2051: j > from && Double.compare(array[j - 1], array[j]) > 0; 2052: j--) 2053: { 2054: swap(j, j - 1, array); 2055: } 2056: return; 2057: } 2058: 2059: // Determine a good median element. 2060: int mid = count / 2; 2061: int lo = from; 2062: int hi = from + count - 1; 2063: 2064: if (count > 40) 2065: { // big arrays, pseudomedian of 9 2066: int s = count / 8; 2067: lo = med3(lo, lo + s, lo + 2 * s, array); 2068: mid = med3(mid - s, mid, mid + s, array); 2069: hi = med3(hi - 2 * s, hi - s, hi, array); 2070: } 2071: mid = med3(lo, mid, hi, array); 2072: 2073: int a, b, c, d; 2074: int comp; 2075: 2076: // Pull the median element out of the fray, and use it as a pivot. 2077: swap(from, mid, array); 2078: a = b = from; 2079: c = d = from + count - 1; 2080: 2081: // Repeatedly move b and c to each other, swapping elements so 2082: // that all elements before index b are less than the pivot, and all 2083: // elements after index c are greater than the pivot. a and b track 2084: // the elements equal to the pivot. 2085: while (true) 2086: { 2087: while (b <= c && (comp = Double.compare(array[b], array[from])) <= 0) 2088: { 2089: if (comp == 0) 2090: { 2091: swap(a, b, array); 2092: a++; 2093: } 2094: b++; 2095: } 2096: while (c >= b && (comp = Double.compare(array[c], array[from])) >= 0) 2097: { 2098: if (comp == 0) 2099: { 2100: swap(c, d, array); 2101: d--; 2102: } 2103: c--; 2104: } 2105: if (b > c) 2106: break; 2107: swap(b, c, array); 2108: b++; 2109: c--; 2110: } 2111: 2112: // Swap pivot(s) back in place, the recurse on left and right sections. 2113: hi = from + count; 2114: int span; 2115: span = Math.min(a - from, b - a); 2116: vecswap(from, b - span, span, array); 2117: 2118: span = Math.min(d - c, hi - d - 1); 2119: vecswap(b, hi - span, span, array); 2120: 2121: span = b - a; 2122: if (span > 1) 2123: qsort(array, from, span); 2124: 2125: span = d - c; 2126: if (span > 1) 2127: qsort(array, hi - span, span); 2128: } 2129: 2130: /** 2131: * Sort an array of Objects according to their natural ordering. The sort is 2132: * guaranteed to be stable, that is, equal elements will not be reordered. 2133: * The sort algorithm is a mergesort with the merge omitted if the last 2134: * element of one half comes before the first element of the other half. This 2135: * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2136: * copy of the array. 2137: * 2138: * @param a the array to be sorted 2139: * @throws ClassCastException if any two elements are not mutually 2140: * comparable 2141: * @throws NullPointerException if an element is null (since 2142: * null.compareTo cannot work) 2143: * @see Comparable 2144: */ 2145: public static void sort(Object[] a) 2146: { 2147: sort(a, 0, a.length, null); 2148: } 2149: 2150: /** 2151: * Sort an array of Objects according to a Comparator. The sort is 2152: * guaranteed to be stable, that is, equal elements will not be reordered. 2153: * The sort algorithm is a mergesort with the merge omitted if the last 2154: * element of one half comes before the first element of the other half. This 2155: * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2156: * copy of the array. 2157: * 2158: * @param a the array to be sorted 2159: * @param c a Comparator to use in sorting the array; or null to indicate 2160: * the elements' natural order 2161: * @throws ClassCastException if any two elements are not mutually 2162: * comparable by the Comparator provided 2163: * @throws NullPointerException if a null element is compared with natural 2164: * ordering (only possible when c is null) 2165: */ 2166: public static void sort(Object[] a, Comparator c) 2167: { 2168: sort(a, 0, a.length, c); 2169: } 2170: 2171: /** 2172: * Sort an array of Objects according to their natural ordering. The sort is 2173: * guaranteed to be stable, that is, equal elements will not be reordered. 2174: * The sort algorithm is a mergesort with the merge omitted if the last 2175: * element of one half comes before the first element of the other half. This 2176: * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2177: * copy of the array. 2178: * 2179: * @param a the array to be sorted 2180: * @param fromIndex the index of the first element to be sorted 2181: * @param toIndex the index of the last element to be sorted plus one 2182: * @throws ClassCastException if any two elements are not mutually 2183: * comparable 2184: * @throws NullPointerException if an element is null (since 2185: * null.compareTo cannot work) 2186: * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex 2187: * are not in range. 2188: * @throws IllegalArgumentException if fromIndex > toIndex 2189: */ 2190: public static void sort(Object[] a, int fromIndex, int toIndex) 2191: { 2192: sort(a, fromIndex, toIndex, null); 2193: } 2194: 2195: /** 2196: * Sort an array of Objects according to a Comparator. The sort is 2197: * guaranteed to be stable, that is, equal elements will not be reordered. 2198: * The sort algorithm is a mergesort with the merge omitted if the last 2199: * element of one half comes before the first element of the other half. This 2200: * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a 2201: * copy of the array. 2202: * 2203: * @param a the array to be sorted 2204: * @param fromIndex the index of the first element to be sorted 2205: * @param toIndex the index of the last element to be sorted plus one 2206: * @param c a Comparator to use in sorting the array; or null to indicate 2207: * the elements' natural order 2208: * @throws ClassCastException if any two elements are not mutually 2209: * comparable by the Comparator provided 2210: * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex 2211: * are not in range. 2212: * @throws IllegalArgumentException if fromIndex > toIndex 2213: * @throws NullPointerException if a null element is compared with natural 2214: * ordering (only possible when c is null) 2215: */ 2216: public static void sort(Object[] a, int fromIndex, int toIndex, Comparator c) 2217: { 2218: if (fromIndex > toIndex) 2219: throw new IllegalArgumentException("fromIndex " + fromIndex 2220: + " > toIndex " + toIndex); 2221: if (fromIndex < 0) 2222: throw new ArrayIndexOutOfBoundsException(); 2223: 2224: // In general, the code attempts to be simple rather than fast, the 2225: // idea being that a good optimising JIT will be able to optimise it 2226: // better than I can, and if I try it will make it more confusing for 2227: // the JIT. First presort the array in chunks of length 6 with insertion 2228: // sort. A mergesort would give too much overhead for this length. 2229: for (int chunk = fromIndex; chunk < toIndex; chunk += 6) 2230: { 2231: int end = Math.min(chunk + 6, toIndex); 2232: for (int i = chunk + 1; i < end; i++) 2233: { 2234: if (Collections.compare(a[i - 1], a[i], c) > 0) 2235: { 2236: // not already sorted 2237: int j = i; 2238: Object elem = a[j]; 2239: do 2240: { 2241: a[j] = a[j - 1]; 2242: j--; 2243: } 2244: while (j > chunk 2245: && Collections.compare(a[j - 1], elem, c) > 0); 2246: a[j] = elem; 2247: } 2248: } 2249: } 2250: 2251: int len = toIndex - fromIndex; 2252: // If length is smaller or equal 6 we are done. 2253: if (len <= 6) 2254: return; 2255: 2256: Object[] src = a; 2257: Object[] dest = new Object[len]; 2258: Object[] t = null; // t is used for swapping src and dest 2259: 2260: // The difference of the fromIndex of the src and dest array. 2261: int srcDestDiff = -fromIndex; 2262: 2263: // The merges are done in this loop 2264: for (int size = 6; size < len; size <<= 1) 2265: { 2266: for (int start = fromIndex; start < toIndex; start += size << 1) 2267: { 2268: // mid is the start of the second sublist; 2269: // end the start of the next sublist (or end of array). 2270: int mid = start + size; 2271: int end = Math.min(toIndex, mid + size); 2272: 2273: // The second list is empty or the elements are already in 2274: // order - no need to merge 2275: if (mid >= end 2276: || Collections.compare(src[mid - 1], src[mid], c) <= 0) 2277: { 2278: System.arraycopy(src, start, 2279: dest, start + srcDestDiff, end - start); 2280: 2281: // The two halves just need swapping - no need to merge 2282: } 2283: else if (Collections.compare(src[start], src[end - 1], c) > 0) 2284: { 2285: System.arraycopy(src, start, 2286: dest, end - size + srcDestDiff, size); 2287: System.arraycopy(src, mid, 2288: dest, start + srcDestDiff, end - mid); 2289: 2290: } 2291: else 2292: { 2293: // Declare a lot of variables to save repeating 2294: // calculations. Hopefully a decent JIT will put these 2295: // in registers and make this fast 2296: int p1 = start; 2297: int p2 = mid; 2298: int i = start + srcDestDiff; 2299: 2300: // The main merge loop; terminates as soon as either 2301: // half is ended 2302: while (p1 < mid && p2 < end) 2303: { 2304: dest[i++] = 2305: src[(Collections.compare(src[p1], src[p2], c) <= 0 2306: ? p1++ : p2++)]; 2307: } 2308: 2309: // Finish up by copying the remainder of whichever half 2310: // wasn't finished. 2311: if (p1 < mid) 2312: System.arraycopy(src, p1, dest, i, mid - p1); 2313: else 2314: System.arraycopy(src, p2, dest, i, end - p2); 2315: } 2316: } 2317: // swap src and dest ready for the next merge 2318: t = src; 2319: src = dest; 2320: dest = t; 2321: fromIndex += srcDestDiff; 2322: toIndex += srcDestDiff; 2323: srcDestDiff = -srcDestDiff; 2324: } 2325: 2326: // make sure the result ends up back in the right place. Note 2327: // that src and dest may have been swapped above, so src 2328: // contains the sorted array. 2329: if (src != a) 2330: { 2331: // Note that fromIndex == 0. 2332: System.arraycopy(src, 0, a, srcDestDiff, toIndex); 2333: } 2334: } 2335: 2336: /** 2337: * Returns a list "view" of the specified array. This method is intended to 2338: * make it easy to use the Collections API with existing array-based APIs and 2339: * programs. Changes in the list or the array show up in both places. The 2340: * list does not support element addition or removal, but does permit 2341: * value modification. The returned list implements both Serializable and 2342: * RandomAccess. 2343: * 2344: * @param a the array to return a view of 2345: * @return a fixed-size list, changes to which "write through" to the array 2346: * @see Serializable 2347: * @see RandomAccess 2348: * @see Arrays.ArrayList 2349: */ 2350: public static List asList(final Object[] a) 2351: { 2352: return new Arrays.ArrayList(a); 2353: } 2354: 2355: /** 2356: * Returns a String representation of the argument array. Returns "null" 2357: * if <code>a</code> is null. 2358: * @param a the array to represent 2359: * @return a String representing this array 2360: * @since 1.5 2361: */ 2362: public static String toString (long[] a) 2363: { 2364: if (a == null) 2365: return "null"; 2366: if (a.length == 0) 2367: return "[]"; 2368: String result = "["; 2369: for (int i = 0; i < a.length - 1; i++) 2370: result += String.valueOf(a[i]) + ", "; 2371: result += String.valueOf(a[a.length - 1]) + "]"; 2372: return result; 2373: } 2374: 2375: /** 2376: * Returns a String representation of the argument array. Returns "null" 2377: * if <code>a</code> is null. 2378: * @param a the array to represent 2379: * @return a String representing this array 2380: * @since 1.5 2381: */ 2382: public static String toString (int[] a) 2383: { 2384: if (a == null) 2385: return "null"; 2386: if (a.length == 0) 2387: return "[]"; 2388: String result = "["; 2389: for (int i = 0; i < a.length - 1; i++) 2390: result += String.valueOf(a[i]) + ", "; 2391: result += String.valueOf(a[a.length - 1]) + "]"; 2392: return result; 2393: } 2394: 2395: /** 2396: * Returns a String representation of the argument array. Returns "null" 2397: * if <code>a</code> is null. 2398: * @param a the array to represent 2399: * @return a String representing this array 2400: * @since 1.5 2401: */ 2402: public static String toString (short[] a) 2403: { 2404: if (a == null) 2405: return "null"; 2406: if (a.length == 0) 2407: return "[]"; 2408: String result = "["; 2409: for (int i = 0; i < a.length - 1; i++) 2410: result += String.valueOf(a[i]) + ", "; 2411: result += String.valueOf(a[a.length - 1]) + "]"; 2412: return result; 2413: } 2414: 2415: /** 2416: * Returns a String representation of the argument array. Returns "null" 2417: * if <code>a</code> is null. 2418: * @param a the array to represent 2419: * @return a String representing this array 2420: * @since 1.5 2421: */ 2422: public static String toString (char[] a) 2423: { 2424: if (a == null) 2425: return "null"; 2426: if (a.length == 0) 2427: return "[]"; 2428: String result = "["; 2429: for (int i = 0; i < a.length - 1; i++) 2430: result += String.valueOf(a[i]) + ", "; 2431: result += String.valueOf(a[a.length - 1]) + "]"; 2432: return result; 2433: } 2434: 2435: /** 2436: * Returns a String representation of the argument array. Returns "null" 2437: * if <code>a</code> is null. 2438: * @param a the array to represent 2439: * @return a String representing this array 2440: * @since 1.5 2441: */ 2442: public static String toString (byte[] a) 2443: { 2444: if (a == null) 2445: return "null"; 2446: if (a.length == 0) 2447: return "[]"; 2448: String result = "["; 2449: for (int i = 0; i < a.length - 1; i++) 2450: result += String.valueOf(a[i]) + ", "; 2451: result += String.valueOf(a[a.length - 1]) + "]"; 2452: return result; 2453: } 2454: 2455: /** 2456: * Returns a String representation of the argument array. Returns "null" 2457: * if <code>a</code> is null. 2458: * @param a the array to represent 2459: * @return a String representing this array 2460: * @since 1.5 2461: */ 2462: public static String toString (boolean[] a) 2463: { 2464: if (a == null) 2465: return "null"; 2466: if (a.length == 0) 2467: return "[]"; 2468: String result = "["; 2469: for (int i = 0; i < a.length - 1; i++) 2470: result += String.valueOf(a[i]) + ", "; 2471: result += String.valueOf(a[a.length - 1]) + "]"; 2472: return result; 2473: } 2474: 2475: /** 2476: * Returns a String representation of the argument array. Returns "null" 2477: * if <code>a</code> is null. 2478: * @param a the array to represent 2479: * @return a String representing this array 2480: * @since 1.5 2481: */ 2482: public static String toString (float[] a) 2483: { 2484: if (a == null) 2485: return "null"; 2486: if (a.length == 0) 2487: return "[]"; 2488: String result = "["; 2489: for (int i = 0; i < a.length - 1; i++) 2490: result += String.valueOf(a[i]) + ", "; 2491: result += String.valueOf(a[a.length - 1]) + "]"; 2492: return result; 2493: } 2494: 2495: /** 2496: * Returns a String representation of the argument array. Returns "null" 2497: * if <code>a</code> is null. 2498: * @param a the array to represent 2499: * @return a String representing this array 2500: * @since 1.5 2501: */ 2502: public static String toString (double[] a) 2503: { 2504: if (a == null) 2505: return "null"; 2506: if (a.length == 0) 2507: return "[]"; 2508: String result = "["; 2509: for (int i = 0; i < a.length - 1; i++) 2510: result += String.valueOf(a[i]) + ", "; 2511: result += String.valueOf(a[a.length - 1]) + "]"; 2512: return result; 2513: } 2514: 2515: /** 2516: * Returns a String representation of the argument array. Returns "null" 2517: * if <code>a</code> is null. 2518: * @param a the array to represent 2519: * @return a String representing this array 2520: * @since 1.5 2521: */ 2522: public static String toString (Object[] a) 2523: { 2524: if (a == null) 2525: return "null"; 2526: if (a.length == 0) 2527: return "[]"; 2528: String result = "["; 2529: for (int i = 0; i < a.length - 1; i++) 2530: result += String.valueOf(a[i]) + ", "; 2531: result += String.valueOf(a[a.length - 1]) + "]"; 2532: return result; 2533: } 2534: 2535: /** 2536: * Inner class used by {@link #asList(Object[])} to provide a list interface 2537: * to an array. The name, though it clashes with java.util.ArrayList, is 2538: * Sun's choice for Serialization purposes. Element addition and removal 2539: * is prohibited, but values can be modified. 2540: * 2541: * @author Eric Blake (ebb9@email.byu.edu) 2542: * @status updated to 1.4 2543: */ 2544: private static final class ArrayList extends AbstractList 2545: implements Serializable, RandomAccess 2546: { 2547: // We override the necessary methods, plus others which will be much 2548: // more efficient with direct iteration rather than relying on iterator(). 2549: 2550: /** 2551: * Compatible with JDK 1.4. 2552: */ 2553: private static final long serialVersionUID = -2764017481108945198L; 2554: 2555: /** 2556: * The array we are viewing. 2557: * @serial the array 2558: */ 2559: private final Object[] a; 2560: 2561: /** 2562: * Construct a list view of the array. 2563: * @param a the array to view 2564: * @throws NullPointerException if a is null 2565: */ 2566: ArrayList(Object[] a) 2567: { 2568: // We have to explicitly check. 2569: if (a == null) 2570: throw new NullPointerException(); 2571: this.a = a; 2572: } 2573: 2574: /** 2575: * Returns the object at the specified index in 2576: * the array. 2577: * 2578: * @param index The index to retrieve an object from. 2579: * @return The object at the array index specified. 2580: */ 2581: public Object get(int index) 2582: { 2583: return a[index]; 2584: } 2585: 2586: /** 2587: * Returns the size of the array. 2588: * 2589: * @return The size. 2590: */ 2591: public int size() 2592: { 2593: return a.length; 2594: } 2595: 2596: /** 2597: * Replaces the object at the specified index 2598: * with the supplied element. 2599: * 2600: * @param index The index at which to place the new object. 2601: * @param element The new object. 2602: * @return The object replaced by this operation. 2603: */ 2604: public Object set(int index, Object element) 2605: { 2606: Object old = a[index]; 2607: a[index] = element; 2608: return old; 2609: } 2610: 2611: /** 2612: * Returns true if the array contains the 2613: * supplied object. 2614: * 2615: * @param o The object to look for. 2616: * @return True if the object was found. 2617: */ 2618: public boolean contains(Object o) 2619: { 2620: return lastIndexOf(o) >= 0; 2621: } 2622: 2623: /** 2624: * Returns the first index at which the 2625: * object, o, occurs in the array. 2626: * 2627: * @param o The object to search for. 2628: * @return The first relevant index. 2629: */ 2630: public int indexOf(Object o) 2631: { 2632: int size = a.length; 2633: for (int i = 0; i < size; i++) 2634: if (ArrayList.equals(o, a[i])) 2635: return i; 2636: return -1; 2637: } 2638: 2639: /** 2640: * Returns the last index at which the 2641: * object, o, occurs in the array. 2642: * 2643: * @param o The object to search for. 2644: * @return The last relevant index. 2645: */ 2646: public int lastIndexOf(Object o) 2647: { 2648: int i = a.length; 2649: while (--i >= 0) 2650: if (ArrayList.equals(o, a[i])) 2651: return i; 2652: return -1; 2653: } 2654: 2655: /** 2656: * Transforms the list into an array of 2657: * objects, by simplying cloning the array 2658: * wrapped by this list. 2659: * 2660: * @return A clone of the internal array. 2661: */ 2662: public Object[] toArray() 2663: { 2664: return (Object[]) a.clone(); 2665: } 2666: 2667: /** 2668: * Copies the objects from this list into 2669: * the supplied array. The supplied array 2670: * is shrunk or enlarged to the size of the 2671: * internal array, and filled with its objects. 2672: * 2673: * @param array The array to fill with the objects in this list. 2674: * @return The array containing the objects in this list, 2675: * which may or may not be == to array. 2676: */ 2677: public Object[] toArray(Object[] array) 2678: { 2679: int size = a.length; 2680: if (array.length < size) 2681: array = (Object[]) 2682: Array.newInstance(array.getClass().getComponentType(), size); 2683: else if (array.length > size) 2684: array[size] = null; 2685: 2686: System.arraycopy(a, 0, array, 0, size); 2687: return array; 2688: } 2689: } 2690: }
GNU Classpath (0.20) |