libjava/java/util/Arrays.java

   1 /* Arrays.java -- Utility class with methods to operate on arrays
   2    Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 USA.
  20
  21 As a special exception, if you link this library with other files to
  22 produce an executable, this library does not by itself cause the
  23 resulting executable to be covered by the GNU General Public License.
  24 This exception does not however invalidate any other reasons why the
  25 executable file might be covered by the GNU General Public License. */
  26
  27
  28 // TO DO:
  29 // ~ Fix the behaviour of sort and binarySearch as applied to float and double
  30 //   arrays containing NaN values. See the JDC, bug ID 4143272.
  31
  32 package java.util;
  33
  34 /**
  35  * This class contains various static utility methods performing operations on
  36  * arrays, and a method to provide a List "view" of an array to facilitate
  37  * using arrays with Collection-based APIs.
  38  */
  39 public class Arrays {
  40
  41   /**
  42    * This class is non-instantiable.
  43    */
  44   private Arrays() {
  45   }
  46
  47   private static Comparator defaultComparator = new Comparator() {
  48     public int compare(Object o1, Object o2) {
  49       return ((Comparable)o1).compareTo(o2);
  50     }
  51   };
  52
  53   /**
  54    * Perform a binary search of a byte array for a key. The array must be
  55    * sorted (as by the sort() method) - if it is not, the behaviour of this
  56    * method is undefined, and may be an infinite loop. If the array contains
  57    * the key more than once, any one of them may be found. Note: although the
  58    * specification allows for an infinite loop if the array is unsorted, it
  59    * will not happen in this implementation.
  60    *
  61    * @param a the array to search (must be sorted)
  62    * @param key the value to search for
  63    * @returns the index at which the key was found, or -n-1 if it was not
  64    *   found, where n is the index of the first value higher than key or
  65    *   a.length if there is no such value.
  66    */
  67   public static int binarySearch(byte[] a, byte key) {
  68     int low = 0;
  69     int hi = a.length - 1;
  70     int mid = 0;
  71     while (low <= hi) {
  72       mid = (low + hi) >> 1;
  73       final byte d = a[mid];
  74       if (d == key) {
  75         return mid;
  76       } else if (d > key) {
  77         hi = mid - 1;
  78       } else {
  79         low = ++mid; // This gets the insertion point right on the last loop
  80       }
  81     }
  82     return -mid - 1;
  83   }
  84
  85   /**
  86    * Perform a binary search of a char array for a key. The array must be
  87    * sorted (as by the sort() method) - if it is not, the behaviour of this
  88    * method is undefined, and may be an infinite loop. If the array contains
  89    * the key more than once, any one of them may be found. Note: although the
  90    * specification allows for an infinite loop if the array is unsorted, it
  91    * will not happen in this implementation.
  92    *
  93    * @param a the array to search (must be sorted)
  94    * @param key the value to search for
  95    * @returns the index at which the key was found, or -n-1 if it was not
  96    *   found, where n is the index of the first value higher than key or
  97    *   a.length if there is no such value.
  98    */
  99   public static int binarySearch(char[] a, char key) {
 100     int low = 0;
 101     int hi = a.length - 1;
 102     int mid = 0;
 103     while (low <= hi) {
 104       mid = (low + hi) >> 1;
 105       final char d = a[mid];
 106       if (d == key) {
 107         return mid;
 108       } else if (d > key) {
 109         hi = mid - 1;
 110       } else {
 111         low = ++mid; // This gets the insertion point right on the last loop
 112       }
 113     }
 114     return -mid - 1;
 115   }
 116
 117   /**
 118    * Perform a binary search of a double array for a key. The array must be
 119    * sorted (as by the sort() method) - if it is not, the behaviour of this
 120    * method is undefined, and may be an infinite loop. If the array contains
 121    * the key more than once, any one of them may be found. Note: although the
 122    * specification allows for an infinite loop if the array is unsorted, it
 123    * will not happen in this implementation.
 124    *
 125    * @param a the array to search (must be sorted)
 126    * @param key the value to search for
 127    * @returns the index at which the key was found, or -n-1 if it was not
 128    *   found, where n is the index of the first value higher than key or
 129    *   a.length if there is no such value.
 130    */
 131   public static int binarySearch(double[] a, double key) {
 132     int low = 0;
 133     int hi = a.length - 1;
 134     int mid = 0;
 135     while (low <= hi) {
 136       mid = (low + hi) >> 1;
 137       final double d = a[mid];
 138       if (d == key) {
 139         return mid;
 140       } else if (d > key) {
 141         hi = mid - 1;
 142       } else {
 143         low = ++mid; // This gets the insertion point right on the last loop
 144       }
 145     }
 146     return -mid - 1;
 147   }
 148
 149   /**
 150    * Perform a binary search of a float array for a key. The array must be
 151    * sorted (as by the sort() method) - if it is not, the behaviour of this
 152    * method is undefined, and may be an infinite loop. If the array contains
 153    * the key more than once, any one of them may be found. Note: although the
 154    * specification allows for an infinite loop if the array is unsorted, it
 155    * will not happen in this implementation.
 156    *
 157    * @param a the array to search (must be sorted)
 158    * @param key the value to search for
 159    * @returns the index at which the key was found, or -n-1 if it was not
 160    *   found, where n is the index of the first value higher than key or
 161    *   a.length if there is no such value.
 162    */
 163   public static int binarySearch(float[] a, float key) {
 164     int low = 0;
 165     int hi = a.length - 1;
 166     int mid = 0;
 167     while (low <= hi) {
 168       mid = (low + hi) >> 1;
 169       final float d = a[mid];
 170       if (d == key) {
 171         return mid;
 172       } else if (d > key) {
 173         hi = mid - 1;
 174       } else {
 175         low = ++mid; // This gets the insertion point right on the last loop
 176       }
 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    * @returns 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     int low = 0;
 197     int hi = a.length - 1;
 198     int mid = 0;
 199     while (low <= hi) {
 200       mid = (low + hi) >> 1;
 201       final int d = a[mid];
 202       if (d == key) {
 203         return mid;
 204       } else if (d > key) {
 205         hi = mid - 1;
 206       } else {
 207         low = ++mid; // This gets the insertion point right on the last loop
 208       }
 209     }
 210     return -mid - 1;
 211   }
 212
 213   /**
 214    * Perform a binary search of a long array for a key. The array must be
 215    * sorted (as by the sort() method) - if it is not, the behaviour of this
 216    * method is undefined, and may be an infinite loop. If the array contains
 217    * the key more than once, any one of them may be found. Note: although the
 218    * specification allows for an infinite loop if the array is unsorted, it
 219    * will not happen in this implementation.
 220    *
 221    * @param a the array to search (must be sorted)
 222    * @param key the value to search for
 223    * @returns the index at which the key was found, or -n-1 if it was not
 224    *   found, where n is the index of the first value higher than key or
 225    *   a.length if there is no such value.
 226    */
 227   public static int binarySearch(long[] a, long key) {
 228     int low = 0;
 229     int hi = a.length - 1;
 230     int mid = 0;
 231     while (low <= hi) {
 232       mid = (low + hi) >> 1;
 233       final long d = a[mid];
 234       if (d == key) {
 235         return mid;
 236       } else if (d > key) {
 237         hi = mid - 1;
 238       } else {
 239         low = ++mid; // This gets the insertion point right on the last loop
 240       }
 241     }
 242     return -mid - 1;
 243   }
 244
 245   /**
 246    * Perform a binary search of a short array for a key. The array must be
 247    * sorted (as by the sort() method) - if it is not, the behaviour of this
 248    * method is undefined, and may be an infinite loop. If the array contains
 249    * the key more than once, any one of them may be found. Note: although the
 250    * specification allows for an infinite loop if the array is unsorted, it
 251    * will not happen in this implementation.
 252    *
 253    * @param a the array to search (must be sorted)
 254    * @param key the value to search for
 255    * @returns the index at which the key was found, or -n-1 if it was not
 256    *   found, where n is the index of the first value higher than key or
 257    *   a.length if there is no such value.
 258    */
 259   public static int binarySearch(short[] a, short key) {
 260     int low = 0;
 261     int hi = a.length - 1;
 262     int mid = 0;
 263     while (low <= hi) {
 264       mid = (low + hi) >> 1;
 265       final short d = a[mid];
 266       if (d == key) {
 267         return mid;
 268       } else if (d > key) {
 269         hi = mid - 1;
 270       } else {
 271         low = ++mid; // This gets the insertion point right on the last loop
 272       }
 273     }
 274     return -mid - 1;
 275   }
 276
 277   /**
 278    * This method does the work for the Object binary search methods.
 279    * @exception NullPointerException if the specified comparator is null.
 280    * @exception ClassCastException if the objects are not comparable by c.
 281    */
 282   private static int objectSearch(Object[] a, Object key, final Comparator c) {
 283     int low = 0;
 284     int hi = a.length - 1;
 285     int mid = 0;
 286     while (low <= hi) {
 287       mid = (low + hi) >> 1;
 288       final int d = c.compare(key, a[mid]);
 289       if (d == 0) {
 290         return mid;
 291       } else if (d < 0) {
 292         hi = mid - 1;
 293       } else {
 294         low = ++mid; // This gets the insertion point right on the last loop
 295       }
 296     }
 297     return -mid - 1;
 298   }
 299
 300   /**
 301    * Perform a binary search of an Object array for a key, using the natural
 302    * ordering of the elements. The array must be sorted (as by the sort()
 303    * method) - if it is not, the behaviour of this method is undefined, and may
 304    * be an infinite loop. Further, the key must be comparable with every item
 305    * in the array. If the array contains the key more than once, any one of
 306    * them may be found. Note: although the specification allows for an infinite
 307    * loop if the array is unsorted, it will not happen in this (JCL)
 308    * implementation.
 309    *
 310    * @param a the array to search (must be sorted)
 311    * @param key the value to search for
 312    * @returns the index at which the key was found, or -n-1 if it was not
 313    *   found, where n is the index of the first value higher than key or
 314    *   a.length if there is no such value.
 315    * @exception ClassCastException if key could not be compared with one of the
 316    *   elements of a
 317    * @exception NullPointerException if a null element has compareTo called
 318    */
 319   public static int binarySearch(Object[] a, Object key) {
 320     return objectSearch(a, key, defaultComparator);
 321   }
 322
 323   /**
 324    * Perform a binary search of an Object array for a key, using a supplied
 325    * Comparator. The array must be sorted (as by the sort() method with the
 326    * same Comparator) - if it is not, the behaviour of this method is
 327    * undefined, and may be an infinite loop. Further, the key must be
 328    * comparable with every item in the array. If the array contains the key
 329    * more than once, any one of them may be found. Note: although the
 330    * specification allows for an infinite loop if the array is unsorted, it
 331    * will not happen in this (JCL) implementation.
 332    *
 333    * @param a the array to search (must be sorted)
 334    * @param key the value to search for
 335    * @param c the comparator by which the array is sorted
 336    * @returns the index at which the key was found, or -n-1 if it was not
 337    *   found, where n is the index of the first value higher than key or
 338    *   a.length if there is no such value.
 339    * @exception ClassCastException if key could not be compared with one of the
 340    *   elements of a
 341    */
 342   public static int binarySearch(Object[] a, Object key, Comparator c) {
 343     return objectSearch(a, key, c);
 344   }
 345
 346   /**
 347    * Compare two byte arrays for equality.
 348    *
 349    * @param a1 the first array to compare
 350    * @param a2 the second array to compare
 351    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 352    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 353    */
 354   public static boolean equals(byte[] a1, byte[] a2) {
 355
 356     // Quick test which saves comparing elements of the same array, and also
 357     // catches the case that both are null.
 358     if (a1 == a2) {
 359       return true;
 360     }
 361     try {
 362
 363       // If they're the same length, test each element
 364       if (a1.length == a2.length) {
 365         for (int i = 0; i < a1.length; i++) {
 366           if (a1[i] != a2[i]) {
 367             return false;
 368           }
 369         }
 370         return true;
 371       }
 372
 373     // If a1 == null or a2 == null but not both then we will get a NullPointer
 374     } catch (NullPointerException e) {
 375     }
 376
 377     return false;
 378   }
 379
 380   /**
 381    * Compare two char arrays for equality.
 382    *
 383    * @param a1 the first array to compare
 384    * @param a2 the second array to compare
 385    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 386    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 387    */
 388   public static boolean equals(char[] a1, char[] a2) {
 389
 390     // Quick test which saves comparing elements of the same array, and also
 391     // catches the case that both are null.
 392     if (a1 == a2) {
 393       return true;
 394     }
 395     try {
 396
 397       // If they're the same length, test each element
 398       if (a1.length == a2.length) {
 399         for (int i = 0; i < a1.length; i++) {
 400           if (a1[i] != a2[i]) {
 401             return false;
 402           }
 403         }
 404         return true;
 405       }
 406
 407     // If a1 == null or a2 == null but not both then we will get a NullPointer
 408     } catch (NullPointerException e) {
 409     }
 410
 411     return false;
 412   }
 413
 414   /**
 415    * Compare two double arrays for equality.
 416    *
 417    * @param a1 the first array to compare
 418    * @param a2 the second array to compare
 419    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 420    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 421    */
 422   public static boolean equals(double[] a1, double[] a2) {
 423
 424     // Quick test which saves comparing elements of the same array, and also
 425     // catches the case that both are null.
 426     if (a1 == a2) {
 427       return true;
 428     }
 429     try {
 430
 431       // If they're the same length, test each element
 432       if (a1.length == a2.length) {
 433         for (int i = 0; i < a1.length; i++) {
 434           if (a1[i] != a2[i]) {
 435             return false;
 436           }
 437         }
 438         return true;
 439       }
 440
 441     // If a1 == null or a2 == null but not both then we will get a NullPointer
 442     } catch (NullPointerException e) {
 443     }
 444
 445     return false;
 446   }
 447
 448   /**
 449    * Compare two float arrays for equality.
 450    *
 451    * @param a1 the first array to compare
 452    * @param a2 the second array to compare
 453    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 454    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 455    */
 456   public static boolean equals(float[] a1, float[] a2) {
 457
 458     // Quick test which saves comparing elements of the same array, and also
 459     // catches the case that both are null.
 460     if (a1 == a2) {
 461       return true;
 462     }
 463     try {
 464
 465       // If they're the same length, test each element
 466       if (a1.length == a2.length) {
 467         for (int i = 0; i < a1.length; i++) {
 468           if (a1[i] != a2[i]) {
 469             return false;
 470           }
 471         }
 472         return true;
 473       }
 474
 475     // If a1 == null or a2 == null but not both then we will get a NullPointer
 476     } catch (NullPointerException e) {
 477     }
 478
 479     return false;
 480   }
 481
 482   /**
 483    * Compare two long arrays for equality.
 484    *
 485    * @param a1 the first array to compare
 486    * @param a2 the second array to compare
 487    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 488    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 489    */
 490   public static boolean equals(long[] a1, long[] a2) {
 491
 492     // Quick test which saves comparing elements of the same array, and also
 493     // catches the case that both are null.
 494     if (a1 == a2) {
 495       return true;
 496     }
 497     try {
 498
 499       // If they're the same length, test each element
 500       if (a1.length == a2.length) {
 501         for (int i = 0; i < a1.length; i++) {
 502           if (a1[i] != a2[i]) {
 503             return false;
 504           }
 505         }
 506         return true;
 507       }
 508
 509     // If a1 == null or a2 == null but not both then we will get a NullPointer
 510     } catch (NullPointerException e) {
 511     }
 512
 513     return false;
 514   }
 515
 516   /**
 517    * Compare two short arrays for equality.
 518    *
 519    * @param a1 the first array to compare
 520    * @param a2 the second array to compare
 521    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 522    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 523    */
 524   public static boolean equals(short[] a1, short[] a2) {
 525
 526     // Quick test which saves comparing elements of the same array, and also
 527     // catches the case that both are null.
 528     if (a1 == a2) {
 529       return true;
 530     }
 531     try {
 532
 533       // If they're the same length, test each element
 534       if (a1.length == a2.length) {
 535         for (int i = 0; i < a1.length; i++) {
 536           if (a1[i] != a2[i]) {
 537             return false;
 538           }
 539         }
 540         return true;
 541       }
 542
 543     // If a1 == null or a2 == null but not both then we will get a NullPointer
 544     } catch (NullPointerException e) {
 545     }
 546
 547     return false;
 548   }
 549
 550   /**
 551    * Compare two boolean arrays for equality.
 552    *
 553    * @param a1 the first array to compare
 554    * @param a2 the second array to compare
 555    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 556    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 557    */
 558   public static boolean equals(boolean[] a1, boolean[] a2) {
 559
 560     // Quick test which saves comparing elements of the same array, and also
 561     // catches the case that both are null.
 562     if (a1 == a2) {
 563       return true;
 564     }
 565     try {
 566
 567       // If they're the same length, test each element
 568       if (a1.length == a2.length) {
 569         for (int i = 0; i < a1.length; i++) {
 570           if (a1[i] != a2[i]) {
 571             return false;
 572           }
 573         }
 574         return true;
 575       }
 576
 577     // If a1 == null or a2 == null but not both then we will get a NullPointer
 578     } catch (NullPointerException e) {
 579     }
 580
 581     return false;
 582   }
 583
 584   /**
 585    * Compare two int arrays for equality.
 586    *
 587    * @param a1 the first array to compare
 588    * @param a2 the second array to compare
 589    * @returns true if a1 and a2 are both null, or if a2 is of the same length
 590    *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
 591    */
 592   public static boolean equals(int[] a1, int[] a2) {
 593
 594     // Quick test which saves comparing elements of the same array, and also
 595     // catches the case that both are null.
 596     if (a1 == a2) {
 597       return true;
 598     }
 599     try {
 600
 601       // If they're the same length, test each element
 602       if (a1.length == a2.length) {
 603         for (int i = 0; i < a1.length; i++) {
 604           if (a1[i] != a2[i]) {
 605             return false;
 606           }
 607         }
 608         return true;
 609       }
 610
 611     // If a1 == null or a2 == null but not both then we will get a NullPointer
 612     } catch (NullPointerException e) {
 613     }
 614
 615     return false;
 616   }
 617
 618   /**
 619    * Compare two Object arrays for equality.
 620    *
 621    * @param a1 the first array to compare
 622    * @param a2 the second array to compare
 623    * @returns true if a1 and a2 are both null, or if a1 is of the same length
 624    *   as a2, and for each 0 <= i < a.length, a1[i] == null ? a2[i] == null :
 625    *   a1[i].equals(a2[i]).
 626    */
 627   public static boolean equals(Object[] a1, Object[] a2) {
 628
 629     // Quick test which saves comparing elements of the same array, and also
 630     // catches the case that both are null.
 631     if (a1 == a2) {
 632       return true;
 633     }
 634     try {
 635
 636       // If they're the same length, test each element
 637       if (a1.length == a2.length) {
 638         for (int i = 0; i < a1.length; i++) {
 639           if (!(a1[i] == null ? a2[i] == null : a1[i].equals(a2[i]))) {
 640             return false;
 641           }
 642         }
 643         return true;
 644       }
 645
 646     // If a1 == null or a2 == null but not both then we will get a NullPointer
 647     } catch (NullPointerException e) {
 648     }
 649
 650     return false;
 651   }
 652
 653   /**
 654    * Fill an array with a boolean value.
 655    *
 656    * @param a the array to fill
 657    * @param val the value to fill it with
 658    */
 659   public static void fill(boolean[] a, boolean val) {
 660     // This implementation is slightly inefficient timewise, but the extra
 661     // effort over inlining it is O(1) and small, and I refuse to repeat code
 662     // if it can be helped.
 663     fill(a, 0, a.length, val);
 664   }
 665
 666   /**
 667    * Fill a range of an array with a boolean value.
 668    *
 669    * @param a the array to fill
 670    * @param fromIndex the index to fill from, inclusive
 671    * @param toIndex the index to fill to, exclusive
 672    * @param val the value to fill with
 673    */
 674   public static void fill(boolean[] a, int fromIndex, int toIndex,
 675                           boolean val) {
 676     for (int i = fromIndex; i < toIndex; i++) {
 677       a[i] = val;
 678     }
 679   }
 680
 681   /**
 682    * Fill an array with a byte value.
 683    *
 684    * @param a the array to fill
 685    * @param val the value to fill it with
 686    */
 687   public static void fill(byte[] a, byte val) {
 688     // This implementation is slightly inefficient timewise, but the extra
 689     // effort over inlining it is O(1) and small, and I refuse to repeat code
 690     // if it can be helped.
 691     fill(a, 0, a.length, val);
 692   }
 693
 694   /**
 695    * Fill a range of an array with a byte value.
 696    *
 697    * @param a the array to fill
 698    * @param fromIndex the index to fill from, inclusive
 699    * @param toIndex the index to fill to, exclusive
 700    * @param val the value to fill with
 701    */
 702   public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
 703     for (int i = fromIndex; i < toIndex; i++) {
 704       a[i] = val;
 705     }
 706   }
 707
 708   /**
 709    * Fill an array with a char value.
 710    *
 711    * @param a the array to fill
 712    * @param val the value to fill it with
 713    */
 714   public static void fill(char[] a, char val) {
 715     // This implementation is slightly inefficient timewise, but the extra
 716     // effort over inlining it is O(1) and small, and I refuse to repeat code
 717     // if it can be helped.
 718     fill(a, 0, a.length, val);
 719   }
 720
 721   /**
 722    * Fill a range of an array with a char value.
 723    *
 724    * @param a the array to fill
 725    * @param fromIndex the index to fill from, inclusive
 726    * @param toIndex the index to fill to, exclusive
 727    * @param val the value to fill with
 728    */
 729   public static void fill(char[] a, int fromIndex, int toIndex, char val) {
 730     for (int i = fromIndex; i < toIndex; i++) {
 731       a[i] = val;
 732     }
 733   }
 734
 735   /**
 736    * Fill an array with a double value.
 737    *
 738    * @param a the array to fill
 739    * @param val the value to fill it with
 740    */
 741   public static void fill(double[] a, double val) {
 742     // This implementation is slightly inefficient timewise, but the extra
 743     // effort over inlining it is O(1) and small, and I refuse to repeat code
 744     // if it can be helped.
 745     fill(a, 0, a.length, val);
 746   }
 747
 748   /**
 749    * Fill a range of an array with a double value.
 750    *
 751    * @param a the array to fill
 752    * @param fromIndex the index to fill from, inclusive
 753    * @param toIndex the index to fill to, exclusive
 754    * @param val the value to fill with
 755    */
 756   public static void fill(double[] a, int fromIndex, int toIndex, double val) {
 757     for (int i = fromIndex; i < toIndex; i++) {
 758       a[i] = val;
 759     }
 760   }
 761
 762   /**
 763    * Fill an array with a float value.
 764    *
 765    * @param a the array to fill
 766    * @param val the value to fill it with
 767    */
 768   public static void fill(float[] a, float val) {
 769     // This implementation is slightly inefficient timewise, but the extra
 770     // effort over inlining it is O(1) and small, and I refuse to repeat code
 771     // if it can be helped.
 772     fill(a, 0, a.length, val);
 773   }
 774
 775   /**
 776    * Fill a range of an array with a float value.
 777    *
 778    * @param a the array to fill
 779    * @param fromIndex the index to fill from, inclusive
 780    * @param toIndex the index to fill to, exclusive
 781    * @param val the value to fill with
 782    */
 783   public static void fill(float[] a, int fromIndex, int toIndex, float val) {
 784     for (int i = fromIndex; i < toIndex; i++) {
 785       a[i] = val;
 786     }
 787   }
 788
 789   /**
 790    * Fill an array with an int value.
 791    *
 792    * @param a the array to fill
 793    * @param val the value to fill it with
 794    */
 795   public static void fill(int[] a, int val) {
 796     // This implementation is slightly inefficient timewise, but the extra
 797     // effort over inlining it is O(1) and small, and I refuse to repeat code
 798     // if it can be helped.
 799     fill(a, 0, a.length, val);
 800   }
 801
 802   /**
 803    * Fill a range of an array with an int value.
 804    *
 805    * @param a the array to fill
 806    * @param fromIndex the index to fill from, inclusive
 807    * @param toIndex the index to fill to, exclusive
 808    * @param val the value to fill with
 809    */
 810   public static void fill(int[] a, int fromIndex, int toIndex, int val) {
 811     for (int i = fromIndex; i < toIndex; i++) {
 812       a[i] = val;
 813     }
 814   }
 815
 816   /**
 817    * Fill an array with a long value.
 818    *
 819    * @param a the array to fill
 820    * @param val the value to fill it with
 821    */
 822   public static void fill(long[] a, long val) {
 823     // This implementation is slightly inefficient timewise, but the extra
 824     // effort over inlining it is O(1) and small, and I refuse to repeat code
 825     // if it can be helped.
 826     fill(a, 0, a.length, val);
 827   }
 828
 829   /**
 830    * Fill a range of an array with a long value.
 831    *
 832    * @param a the array to fill
 833    * @param fromIndex the index to fill from, inclusive
 834    * @param toIndex the index to fill to, exclusive
 835    * @param val the value to fill with
 836    */
 837   public static void fill(long[] a, int fromIndex, int toIndex, long val) {
 838     for (int i = fromIndex; i < toIndex; i++) {
 839       a[i] = val;
 840     }
 841   }
 842
 843   /**
 844    * Fill an array with a short value.
 845    *
 846    * @param a the array to fill
 847    * @param val the value to fill it with
 848    */
 849   public static void fill(short[] a, short val) {
 850     // This implementation is slightly inefficient timewise, but the extra
 851     // effort over inlining it is O(1) and small, and I refuse to repeat code
 852     // if it can be helped.
 853     fill(a, 0, a.length, val);
 854   }
 855
 856   /**
 857    * Fill a range of an array with a short value.
 858    *
 859    * @param a the array to fill
 860    * @param fromIndex the index to fill from, inclusive
 861    * @param toIndex the index to fill to, exclusive
 862    * @param val the value to fill with
 863    */
 864   public static void fill(short[] a, int fromIndex, int toIndex, short val) {
 865     for (int i = fromIndex; i < toIndex; i++) {
 866       a[i] = val;
 867     }
 868   }
 869
 870   /**
 871    * Fill an array with an Object value.
 872    *
 873    * @param a the array to fill
 874    * @param val the value to fill it with
 875    * @exception ClassCastException if val is not an instance of the element
 876    *   type of a.
 877    */
 878   public static void fill(Object[] a, Object val) {
 879     // This implementation is slightly inefficient timewise, but the extra
 880     // effort over inlining it is O(1) and small, and I refuse to repeat code
 881     // if it can be helped.
 882     fill(a, 0, a.length, val);
 883   }
 884
 885   /**
 886    * Fill a range of an array with an Object value.
 887    *
 888    * @param a the array to fill
 889    * @param fromIndex the index to fill from, inclusive
 890    * @param toIndex the index to fill to, exclusive
 891    * @param val the value to fill with
 892    * @exception ClassCastException if val is not an instance of the element
 893    *   type of a.
 894    */
 895   public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
 896     for (int i = fromIndex; i < toIndex; i++) {
 897       a[i] = val;
 898     }
 899   }
 900
 901   // Thanks to Paul Fisher <rao@gnu.org> for finding this quicksort algorithm
 902   // as specified by Sun and porting it to Java.
 903
 904   /**
 905    * Sort a byte array into ascending order. The sort algorithm is an optimised
 906    * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
 907    * "Engineering a Sort Function", Software-Practice and Experience, Vol.
 908    * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
 909    * performance on many arrays that would take quadratic time with a standard
 910    * quicksort.
 911    *
 912    * @param a the array to sort
 913    */
 914   public static void sort(byte[] a) {
 915     qsort(a, 0, a.length);
 916   }
 917
 918   private static short cmp(byte i, byte j) {
 919     return (short)(i-j);
 920   }
 921
 922   private static int med3(int a, int b, int c, byte[] d) {
 923     return cmp(d[a], d[b]) < 0 ?
 924       (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
 925     : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
 926   }
 927
 928   private static void swap(int i, int j, byte[] a) {
 929     byte c = a[i];
 930     a[i] = a[j];
 931     a[j] = c;
 932   }
 933
 934   private static void qsort(byte[] a, int start, int n) {
 935     // use an insertion sort on small arrays
 936     if (n < 7) {
 937       for (int i = start + 1; i < start + n; i++)
 938         for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
 939           swap(j, j-1, a);
 940       return;
 941     }
 942
 943     int pm = n/2;       // small arrays, middle element
 944     if (n > 7) {
 945       int pl = start;
 946       int pn = start + n-1;
 947
 948       if (n > 40) {     // big arrays, pseudomedian of 9
 949         int s = n/8;
 950         pl = med3(pl, pl+s, pl+2*s, a);
 951         pm = med3(pm-s, pm, pm+s, a);
 952         pn = med3(pn-2*s, pn-s, pn, a);
 953       }
 954       pm = med3(pl, pm, pn, a); // mid-size, med of 3
 955     }
 956
 957     int pa, pb, pc, pd, pv;
 958     short r;
 959
 960     pv = start; swap(pv, pm, a);
 961     pa = pb = start;
 962     pc = pd = start + n-1;
 963
 964     for (;;) {
 965       while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
 966         if (r == 0) { swap(pa, pb, a); pa++; }
 967         pb++;
 968       }
 969       while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
 970         if (r == 0) { swap(pc, pd, a); pd--; }
 971         pc--;
 972       }
 973       if (pb > pc) break;
 974       swap(pb, pc, a);
 975       pb++;
 976       pc--;
 977     }
 978     int pn = start + n;
 979     int s;
 980     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
 981     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
 982     if ((s = pb-pa) > 1) qsort(a, start, s);
 983     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
 984   }
 985
 986   private static void vecswap(int i, int j, int n, byte[] a) {
 987     for (; n > 0; i++, j++, n--)
 988       swap(i, j, a);
 989   }
 990
 991   /**
 992    * Sort a char array into ascending order. The sort algorithm is an optimised
 993    * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
 994    * "Engineering a Sort Function", Software-Practice and Experience, Vol.
 995    * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
 996    * performance on many arrays that would take quadratic time with a standard
 997    * quicksort.
 998    *
 999    * @param a the array to sort
1000    */
1001   public static void sort(char[] a) {
1002     qsort(a, 0, a.length);
1003   }
1004
1005   private static int cmp(char i, char j) {
1006     return i-j;
1007   }
1008
1009   private static int med3(int a, int b, int c, char[] d) {
1010     return cmp(d[a], d[b]) < 0 ?
1011       (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
1012     : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
1013   }
1014
1015   private static void swap(int i, int j, char[] a) {
1016     char c = a[i];
1017     a[i] = a[j];
1018     a[j] = c;
1019   }
1020
1021   private static void qsort(char[] a, int start, int n) {
1022     // use an insertion sort on small arrays
1023     if (n < 7) {
1024       for (int i = start + 1; i < start + n; i++)
1025         for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
1026           swap(j, j-1, a);
1027       return;
1028     }
1029
1030     int pm = n/2;       // small arrays, middle element
1031     if (n > 7) {
1032       int pl = start;
1033       int pn = start + n-1;
1034
1035       if (n > 40) {     // big arrays, pseudomedian of 9
1036         int s = n/8;
1037         pl = med3(pl, pl+s, pl+2*s, a);
1038         pm = med3(pm-s, pm, pm+s, a);
1039         pn = med3(pn-2*s, pn-s, pn, a);
1040       }
1041       pm = med3(pl, pm, pn, a); // mid-size, med of 3
1042     }
1043
1044     int pa, pb, pc, pd, pv;
1045     int r;
1046
1047     pv = start; swap(pv, pm, a);
1048     pa = pb = start;
1049     pc = pd = start + n-1;
1050
1051     for (;;) {
1052       while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
1053         if (r == 0) { swap(pa, pb, a); pa++; }
1054         pb++;
1055       }
1056       while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
1057         if (r == 0) { swap(pc, pd, a); pd--; }
1058         pc--;
1059       }
1060       if (pb > pc) break;
1061       swap(pb, pc, a);
1062       pb++;
1063       pc--;
1064     }
1065     int pn = start + n;
1066     int s;
1067     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
1068     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
1069     if ((s = pb-pa) > 1) qsort(a, start, s);
1070     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
1071   }
1072
1073   private static void vecswap(int i, int j, int n, char[] a) {
1074     for (; n > 0; i++, j++, n--)
1075       swap(i, j, a);
1076   }
1077
1078   /**
1079    * Sort a double array into ascending order. The sort algorithm is an
1080    * optimised quicksort, as described in Jon L. Bentley and M. Douglas
1081    * McIlroy's "Engineering a Sort Function", Software-Practice and Experience,
1082    * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
1083    * performance on many arrays that would take quadratic time with a standard
1084    * quicksort. Note that this implementation, like Sun's, has undefined
1085    * behaviour if the array contains any NaN values.
1086    *
1087    * @param a the array to sort
1088    */
1089   public static void sort(double[] a) {
1090     qsort(a, 0, a.length);
1091   }
1092
1093   private static double cmp(double i, double j) {
1094     return i-j;
1095   }
1096
1097   private static int med3(int a, int b, int c, double[] d) {
1098     return cmp(d[a], d[b]) < 0 ?
1099       (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
1100     : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
1101   }
1102
1103   private static void swap(int i, int j, double[] a) {
1104     double c = a[i];
1105     a[i] = a[j];
1106     a[j] = c;
1107   }
1108
1109   private static void qsort(double[] a, int start, int n) {
1110     // use an insertion sort on small arrays
1111     if (n < 7) {
1112       for (int i = start + 1; i < start + n; i++)
1113         for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
1114           swap(j, j-1, a);
1115       return;
1116     }
1117
1118     int pm = n/2;       // small arrays, middle element
1119     if (n > 7) {
1120       int pl = start;
1121       int pn = start + n-1;
1122
1123       if (n > 40) {     // big arrays, pseudomedian of 9
1124         int s = n/8;
1125         pl = med3(pl, pl+s, pl+2*s, a);
1126         pm = med3(pm-s, pm, pm+s, a);
1127         pn = med3(pn-2*s, pn-s, pn, a);
1128       }
1129       pm = med3(pl, pm, pn, a); // mid-size, med of 3
1130     }
1131
1132     int pa, pb, pc, pd, pv;
1133     double r;
1134
1135     pv = start; swap(pv, pm, a);
1136     pa = pb = start;
1137     pc = pd = start + n-1;
1138
1139     for (;;) {
1140       while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
1141         if (r == 0) { swap(pa, pb, a); pa++; }
1142         pb++;
1143       }
1144       while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
1145         if (r == 0) { swap(pc, pd, a); pd--; }
1146         pc--;
1147       }
1148       if (pb > pc) break;
1149       swap(pb, pc, a);
1150       pb++;
1151       pc--;
1152     }
1153     int pn = start + n;
1154     int s;
1155     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
1156     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
1157     if ((s = pb-pa) > 1) qsort(a, start, s);
1158     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
1159   }
1160
1161   private static void vecswap(int i, int j, int n, double[] a) {
1162     for (; n > 0; i++, j++, n--)
1163       swap(i, j, a);
1164   }
1165
1166   /**
1167    * Sort a float array into ascending order. The sort algorithm is an
1168    * optimised quicksort, as described in Jon L. Bentley and M. Douglas
1169    * McIlroy's "Engineering a Sort Function", Software-Practice and Experience,
1170    * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
1171    * performance on many arrays that would take quadratic time with a standard
1172    * quicksort. Note that this implementation, like Sun's, has undefined
1173    * behaviour if the array contains any NaN values.
1174    *
1175    * @param a the array to sort
1176    */
1177   public static void sort(float[] a) {
1178     qsort(a, 0, a.length);
1179   }
1180
1181   private static float cmp(float i, float j) {
1182     return i-j;
1183   }
1184
1185   private static int med3(int a, int b, int c, float[] d) {
1186     return cmp(d[a], d[b]) < 0 ?
1187       (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
1188     : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
1189   }
1190
1191   private static void swap(int i, int j, float[] a) {
1192     float c = a[i];
1193     a[i] = a[j];
1194     a[j] = c;
1195   }
1196
1197   private static void qsort(float[] a, int start, int n) {
1198     // use an insertion sort on small arrays
1199     if (n < 7) {
1200       for (int i = start + 1; i < start + n; i++)
1201         for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
1202           swap(j, j-1, a);
1203       return;
1204     }
1205
1206     int pm = n/2;       // small arrays, middle element
1207     if (n > 7) {
1208       int pl = start;
1209       int pn = start + n-1;
1210
1211       if (n > 40) {     // big arrays, pseudomedian of 9
1212         int s = n/8;
1213         pl = med3(pl, pl+s, pl+2*s, a);
1214         pm = med3(pm-s, pm, pm+s, a);
1215         pn = med3(pn-2*s, pn-s, pn, a);
1216       }
1217       pm = med3(pl, pm, pn, a); // mid-size, med of 3
1218     }
1219
1220     int pa, pb, pc, pd, pv;
1221     float r;
1222
1223     pv = start; swap(pv, pm, a);
1224     pa = pb = start;
1225     pc = pd = start + n-1;
1226
1227     for (;;) {
1228       while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
1229         if (r == 0) { swap(pa, pb, a); pa++; }
1230         pb++;
1231       }
1232       while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
1233         if (r == 0) { swap(pc, pd, a); pd--; }
1234         pc--;
1235       }
1236       if (pb > pc) break;
1237       swap(pb, pc, a);
1238       pb++;
1239       pc--;
1240     }
1241     int pn = start + n;
1242     int s;
1243     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
1244     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
1245     if ((s = pb-pa) > 1) qsort(a, start, s);
1246     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
1247   }
1248
1249   private static void vecswap(int i, int j, int n, float[] a) {
1250     for (; n > 0; i++, j++, n--)
1251       swap(i, j, a);
1252   }
1253
1254   /**
1255    * Sort an int array into ascending order. The sort algorithm is an optimised
1256    * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
1257    * "Engineering a Sort Function", Software-Practice and Experience, Vol.
1258    * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
1259    * performance on many arrays that would take quadratic time with a standard
1260    * quicksort.
1261    *
1262    * @param a the array to sort
1263    */
1264   public static void sort(int[] a) {
1265     qsort(a, 0, a.length);
1266   }
1267
1268   private static long cmp(int i, int j) {
1269     return (long)i-(long)j;
1270   }
1271
1272   private static int med3(int a, int b, int c, int[] d) {
1273     return cmp(d[a], d[b]) < 0 ?
1274       (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
1275     : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
1276   }
1277
1278   private static void swap(int i, int j, int[] a) {
1279     int c = a[i];
1280     a[i] = a[j];
1281     a[j] = c;
1282   }
1283
1284   private static void qsort(int[] a, int start, int n) {
1285     // use an insertion sort on small arrays
1286     if (n < 7) {
1287       for (int i = start + 1; i < start + n; i++)
1288         for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
1289           swap(j, j-1, a);
1290       return;
1291     }
1292
1293     int pm = n/2;       // small arrays, middle element
1294     if (n > 7) {
1295       int pl = start;
1296       int pn = start + n-1;
1297
1298       if (n > 40) {     // big arrays, pseudomedian of 9
1299         int s = n/8;
1300         pl = med3(pl, pl+s, pl+2*s, a);
1301         pm = med3(pm-s, pm, pm+s, a);
1302         pn = med3(pn-2*s, pn-s, pn, a);
1303       }
1304       pm = med3(pl, pm, pn, a); // mid-size, med of 3
1305     }
1306
1307     int pa, pb, pc, pd, pv;
1308     long r;
1309
1310     pv = start; swap(pv, pm, a);
1311     pa = pb = start;
1312     pc = pd = start + n-1;
1313
1314     for (;;) {
1315       while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
1316         if (r == 0) { swap(pa, pb, a); pa++; }
1317         pb++;
1318       }
1319       while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
1320         if (r == 0) { swap(pc, pd, a); pd--; }
1321         pc--;
1322       }
1323       if (pb > pc) break;
1324       swap(pb, pc, a);
1325       pb++;
1326       pc--;
1327     }
1328     int pn = start + n;
1329     int s;
1330     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
1331     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
1332     if ((s = pb-pa) > 1) qsort(a, start, s);
1333     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
1334   }
1335
1336   private static void vecswap(int i, int j, int n, int[] a) {
1337     for (; n > 0; i++, j++, n--)
1338       swap(i, j, a);
1339   }
1340
1341   /**
1342    * Sort a long array into ascending order. The sort algorithm is an optimised
1343    * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
1344    * "Engineering a Sort Function", Software-Practice and Experience, Vol.
1345    * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
1346    * performance on many arrays that would take quadratic time with a standard
1347    * quicksort.
1348    *
1349    * @param a the array to sort
1350    */
1351   public static void sort(long[] a) {
1352     qsort(a, 0, a.length);
1353   }
1354
1355   // The "cmp" method has been removed from here and replaced with direct
1356   // compares in situ, to avoid problems with overflow if the difference
1357   // between two numbers is bigger than a long will hold.
1358   // One particular change as a result is the use of r1 and r2 in qsort
1359
1360   private static int med3(int a, int b, int c, long[] d) {
1361     return d[a] < d[b] ?
1362       (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1363     : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
1364   }
1365
1366   private static void swap(int i, int j, long[] a) {
1367     long c = a[i];
1368     a[i] = a[j];
1369     a[j] = c;
1370   }
1371
1372   private static void qsort(long[] a, int start, int n) {
1373     // use an insertion sort on small arrays
1374     if (n < 7) {
1375       for (int i = start + 1; i < start + n; i++)
1376         for (int j = i; j > 0 && a[j-1] > a[j]; j--)
1377           swap(j, j-1, a);
1378       return;
1379     }
1380
1381     int pm = n/2;       // small arrays, middle element
1382     if (n > 7) {
1383       int pl = start;
1384       int pn = start + n-1;
1385
1386       if (n > 40) {     // big arrays, pseudomedian of 9
1387         int s = n/8;
1388         pl = med3(pl, pl+s, pl+2*s, a);
1389         pm = med3(pm-s, pm, pm+s, a);
1390         pn = med3(pn-2*s, pn-s, pn, a);
1391       }
1392       pm = med3(pl, pm, pn, a); // mid-size, med of 3
1393     }
1394
1395     int pa, pb, pc, pd, pv;
1396     long r1, r2;
1397
1398     pv = start; swap(pv, pm, a);
1399     pa = pb = start;
1400     pc = pd = start + n-1;
1401
1402     for (;;) {
1403       while (pb <= pc && (r1 = a[pb]) <= (r2 = a[pv])) {
1404         if (r1 == r2) { swap(pa, pb, a); pa++; }
1405         pb++;
1406       }
1407       while (pc >= pb && (r1 = a[pc]) >= (r2 = a[pv])) {
1408         if (r1 == r2) { swap(pc, pd, a); pd--; }
1409         pc--;
1410       }
1411       if (pb > pc) break;
1412       swap(pb, pc, a);
1413       pb++;
1414       pc--;
1415     }
1416     int pn = start + n;
1417     int s;
1418     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
1419     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
1420     if ((s = pb-pa) > 1) qsort(a, start, s);
1421     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
1422   }
1423
1424   private static void vecswap(int i, int j, int n, long[] a) {
1425     for (; n > 0; i++, j++, n--)
1426       swap(i, j, a);
1427   }
1428
1429   /**
1430    * Sort a short array into ascending order. The sort algorithm is an
1431    * optimised quicksort, as described in Jon L. Bentley and M. Douglas
1432    * McIlroy's "Engineering a Sort Function", Software-Practice and Experience,
1433    * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
1434    * performance on many arrays that would take quadratic time with a standard
1435    * quicksort.
1436    *
1437    * @param a the array to sort
1438    */
1439   public static void sort(short[] a) {
1440     qsort(a, 0, a.length);
1441   }
1442
1443   private static int cmp(short i, short j) {
1444     return i-j;
1445   }
1446
1447   private static int med3(int a, int b, int c, short[] d) {
1448     return cmp(d[a], d[b]) < 0 ?
1449       (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
1450     : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
1451   }
1452
1453   private static void swap(int i, int j, short[] a) {
1454     short c = a[i];
1455     a[i] = a[j];
1456     a[j] = c;
1457   }
1458
1459   private static void qsort(short[] a, int start, int n) {
1460     // use an insertion sort on small arrays
1461     if (n < 7) {
1462       for (int i = start + 1; i < start + n; i++)
1463         for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
1464           swap(j, j-1, a);
1465       return;
1466     }
1467
1468     int pm = n/2;       // small arrays, middle element
1469     if (n > 7) {
1470       int pl = start;
1471       int pn = start + n-1;
1472
1473       if (n > 40) {     // big arrays, pseudomedian of 9
1474         int s = n/8;
1475         pl = med3(pl, pl+s, pl+2*s, a);
1476         pm = med3(pm-s, pm, pm+s, a);
1477         pn = med3(pn-2*s, pn-s, pn, a);
1478       }
1479       pm = med3(pl, pm, pn, a); // mid-size, med of 3
1480     }
1481
1482     int pa, pb, pc, pd, pv;
1483     int r;
1484
1485     pv = start; swap(pv, pm, a);
1486     pa = pb = start;
1487     pc = pd = start + n-1;
1488
1489     for (;;) {
1490       while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
1491         if (r == 0) { swap(pa, pb, a); pa++; }
1492         pb++;
1493       }
1494       while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
1495         if (r == 0) { swap(pc, pd, a); pd--; }
1496         pc--;
1497       }
1498       if (pb > pc) break;
1499       swap(pb, pc, a);
1500       pb++;
1501       pc--;
1502     }
1503     int pn = start + n;
1504     int s;
1505     s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
1506     s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
1507     if ((s = pb-pa) > 1) qsort(a, start, s);
1508     if ((s = pd-pc) > 1) qsort(a, pn-s, s);
1509   }
1510
1511   private static void vecswap(int i, int j, int n, short[] a) {
1512     for (; n > 0; i++, j++, n--)
1513       swap(i, j, a);
1514   }
1515
1516   /**
1517    * The bulk of the work for the object sort routines.  In general,
1518    * the code attempts to be simple rather than fast, the idea being
1519    * that a good optimising JIT will be able to optimise it better
1520    * than I can, and if I try it will make it more confusing for the
1521    * JIT.
1522    */
1523   private static void mergeSort(Object[] a, int from, int to, Comparator c)
1524   {
1525     // First presort the array in chunks of length 6 with insertion sort.
1526     // mergesort would give too much overhead for this length.
1527     for (int chunk = from; chunk < to; chunk += 6)
1528       {
1529         int end = Math.min(chunk+6, to);
1530         for (int i = chunk + 1; i < end; i++)
1531           {
1532             if (c.compare(a[i-1], a[i]) > 0)
1533               {
1534                 // not already sorted
1535                 int j=i;
1536                 Object elem = a[j];
1537                 do
1538                   {
1539                     a[j] = a[j-1];
1540                     j--;
1541                   }
1542                 while (j>chunk && c.compare(a[j-1], elem) > 0);
1543                 a[j] = elem;
1544               }
1545           }
1546       }
1547
1548     int len = to - from;
1549     // If length is smaller or equal 6 we are done.
1550     if (len <= 6)
1551       return;
1552
1553     Object[] src = a;
1554     Object[] dest = new Object[len];
1555     Object[] t = null; // t is used for swapping src and dest
1556
1557     // The difference of the fromIndex of the src and dest array.
1558     int srcDestDiff = -from;
1559
1560     // The merges are done in this loop
1561     for (int size = 6; size < len; size <<= 1)
1562       {
1563         for (int start = from; start < to; start += size << 1)
1564           {
1565             // mid ist the start of the second sublist;
1566             // end the start of the next sublist (or end of array).
1567             int mid = start + size;
1568             int end = Math.min(to, mid + size);
1569
1570             // The second list is empty or the elements are already in
1571             // order - no need to merge
1572             if (mid >= end || c.compare(src[mid - 1], src[mid]) <= 0) {
1573               System.arraycopy(src, start,
1574                                dest, start + srcDestDiff, end - start);
1575
1576               // The two halves just need swapping - no need to merge
1577             } else if (c.compare(src[start], src[end - 1]) > 0) {
1578               System.arraycopy(src, start,
1579                                dest, end - size + srcDestDiff, size);
1580               System.arraycopy(src, mid,
1581                                dest, start + srcDestDiff, end - mid);
1582
1583             } else {
1584               // Declare a lot of variables to save repeating
1585               // calculations.  Hopefully a decent JIT will put these
1586               // in registers and make this fast
1587               int p1 = start;
1588               int p2 = mid;
1589               int i = start + srcDestDiff;
1590
1591               // The main merge loop; terminates as soon as either
1592               // half is ended
1593               while (p1 < mid && p2 < end)
1594                 {
1595                   dest[i++] =
1596                     src[c.compare(src[p1], src[p2]) <= 0 ? p1++ : p2++];
1597                 }
1598
1599               // Finish up by copying the remainder of whichever half
1600               // wasn't finished.
1601               if (p1 < mid)
1602                 System.arraycopy(src, p1, dest, i, mid - p1);
1603               else
1604                 System.arraycopy(src, p2, dest, i, end - p2);
1605             }
1606           }
1607         // swap src and dest ready for the next merge
1608         t = src; src = dest; dest = t;
1609         from += srcDestDiff;
1610         to   += srcDestDiff;
1611         srcDestDiff = -srcDestDiff;
1612       }
1613
1614     // make sure the result ends up back in the right place.  Note
1615     // that src and dest may have been swapped above, so src
1616     // contains the sorted array.
1617     if (src != a)
1618       {
1619         // Note that from == 0.
1620         System.arraycopy(src, 0, a, srcDestDiff, to);
1621       }
1622   }
1623
1624   /**
1625    * Sort an array of Objects according to their natural ordering. The sort is
1626    * guaranteed to be stable, that is, equal elements will not be reordered.
1627    * The sort algorithm is a mergesort with the merge omitted if the last
1628    * element of one half comes before the first element of the other half. This
1629    * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
1630    * copy of the array.
1631    *
1632    * @param a the array to be sorted
1633    * @exception ClassCastException if any two elements are not mutually
1634    *   comparable
1635    * @exception NullPointerException if an element is null (since
1636    *   null.compareTo cannot work)
1637    */
1638   public static void sort(Object[] a) {
1639     mergeSort(a, 0, a.length, defaultComparator);
1640   }
1641
1642   /**
1643    * Sort an array of Objects according to a Comparator. The sort is
1644    * guaranteed to be stable, that is, equal elements will not be reordered.
1645    * The sort algorithm is a mergesort with the merge omitted if the last
1646    * element of one half comes before the first element of the other half. This
1647    * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
1648    * copy of the array.
1649    *
1650    * @param a the array to be sorted
1651    * @param c a Comparator to use in sorting the array
1652    * @exception ClassCastException if any two elements are not mutually
1653    *   comparable by the Comparator provided
1654    */
1655   public static void sort(Object[] a, Comparator c) {
1656     mergeSort(a, 0, a.length, c);
1657   }
1658
1659   /**
1660    * Sort an array of Objects according to their natural ordering. The sort is
1661    * guaranteed to be stable, that is, equal elements will not be reordered.
1662    * The sort algorithm is a mergesort with the merge omitted if the last
1663    * element of one half comes before the first element of the other half. This
1664    * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
1665    * copy of the array.
1666    *
1667    * @param a the array to be sorted
1668    * @param fromIndex the index of the first element to be sorted.
1669    * @param toIndex the index of the last element to be sorted plus one.
1670    * @exception ClassCastException if any two elements are not mutually
1671    *   comparable by the Comparator provided
1672    * @exception ArrayIndexOutOfBoundsException, if fromIndex and toIndex
1673    *   are not in range.
1674    * @exception IllegalArgumentException if fromIndex > toIndex
1675    */
1676   public static void sort(Object[] a, int fromIndex,
1677                           int toIndex) {
1678     if (fromIndex > toIndex)
1679       throw new IllegalArgumentException("fromIndex "+fromIndex
1680                                          +" > toIndex "+toIndex);
1681     mergeSort(a, fromIndex, toIndex, defaultComparator);
1682   }
1683
1684   /**
1685    * Sort an array of Objects according to a Comparator. The sort is
1686    * guaranteed to be stable, that is, equal elements will not be reordered.
1687    * The sort algorithm is a mergesort with the merge omitted if the last
1688    * element of one half comes before the first element of the other half. This
1689    * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
1690    * copy of the array.
1691    *
1692    * @param a the array to be sorted
1693    * @param fromIndex the index of the first element to be sorted.
1694    * @param toIndex the index of the last element to be sorted plus one.
1695    * @param c a Comparator to use in sorting the array
1696    * @exception ClassCastException if any two elements are not mutually
1697    *   comparable by the Comparator provided
1698    * @exception ArrayIndexOutOfBoundsException, if fromIndex and toIndex
1699    *   are not in range.
1700    * @exception IllegalArgumentException if fromIndex > toIndex
1701    */
1702   public static void sort(Object[] a, int fromIndex,
1703                           int toIndex, Comparator c) {
1704     if (fromIndex > toIndex)
1705       throw new IllegalArgumentException("fromIndex "+fromIndex
1706                                          +" > toIndex "+toIndex);
1707     mergeSort(a, fromIndex, toIndex, c);
1708   }
1709
1710   /**
1711    * Returns a list "view" of the specified array. This method is intended to
1712    * make it easy to use the Collections API with existing array-based APIs and
1713    * programs.
1714    *
1715    * @param a the array to return a view of
1716    * @returns a fixed-size list, changes to which "write through" to the array
1717    */
1718   public static List asList(final Object[] a) {
1719
1720     if (a == null) {
1721       throw new NullPointerException();
1722     }
1723
1724     return new ListImpl( a );
1725   }
1726
1727
1728   /**
1729    * Inner class used by asList(Object[]) to provide a list interface
1730    * to an array. The methods are all simple enough to be self documenting.
1731    * Note: When Sun fully specify serialized forms, this class will have to
1732    * be renamed.
1733    */
1734   private static class ListImpl extends AbstractList {
1735
1736     ListImpl(Object[] a) {
1737       this.a = a;
1738     }
1739
1740     public Object get(int index) {
1741       return a[index];
1742     }
1743
1744     public int size() {
1745       return a.length;
1746     }
1747
1748     public Object set(int index, Object element) {
1749       Object old = a[index];
1750       a[index] = element;
1751       return old;
1752     }
1753
1754     private Object[] a;
1755   }
1756
1757 }