| /* |
| * 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. |
| */ |
| package org.apache.lucene.util; |
| |
| import java.util.Arrays; |
| import java.util.Comparator; |
| |
| /** |
| * Methods for manipulating arrays. |
| * |
| * @lucene.internal |
| */ |
| |
| public final class ArrayUtil { |
| |
| /** Maximum length for an array (Integer.MAX_VALUE - RamUsageEstimator.NUM_BYTES_ARRAY_HEADER). */ |
| public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - RamUsageEstimator.NUM_BYTES_ARRAY_HEADER; |
| |
| private 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 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; |
| } |
| |
| if (minTargetSize > MAX_ARRAY_LENGTH) { |
| throw new IllegalArgumentException("requested array size " + minTargetSize + " exceeds maximum array in java (" + MAX_ARRAY_LENGTH + ")"); |
| } |
| |
| // 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 || newSize+7 > MAX_ARRAY_LENGTH) { |
| // int overflowed, or we exceeded the maximum array length |
| return MAX_ARRAY_LENGTH; |
| } |
| |
| 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 <T> T[] grow(T[] array, int minSize) { |
| assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?"; |
| if (array.length < minSize) { |
| return Arrays.copyOf(array, oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)); |
| } else |
| return array; |
| } |
| |
| public static short[] grow(short[] array, int minSize) { |
| assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?"; |
| if (array.length < minSize) { |
| return Arrays.copyOf(array, oversize(minSize, Short.BYTES)); |
| } 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) { |
| return Arrays.copyOf(array, oversize(minSize, Float.BYTES)); |
| } 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) { |
| return Arrays.copyOf(array, oversize(minSize, Double.BYTES)); |
| } else |
| return array; |
| } |
| |
| public static double[] grow(double[] array) { |
| return grow(array, 1 + array.length); |
| } |
| |
| public static int[] grow(int[] array, int minSize) { |
| assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?"; |
| if (array.length < minSize) { |
| return Arrays.copyOf(array, oversize(minSize, Integer.BYTES)); |
| } else |
| return array; |
| } |
| |
| public static int[] grow(int[] array) { |
| return grow(array, 1 + array.length); |
| } |
| |
| public static long[] grow(long[] array, int minSize) { |
| assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?"; |
| if (array.length < minSize) { |
| return Arrays.copyOf(array, oversize(minSize, Long.BYTES)); |
| } else |
| return array; |
| } |
| |
| public static long[] grow(long[] array) { |
| return grow(array, 1 + array.length); |
| } |
| |
| public static byte[] grow(byte[] array, int minSize) { |
| assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?"; |
| if (array.length < minSize) { |
| return Arrays.copyOf(array, oversize(minSize, Byte.BYTES)); |
| } else |
| return array; |
| } |
| |
| public static byte[] grow(byte[] array) { |
| return grow(array, 1 + array.length); |
| } |
| |
| public static char[] grow(char[] array, int minSize) { |
| assert minSize >= 0: "size must be positive (got " + minSize + "): likely integer overflow?"; |
| if (array.length < minSize) { |
| return Arrays.copyOf(array, oversize(minSize, Character.BYTES)); |
| } else |
| return array; |
| } |
| |
| public static char[] grow(char[] array) { |
| return grow(array, 1 + array.length); |
| } |
| |
| /** |
| * 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; |
| } |
| |
| // 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(byte[], byte[]) |
| */ |
| public static boolean equals(byte[] left, int offsetLeft, byte[] 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; |
| } |
| |
| /** Swap values stored in slots <code>i</code> and <code>j</code> */ |
| public static <T> void swap(T[] arr, int i, int j) { |
| final T tmp = arr[i]; |
| arr[i] = arr[j]; |
| arr[j] = tmp; |
| } |
| |
| // intro-sorts |
| |
| /** |
| * Sorts the given array slice using the {@link Comparator}. This method uses the intro 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 introSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) { |
| if (toIndex-fromIndex <= 1) return; |
| new ArrayIntroSorter<>(a, comp).sort(fromIndex, toIndex); |
| } |
| |
| /** |
| * Sorts the given array using the {@link Comparator}. This method uses the intro sort |
| * algorithm, but falls back to insertion sort for small arrays. |
| */ |
| public static <T> void introSort(T[] a, Comparator<? super T> comp) { |
| introSort(a, 0, a.length, comp); |
| } |
| |
| /** |
| * Sorts the given array slice in natural order. This method uses the intro 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 introSort(T[] a, int fromIndex, int toIndex) { |
| if (toIndex-fromIndex <= 1) return; |
| introSort(a, fromIndex, toIndex, Comparator.naturalOrder()); |
| } |
| |
| /** |
| * Sorts the given array in natural order. This method uses the intro sort |
| * algorithm, but falls back to insertion sort for small arrays. |
| */ |
| public static <T extends Comparable<? super T>> void introSort(T[] a) { |
| introSort(a, 0, a.length); |
| } |
| |
| // tim sorts: |
| |
| /** |
| * Sorts the given array slice using the {@link Comparator}. This method uses the Tim sort |
| * algorithm, but falls back to binary sort for small arrays. |
| * @param fromIndex start index (inclusive) |
| * @param toIndex end index (exclusive) |
| */ |
| public static <T> void timSort(T[] a, int fromIndex, int toIndex, Comparator<? super T> comp) { |
| if (toIndex-fromIndex <= 1) return; |
| new ArrayTimSorter<>(a, comp, a.length / 64).sort(fromIndex, toIndex); |
| } |
| |
| /** |
| * Sorts the given array using the {@link Comparator}. This method uses the Tim sort |
| * algorithm, but falls back to binary sort for small arrays. |
| */ |
| public static <T> void timSort(T[] a, Comparator<? super T> comp) { |
| timSort(a, 0, a.length, comp); |
| } |
| |
| /** |
| * Sorts the given array slice in natural order. This method uses the Tim sort |
| * algorithm, but falls back to binary sort for small arrays. |
| * @param fromIndex start index (inclusive) |
| * @param toIndex end index (exclusive) |
| */ |
| public static <T extends Comparable<? super T>> void timSort(T[] a, int fromIndex, int toIndex) { |
| if (toIndex-fromIndex <= 1) return; |
| timSort(a, fromIndex, toIndex, Comparator.naturalOrder()); |
| } |
| |
| /** |
| * Sorts the given array in natural order. This method uses the Tim sort |
| * algorithm, but falls back to binary sort for small arrays. |
| */ |
| public static <T extends Comparable<? super T>> void timSort(T[] a) { |
| timSort(a, 0, a.length); |
| } |
| |
| /** Reorganize {@code arr[from:to[} so that the element at offset k is at the |
| * same position as if {@code arr[from:to[} was sorted, and all elements on |
| * its left are less than or equal to it, and all elements on its right are |
| * greater than or equal to it. |
| * This runs in linear time on average and in {@code n log(n)} time in the |
| * worst case.*/ |
| public static <T> void select(T[] arr, int from, int to, int k, Comparator<? super T> comparator) { |
| new IntroSelector() { |
| |
| T pivot; |
| |
| @Override |
| protected void swap(int i, int j) { |
| ArrayUtil.swap(arr, i, j); |
| } |
| |
| @Override |
| protected void setPivot(int i) { |
| pivot = arr[i]; |
| } |
| |
| @Override |
| protected int comparePivot(int j) { |
| return comparator.compare(pivot, arr[j]); |
| } |
| }.select(from, to, k); |
| } |
| |
| } |