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

            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 float array to sort
   */
  public static void sort(float[] a)
  {
    qsort(a, 0, a.length);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the float array to sort
   * @param fromIndex the first index to sort (inclusive)
   * @param toIndex the last index to sort (exclusive)
   * @throws IllegalArgumentException if fromIndex > toIndex
   * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
   *         || toIndex > a.length
   */
  public static void sort(float[] 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, float[] d)
  {
    return (Float.compare(d[a], d[b]) < 0
            ? (Float.compare(d[b], d[c]) < 0 ? b
               : Float.compare(d[a], d[c]) < 0 ? c : a)
            : (Float.compare(d[b], d[c]) > 0 ? b
               : Float.compare(d[a], d[c]) > 0 ? 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, float[] a)
  {
    float 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, float[] 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(float[] 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 && Float.compare(array[j - 1], array[j]) > 0;
               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 = Float.compare(array[b], array[from])) <= 0)
          {
            if (comp == 0)
              {
                swap(a, b, array);
                a++;
              }
            b++;
          }
        while (c >= b && (comp = Float.compare(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 double array to sort
   */
  public static void sort(double[] a)
  {
    qsort(a, 0, a.length);
  }

  /**
   * Performs a stable sort on the elements, arranging them according to their
   * natural order.
   *
   * @param a the double 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(double[] 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, double[] d)
  {
    return (Double.compare(d[a], d[b]) < 0
            ? (Double.compare(d[b], d[c]) < 0 ? b
               : Double.compare(d[a], d[c]) < 0 ? c : a)
            : (Double.compare(d[b], d[c]) > 0 ? b
               : Double.compare(d[a], d[c]) > 0 ? 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, double[] a)
  {
    double 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, double[] 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(double[] 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 && Double.compare(array[j - 1], array[j]) > 0;
               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 = Double.compare(array[b], array[from])) <= 0)
          {
            if (comp == 0)
              {
                swap(a, b, array);
                a++;
              }
            b++;
          }
        while (c >= b && (comp = Double.compare(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);
  }

  /**
   * Sort an array of Objects according to their natural ordering. The sort is
   * guaranteed to be stable, that is, equal elements will not be reordered.
   * The sort algorithm is a mergesort with the merge omitted if the last
   * element of one half comes before the first element of the other half. This
   * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
   * copy of the array.
   *
   * @param a the array to be sorted
   * @throws ClassCastException if any two elements are not mutually
   *         comparable
   * @throws NullPointerException if an element is null (since
   *         null.compareTo cannot work)
   * @see Comparable
   */
  public static void sort(Object[] a)
  {
    sort(a, 0, a.length, null);
  }

  /**
   * Sort an array of Objects according to a Comparator. The sort is
   * guaranteed to be stable, that is, equal elements will not be reordered.
   * The sort algorithm is a mergesort with the merge omitted if the last
   * element of one half comes before the first element of the other half. This
   * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
   * copy of the array.
   *
   * @param a the array to be sorted
   * @param c a Comparator to use in sorting the array; or null to indicate
   *        the elements' natural order
   * @throws ClassCastException if any two elements are not mutually
   *         comparable by the Comparator provided
   * @throws NullPointerException if a null element is compared with natural
   *         ordering (only possible when c is null)
   */
  public static void sort(Object[] a, Comparator c)
  {
    sort(a, 0, a.length, c);
  }

  /**
   * Sort an array of Objects according to their natural ordering. The sort is
   * guaranteed to be stable, that is, equal elements will not be reordered.
   * The sort algorithm is a mergesort with the merge omitted if the last
   * element of one half comes before the first element of the other half. This
   * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
   * copy of the array.
   *
   * @param a the array to be sorted
   * @param fromIndex the index of the first element to be sorted
   * @param toIndex the index of the last element to be sorted plus one
   * @throws ClassCastException if any two elements are not mutually
   *         comparable
   * @throws NullPointerException if an element is null (since
   *         null.compareTo cannot work)
   * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
   *         are not in range.
   * @throws IllegalArgumentException if fromIndex &gt; toIndex
   */
  public static void sort(Object[] a, int fromIndex, int toIndex)
  {
    sort(a, fromIndex, toIndex, null);
  }

  /**
   * Sort an array of Objects according to a Comparator. The sort is
   * guaranteed to be stable, that is, equal elements will not be reordered.
   * The sort algorithm is a mergesort with the merge omitted if the last
   * element of one half comes before the first element of the other half. This
   * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
   * copy of the array.
   *
   * @param a the array to be sorted
   * @param fromIndex the index of the first element to be sorted
   * @param toIndex the index of the last element to be sorted plus one
   * @param c a Comparator to use in sorting the array; or null to indicate
   *        the elements' natural order
   * @throws ClassCastException if any two elements are not mutually
   *         comparable by the Comparator provided
   * @throws ArrayIndexOutOfBoundsException if f