Source for java.util.Arrays

   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 &gt; toIndex
 681:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 682:    *         || toIndex &gt; 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 &gt; toIndex
 711:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 712:    *         || toIndex &gt; 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 &gt; toIndex
 741:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 742:    *         || toIndex &gt; 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 &gt; toIndex
 771:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 772:    *         || toIndex &gt; 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 &gt; toIndex
 801:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 802:    *         || toIndex &gt; 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 &gt; toIndex
 831:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 832:    *         || toIndex &gt; 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 &gt; toIndex
 861:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 862:    *         || toIndex &gt; 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 &gt; toIndex
 891:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 892:    *         || toIndex &gt; 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 &gt; toIndex
 925:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 926:    *         || toIndex &gt; 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 &gt; toIndex
 965:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
 966:    *         || toIndex &gt; 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 &gt; toIndex
1129:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1130:    *         || toIndex &gt; 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 &gt; toIndex
1293:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1294:    *         || toIndex &gt; 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 &gt; toIndex
1457:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1458:    *         || toIndex &gt; 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 &lt; 0, 0, or &gt; 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 &gt; toIndex
1633:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1634:    *         || toIndex &gt; 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 &lt; 0, 0, or &gt; 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 &gt; toIndex
1809:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1810:    *         || toIndex &gt; 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 &gt; toIndex
1979:    * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1980:    *         || toIndex &gt; 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 &gt; 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 &gt; 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: }