arrays.java

this gcc-g++-3.3.1.tar.gz is a source file of gcc, you can learn more about gcc through this codes f

   * @param val the value to fill with
   * @throws IllegalArgumentException if fromIndex > toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
   *         || toIndex > a.length
   */
  public static void fill(float[] a, int fromIndex, int toIndex, float val)
  {
    if (fromIndex > toIndex)
      throw new IllegalArgumentException();
    for (int i = fromIndex; i < toIndex; i++)
      a[i] = val;
  }

  /**
   * Fill an array with a double value.
   *
   * @param a the array to fill
   * @param val the value to fill it with
   */
  public static void fill(double[] a, double val)
  {
    fill(a, 0, a.length, val);
  }

  /**
   * Fill a range of an array with a double value.
   *
   * @param a the array to fill
   * @param fromIndex the index to fill from, inclusive
   * @param toIndex the index to fill to, exclusive
   * @param val the value to fill with
   * @throws IllegalArgumentException if fromIndex &gt; toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
   *         || toIndex &gt; a.length
   */
  public static void fill(double[] a, int fromIndex, int toIndex, double val)
  {
    if (fromIndex > toIndex)
      throw new IllegalArgumentException();
    for (int i = fromIndex; i < toIndex; i++)
      a[i] = val;
  }

  /**
   * Fill an array with an Object value.
   *
   * @param a the array to fill
   * @param val the value to fill it with
   * @throws ClassCastException if val is not an instance of the element
   *         type of a.
   */
  public static void fill(Object[] a, Object val)
  {
    fill(a, 0, a.length, val);
  }

  /**
   * Fill a range of an array with an Object value.
   *
   * @param a the array to fill
   * @param fromIndex the index to fill from, inclusive
   * @param toIndex the index to fill to, exclusive
   * @param val the value to fill with
   * @throws ClassCastException if val is not an instance of the element
   *         type of a.
   * @throws IllegalArgumentException if fromIndex &gt; toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
   *         || toIndex &gt; a.length
   */
  public static void fill(Object[] a, int fromIndex, int toIndex, Object val)
  {
    if (fromIndex > toIndex)
      throw new IllegalArgumentException();
    for (int i = fromIndex; i < toIndex; i++)
      a[i] = val;
  }


// sort
  // Thanks to Paul Fisher <[e-mail]> for finding this quicksort algorithm
  // as specified by Sun and porting it to Java. The algorithm is an optimised
  // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
  // "Engineering a Sort Function", Software-Practice and Experience, Vol.
  // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
  // performance on many arrays that would take quadratic time with a standard
  // quicksort.

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the byte array to sort
   */
  public static void sort(byte[] a)
  {
    qsort(a, 0, a.length);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the byte array to sort
   * @param fromIndex the first index to sort (inclusive)
   * @param toIndex the last index to sort (exclusive)
   * @throws IllegalArgumentException if fromIndex &gt; toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
   *         || toIndex &gt; a.length
   */
  public static void sort(byte[] a, int fromIndex, int toIndex)
  {
    if (fromIndex > toIndex)
      throw new IllegalArgumentException();
    qsort(a, fromIndex, toIndex - fromIndex);
  }

  /**
   * Finds the index of the median of three array elements.
   *
   * @param a the first index
   * @param b the second index
   * @param c the third index
   * @param d the array
   * @return the index (a, b, or c) which has the middle value of the three
   */
  private static int med3(int a, int b, int c, byte[] d)
  {
    return (d[a] < d[b]
            ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
            : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
  }

  /**
   * Swaps the elements at two locations of an array
   *
   * @param i the first index
   * @param j the second index
   * @param a the array
   */
  private static void swap(int i, int j, byte[] a)
  {
    byte c = a[i];
    a[i] = a[j];
    a[j] = c;
  }

  /**
   * Swaps two ranges of an array.
   *
   * @param i the first range start
   * @param j the second range start
   * @param n the element count
   * @param a the array
   */
  private static void vecswap(int i, int j, int n, byte[] a)
  {
    for ( ; n > 0; i++, j++, n--)
      swap(i, j, a);
  }

  /**
   * Performs a recursive modified quicksort.
   *
   * @param a the array to sort
   * @param from the start index (inclusive)
   * @param count the number of elements to sort
   */
  private static void qsort(byte[] array, int from, int count)
  {
    // Use an insertion sort on small arrays.
    if (count <= 7)
      {
        for (int i = from + 1; i < from + count; i++)
          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
            swap(j, j - 1, array);
        return;
      }

    // Determine a good median element.
    int mid = count / 2;
    int lo = from;
    int hi = from + count - 1;

    if (count > 40)
      { // big arrays, pseudomedian of 9
        int s = count / 8;
        lo = med3(lo, lo + s, lo + 2 * s, array);
        mid = med3(mid - s, mid, mid + s, array);
        hi = med3(hi - 2 * s, hi - s, hi, array);
      }
    mid = med3(lo, mid, hi, array);

    int a, b, c, d;
    int comp;

    // Pull the median element out of the fray, and use it as a pivot.
    swap(from, mid, array);
    a = b = from;
    c = d = from + count - 1;

    // Repeatedly move b and c to each other, swapping elements so
    // that all elements before index b are less than the pivot, and all
    // elements after index c are greater than the pivot. a and b track
    // the elements equal to the pivot.
    while (true)
      {
        while (b <= c && (comp = array[b] - array[from]) <= 0)
          {
            if (comp == 0)
              {
                swap(a, b, array);
                a++;
              }
            b++;
          }
        while (c >= b && (comp = array[c] - array[from]) >= 0)
          {
            if (comp == 0)
              {
                swap(c, d, array);
                d--;
              }
            c--;
          }
        if (b > c)
          break;
        swap(b, c, array);
        b++;
        c--;
      }

    // Swap pivot(s) back in place, the recurse on left and right sections.
    hi = from + count;
    int span;
    span = Math.min(a - from, b - a);
    vecswap(from, b - span, span, array);

    span = Math.min(d - c, hi - d - 1);
    vecswap(b, hi - span, span, array);

    span = b - a;
    if (span > 1)
      qsort(array, from, span);

    span = d - c;
    if (span > 1)
      qsort(array, hi - span, span);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the char array to sort
   */
  public static void sort(char[] a)
  {
    qsort(a, 0, a.length);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the char array to sort
   * @param fromIndex the first index to sort (inclusive)
   * @param toIndex the last index to sort (exclusive)
   * @throws IllegalArgumentException if fromIndex &gt; toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
   *         || toIndex &gt; a.length
   */
  public static void sort(char[] a, int fromIndex, int toIndex)
  {
    if (fromIndex > toIndex)
      throw new IllegalArgumentException();
    qsort(a, fromIndex, toIndex - fromIndex);
  }

  /**
   * Finds the index of the median of three array elements.
   *
   * @param a the first index
   * @param b the second index
   * @param c the third index
   * @param d the array
   * @return the index (a, b, or c) which has the middle value of the three
   */
  private static int med3(int a, int b, int c, char[] d)
  {
    return (d[a] < d[b]
            ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
            : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
  }

  /**
   * Swaps the elements at two locations of an array
   *
   * @param i the first index
   * @param j the second index
   * @param a the array
   */
  private static void swap(int i, int j, char[] a)
  {
    char c = a[i];
    a[i] = a[j];
    a[j] = c;
  }

  /**
   * Swaps two ranges of an array.
   *
   * @param i the first range start
   * @param j the second range start
   * @param n the element count
   * @param a the array
   */
  private static void vecswap(int i, int j, int n, char[] a)
  {
    for ( ; n > 0; i++, j++, n--)
      swap(i, j, a);
  }

  /**
   * Performs a recursive modified quicksort.
   *
   * @param a the array to sort
   * @param from the start index (inclusive)
   * @param count the number of elements to sort
   */
  private static void qsort(char[] array, int from, int count)
  {
    // Use an insertion sort on small arrays.
    if (count <= 7)
      {
        for (int i = from + 1; i < from + count; i++)
          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
            swap(j, j - 1, array);
        return;
      }

    // Determine a good median element.
    int mid = count / 2;
    int lo = from;
    int hi = from + count - 1;

    if (count > 40)
      { // big arrays, pseudomedian of 9
        int s = count / 8;
        lo = med3(lo, lo + s, lo + 2 * s, array);
        mid = med3(mid - s, mid, mid + s, array);
        hi = med3(hi - 2 * s, hi - s, hi, array);
      }
    mid = med3(lo, mid, hi, array);

    int a, b, c, d;
    int comp;

    // Pull the median element out of the fray, and use it as a pivot.
    swap(from, mid, array);
    a = b = from;
    c = d = from + count - 1;

    // Repeatedly move b and c to each other, swapping elements so
    // that all elements before index b are less than the pivot, and all
    // elements after index c are greater than the pivot. a and b track
    // the elements equal to the pivot.
    while (true)
      {
        while (b <= c && (comp = array[b] - array[from]) <= 0)
          {
            if (comp == 0)
              {
                swap(a, b, array);
                a++;
              }
            b++;
          }
        while (c >= b && (comp = array[c] - array[from]) >= 0)
          {
            if (comp == 0)
              {
                swap(c, d, array);
                d--;
              }
            c--;
          }
        if (b > c)
          break;
        swap(b, c, array);
        b++;
        c--;
      }

    // Swap pivot(s) back in place, the recurse on left and right sections.
    hi = from + count;
    int span;
    span = Math.min(a - from, b - a);
    vecswap(from, b - span, span, array);

    span = Math.min(d - c, hi - d - 1);
    vecswap(b, hi - span, span, array);

    span = b - a;
    if (span > 1)
      qsort(array, from, span);

    span = d - c;
    if (span > 1)
      qsort(array, hi - span, span);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the short array to sort
   */
  public static void sort(short[] a)
  {
    qsort(a, 0, a.length);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the short array to sort
   * @param fromIndex the first index to sort (inclusive)
   * @param toIndex the last index to sort (exclusive)
   * @throws IllegalArgumentException if fromIndex &gt; toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
   *         || toIndex &gt; a.length
   */
  public static void sort(short[] a, int fromIndex, int toIndex)
  {
    if (fromIndex > toIndex)
      throw new IllegalArgumentException();
    qsort(a, fromIndex, toIndex - fromIndex);
  }

  /**
   * Finds the index of the median of three array elements.
   *
   * @param a the first index
   * @param b the second index
   * @param c the third index
   * @param d the array