/*
 * @(#)Arrays.java	1.59 04/04/01
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

/**
 * This class contains various methods for manipulating arrays (such as sorting and searching). This class also contains
 * a static factory that allows arrays to be viewed as lists.
 *
 * <p>
 * The methods in this class all throw a <tt>NullPointerException</tt> if the specified array reference is null, except
 * where noted.
 *
 * <p>
 * The documentation for the methods contained in this class includes briefs description of the <i>implementations</i>.
 * Such descriptions should be regarded as <i>implementation notes</i>, rather than parts of the <i>specification</i>.
 * Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to. (For
 * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be a mergesort, but it does have to be
 * <i>stable</i>.)
 *
 * <p>
 * This class is a member of the <a href="{@docRoot}/../guide/collections/index.html"> Java Collections Framework</a>.
 *
 * @author Josh Bloch
 * @author Neal Gafter
 * @version 1.59, 04/01/04
 * @see Comparable
 * @see Comparator
 * @since 1.2
 */

public class Arrays {
    // Suppresses default constructor, ensuring non-instantiability.
    private Arrays() {
    }

    // Sorting

    /**
     * Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort,
     * adapted from 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 offers n*log(n) performance on many data
     * sets that cause other quicksorts to degrade to quadratic performance.
     *
     * @param a
     *            the array to be sorted.
     */
    public static void sort(int[] a) {
        sort1(a, 0, a.length);
    }

    /**
     * Sorts the specified sub-array of integers into ascending order.
     */
    private static void sort1(int x[], int off, int len) {
        // Insertion sort on smallest arrays
        if (len < 7) {
            for (int i = off; i < len + off; i++)
                for (int j = i; j > off && x[j - 1] > x[j]; j--)
                    swap(x, j, j - 1);
            return;
        }

        // Choose a partition element, v
        int m = off + (len >> 1); // Small arrays, middle element
        if (len > 7) {
            int l = off;
            int n = off + len - 1;
            /*
             * if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x,
             * m-s, m, m+s); n = med3(x, n-2*s, n-s, n); }
             */
            m = med3(x, l, m, n); // Mid-size, med of 3
        }
        int v = x[m];

        // Establish Invariant: v* (<v)* (>v)* v*
        int a = off, b = a, c = off + len - 1, d = c;
        while (true) {
            while (b <= c && x[b] <= v) {
                if (x[b] == v)
                    swap(x, a++, b);
                b++;
            }
            while (c >= b && x[c] >= v) {
                if (x[c] == v)
                    swap(x, c, d--);
                c--;
            }
            if (b > c)
                break;
            swap(x, b++, c--);
        }

        // Swap partition elements back to middle
        int s, n = off + len;
        s = Math.min(a - off, b - a);
        vecswap(x, off, b - s, s);
        s = Math.min(d - c, n - d - 1);
        vecswap(x, b, n - s, s);

        // Recursively sort non-partition-elements
        if ((s = b - a) > 1)
            sort1(x, off, s);
        if ((s = d - c) > 1)
            sort1(x, n - s, s);
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(int x[], int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    /**
     * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
     */
    private static void vecswap(int x[], int a, int b, int n) {
        for (int i = 0; i < n; i++, a++, b++)
            swap(x, a, b);
    }

    /**
     * Returns the index of the median of the three indexed integers.
     */
    private static int med3(int x[], int a, int b, int c) {
        return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
    }

    /**
     * Sorts the specified array of objects into ascending order, according to the <i>natural ordering</i> of its
     * elements. All elements in the array must implement the <tt>Comparable</tt> interface. Furthermore, all elements
     * in the array must be <i>mutually comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
     * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in the array).
     * <p>
     *
     * This sort is guaranteed to be <i>stable</i>: equal elements will not be reordered as a result of the sort.
     * <p>
     *
     * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low
     * sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n)
     * performance.
     *
     * @param a
     *            the array to be sorted.
     * @throws ClassCastException
     *             if the array contains elements that are not <i>mutually comparable</i> (for example, strings and
     *             integers).
     * @see Comparable
     */
    public static void sort(Object[] a) {
        Object[] aux = (Object[]) a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }

    /**
     * Tuning parameter: list size at or below which insertion sort will be used in preference to mergesort or
     * quicksort.
     */
    private static final int INSERTIONSORT_THRESHOLD = 7;

    /**
     * Src is the source array that starts at index 0 Dest is the (possibly larger) array destination with a possible
     * offset low is the index in dest to start sorting high is the end index in dest to end sorting off is the offset
     * to generate corresponding low, high in src
     */
    private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i = low; i < high; i++)
                for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                    swap(dest, j, j - 1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest. This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
}
