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