content: 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);
    }
  
  }