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