X-Git-Url: https://git.mdrn.pl/pylucene.git/blobdiff_plain/a2e61f0c04805cfcb8706176758d1283c7e3a55c..aaeed5504b982cf3545252ab528713250aa33eed:/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/ArrayUtil.java?ds=inline diff --git a/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/ArrayUtil.java b/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/ArrayUtil.java deleted file mode 100644 index 253db78..0000000 --- a/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/ArrayUtil.java +++ /dev/null @@ -1,738 +0,0 @@ -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 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 SorterTemplate getSorter(final T[] a, final Comparator 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 > 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 void quickSort(T[] a, int fromIndex, int toIndex, Comparator 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 void quickSort(T[] a, Comparator 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 > 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 > 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 void mergeSort(T[] a, int fromIndex, int toIndex, Comparator 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 void mergeSort(T[] a, Comparator 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 > 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 > 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 void insertionSort(T[] a, int fromIndex, int toIndex, Comparator 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 void insertionSort(T[] a, Comparator 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 > 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 > void insertionSort(T[] a) { - insertionSort(a, 0, a.length); - } - -} \ No newline at end of file