--- /dev/null
+package org.apache.lucene.util;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.Collection;
+import java.util.Comparator;
+
+/**
+ * Methods for manipulating arrays.
+ *
+ * @lucene.internal
+ */
+public final class ArrayUtil {
+
+ /**
+ * @deprecated This constructor was not intended to be public and should not be used.
+ * This class contains solely a static utility methods.
+ * It will be made private in Lucene 4.0
+ */
+ // make private in 4.0!
+ @Deprecated
+ public ArrayUtil() {} // no instance
+
+ /*
+ Begin Apache Harmony code
+
+ 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
+
+ */
+
+ /**
+ * Parses the string argument as if it was an int value and returns the
+ * result. Throws NumberFormatException if the string does not represent an
+ * int quantity.
+ *
+ * @param chars a string representation of an int quantity.
+ * @return int the value represented by the argument
+ * @throws NumberFormatException if the argument could not be parsed as an int quantity.
+ */
+ public static int parseInt(char[] chars) throws NumberFormatException {
+ return parseInt(chars, 0, chars.length, 10);
+ }
+
+ /**
+ * Parses a char array into an int.
+ * @param chars the character array
+ * @param offset The offset into the array
+ * @param len The length
+ * @return the int
+ * @throws NumberFormatException if it can't parse
+ */
+ public static int parseInt(char[] chars, int offset, int len) throws NumberFormatException {
+ return parseInt(chars, offset, len, 10);
+ }
+
+ /**
+ * Parses the string argument as if it was an int value and returns the
+ * result. Throws NumberFormatException if the string does not represent an
+ * int quantity. The second argument specifies the radix to use when parsing
+ * the value.
+ *
+ * @param chars a string representation of an int quantity.
+ * @param radix the base to use for conversion.
+ * @return int the value represented by the argument
+ * @throws NumberFormatException if the argument could not be parsed as an int quantity.
+ */
+ public static int parseInt(char[] chars, int offset, int len, int radix)
+ throws NumberFormatException {
+ if (chars == null || radix < Character.MIN_RADIX
+ || radix > Character.MAX_RADIX) {
+ throw new NumberFormatException();
+ }
+ int i = 0;
+ if (len == 0) {
+ throw new NumberFormatException("chars length is 0");
+ }
+ boolean negative = chars[offset + i] == '-';
+ if (negative && ++i == len) {
+ throw new NumberFormatException("can't convert to an int");
+ }
+ if (negative == true){
+ offset++;
+ len--;
+ }
+ return parse(chars, offset, len, radix, negative);
+ }
+
+
+ private static int parse(char[] chars, int offset, int len, int radix,
+ boolean negative) throws NumberFormatException {
+ int max = Integer.MIN_VALUE / radix;
+ int result = 0;
+ for (int i = 0; i < len; i++){
+ int digit = Character.digit(chars[i + offset], radix);
+ if (digit == -1) {
+ throw new NumberFormatException("Unable to parse");
+ }
+ if (max > result) {
+ throw new NumberFormatException("Unable to parse");
+ }
+ int next = result * radix - digit;
+ if (next > result) {
+ throw new NumberFormatException("Unable to parse");
+ }
+ result = next;
+ }
+ /*while (offset < len) {
+
+ }*/
+ if (!negative) {
+ result = -result;
+ if (result < 0) {
+ throw new NumberFormatException("Unable to parse");
+ }
+ }
+ return result;
+ }
+
+
+ /*
+
+ END APACHE HARMONY CODE
+ */
+
+ /** Returns an array size >= minTargetSize, generally
+ * over-allocating exponentially to achieve amortized
+ * linear-time cost as the array grows.
+ *
+ * NOTE: this was originally borrowed from Python 2.4.2
+ * listobject.c sources (attribution in LICENSE.txt), but
+ * has now been substantially changed based on
+ * discussions from java-dev thread with subject "Dynamic
+ * array reallocation algorithms", started on Jan 12
+ * 2010.
+ *
+ * @param minTargetSize Minimum required value to be returned.
+ * @param bytesPerElement Bytes used by each element of
+ * the array. See constants in {@link RamUsageEstimator}.
+ *
+ * @lucene.internal
+ */
+
+ public static int oversize(int minTargetSize, int bytesPerElement) {
+
+ if (minTargetSize < 0) {
+ // catch usage that accidentally overflows int
+ throw new IllegalArgumentException("invalid array size " + minTargetSize);
+ }
+
+ if (minTargetSize == 0) {
+ // wait until at least one element is requested
+ return 0;
+ }
+
+ // asymptotic exponential growth by 1/8th, favors
+ // spending a bit more CPU to not tie up too much wasted
+ // RAM:
+ int extra = minTargetSize >> 3;
+
+ if (extra < 3) {
+ // for very small arrays, where constant overhead of
+ // realloc is presumably relatively high, we grow
+ // faster
+ extra = 3;
+ }
+
+ int newSize = minTargetSize + extra;
+
+ // add 7 to allow for worst case byte alignment addition below:
+ if (newSize+7 < 0) {
+ // int overflowed -- return max allowed array size
+ return Integer.MAX_VALUE;
+ }
+
+ if (Constants.JRE_IS_64BIT) {
+ // round up to 8 byte alignment in 64bit env
+ switch(bytesPerElement) {
+ case 4:
+ // round up to multiple of 2
+ return (newSize + 1) & 0x7ffffffe;
+ case 2:
+ // round up to multiple of 4
+ return (newSize + 3) & 0x7ffffffc;
+ case 1:
+ // round up to multiple of 8
+ return (newSize + 7) & 0x7ffffff8;
+ case 8:
+ // no rounding
+ default:
+ // odd (invalid?) size
+ return newSize;
+ }
+ } else {
+ // round up to 4 byte alignment in 64bit env
+ switch(bytesPerElement) {
+ case 2:
+ // round up to multiple of 2
+ return (newSize + 1) & 0x7ffffffe;
+ case 1:
+ // round up to multiple of 4
+ return (newSize + 3) & 0x7ffffffc;
+ case 4:
+ case 8:
+ // no rounding
+ default:
+ // odd (invalid?) size
+ return newSize;
+ }
+ }
+ }
+
+ public static int getShrinkSize(int currentSize, int targetSize, int bytesPerElement) {
+ final int newSize = oversize(targetSize, bytesPerElement);
+ // Only reallocate if we are "substantially" smaller.
+ // This saves us from "running hot" (constantly making a
+ // bit bigger then a bit smaller, over and over):
+ if (newSize < currentSize / 2)
+ return newSize;
+ else
+ return currentSize;
+ }
+
+ public static short[] grow(short[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ short[] newArray = new short[oversize(minSize, RamUsageEstimator.NUM_BYTES_SHORT)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static short[] grow(short[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static float[] grow(float[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ float[] newArray = new float[oversize(minSize, RamUsageEstimator.NUM_BYTES_FLOAT)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static float[] grow(float[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static double[] grow(double[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ double[] newArray = new double[oversize(minSize, RamUsageEstimator.NUM_BYTES_DOUBLE)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static double[] grow(double[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static short[] shrink(short[] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_SHORT);
+ if (newSize != array.length) {
+ short[] newArray = new short[newSize];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static int[] grow(int[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ int[] newArray = new int[oversize(minSize, RamUsageEstimator.NUM_BYTES_INT)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static int[] grow(int[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static int[] shrink(int[] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_INT);
+ if (newSize != array.length) {
+ int[] newArray = new int[newSize];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static long[] grow(long[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ long[] newArray = new long[oversize(minSize, RamUsageEstimator.NUM_BYTES_LONG)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static long[] grow(long[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static long[] shrink(long[] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_LONG);
+ if (newSize != array.length) {
+ long[] newArray = new long[newSize];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static byte[] grow(byte[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ byte[] newArray = new byte[oversize(minSize, 1)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static byte[] grow(byte[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static byte[] shrink(byte[] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, 1);
+ if (newSize != array.length) {
+ byte[] newArray = new byte[newSize];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static boolean[] grow(boolean[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ boolean[] newArray = new boolean[oversize(minSize, 1)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static boolean[] grow(boolean[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static boolean[] shrink(boolean[] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, 1);
+ if (newSize != array.length) {
+ boolean[] newArray = new boolean[newSize];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static char[] grow(char[] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ char[] newArray = new char[oversize(minSize, RamUsageEstimator.NUM_BYTES_CHAR)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static char[] grow(char[] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static char[] shrink(char[] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_CHAR);
+ if (newSize != array.length) {
+ char[] newArray = new char[newSize];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else
+ return array;
+ }
+
+ public static int[][] grow(int[][] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ int[][] newArray = new int[oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else {
+ return array;
+ }
+ }
+
+ public static int[][] grow(int[][] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static int[][] shrink(int[][] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
+ if (newSize != array.length) {
+ int[][] newArray = new int[newSize][];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else {
+ return array;
+ }
+ }
+
+ public static float[][] grow(float[][] array, int minSize) {
+ assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?";
+ if (array.length < minSize) {
+ float[][] newArray = new float[oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ return newArray;
+ } else {
+ return array;
+ }
+ }
+
+ public static float[][] grow(float[][] array) {
+ return grow(array, 1 + array.length);
+ }
+
+ public static float[][] shrink(float[][] array, int targetSize) {
+ assert targetSize >= 0: "size must be positive (got " + targetSize + "): likely integer overflow?";
+ final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
+ if (newSize != array.length) {
+ float[][] newArray = new float[newSize][];
+ System.arraycopy(array, 0, newArray, 0, newSize);
+ return newArray;
+ } else {
+ return array;
+ }
+ }
+
+ /**
+ * Returns hash of chars in range start (inclusive) to
+ * end (inclusive)
+ */
+ public static int hashCode(char[] array, int start, int end) {
+ int code = 0;
+ for (int i = end - 1; i >= start; i--)
+ code = code * 31 + array[i];
+ return code;
+ }
+
+ /**
+ * Returns hash of bytes in range start (inclusive) to
+ * end (inclusive)
+ */
+ public static int hashCode(byte[] array, int start, int end) {
+ int code = 0;
+ for (int i = end - 1; i >= start; i--)
+ code = code * 31 + array[i];
+ return code;
+ }
+
+
+ // Since Arrays.equals doesn't implement offsets for equals
+ /**
+ * See if two array slices are the same.
+ *
+ * @param left The left array to compare
+ * @param offsetLeft The offset into the array. Must be positive
+ * @param right The right array to compare
+ * @param offsetRight the offset into the right array. Must be positive
+ * @param length The length of the section of the array to compare
+ * @return true if the two arrays, starting at their respective offsets, are equal
+ *
+ * @see java.util.Arrays#equals(char[], char[])
+ */
+ public static boolean equals(char[] left, int offsetLeft, char[] right, int offsetRight, int length) {
+ if ((offsetLeft + length <= left.length) && (offsetRight + length <= right.length)) {
+ for (int i = 0; i < length; i++) {
+ if (left[offsetLeft + i] != right[offsetRight + i]) {
+ return false;
+ }
+
+ }
+ return true;
+ }
+ return false;
+ }
+
+ // Since Arrays.equals doesn't implement offsets for equals
+ /**
+ * See if two array slices are the same.
+ *
+ * @param left The left array to compare
+ * @param offsetLeft The offset into the array. Must be positive
+ * @param right The right array to compare
+ * @param offsetRight the offset into the right array. Must be positive
+ * @param length The length of the section of the array to compare
+ * @return true if the two arrays, starting at their respective offsets, are equal
+ *
+ * @see java.util.Arrays#equals(char[], char[])
+ */
+ public static boolean equals(int[] left, int offsetLeft, int[] right, int offsetRight, int length) {
+ if ((offsetLeft + length <= left.length) && (offsetRight + length <= right.length)) {
+ for (int i = 0; i < length; i++) {
+ if (left[offsetLeft + i] != right[offsetRight + i]) {
+ return false;
+ }
+
+ }
+ return true;
+ }
+ return false;
+ }
+
+ public static int[] toIntArray(Collection<Integer> ints) {
+
+ final int[] result = new int[ints.size()];
+ int upto = 0;
+ for(int v : ints) {
+ result[upto++] = v;
+ }
+
+ // paranoia:
+ assert upto == result.length;
+
+ return result;
+ }
+
+ /** SorterTemplate with custom {@link Comparator} */
+ private static <T> SorterTemplate getSorter(final T[] a, final Comparator<? super T> comp) {
+ return new SorterTemplate() {
+ @Override
+ protected void swap(int i, int j) {
+ final T o = a[i];
+ a[i] = a[j];
+ a[j] = o;
+ }
+
+ @Override
+ protected int compare(int i, int j) {
+ return comp.compare(a[i], a[j]);
+ }
+
+ @Override
+ protected void setPivot(int i) {
+ pivot = a[i];
+ }
+
+ @Override
+ protected int comparePivot(int j) {
+ return comp.compare(pivot, a[j]);
+ }
+
+ private T pivot;
+ };
+ }
+
+ /** Natural SorterTemplate */
+ private static <T extends Comparable<? super T>> SorterTemplate getSorter(final T[] a) {
+ return new SorterTemplate() {
+ @Override
+ protected void swap(int i, int j) {
+ final T o = a[i];
+ a[i] = a[j];
+ a[j] = o;
+ }
+
+ @Override
+ protected int compare(int i, int j) {
+ return a[i].compareTo(a[j]);
+ }
+
+ @Override
+ protected void setPivot(int i) {
+ pivot = a[i];
+ }
+
+ @Override
+ protected int comparePivot(int j) {
+ return pivot.compareTo(a[j]);
+ }
+
+ private T pivot;
+ };
+ }
+
+ // quickSorts (endindex is exclusive!):
+
+ /**
+ * Sorts the given array slice using the {@link Comparator}. This method uses the quick sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ * @param fromIndex start index (inclusive)
+ * @param toIndex end index (exclusive)
+ */
+ public static <T> void quickSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+ if (toIndex-fromIndex <= 1) return;
+ getSorter(a, comp).quickSort(fromIndex, toIndex-1);
+ }
+
+ /**
+ * Sorts the given array using the {@link Comparator}. This method uses the quick sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ */
+ public static <T> void quickSort(T[] a, Comparator<? super T> comp) {
+ quickSort(a, 0, a.length, comp);
+ }
+
+ /**
+ * Sorts the given array slice in natural order. This method uses the quick sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ * @param fromIndex start index (inclusive)
+ * @param toIndex end index (exclusive)
+ */
+ public static <T extends Comparable<? super T>> void quickSort(T[] a, int fromIndex, int toIndex) {
+ if (toIndex-fromIndex <= 1) return;
+ getSorter(a).quickSort(fromIndex, toIndex-1);
+ }
+
+ /**
+ * Sorts the given array in natural order. This method uses the quick sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ */
+ public static <T extends Comparable<? super T>> void quickSort(T[] a) {
+ quickSort(a, 0, a.length);
+ }
+
+ // mergeSorts:
+
+ /**
+ * Sorts the given array slice using the {@link Comparator}. This method uses the merge sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ * @param fromIndex start index (inclusive)
+ * @param toIndex end index (exclusive)
+ */
+ public static <T> void mergeSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+ if (toIndex-fromIndex <= 1) return;
+ //System.out.println("SORT: " + (toIndex-fromIndex));
+ getSorter(a, comp).mergeSort(fromIndex, toIndex-1);
+ }
+
+ /**
+ * Sorts the given array using the {@link Comparator}. This method uses the merge sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ */
+ public static <T> void mergeSort(T[] a, Comparator<? super T> comp) {
+ mergeSort(a, 0, a.length, comp);
+ }
+
+ /**
+ * Sorts the given array slice in natural order. This method uses the merge sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ * @param fromIndex start index (inclusive)
+ * @param toIndex end index (exclusive)
+ */
+ public static <T extends Comparable<? super T>> void mergeSort(T[] a, int fromIndex, int toIndex) {
+ if (toIndex-fromIndex <= 1) return;
+ getSorter(a).mergeSort(fromIndex, toIndex-1);
+ }
+
+ /**
+ * Sorts the given array in natural order. This method uses the merge sort
+ * algorithm, but falls back to insertion sort for small arrays.
+ */
+ public static <T extends Comparable<? super T>> void mergeSort(T[] a) {
+ mergeSort(a, 0, a.length);
+ }
+
+ // insertionSorts:
+
+ /**
+ * Sorts the given array slice using the {@link Comparator}. This method uses the insertion sort
+ * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
+ * @param fromIndex start index (inclusive)
+ * @param toIndex end index (exclusive)
+ */
+ public static <T> void insertionSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) {
+ if (toIndex-fromIndex <= 1) return;
+ getSorter(a, comp).insertionSort(fromIndex, toIndex-1);
+ }
+
+ /**
+ * Sorts the given array using the {@link Comparator}. This method uses the insertion sort
+ * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
+ */
+ public static <T> void insertionSort(T[] a, Comparator<? super T> comp) {
+ insertionSort(a, 0, a.length, comp);
+ }
+
+ /**
+ * Sorts the given array slice in natural order. This method uses the insertion sort
+ * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
+ * @param fromIndex start index (inclusive)
+ * @param toIndex end index (exclusive)
+ */
+ public static <T extends Comparable<? super T>> void insertionSort(T[] a, int fromIndex, int toIndex) {
+ if (toIndex-fromIndex <= 1) return;
+ getSorter(a).insertionSort(fromIndex, toIndex-1);
+ }
+
+ /**
+ * Sorts the given array in natural order. This method uses the insertion sort
+ * algorithm. It is only recommended to use this algorithm for partially sorted small arrays!
+ */
+ public static <T extends Comparable<? super T>> void insertionSort(T[] a) {
+ insertionSort(a, 0, a.length);
+ }
+
+}
\ No newline at end of file
fnp / pylucene.git / blobdiff