lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/ArrayUtil.java

   1 package org.apache.lucene.util;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import java.util.Collection;
  21 import java.util.Comparator;
  22
  23 /**
  24  * Methods for manipulating arrays.
  25  *
  26  * @lucene.internal
  27  */
  28 public final class ArrayUtil {
  29
  30   /**
  31    * @deprecated This constructor was not intended to be public and should not be used.
  32    *  This class contains solely a static utility methods.
  33    *  It will be made private in Lucene 4.0
  34    */
  35   // make private in 4.0!
  36   @Deprecated
  37   public ArrayUtil() {} // no instance
  38
  39   /*
  40      Begin Apache Harmony code
  41
  42      Revision taken on Friday, June 12. https://svn.apache.org/repos/asf/harmony/enhanced/classlib/archive/java6/modules/luni/src/main/java/java/lang/Integer.java
  43
  44    */
  45
  46   /**
  47    * Parses the string argument as if it was an int value and returns the
  48    * result. Throws NumberFormatException if the string does not represent an
  49    * int quantity.
  50    *
  51    * @param chars a string representation of an int quantity.
  52    * @return int the value represented by the argument
  53    * @throws NumberFormatException if the argument could not be parsed as an int quantity.
  54    */
  55   public static int parseInt(char[] chars) throws NumberFormatException {
  56     return parseInt(chars, 0, chars.length, 10);
  57   }
  58
  59   /**
  60    * Parses a char array into an int.
  61    * @param chars the character array
  62    * @param offset The offset into the array
  63    * @param len The length
  64    * @return the int
  65    * @throws NumberFormatException if it can't parse
  66    */
  67   public static int parseInt(char[] chars, int offset, int len) throws NumberFormatException {
  68     return parseInt(chars, offset, len, 10);
  69   }
  70
  71   /**
  72    * Parses the string argument as if it was an int value and returns the
  73    * result. Throws NumberFormatException if the string does not represent an
  74    * int quantity. The second argument specifies the radix to use when parsing
  75    * the value.
  76    *
  77    * @param chars a string representation of an int quantity.
  78    * @param radix the base to use for conversion.
  79    * @return int the value represented by the argument
  80    * @throws NumberFormatException if the argument could not be parsed as an int quantity.
  81    */
  82   public static int parseInt(char[] chars, int offset, int len, int radix)
  83           throws NumberFormatException {
  84     if (chars == null || radix < Character.MIN_RADIX
  85             || radix > Character.MAX_RADIX) {
  86       throw new NumberFormatException();
  87     }
  88     int  i = 0;
  89     if (len == 0) {
  90       throw new NumberFormatException("chars length is 0");
  91     }
  92     boolean negative = chars[offset + i] == '-';
  93     if (negative && ++i == len) {
  94       throw new NumberFormatException("can't convert to an int");
  95     }
  96     if (negative == true){
  97       offset++;
  98       len--;
  99     }
 100     return parse(chars, offset, len, radix, negative);
 101   }
 102
 103
 104   private static int parse(char[] chars, int offset, int len, int radix,
 105                            boolean negative) throws NumberFormatException {
 106     int max = Integer.MIN_VALUE / radix;
 107     int result = 0;
 108     for (int i = 0; i < len; i++){
 109       int digit = Character.digit(chars[i + offset], radix);
 110       if (digit == -1) {
 111         throw new NumberFormatException("Unable to parse");
 112       }
 113       if (max > result) {
 114         throw new NumberFormatException("Unable to parse");
 115       }
 116       int next = result * radix - digit;
 117       if (next > result) {
 118         throw new NumberFormatException("Unable to parse");
 119       }
 120       result = next;
 121     }
 122     /*while (offset < len) {
 123
 124     }*/
 125     if (!negative) {
 126       result = -result;
 127       if (result < 0) {
 128         throw new NumberFormatException("Unable to parse");
 129       }
 130     }
 131     return result;
 132   }
 133
 134
 135   /*
 136
 137  END APACHE HARMONY CODE
 138   */
 139
 140   /** Returns an array size >= minTargetSize, generally
 141    *  over-allocating exponentially to achieve amortized
 142    *  linear-time cost as the array grows.
 143    *
 144    *  NOTE: this was originally borrowed from Python 2.4.2
 145    *  listobject.c sources (attribution in LICENSE.txt), but
 146    *  has now been substantially changed based on
 147    *  discussions from java-dev thread with subject "Dynamic
 148    *  array reallocation algorithms", started on Jan 12
 149    *  2010.
 150    *
 151    * @param minTargetSize Minimum required value to be returned.
 152    * @param bytesPerElement Bytes used by each element of
 153    * the array.  See constants in {@link RamUsageEstimator}.
 154    *
 155    * @lucene.internal
 156    */
 157
 158   public static int oversize(int minTargetSize, int bytesPerElement) {
 159
 160     if (minTargetSize < 0) {
 161       // catch usage that accidentally overflows int
 162       throw new IllegalArgumentException("invalid array size " + minTargetSize);
 163     }
 164
 165     if (minTargetSize == 0) {
 166       // wait until at least one element is requested
 167       return 0;
 168     }
 169
 170     // asymptotic exponential growth by 1/8th, favors
 171     // spending a bit more CPU to not tie up too much wasted
 172     // RAM:
 173     int extra = minTargetSize >> 3;
 174
 175     if (extra < 3) {
 176       // for very small arrays, where constant overhead of
 177       // realloc is presumably relatively high, we grow
 178       // faster
 179       extra = 3;
 180     }
 181
 182     int newSize = minTargetSize + extra;
 183
 184     // add 7 to allow for worst case byte alignment addition below:
 185     if (newSize+7 < 0) {
 186       // int overflowed -- return max allowed array size
 187       return Integer.MAX_VALUE;
 188     }
 189
 190     if (Constants.JRE_IS_64BIT) {
 191       // round up to 8 byte alignment in 64bit env
 192       switch(bytesPerElement) {
 193       case 4:
 194         // round up to multiple of 2
 195         return (newSize + 1) & 0x7ffffffe;
 196       case 2:
 197         // round up to multiple of 4
 198         return (newSize + 3) & 0x7ffffffc;
 199       case 1:
 200         // round up to multiple of 8
 201         return (newSize + 7) & 0x7ffffff8;
 202       case 8:
 203         // no rounding
 204       default:
 205         // odd (invalid?) size
 206         return newSize;
 207       }
 208     } else {
 209       // round up to 4 byte alignment in 64bit env
 210       switch(bytesPerElement) {
 211       case 2:
 212         // round up to multiple of 2
 213         return (newSize + 1) & 0x7ffffffe;
 214       case 1:
 215         // round up to multiple of 4
 216         return (newSize + 3) & 0x7ffffffc;
 217       case 4:
 218       case 8:
 219         // no rounding
 220       default:
 221         // odd (invalid?) size
 222         return newSize;
 223       }
 224     }
 225   }
 226
 227   public static int getShrinkSize(int currentSize, int targetSize, int bytesPerElement) {
 228     final int newSize = oversize(targetSize, bytesPerElement);
 229     // Only reallocate if we are "substantially" smaller.
 230     // This saves us from "running hot" (constantly making a
 231     // bit bigger then a bit smaller, over and over):
 232     if (newSize < currentSize / 2)
 233       return newSize;
 234     else
 235       return currentSize;
 236   }
 237
 238   public static short[] grow(short[] array, int minSize) {
 239     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 240     if (array.length < minSize) {
 241       short[] newArray = new short[oversize(minSize, RamUsageEstimator.NUM_BYTES_SHORT)];
 242       System.arraycopy(array, 0, newArray, 0, array.length);
 243       return newArray;
 244     } else
 245       return array;
 246   }
 247
 248   public static short[] grow(short[] array) {
 249     return grow(array, 1 + array.length);
 250   }
 251
 252   public static float[] grow(float[] array, int minSize) {
 253     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 254     if (array.length < minSize) {
 255       float[] newArray = new float[oversize(minSize, RamUsageEstimator.NUM_BYTES_FLOAT)];
 256       System.arraycopy(array, 0, newArray, 0, array.length);
 257       return newArray;
 258     } else
 259       return array;
 260   }
 261
 262   public static float[] grow(float[] array) {
 263     return grow(array, 1 + array.length);
 264   }
 265
 266   public static double[] grow(double[] array, int minSize) {
 267     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 268     if (array.length < minSize) {
 269       double[] newArray = new double[oversize(minSize, RamUsageEstimator.NUM_BYTES_DOUBLE)];
 270       System.arraycopy(array, 0, newArray, 0, array.length);
 271       return newArray;
 272     } else
 273       return array;
 274   }
 275
 276   public static double[] grow(double[] array) {
 277     return grow(array, 1 + array.length);
 278   }
 279
 280   public static short[] shrink(short[] array, int targetSize) {
 281     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 282     final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_SHORT);
 283     if (newSize != array.length) {
 284       short[] newArray = new short[newSize];
 285       System.arraycopy(array, 0, newArray, 0, newSize);
 286       return newArray;
 287     } else
 288       return array;
 289   }
 290
 291   public static int[] grow(int[] array, int minSize) {
 292     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 293     if (array.length < minSize) {
 294       int[] newArray = new int[oversize(minSize, RamUsageEstimator.NUM_BYTES_INT)];
 295       System.arraycopy(array, 0, newArray, 0, array.length);
 296       return newArray;
 297     } else
 298       return array;
 299   }
 300
 301   public static int[] grow(int[] array) {
 302     return grow(array, 1 + array.length);
 303   }
 304
 305   public static int[] shrink(int[] array, int targetSize) {
 306     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 307     final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_INT);
 308     if (newSize != array.length) {
 309       int[] newArray = new int[newSize];
 310       System.arraycopy(array, 0, newArray, 0, newSize);
 311       return newArray;
 312     } else
 313       return array;
 314   }
 315
 316   public static long[] grow(long[] array, int minSize) {
 317     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 318     if (array.length < minSize) {
 319       long[] newArray = new long[oversize(minSize, RamUsageEstimator.NUM_BYTES_LONG)];
 320       System.arraycopy(array, 0, newArray, 0, array.length);
 321       return newArray;
 322     } else
 323       return array;
 324   }
 325
 326   public static long[] grow(long[] array) {
 327     return grow(array, 1 + array.length);
 328   }
 329
 330   public static long[] shrink(long[] array, int targetSize) {
 331     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 332     final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_LONG);
 333     if (newSize != array.length) {
 334       long[] newArray = new long[newSize];
 335       System.arraycopy(array, 0, newArray, 0, newSize);
 336       return newArray;
 337     } else
 338       return array;
 339   }
 340
 341   public static byte[] grow(byte[] array, int minSize) {
 342     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 343     if (array.length < minSize) {
 344       byte[] newArray = new byte[oversize(minSize, 1)];
 345       System.arraycopy(array, 0, newArray, 0, array.length);
 346       return newArray;
 347     } else
 348       return array;
 349   }
 350
 351   public static byte[] grow(byte[] array) {
 352     return grow(array, 1 + array.length);
 353   }
 354
 355   public static byte[] shrink(byte[] array, int targetSize) {
 356     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 357     final int newSize = getShrinkSize(array.length, targetSize, 1);
 358     if (newSize != array.length) {
 359       byte[] newArray = new byte[newSize];
 360       System.arraycopy(array, 0, newArray, 0, newSize);
 361       return newArray;
 362     } else
 363       return array;
 364   }
 365
 366   public static boolean[] grow(boolean[] array, int minSize) {
 367     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 368     if (array.length < minSize) {
 369       boolean[] newArray = new boolean[oversize(minSize, 1)];
 370       System.arraycopy(array, 0, newArray, 0, array.length);
 371       return newArray;
 372     } else
 373       return array;
 374   }
 375
 376   public static boolean[] grow(boolean[] array) {
 377     return grow(array, 1 + array.length);
 378   }
 379
 380   public static boolean[] shrink(boolean[] array, int targetSize) {
 381     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 382     final int newSize = getShrinkSize(array.length, targetSize, 1);
 383     if (newSize != array.length) {
 384       boolean[] newArray = new boolean[newSize];
 385       System.arraycopy(array, 0, newArray, 0, newSize);
 386       return newArray;
 387     } else
 388       return array;
 389   }
 390
 391   public static char[] grow(char[] array, int minSize) {
 392     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 393     if (array.length < minSize) {
 394       char[] newArray = new char[oversize(minSize, RamUsageEstimator.NUM_BYTES_CHAR)];
 395       System.arraycopy(array, 0, newArray, 0, array.length);
 396       return newArray;
 397     } else
 398       return array;
 399   }
 400
 401   public static char[] grow(char[] array) {
 402     return grow(array, 1 + array.length);
 403   }
 404
 405   public static char[] shrink(char[] array, int targetSize) {
 406     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 407     final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_CHAR);
 408     if (newSize != array.length) {
 409       char[] newArray = new char[newSize];
 410       System.arraycopy(array, 0, newArray, 0, newSize);
 411       return newArray;
 412     } else
 413       return array;
 414   }
 415
 416   public static int[][] grow(int[][] array, int minSize) {
 417     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 418     if (array.length < minSize) {
 419       int[][] newArray = new int[oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
 420       System.arraycopy(array, 0, newArray, 0, array.length);
 421       return newArray;
 422     } else {
 423       return array;
 424     }
 425   }
 426
 427   public static int[][] grow(int[][] array) {
 428     return grow(array, 1 + array.length);
 429   }
 430
 431   public static int[][] shrink(int[][] array, int targetSize) {
 432     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 433     final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
 434     if (newSize != array.length) {
 435       int[][] newArray = new int[newSize][];
 436       System.arraycopy(array, 0, newArray, 0, newSize);
 437       return newArray;
 438     } else {
 439       return array;
 440     }
 441   }
 442
 443   public static float[][] grow(float[][] array, int minSize) {
 444     assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
 445     if (array.length < minSize) {
 446       float[][] newArray = new float[oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
 447       System.arraycopy(array, 0, newArray, 0, array.length);
 448       return newArray;
 449     } else {
 450       return array;
 451     }
 452   }
 453
 454   public static float[][] grow(float[][] array) {
 455     return grow(array, 1 + array.length);
 456   }
 457
 458   public static float[][] shrink(float[][] array, int targetSize) {
 459     assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
 460     final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
 461     if (newSize != array.length) {
 462       float[][] newArray = new float[newSize][];
 463       System.arraycopy(array, 0, newArray, 0, newSize);
 464       return newArray;
 465     } else {
 466       return array;
 467     }
 468   }
 469
 470   /**
 471    * Returns hash of chars in range start (inclusive) to
 472    * end (inclusive)
 473    */
 474   public static int hashCode(char[] array, int start, int end) {
 475     int code = 0;
 476     for (int i = end - 1; i >= start; i--)
 477       code = code * 31 + array[i];
 478     return code;
 479   }
 480
 481   /**
 482    * Returns hash of bytes in range start (inclusive) to
 483    * end (inclusive)
 484    */
 485   public static int hashCode(byte[] array, int start, int end) {
 486     int code = 0;
 487     for (int i = end - 1; i >= start; i--)
 488       code = code * 31 + array[i];
 489     return code;
 490   }
 491
 492
 493   // Since Arrays.equals doesn't implement offsets for equals
 494   /**
 495    * See if two array slices are the same.
 496    *
 497    * @param left        The left array to compare
 498    * @param offsetLeft  The offset into the array.  Must be positive
 499    * @param right       The right array to compare
 500    * @param offsetRight the offset into the right array.  Must be positive
 501    * @param length      The length of the section of the array to compare
 502    * @return true if the two arrays, starting at their respective offsets, are equal
 503    *
 504    * @see java.util.Arrays#equals(char[], char[])
 505    */
 506   public static boolean equals(char[] left, int offsetLeft, char[] right, int offsetRight, int length) {
 507     if ((offsetLeft + length <= left.length) && (offsetRight + length <= right.length)) {
 508       for (int i = 0; i < length; i++) {
 509         if (left[offsetLeft + i] != right[offsetRight + i]) {
 510           return false;
 511         }
 512
 513       }
 514       return true;
 515     }
 516     return false;
 517   }
 518
 519   // Since Arrays.equals doesn't implement offsets for equals
 520   /**
 521    * See if two array slices are the same.
 522    *
 523    * @param left        The left array to compare
 524    * @param offsetLeft  The offset into the array.  Must be positive
 525    * @param right       The right array to compare
 526    * @param offsetRight the offset into the right array.  Must be positive
 527    * @param length      The length of the section of the array to compare
 528    * @return true if the two arrays, starting at their respective offsets, are equal
 529    *
 530    * @see java.util.Arrays#equals(char[], char[])
 531    */
 532   public static boolean equals(int[] left, int offsetLeft, int[] right, int offsetRight, int length) {
 533     if ((offsetLeft + length <= left.length) && (offsetRight + length <= right.length)) {
 534       for (int i = 0; i < length; i++) {
 535         if (left[offsetLeft + i] != right[offsetRight + i]) {
 536           return false;
 537         }
 538
 539       }
 540       return true;
 541     }
 542     return false;
 543   }
 544
 545   public static int[] toIntArray(Collection<Integer> ints) {
 546
 547     final int[] result = new int[ints.size()];
 548     int upto = 0;
 549     for(int v : ints) {
 550       result[upto++] = v;
 551     }
 552
 553     // paranoia:
 554     assert upto == result.length;
 555
 556     return result;
 557   }
 558
 559   /** SorterTemplate with custom {@link Comparator} */
 560   private static <T> SorterTemplate getSorter(final T[] a, final Comparator<? super T> comp) {
 561     return new SorterTemplate() {
 562       @Override
 563       protected void swap(int i, int j) {
 564         final T o = a[i];
 565         a[i] = a[j];
 566         a[j] = o;
 567       }
 568
 569       @Override
 570       protected int compare(int i, int j) {
 571         return comp.compare(a[i], a[j]);
 572       }
 573
 574       @Override
 575       protected void setPivot(int i) {
 576         pivot = a[i];
 577       }
 578
 579       @Override
 580       protected int comparePivot(int j) {
 581         return comp.compare(pivot, a[j]);
 582       }
 583
 584       private T pivot;
 585     };
 586   }
 587
 588   /** Natural SorterTemplate */
 589   private static <T extends Comparable<? super T>> SorterTemplate getSorter(final T[] a) {
 590     return new SorterTemplate() {
 591       @Override
 592       protected void swap(int i, int j) {
 593         final T o = a[i];
 594         a[i] = a[j];
 595         a[j] = o;
 596       }
 597
 598       @Override
 599       protected int compare(int i, int j) {
 600         return a[i].compareTo(a[j]);
 601       }
 602
 603       @Override
 604       protected void setPivot(int i) {
 605         pivot = a[i];
 606       }
 607
 608       @Override
 609       protected int comparePivot(int j) {
 610         return pivot.compareTo(a[j]);
 611       }
 612
 613       private T pivot;
 614     };
 615   }
 616
 617   // quickSorts (endindex is exclusive!):
 618
 619   /**
 620    * Sorts the given array slice using the {@link Comparator}. This method uses the quick sort
 621    * algorithm, but falls back to insertion sort for small arrays.
 622    * @param fromIndex start index (inclusive)
 623    * @param toIndex end index (exclusive)
 624    */
 625   public static <T> void quickSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
 626     if (toIndex-fromIndex <= 1) return;
 627     getSorter(a, comp).quickSort(fromIndex, toIndex-1);
 628   }
 629
 630   /**
 631    * Sorts the given array using the {@link Comparator}. This method uses the quick sort
 632    * algorithm, but falls back to insertion sort for small arrays.
 633    */
 634   public static <T> void quickSort(T[] a, Comparator<? super T> comp) {
 635     quickSort(a, 0, a.length, comp);
 636   }
 637
 638   /**
 639    * Sorts the given array slice in natural order. This method uses the quick sort
 640    * algorithm, but falls back to insertion sort for small arrays.
 641    * @param fromIndex start index (inclusive)
 642    * @param toIndex end index (exclusive)
 643    */
 644   public static <T extends Comparable<? super T>> void quickSort(T[] a, int fromIndex, int toIndex) {
 645     if (toIndex-fromIndex <= 1) return;
 646     getSorter(a).quickSort(fromIndex, toIndex-1);
 647   }
 648
 649   /**
 650    * Sorts the given array in natural order. This method uses the quick sort
 651    * algorithm, but falls back to insertion sort for small arrays.
 652    */
 653   public static <T extends Comparable<? super T>> void quickSort(T[] a) {
 654     quickSort(a, 0, a.length);
 655   }
 656
 657   // mergeSorts:
 658
 659   /**
 660    * Sorts the given array slice using the {@link Comparator}. This method uses the merge sort
 661    * algorithm, but falls back to insertion sort for small arrays.
 662    * @param fromIndex start index (inclusive)
 663    * @param toIndex end index (exclusive)
 664    */
 665   public static <T> void mergeSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
 666     if (toIndex-fromIndex <= 1) return;
 667     //System.out.println("SORT: " + (toIndex-fromIndex));
 668     getSorter(a, comp).mergeSort(fromIndex, toIndex-1);
 669   }
 670
 671   /**
 672    * Sorts the given array using the {@link Comparator}. This method uses the merge sort
 673    * algorithm, but falls back to insertion sort for small arrays.
 674    */
 675   public static <T> void mergeSort(T[] a, Comparator<? super T> comp) {
 676     mergeSort(a, 0, a.length, comp);
 677   }
 678
 679   /**
 680    * Sorts the given array slice in natural order. This method uses the merge sort
 681    * algorithm, but falls back to insertion sort for small arrays.
 682    * @param fromIndex start index (inclusive)
 683    * @param toIndex end index (exclusive)
 684    */
 685   public static <T extends Comparable<? super T>> void mergeSort(T[] a, int fromIndex, int toIndex) {
 686     if (toIndex-fromIndex <= 1) return;
 687     getSorter(a).mergeSort(fromIndex, toIndex-1);
 688   }
 689
 690   /**
 691    * Sorts the given array in natural order. This method uses the merge sort
 692    * algorithm, but falls back to insertion sort for small arrays.
 693    */
 694   public static <T extends Comparable<? super T>> void mergeSort(T[] a) {
 695     mergeSort(a, 0, a.length);
 696   }
 697
 698   // insertionSorts:
 699
 700   /**
 701    * Sorts the given array slice using the {@link Comparator}. This method uses the insertion sort
 702    * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
 703    * @param fromIndex start index (inclusive)
 704    * @param toIndex end index (exclusive)
 705    */
 706   public static <T> void insertionSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
 707     if (toIndex-fromIndex <= 1) return;
 708     getSorter(a, comp).insertionSort(fromIndex, toIndex-1);
 709   }
 710
 711   /**
 712    * Sorts the given array using the {@link Comparator}. This method uses the insertion sort
 713    * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
 714    */
 715   public static <T> void insertionSort(T[] a, Comparator<? super T> comp) {
 716     insertionSort(a, 0, a.length, comp);
 717   }
 718
 719   /**
 720    * Sorts the given array slice in natural order. This method uses the insertion sort
 721    * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
 722    * @param fromIndex start index (inclusive)
 723    * @param toIndex end index (exclusive)
 724    */
 725   public static <T extends Comparable<? super T>> void insertionSort(T[] a, int fromIndex, int toIndex) {
 726     if (toIndex-fromIndex <= 1) return;
 727     getSorter(a).insertionSort(fromIndex, toIndex-1);
 728   }
 729
 730   /**
 731    * Sorts the given array in natural order. This method uses the insertion sort
 732    * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
 733    */
 734   public static <T extends Comparable<? super T>> void insertionSort(T[] a) {
 735     insertionSort(a, 0, a.length);
 736   }
 737
 738 }