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, 2006,
   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 (<code>null</code> not permitted)
2345:    * @return a fixed-size list, changes to which "write through" to the array
2346:    * 
2347:    * @throws NullPointerException if <code>a</code> is <code>null</code>.
2348:    * @see Serializable
2349:    * @see RandomAccess
2350:    * @see Arrays.ArrayList
2351:    */
2352:   public static List asList(final Object[] a)
2353:   {
2354:     return new Arrays.ArrayList(a);
2355:   }
2356: 
2357:   /** 
2358:    * Returns the hashcode of an array of long numbers.  If two arrays
2359:    * are equal, according to <code>equals()</code>, they should have the
2360:    * same hashcode.  The hashcode returned by the method is equal to that
2361:    * obtained by the corresponding <code>List</code> object.  This has the same
2362:    * data, but represents longs in their wrapper class, <code>Long</code>.
2363:    * For <code>null</code>, 0 is returned.
2364:    *
2365:    * @param v an array of long numbers for which the hash code should be
2366:    *          computed.
2367:    * @return the hash code of the array, or 0 if null was given.
2368:    * @since 1.5 
2369:    */
2370:   public static int hashCode(long[] v)
2371:   {
2372:     if (v == null)
2373:       return 0;
2374:     int result = 1;
2375:     for (int i = 0; i < v.length; ++i)
2376:       {
2377:     int elt = (int) (v[i] ^ (v[i] >>> 32));
2378:     result = 31 * result + elt;
2379:       }
2380:     return result;
2381:   }
2382: 
2383:   /** 
2384:    * Returns the hashcode of an array of integer numbers.  If two arrays
2385:    * are equal, according to <code>equals()</code>, they should have the
2386:    * same hashcode.  The hashcode returned by the method is equal to that
2387:    * obtained by the corresponding <code>List</code> object.  This has the same
2388:    * data, but represents ints in their wrapper class, <code>Integer</code>.
2389:    * For <code>null</code>, 0 is returned.
2390:    *
2391:    * @param v an array of integer numbers for which the hash code should be
2392:    *          computed.
2393:    * @return the hash code of the array, or 0 if null was given.
2394:    * @since 1.5 
2395:    */
2396:   public static int hashCode(int[] v)
2397:   {
2398:     if (v == null)
2399:       return 0;
2400:     int result = 1;
2401:     for (int i = 0; i < v.length; ++i)
2402:       result = 31 * result + v[i];
2403:     return result;
2404:   }
2405: 
2406:   /** 
2407:    * Returns the hashcode of an array of short numbers.  If two arrays
2408:    * are equal, according to <code>equals()</code>, they should have the
2409:    * same hashcode.  The hashcode returned by the method is equal to that
2410:    * obtained by the corresponding <code>List</code> object.  This has the same
2411:    * data, but represents shorts in their wrapper class, <code>Short</code>.
2412:    * For <code>null</code>, 0 is returned.
2413:    *
2414:    * @param v an array of short numbers for which the hash code should be
2415:    *          computed.
2416:    * @return the hash code of the array, or 0 if null was given.
2417:    * @since 1.5 
2418:    */
2419:   public static int hashCode(short[] v)
2420:   {
2421:     if (v == null)
2422:       return 0;
2423:     int result = 1;
2424:     for (int i = 0; i < v.length; ++i)
2425:       result = 31 * result + v[i];
2426:     return result;
2427:   }
2428: 
2429:   /** 
2430:    * Returns the hashcode of an array of characters.  If two arrays
2431:    * are equal, according to <code>equals()</code>, they should have the
2432:    * same hashcode.  The hashcode returned by the method is equal to that
2433:    * obtained by the corresponding <code>List</code> object.  This has the same
2434:    * data, but represents chars in their wrapper class, <code>Character</code>.
2435:    * For <code>null</code>, 0 is returned.
2436:    *
2437:    * @param v an array of characters for which the hash code should be
2438:    *          computed.
2439:    * @return the hash code of the array, or 0 if null was given.
2440:    * @since 1.5 
2441:    */
2442:   public static int hashCode(char[] v)
2443:   {
2444:     if (v == null)
2445:       return 0;
2446:     int result = 1;
2447:     for (int i = 0; i < v.length; ++i)
2448:       result = 31 * result + v[i];
2449:     return result;
2450:   }
2451: 
2452:   /** 
2453:    * Returns the hashcode of an array of bytes.  If two arrays
2454:    * are equal, according to <code>equals()</code>, they should have the
2455:    * same hashcode.  The hashcode returned by the method is equal to that
2456:    * obtained by the corresponding <code>List</code> object.  This has the same
2457:    * data, but represents bytes in their wrapper class, <code>Byte</code>.
2458:    * For <code>null</code>, 0 is returned.
2459:    *
2460:    * @param v an array of bytes for which the hash code should be
2461:    *          computed.
2462:    * @return the hash code of the array, or 0 if null was given.
2463:    * @since 1.5 
2464:    */
2465:   public static int hashCode(byte[] v)
2466:   {
2467:     if (v == null)
2468:       return 0;
2469:     int result = 1;
2470:     for (int i = 0; i < v.length; ++i)
2471:       result = 31 * result + v[i];
2472:     return result;
2473:   }
2474: 
2475:   /** 
2476:    * Returns the hashcode of an array of booleans.  If two arrays
2477:    * are equal, according to <code>equals()</code>, they should have the
2478:    * same hashcode.  The hashcode returned by the method is equal to that
2479:    * obtained by the corresponding <code>List</code> object.  This has the same
2480:    * data, but represents booleans in their wrapper class,
2481:    * <code>Boolean</code>.  For <code>null</code>, 0 is returned.
2482:    *
2483:    * @param v an array of booleans for which the hash code should be
2484:    *          computed.
2485:    * @return the hash code of the array, or 0 if null was given.
2486:    * @since 1.5 
2487:    */
2488:   public static int hashCode(boolean[] v)
2489:   {
2490:     if (v == null)
2491:       return 0;
2492:     int result = 1;
2493:     for (int i = 0; i < v.length; ++i)
2494:       result = 31 * result + (v[i] ? 1231 : 1237);
2495:     return result;
2496:   }
2497: 
2498:   /** 
2499:    * Returns the hashcode of an array of floats.  If two arrays
2500:    * are equal, according to <code>equals()</code>, they should have the
2501:    * same hashcode.  The hashcode returned by the method is equal to that
2502:    * obtained by the corresponding <code>List</code> object.  This has the same
2503:    * data, but represents floats in their wrapper class, <code>Float</code>.
2504:    * For <code>null</code>, 0 is returned.
2505:    *
2506:    * @param v an array of floats for which the hash code should be
2507:    *          computed.
2508:    * @return the hash code of the array, or 0 if null was given.
2509:    * @since 1.5 
2510:    */
2511:   public static int hashCode(float[] v)
2512:   {
2513:     if (v == null)
2514:       return 0;
2515:     int result = 1;
2516:     for (int i = 0; i < v.length; ++i)
2517:       result = 31 * result + Float.floatToIntBits(v[i]);
2518:     return result;
2519:   }
2520: 
2521:   /** 
2522:    * Returns the hashcode of an array of doubles.  If two arrays
2523:    * are equal, according to <code>equals()</code>, they should have the
2524:    * same hashcode.  The hashcode returned by the method is equal to that
2525:    * obtained by the corresponding <code>List</code> object.  This has the same
2526:    * data, but represents doubles in their wrapper class, <code>Double</code>.
2527:    * For <code>null</code>, 0 is returned.
2528:    *
2529:    * @param v an array of doubles for which the hash code should be
2530:    *          computed.
2531:    * @return the hash code of the array, or 0 if null was given.
2532:    * @since 1.5 
2533:    */
2534:   public static int hashCode(double[] v)
2535:   {
2536:     if (v == null)
2537:       return 0;
2538:     int result = 1;
2539:     for (int i = 0; i < v.length; ++i)
2540:       {
2541:     long l = Double.doubleToLongBits(v[i]);
2542:     int elt = (int) (l ^ (l >>> 32));
2543:     result = 31 * result + elt;
2544:       }
2545:     return result;
2546:   }
2547: 
2548:   /** 
2549:    * Returns the hashcode of an array of integer numbers.  If two arrays
2550:    * are equal, according to <code>equals()</code>, they should have the
2551:    * same hashcode.  The hashcode returned by the method is equal to that
2552:    * obtained by the corresponding <code>List</code> object.  This has the same
2553:    * data, but represents ints in their wrapper class, <code>Integer</code>.
2554:    * For <code>null</code>, 0 is returned.
2555:    *
2556:    * @param v an array of integer numbers for which the hash code should be
2557:    *          computed.
2558:    * @return the hash code of the array, or 0 if null was given.
2559:    * @since 1.5 
2560:    */
2561:   public static int hashCode(Object[] v)
2562:   {
2563:     if (v == null)
2564:       return 0;
2565:     int result = 1;
2566:     for (int i = 0; i < v.length; ++i)
2567:       {
2568:     int elt = v[i] == null ? 0 : v[i].hashCode();
2569:     result = 31 * result + elt;
2570:       }
2571:     return result;
2572:   }
2573: 
2574:   /** @since 1.5 */
2575:   public static int deepHashCode(Object[] v)
2576:   {
2577:     if (v == null)
2578:       return 0;
2579:     int result = 1;
2580:     for (int i = 0; i < v.length; ++i)
2581:       {
2582:     int elt;
2583:     if (v[i] == null)
2584:       elt = 0;
2585:     else if (v[i] instanceof boolean[])
2586:       elt = hashCode((boolean[]) v[i]);
2587:     else if (v[i] instanceof byte[])
2588:       elt = hashCode((byte[]) v[i]);
2589:     else if (v[i] instanceof char[])
2590:       elt = hashCode((char[]) v[i]);
2591:     else if (v[i] instanceof short[])
2592:       elt = hashCode((short[]) v[i]);
2593:     else if (v[i] instanceof int[])
2594:       elt = hashCode((int[]) v[i]);
2595:     else if (v[i] instanceof long[])
2596:       elt = hashCode((long[]) v[i]);
2597:     else if (v[i] instanceof float[])
2598:       elt = hashCode((float[]) v[i]);
2599:     else if (v[i] instanceof double[])
2600:       elt = hashCode((double[]) v[i]);
2601:     else if (v[i] instanceof Object[])
2602:       elt = hashCode((Object[]) v[i]);
2603:     else
2604:       elt = v[i].hashCode();
2605:     result = 31 * result + elt;
2606:       }
2607:     return result;
2608:   }
2609: 
2610:   /** @since 1.5 */
2611:   public static boolean deepEquals(Object[] v1, Object[] v2)
2612:   {
2613:     if (v1 == null)
2614:       return v2 == null;
2615:     if (v2 == null || v1.length != v2.length)
2616:       return false;
2617: 
2618:     for (int i = 0; i < v1.length; ++i)
2619:       {
2620:     Object e1 = v1[i];
2621:     Object e2 = v2[i];
2622: 
2623:     if (e1 == e2)
2624:       continue;
2625:     if (e1 == null || e2 == null)
2626:       return false;
2627: 
2628:     boolean check;
2629:     if (e1 instanceof boolean[] && e2 instanceof boolean[])
2630:       check = equals((boolean[]) e1, (boolean[]) e2);
2631:     else if (e1 instanceof byte[] && e2 instanceof byte[])
2632:       check = equals((byte[]) e1, (byte[]) e2);
2633:     else if (e1 instanceof char[] && e2 instanceof char[])
2634:       check = equals((char[]) e1, (char[]) e2);
2635:     else if (e1 instanceof short[] && e2 instanceof short[])
2636:       check = equals((short[]) e1, (short[]) e2);
2637:     else if (e1 instanceof int[] && e2 instanceof int[])
2638:       check = equals((int[]) e1, (int[]) e2);
2639:     else if (e1 instanceof long[] && e2 instanceof long[])
2640:       check = equals((long[]) e1, (long[]) e2);
2641:     else if (e1 instanceof float[] && e2 instanceof float[])
2642:       check = equals((float[]) e1, (float[]) e2);
2643:     else if (e1 instanceof double[] && e2 instanceof double[])
2644:       check = equals((double[]) e1, (double[]) e2);
2645:     else if (e1 instanceof Object[] && e2 instanceof Object[])
2646:       check = equals((Object[]) e1, (Object[]) e2);
2647:     else
2648:       check = e1.equals(e2);
2649:     if (! check)
2650:       return false;
2651:       }
2652: 
2653:     return true;
2654:   }
2655: 
2656:   /**
2657:    * Returns a String representation of the argument array.  Returns "null"
2658:    * if <code>a</code> is null.
2659:    * @param v the array to represent
2660:    * @return a String representing this array
2661:    * @since 1.5
2662:    */
2663:   public static String toString(boolean[] v)
2664:   {
2665:     if (v == null)
2666:       return "null";
2667:     StringBuilder b = new StringBuilder("[");
2668:     for (int i = 0; i < v.length; ++i)
2669:       {
2670:     if (i > 0)
2671:       b.append(", ");
2672:     b.append(v[i]);
2673:       }
2674:     b.append("]");
2675:     return b.toString();
2676:   }
2677: 
2678:   /**
2679:    * Returns a String representation of the argument array.  Returns "null"
2680:    * if <code>a</code> is null.
2681:    * @param v the array to represent
2682:    * @return a String representing this array
2683:    * @since 1.5
2684:    */
2685:   public static String toString(byte[] v)
2686:   {
2687:     if (v == null)
2688:       return "null";
2689:     StringBuilder b = new StringBuilder("[");
2690:     for (int i = 0; i < v.length; ++i)
2691:       {
2692:     if (i > 0)
2693:       b.append(", ");
2694:     b.append(v[i]);
2695:       }
2696:     b.append("]");
2697:     return b.toString();
2698:   }
2699: 
2700:   /**
2701:    * Returns a String representation of the argument array.  Returns "null"
2702:    * if <code>a</code> is null.
2703:    * @param v the array to represent
2704:    * @return a String representing this array
2705:    * @since 1.5
2706:    */
2707:   public static String toString(char[] v)
2708:   {
2709:     if (v == null)
2710:       return "null";
2711:     StringBuilder b = new StringBuilder("[");
2712:     for (int i = 0; i < v.length; ++i)
2713:       {
2714:     if (i > 0)
2715:       b.append(", ");
2716:     b.append(v[i]);
2717:       }
2718:     b.append("]");
2719:     return b.toString();
2720:   }
2721: 
2722:   /**
2723:    * Returns a String representation of the argument array.  Returns "null"
2724:    * if <code>a</code> is null.
2725:    * @param v the array to represent
2726:    * @return a String representing this array
2727:    * @since 1.5
2728:    */
2729:   public static String toString(short[] v)
2730:   {
2731:     if (v == null)
2732:       return "null";
2733:     StringBuilder b = new StringBuilder("[");
2734:     for (int i = 0; i < v.length; ++i)
2735:       {
2736:     if (i > 0)
2737:       b.append(", ");
2738:     b.append(v[i]);
2739:       }
2740:     b.append("]");
2741:     return b.toString();
2742:   }
2743: 
2744:   /**
2745:    * Returns a String representation of the argument array.  Returns "null"
2746:    * if <code>a</code> is null.
2747:    * @param v the array to represent
2748:    * @return a String representing this array
2749:    * @since 1.5
2750:    */
2751:   public static String toString(int[] v)
2752:   {
2753:     if (v == null)
2754:       return "null";
2755:     StringBuilder b = new StringBuilder("[");
2756:     for (int i = 0; i < v.length; ++i)
2757:       {
2758:     if (i > 0)
2759:       b.append(", ");
2760:     b.append(v[i]);
2761:       }
2762:     b.append("]");
2763:     return b.toString();
2764:   }
2765: 
2766:   /**
2767:    * Returns a String representation of the argument array.  Returns "null"
2768:    * if <code>a</code> is null.
2769:    * @param v the array to represent
2770:    * @return a String representing this array
2771:    * @since 1.5
2772:    */
2773:   public static String toString(long[] v)
2774:   {
2775:     if (v == null)
2776:       return "null";
2777:     StringBuilder b = new StringBuilder("[");
2778:     for (int i = 0; i < v.length; ++i)
2779:       {
2780:     if (i > 0)
2781:       b.append(", ");
2782:     b.append(v[i]);
2783:       }
2784:     b.append("]");
2785:     return b.toString();
2786:   }
2787: 
2788:   /**
2789:    * Returns a String representation of the argument array.  Returns "null"
2790:    * if <code>a</code> is null.
2791:    * @param v the array to represent
2792:    * @return a String representing this array
2793:    * @since 1.5
2794:    */
2795:   public static String toString(float[] v)
2796:   {
2797:     if (v == null)
2798:       return "null";
2799:     StringBuilder b = new StringBuilder("[");
2800:     for (int i = 0; i < v.length; ++i)
2801:       {
2802:     if (i > 0)
2803:       b.append(", ");
2804:     b.append(v[i]);
2805:       }
2806:     b.append("]");
2807:     return b.toString();
2808:   }
2809: 
2810:   /**
2811:    * Returns a String representation of the argument array.  Returns "null"
2812:    * if <code>a</code> is null.
2813:    * @param v the array to represent
2814:    * @return a String representing this array
2815:    * @since 1.5
2816:    */
2817:   public static String toString(double[] v)
2818:   {
2819:     if (v == null)
2820:       return "null";
2821:     StringBuilder b = new StringBuilder("[");
2822:     for (int i = 0; i < v.length; ++i)
2823:       {
2824:     if (i > 0)
2825:       b.append(", ");
2826:     b.append(v[i]);
2827:       }
2828:     b.append("]");
2829:     return b.toString();
2830:   }
2831: 
2832:   /**
2833:    * Returns a String representation of the argument array.  Returns "null"
2834:    * if <code>a</code> is null.
2835:    * @param v the array to represent
2836:    * @return a String representing this array
2837:    * @since 1.5
2838:    */
2839:   public static String toString(Object[] v)
2840:   {
2841:     if (v == null)
2842:       return "null";
2843:     StringBuilder b = new StringBuilder("[");
2844:     for (int i = 0; i < v.length; ++i)
2845:       {
2846:     if (i > 0)
2847:       b.append(", ");
2848:     b.append(v[i]);
2849:       }
2850:     b.append("]");
2851:     return b.toString();
2852:   }
2853: 
2854:   private static void deepToString(Object[] v, StringBuilder b, HashSet seen)
2855:   {
2856:     b.append("[");
2857:     for (int i = 0; i < v.length; ++i)
2858:       {
2859:     if (i > 0)
2860:       b.append(", ");
2861:     Object elt = v[i];
2862:     if (elt == null)
2863:       b.append("null");
2864:     else if (elt instanceof boolean[])
2865:       b.append(toString((boolean[]) elt));
2866:     else if (elt instanceof byte[])
2867:       b.append(toString((byte[]) elt));
2868:     else if (elt instanceof char[])
2869:       b.append(toString((char[]) elt));
2870:     else if (elt instanceof short[])
2871:       b.append(toString((short[]) elt));
2872:     else if (elt instanceof int[])
2873:       b.append(toString((int[]) elt));
2874:     else if (elt instanceof long[])
2875:       b.append(toString((long[]) elt));
2876:     else if (elt instanceof float[])
2877:       b.append(toString((float[]) elt));
2878:     else if (elt instanceof double[])
2879:       b.append(toString((double[]) elt));
2880:     else if (elt instanceof Object[])
2881:       {
2882:         Object[] os = (Object[]) elt;
2883:         if (seen.contains(os))
2884:           b.append("[...]");
2885:         else
2886:           {
2887:         seen.add(os);
2888:         deepToString(os, b, seen);
2889:           }
2890:       }
2891:     else
2892:       b.append(elt);
2893:       }
2894:     b.append("]");
2895:   }
2896: 
2897:   /** @since 1.5 */
2898:   public static String deepToString(Object[] v)
2899:   {
2900:     if (v == null)
2901:       return "null";
2902:     HashSet seen = new HashSet();
2903:     StringBuilder b = new StringBuilder();
2904:     deepToString(v, b, seen);
2905:     return b.toString();
2906:   }
2907: 
2908:   /**
2909:    * Inner class used by {@link #asList(Object[])} to provide a list interface
2910:    * to an array. The name, though it clashes with java.util.ArrayList, is
2911:    * Sun's choice for Serialization purposes. Element addition and removal
2912:    * is prohibited, but values can be modified.
2913:    *
2914:    * @author Eric Blake (ebb9@email.byu.edu)
2915:    * @status updated to 1.4
2916:    */
2917:   private static final class ArrayList extends AbstractList
2918:     implements Serializable, RandomAccess
2919:   {
2920:     // We override the necessary methods, plus others which will be much
2921:     // more efficient with direct iteration rather than relying on iterator().
2922: 
2923:     /**
2924:      * Compatible with JDK 1.4.
2925:      */
2926:     private static final long serialVersionUID = -2764017481108945198L;
2927: 
2928:     /**
2929:      * The array we are viewing.
2930:      * @serial the array
2931:      */
2932:     private final Object[] a;
2933: 
2934:     /**
2935:      * Construct a list view of the array.
2936:      * @param a the array to view
2937:      * @throws NullPointerException if a is null
2938:      */
2939:     ArrayList(Object[] a)
2940:     {
2941:       // We have to explicitly check.
2942:       if (a == null)
2943:         throw new NullPointerException();
2944:       this.a = a;
2945:     }
2946: 
2947:     /**
2948:      * Returns the object at the specified index in
2949:      * the array.
2950:      *
2951:      * @param index The index to retrieve an object from.
2952:      * @return The object at the array index specified.
2953:      */ 
2954:     public Object get(int index)
2955:     {
2956:       return a[index];
2957:     }
2958: 
2959:     /**
2960:      * Returns the size of the array.
2961:      *
2962:      * @return The size.
2963:      */
2964:     public int size()
2965:     {
2966:       return a.length;
2967:     }
2968: 
2969:     /**
2970:      * Replaces the object at the specified index
2971:      * with the supplied element.
2972:      *
2973:      * @param index The index at which to place the new object.
2974:      * @param element The new object.
2975:      * @return The object replaced by this operation.
2976:      */
2977:     public Object set(int index, Object element)
2978:     {
2979:       Object old = a[index];
2980:       a[index] = element;
2981:       return old;
2982:     }
2983: 
2984:     /**
2985:      * Returns true if the array contains the
2986:      * supplied object.
2987:      *
2988:      * @param o The object to look for.
2989:      * @return True if the object was found.
2990:      */
2991:     public boolean contains(Object o)
2992:     {
2993:       return lastIndexOf(o) >= 0;
2994:     }
2995: 
2996:     /**
2997:      * Returns the first index at which the
2998:      * object, o, occurs in the array.
2999:      *
3000:      * @param o The object to search for.
3001:      * @return The first relevant index.
3002:      */
3003:     public int indexOf(Object o)
3004:     {
3005:       int size = a.length;
3006:       for (int i = 0; i < size; i++)
3007:         if (ArrayList.equals(o, a[i]))
3008:           return i;
3009:       return -1;
3010:     }
3011: 
3012:     /**
3013:      * Returns the last index at which the
3014:      * object, o, occurs in the array.
3015:      *
3016:      * @param o The object to search for.
3017:      * @return The last relevant index.
3018:      */
3019:     public int lastIndexOf(Object o)
3020:     {
3021:       int i = a.length;
3022:       while (--i >= 0)
3023:         if (ArrayList.equals(o, a[i]))
3024:           return i;
3025:       return -1;
3026:     }
3027: 
3028:     /**
3029:      * Transforms the list into an array of
3030:      * objects, by simplying cloning the array
3031:      * wrapped by this list.
3032:      *
3033:      * @return A clone of the internal array.
3034:      */
3035:     public Object[] toArray()
3036:     {
3037:       return (Object[]) a.clone();
3038:     }
3039: 
3040:     /**
3041:      * Copies the objects from this list into
3042:      * the supplied array.  The supplied array
3043:      * is shrunk or enlarged to the size of the
3044:      * internal array, and filled with its objects.
3045:      *
3046:      * @param array The array to fill with the objects in this list.
3047:      * @return The array containing the objects in this list,
3048:      *         which may or may not be == to array.
3049:      */
3050:     public Object[] toArray(Object[] array)
3051:     {
3052:       int size = a.length;
3053:       if (array.length < size)
3054:         array = (Object[])
3055:           Array.newInstance(array.getClass().getComponentType(), size);
3056:       else if (array.length > size)
3057:         array[size] = null;
3058: 
3059:       System.arraycopy(a, 0, array, 0, size);
3060:       return array;
3061:     }
3062:   }
3063: }