0001: /*
0002: * @(#)Arrays.java 1.44 06/10/10
0003: *
0004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: *
0026: */
0027:
0028: package java.util;
0029:
0030: import java.lang.reflect.*;
0031:
0032: /**
0033: * This class contains various methods for manipulating arrays (such as
0034: * sorting and searching). This class also contains a static factory
0035: * that allows arrays to be viewed as lists.
0036: *
0037: * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
0038: * the specified array reference is null.
0039: *
0040: * <p>The documentation for the methods contained in this class includes
0041: * briefs description of the <i>implementations</i>. Such descriptions should
0042: * be regarded as <i>implementation notes</i>, rather than parts of the
0043: * <i>specification</i>. Implementors should feel free to substitute other
0044: * algorithms, so long as the specification itself is adhered to. (For
0045: * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
0046: * a mergesort, but it does have to be <i>stable</i>.)
0047: *
0048: * <p>This class is a member of the
0049: * <a href="{@docRoot}/../guide/collections/index.html">
0050: * Java Collections Framework</a>.
0051: *
0052: * @author Josh Bloch
0053: * @version 1.44, 10/10/06
0054: * @see Comparable
0055: * @see Comparator
0056: * @since 1.2
0057: */
0058:
0059: public class Arrays {
0060: // Suppresses default constructor, ensuring non-instantiability.
0061: private Arrays() {
0062: }
0063:
0064: // Sorting
0065:
0066: /**
0067: * Sorts the specified array of longs into ascending numerical order.
0068: * The sorting algorithm is a tuned quicksort, adapted from Jon
0069: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0070: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0071: * 1993). This algorithm offers n*log(n) performance on many data sets
0072: * that cause other quicksorts to degrade to quadratic performance.
0073: *
0074: * @param a the array to be sorted.
0075: */
0076: public static void sort(long[] a) {
0077: sort1(a, 0, a.length);
0078: }
0079:
0080: /**
0081: * Sorts the specified range of the specified array of longs into
0082: * ascending numerical order. The range to be sorted extends from index
0083: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0084: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
0085: *
0086: * <p>The sorting algorithm is a tuned quicksort, adapted from Jon
0087: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0088: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0089: * 1993). This algorithm offers n*log(n) performance on many data sets
0090: * that cause other quicksorts to degrade to quadratic performance.
0091: *
0092: * @param a the array to be sorted.
0093: * @param fromIndex the index of the first element (inclusive) to be
0094: * sorted.
0095: * @param toIndex the index of the last element (exclusive) to be sorted.
0096: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0097: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0098: * <tt>toIndex > a.length</tt>
0099: */
0100: public static void sort(long[] a, int fromIndex, int toIndex) {
0101: rangeCheck(a.length, fromIndex, toIndex);
0102: sort1(a, fromIndex, toIndex - fromIndex);
0103: }
0104:
0105: /**
0106: * Sorts the specified array of ints into ascending numerical order.
0107: * The sorting algorithm is a tuned quicksort, adapted from Jon
0108: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0109: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0110: * 1993). This algorithm offers n*log(n) performance on many data sets
0111: * that cause other quicksorts to degrade to quadratic performance.
0112: *
0113: * @param a the array to be sorted.
0114: */
0115: public static void sort(int[] a) {
0116: sort1(a, 0, a.length);
0117: }
0118:
0119: /**
0120: * Sorts the specified range of the specified array of ints into
0121: * ascending numerical order. The range to be sorted extends from index
0122: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0123: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0124: *
0125: * The sorting algorithm is a tuned quicksort, adapted from Jon
0126: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0127: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0128: * 1993). This algorithm offers n*log(n) performance on many data sets
0129: * that cause other quicksorts to degrade to quadratic performance.
0130: *
0131: * @param a the array to be sorted.
0132: * @param fromIndex the index of the first element (inclusive) to be
0133: * sorted.
0134: * @param toIndex the index of the last element (exclusive) to be sorted.
0135: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0136: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0137: * <tt>toIndex > a.length</tt>
0138: */
0139: public static void sort(int[] a, int fromIndex, int toIndex) {
0140: rangeCheck(a.length, fromIndex, toIndex);
0141: sort1(a, fromIndex, toIndex - fromIndex);
0142: }
0143:
0144: /**
0145: * Sorts the specified array of shorts into ascending numerical order.
0146: * The sorting algorithm is a tuned quicksort, adapted from Jon
0147: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0148: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0149: * 1993). This algorithm offers n*log(n) performance on many data sets
0150: * that cause other quicksorts to degrade to quadratic performance.
0151: *
0152: * @param a the array to be sorted.
0153: */
0154: public static void sort(short[] a) {
0155: sort1(a, 0, a.length);
0156: }
0157:
0158: /**
0159: * Sorts the specified range of the specified array of shorts into
0160: * ascending numerical order. The range to be sorted extends from index
0161: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0162: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0163: *
0164: * The sorting algorithm is a tuned quicksort, adapted from Jon
0165: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0166: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0167: * 1993). This algorithm offers n*log(n) performance on many data sets
0168: * that cause other quicksorts to degrade to quadratic performance.
0169: *
0170: * @param a the array to be sorted.
0171: * @param fromIndex the index of the first element (inclusive) to be
0172: * sorted.
0173: * @param toIndex the index of the last element (exclusive) to be sorted.
0174: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0175: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0176: * <tt>toIndex > a.length</tt>
0177: */
0178: public static void sort(short[] a, int fromIndex, int toIndex) {
0179: rangeCheck(a.length, fromIndex, toIndex);
0180: sort1(a, fromIndex, toIndex - fromIndex);
0181: }
0182:
0183: /**
0184: * Sorts the specified array of chars into ascending numerical order.
0185: * The sorting algorithm is a tuned quicksort, adapted from Jon
0186: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0187: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0188: * 1993). This algorithm offers n*log(n) performance on many data sets
0189: * that cause other quicksorts to degrade to quadratic performance.
0190: *
0191: * @param a the array to be sorted.
0192: */
0193: public static void sort(char[] a) {
0194: sort1(a, 0, a.length);
0195: }
0196:
0197: /**
0198: * Sorts the specified range of the specified array of chars into
0199: * ascending numerical order. The range to be sorted extends from index
0200: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0201: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0202: *
0203: * The sorting algorithm is a tuned quicksort, adapted from Jon
0204: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0205: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0206: * 1993). This algorithm offers n*log(n) performance on many data sets
0207: * that cause other quicksorts to degrade to quadratic performance.
0208: *
0209: * @param a the array to be sorted.
0210: * @param fromIndex the index of the first element (inclusive) to be
0211: * sorted.
0212: * @param toIndex the index of the last element (exclusive) to be sorted.
0213: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0214: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0215: * <tt>toIndex > a.length</tt>
0216: */
0217: public static void sort(char[] a, int fromIndex, int toIndex) {
0218: rangeCheck(a.length, fromIndex, toIndex);
0219: sort1(a, fromIndex, toIndex - fromIndex);
0220: }
0221:
0222: /**
0223: * Sorts the specified array of bytes into ascending numerical order.
0224: * The sorting algorithm is a tuned quicksort, adapted from Jon
0225: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0226: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0227: * 1993). This algorithm offers n*log(n) performance on many data sets
0228: * that cause other quicksorts to degrade to quadratic performance.
0229: *
0230: * @param a the array to be sorted.
0231: */
0232: public static void sort(byte[] a) {
0233: sort1(a, 0, a.length);
0234: }
0235:
0236: /**
0237: * Sorts the specified range of the specified array of bytes into
0238: * ascending numerical order. The range to be sorted extends from index
0239: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0240: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0241: *
0242: * The sorting algorithm is a tuned quicksort, adapted from Jon
0243: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0244: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0245: * 1993). This algorithm offers n*log(n) performance on many data sets
0246: * that cause other quicksorts to degrade to quadratic performance.
0247: *
0248: * @param a the array to be sorted.
0249: * @param fromIndex the index of the first element (inclusive) to be
0250: * sorted.
0251: * @param toIndex the index of the last element (exclusive) to be sorted.
0252: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0253: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0254: * <tt>toIndex > a.length</tt>
0255: */
0256: public static void sort(byte[] a, int fromIndex, int toIndex) {
0257: rangeCheck(a.length, fromIndex, toIndex);
0258: sort1(a, fromIndex, toIndex - fromIndex);
0259: }
0260:
0261: /**
0262: * Sorts the specified array of doubles into ascending numerical order.
0263: * <p>
0264: * The <code><</code> relation does not provide a total order on
0265: * all floating-point values; although they are distinct numbers
0266: * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
0267: * compares neither less than, greater than, nor equal to any
0268: * floating-point value, even itself. To allow the sort to
0269: * proceed, instead of using the <code><</code> relation to
0270: * determine ascending numerical order, this method uses the total
0271: * order imposed by {@link Double#compareTo}. This ordering
0272: * differs from the <code><</code> relation in that
0273: * <code>-0.0</code> is treated as less than <code>0.0</code> and
0274: * NaN is considered greater than any other floating-point value.
0275: * For the purposes of sorting, all NaN values are considered
0276: * equivalent and equal.
0277: * <p>
0278: * The sorting algorithm is a tuned quicksort, adapted from Jon
0279: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0280: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0281: * 1993). This algorithm offers n*log(n) performance on many data sets
0282: * that cause other quicksorts to degrade to quadratic performance.
0283: *
0284: * @param a the array to be sorted.
0285: */
0286: public static void sort(double[] a) {
0287: sort2(a, 0, a.length);
0288: }
0289:
0290: /**
0291: * Sorts the specified range of the specified array of doubles into
0292: * ascending numerical order. The range to be sorted extends from index
0293: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0294: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
0295: * <p>
0296: * The <code><</code> relation does not provide a total order on
0297: * all floating-point values; although they are distinct numbers
0298: * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
0299: * compares neither less than, greater than, nor equal to any
0300: * floating-point value, even itself. To allow the sort to
0301: * proceed, instead of using the <code><</code> relation to
0302: * determine ascending numerical order, this method uses the total
0303: * order imposed by {@link Double#compareTo}. This ordering
0304: * differs from the <code><</code> relation in that
0305: * <code>-0.0</code> is treated as less than <code>0.0</code> and
0306: * NaN is considered greater than any other floating-point value.
0307: * For the purposes of sorting, all NaN values are considered
0308: * equivalent and equal.
0309: * <p>
0310: * The sorting algorithm is a tuned quicksort, adapted from Jon
0311: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0312: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0313: * 1993). This algorithm offers n*log(n) performance on many data sets
0314: * that cause other quicksorts to degrade to quadratic performance.
0315: *
0316: * @param a the array to be sorted.
0317: * @param fromIndex the index of the first element (inclusive) to be
0318: * sorted.
0319: * @param toIndex the index of the last element (exclusive) to be sorted.
0320: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0321: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0322: * <tt>toIndex > a.length</tt>
0323: */
0324: public static void sort(double[] a, int fromIndex, int toIndex) {
0325: rangeCheck(a.length, fromIndex, toIndex);
0326: sort2(a, fromIndex, toIndex);
0327: }
0328:
0329: /**
0330: * Sorts the specified array of floats into ascending numerical order.
0331: * <p>
0332: * The <code><</code> relation does not provide a total order on
0333: * all floating-point values; although they are distinct numbers
0334: * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
0335: * compares neither less than, greater than, nor equal to any
0336: * floating-point value, even itself. To allow the sort to
0337: * proceed, instead of using the <code><</code> relation to
0338: * determine ascending numerical order, this method uses the total
0339: * order imposed by {@link Float#compareTo}. This ordering
0340: * differs from the <code><</code> relation in that
0341: * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
0342: * NaN is considered greater than any other floating-point value.
0343: * For the purposes of sorting, all NaN values are considered
0344: * equivalent and equal.
0345: * <p>
0346: * The sorting algorithm is a tuned quicksort, adapted from Jon
0347: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0348: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0349: * 1993). This algorithm offers n*log(n) performance on many data sets
0350: * that cause other quicksorts to degrade to quadratic performance.
0351: *
0352: * @param a the array to be sorted.
0353: */
0354: public static void sort(float[] a) {
0355: sort2(a, 0, a.length);
0356: }
0357:
0358: /**
0359: * Sorts the specified range of the specified array of floats into
0360: * ascending numerical order. The range to be sorted extends from index
0361: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0362: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
0363: * <p>
0364: * The <code><</code> relation does not provide a total order on
0365: * all floating-point values; although they are distinct numbers
0366: * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
0367: * compares neither less than, greater than, nor equal to any
0368: * floating-point value, even itself. To allow the sort to
0369: * proceed, instead of using the <code><</code> relation to
0370: * determine ascending numerical order, this method uses the total
0371: * order imposed by {@link Float#compareTo}. This ordering
0372: * differs from the <code><</code> relation in that
0373: * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
0374: * NaN is considered greater than any other floating-point value.
0375: * For the purposes of sorting, all NaN values are considered
0376: * equivalent and equal.
0377: * <p>
0378: * The sorting algorithm is a tuned quicksort, adapted from Jon
0379: * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0380: * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0381: * 1993). This algorithm offers n*log(n) performance on many data sets
0382: * that cause other quicksorts to degrade to quadratic performance.
0383: *
0384: * @param a the array to be sorted.
0385: * @param fromIndex the index of the first element (inclusive) to be
0386: * sorted.
0387: * @param toIndex the index of the last element (exclusive) to be sorted.
0388: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0389: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0390: * <tt>toIndex > a.length</tt>
0391: */
0392: public static void sort(float[] a, int fromIndex, int toIndex) {
0393: rangeCheck(a.length, fromIndex, toIndex);
0394: sort2(a, fromIndex, toIndex);
0395: }
0396:
0397: private static void sort2(double a[], int fromIndex, int toIndex) {
0398: final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
0399: /*
0400: * The sort is done in three phases to avoid the expense of using
0401: * NaN and -0.0 aware comparisons during the main sort.
0402: */
0403:
0404: /*
0405: * Preprocessing phase: Move any NaN's to end of array, count the
0406: * number of -0.0's, and turn them into 0.0's.
0407: */
0408: int numNegZeros = 0;
0409: int i = fromIndex, n = toIndex;
0410: while (i < n) {
0411: if (a[i] != a[i]) {
0412: double swap = a[i];
0413: a[i] = a[--n];
0414: a[n] = swap;
0415: } else {
0416: if (a[i] == 0
0417: && Double.doubleToLongBits(a[i]) == NEG_ZERO_BITS) {
0418: a[i] = 0.0d;
0419: numNegZeros++;
0420: }
0421: i++;
0422: }
0423: }
0424:
0425: // Main sort phase: quicksort everything but the NaN's
0426: sort1(a, fromIndex, n - fromIndex);
0427:
0428: // Postprocessing phase: change 0.0's to -0.0's as required
0429: if (numNegZeros != 0) {
0430: int j = binarySearch(a, 0.0d, fromIndex, n - 1); // posn of ANY zero
0431: do {
0432: j--;
0433: } while (j >= 0 && a[j] == 0.0d);
0434:
0435: // j is now one less than the index of the FIRST zero
0436: for (int k = 0; k < numNegZeros; k++)
0437: a[++j] = -0.0d;
0438: }
0439: }
0440:
0441: private static void sort2(float a[], int fromIndex, int toIndex) {
0442: final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
0443: /*
0444: * The sort is done in three phases to avoid the expense of using
0445: * NaN and -0.0 aware comparisons during the main sort.
0446: */
0447:
0448: /*
0449: * Preprocessing phase: Move any NaN's to end of array, count the
0450: * number of -0.0's, and turn them into 0.0's.
0451: */
0452: int numNegZeros = 0;
0453: int i = fromIndex, n = toIndex;
0454: while (i < n) {
0455: if (a[i] != a[i]) {
0456: float swap = a[i];
0457: a[i] = a[--n];
0458: a[n] = swap;
0459: } else {
0460: if (a[i] == 0
0461: && Float.floatToIntBits(a[i]) == NEG_ZERO_BITS) {
0462: a[i] = 0.0f;
0463: numNegZeros++;
0464: }
0465: i++;
0466: }
0467: }
0468:
0469: // Main sort phase: quicksort everything but the NaN's
0470: sort1(a, fromIndex, n - fromIndex);
0471:
0472: // Postprocessing phase: change 0.0's to -0.0's as required
0473: if (numNegZeros != 0) {
0474: int j = binarySearch(a, 0.0f, fromIndex, n - 1); // posn of ANY zero
0475: do {
0476: j--;
0477: } while (j >= 0 && a[j] == 0.0f);
0478:
0479: // j is now one less than the index of the FIRST zero
0480: for (int k = 0; k < numNegZeros; k++)
0481: a[++j] = -0.0f;
0482: }
0483: }
0484:
0485: /*
0486: * The code for each of the seven primitive types is largely identical.
0487: * C'est la vie.
0488: */
0489:
0490: /**
0491: * Sorts the specified sub-array of longs into ascending order.
0492: */
0493: private static void sort1(long x[], int off, int len) {
0494: // Insertion sort on smallest arrays
0495: if (len < 7) {
0496: for (int i = off; i < len + off; i++)
0497: for (int j = i; j > off && x[j - 1] > x[j]; j--)
0498: swap(x, j, j - 1);
0499: return;
0500: }
0501:
0502: // Choose a partition element, v
0503: int m = off + (len >> 1); // Small arrays, middle element
0504: if (len > 7) {
0505: int l = off;
0506: int n = off + len - 1;
0507: if (len > 40) { // Big arrays, pseudomedian of 9
0508: int s = len / 8;
0509: l = med3(x, l, l + s, l + 2 * s);
0510: m = med3(x, m - s, m, m + s);
0511: n = med3(x, n - 2 * s, n - s, n);
0512: }
0513: m = med3(x, l, m, n); // Mid-size, med of 3
0514: }
0515: long v = x[m];
0516:
0517: // Establish Invariant: v* (<v)* (>v)* v*
0518: int a = off, b = a, c = off + len - 1, d = c;
0519: while (true) {
0520: while (b <= c && x[b] <= v) {
0521: if (x[b] == v)
0522: swap(x, a++, b);
0523: b++;
0524: }
0525: while (c >= b && x[c] >= v) {
0526: if (x[c] == v)
0527: swap(x, c, d--);
0528: c--;
0529: }
0530: if (b > c)
0531: break;
0532: swap(x, b++, c--);
0533: }
0534:
0535: // Swap partition elements back to middle
0536: int s, n = off + len;
0537: s = Math.min(a - off, b - a);
0538: vecswap(x, off, b - s, s);
0539: s = Math.min(d - c, n - d - 1);
0540: vecswap(x, b, n - s, s);
0541:
0542: // Recursively sort non-partition-elements
0543: if ((s = b - a) > 1)
0544: sort1(x, off, s);
0545: if ((s = d - c) > 1)
0546: sort1(x, n - s, s);
0547: }
0548:
0549: /**
0550: * Swaps x[a] with x[b].
0551: */
0552: private static void swap(long x[], int a, int b) {
0553: long t = x[a];
0554: x[a] = x[b];
0555: x[b] = t;
0556: }
0557:
0558: /**
0559: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0560: */
0561: private static void vecswap(long x[], int a, int b, int n) {
0562: for (int i = 0; i < n; i++, a++, b++)
0563: swap(x, a, b);
0564: }
0565:
0566: /**
0567: * Returns the index of the median of the three indexed longs.
0568: */
0569: private static int med3(long x[], int a, int b, int c) {
0570: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0571: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0572: }
0573:
0574: /**
0575: * Sorts the specified sub-array of integers into ascending order.
0576: */
0577: private static void sort1(int x[], int off, int len) {
0578: // Insertion sort on smallest arrays
0579: if (len < 7) {
0580: for (int i = off; i < len + off; i++)
0581: for (int j = i; j > off && x[j - 1] > x[j]; j--)
0582: swap(x, j, j - 1);
0583: return;
0584: }
0585:
0586: // Choose a partition element, v
0587: int m = off + (len >> 1); // Small arrays, middle element
0588: if (len > 7) {
0589: int l = off;
0590: int n = off + len - 1;
0591: if (len > 40) { // Big arrays, pseudomedian of 9
0592: int s = len / 8;
0593: l = med3(x, l, l + s, l + 2 * s);
0594: m = med3(x, m - s, m, m + s);
0595: n = med3(x, n - 2 * s, n - s, n);
0596: }
0597: m = med3(x, l, m, n); // Mid-size, med of 3
0598: }
0599: int v = x[m];
0600:
0601: // Establish Invariant: v* (<v)* (>v)* v*
0602: int a = off, b = a, c = off + len - 1, d = c;
0603: while (true) {
0604: while (b <= c && x[b] <= v) {
0605: if (x[b] == v)
0606: swap(x, a++, b);
0607: b++;
0608: }
0609: while (c >= b && x[c] >= v) {
0610: if (x[c] == v)
0611: swap(x, c, d--);
0612: c--;
0613: }
0614: if (b > c)
0615: break;
0616: swap(x, b++, c--);
0617: }
0618:
0619: // Swap partition elements back to middle
0620: int s, n = off + len;
0621: s = Math.min(a - off, b - a);
0622: vecswap(x, off, b - s, s);
0623: s = Math.min(d - c, n - d - 1);
0624: vecswap(x, b, n - s, s);
0625:
0626: // Recursively sort non-partition-elements
0627: if ((s = b - a) > 1)
0628: sort1(x, off, s);
0629: if ((s = d - c) > 1)
0630: sort1(x, n - s, s);
0631: }
0632:
0633: /**
0634: * Swaps x[a] with x[b].
0635: */
0636: private static void swap(int x[], int a, int b) {
0637: int t = x[a];
0638: x[a] = x[b];
0639: x[b] = t;
0640: }
0641:
0642: /**
0643: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0644: */
0645: private static void vecswap(int x[], int a, int b, int n) {
0646: for (int i = 0; i < n; i++, a++, b++)
0647: swap(x, a, b);
0648: }
0649:
0650: /**
0651: * Returns the index of the median of the three indexed integers.
0652: */
0653: private static int med3(int x[], int a, int b, int c) {
0654: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0655: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0656: }
0657:
0658: /**
0659: * Sorts the specified sub-array of shorts into ascending order.
0660: */
0661: private static void sort1(short x[], int off, int len) {
0662: // Insertion sort on smallest arrays
0663: if (len < 7) {
0664: for (int i = off; i < len + off; i++)
0665: for (int j = i; j > off && x[j - 1] > x[j]; j--)
0666: swap(x, j, j - 1);
0667: return;
0668: }
0669:
0670: // Choose a partition element, v
0671: int m = off + (len >> 1); // Small arrays, middle element
0672: if (len > 7) {
0673: int l = off;
0674: int n = off + len - 1;
0675: if (len > 40) { // Big arrays, pseudomedian of 9
0676: int s = len / 8;
0677: l = med3(x, l, l + s, l + 2 * s);
0678: m = med3(x, m - s, m, m + s);
0679: n = med3(x, n - 2 * s, n - s, n);
0680: }
0681: m = med3(x, l, m, n); // Mid-size, med of 3
0682: }
0683: short v = x[m];
0684:
0685: // Establish Invariant: v* (<v)* (>v)* v*
0686: int a = off, b = a, c = off + len - 1, d = c;
0687: while (true) {
0688: while (b <= c && x[b] <= v) {
0689: if (x[b] == v)
0690: swap(x, a++, b);
0691: b++;
0692: }
0693: while (c >= b && x[c] >= v) {
0694: if (x[c] == v)
0695: swap(x, c, d--);
0696: c--;
0697: }
0698: if (b > c)
0699: break;
0700: swap(x, b++, c--);
0701: }
0702:
0703: // Swap partition elements back to middle
0704: int s, n = off + len;
0705: s = Math.min(a - off, b - a);
0706: vecswap(x, off, b - s, s);
0707: s = Math.min(d - c, n - d - 1);
0708: vecswap(x, b, n - s, s);
0709:
0710: // Recursively sort non-partition-elements
0711: if ((s = b - a) > 1)
0712: sort1(x, off, s);
0713: if ((s = d - c) > 1)
0714: sort1(x, n - s, s);
0715: }
0716:
0717: /**
0718: * Swaps x[a] with x[b].
0719: */
0720: private static void swap(short x[], int a, int b) {
0721: short t = x[a];
0722: x[a] = x[b];
0723: x[b] = t;
0724: }
0725:
0726: /**
0727: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0728: */
0729: private static void vecswap(short x[], int a, int b, int n) {
0730: for (int i = 0; i < n; i++, a++, b++)
0731: swap(x, a, b);
0732: }
0733:
0734: /**
0735: * Returns the index of the median of the three indexed shorts.
0736: */
0737: private static int med3(short x[], int a, int b, int c) {
0738: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0739: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0740: }
0741:
0742: /**
0743: * Sorts the specified sub-array of chars into ascending order.
0744: */
0745: private static void sort1(char x[], int off, int len) {
0746: // Insertion sort on smallest arrays
0747: if (len < 7) {
0748: for (int i = off; i < len + off; i++)
0749: for (int j = i; j > off && x[j - 1] > x[j]; j--)
0750: swap(x, j, j - 1);
0751: return;
0752: }
0753:
0754: // Choose a partition element, v
0755: int m = off + (len >> 1); // Small arrays, middle element
0756: if (len > 7) {
0757: int l = off;
0758: int n = off + len - 1;
0759: if (len > 40) { // Big arrays, pseudomedian of 9
0760: int s = len / 8;
0761: l = med3(x, l, l + s, l + 2 * s);
0762: m = med3(x, m - s, m, m + s);
0763: n = med3(x, n - 2 * s, n - s, n);
0764: }
0765: m = med3(x, l, m, n); // Mid-size, med of 3
0766: }
0767: char v = x[m];
0768:
0769: // Establish Invariant: v* (<v)* (>v)* v*
0770: int a = off, b = a, c = off + len - 1, d = c;
0771: while (true) {
0772: while (b <= c && x[b] <= v) {
0773: if (x[b] == v)
0774: swap(x, a++, b);
0775: b++;
0776: }
0777: while (c >= b && x[c] >= v) {
0778: if (x[c] == v)
0779: swap(x, c, d--);
0780: c--;
0781: }
0782: if (b > c)
0783: break;
0784: swap(x, b++, c--);
0785: }
0786:
0787: // Swap partition elements back to middle
0788: int s, n = off + len;
0789: s = Math.min(a - off, b - a);
0790: vecswap(x, off, b - s, s);
0791: s = Math.min(d - c, n - d - 1);
0792: vecswap(x, b, n - s, s);
0793:
0794: // Recursively sort non-partition-elements
0795: if ((s = b - a) > 1)
0796: sort1(x, off, s);
0797: if ((s = d - c) > 1)
0798: sort1(x, n - s, s);
0799: }
0800:
0801: /**
0802: * Swaps x[a] with x[b].
0803: */
0804: private static void swap(char x[], int a, int b) {
0805: char t = x[a];
0806: x[a] = x[b];
0807: x[b] = t;
0808: }
0809:
0810: /**
0811: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0812: */
0813: private static void vecswap(char x[], int a, int b, int n) {
0814: for (int i = 0; i < n; i++, a++, b++)
0815: swap(x, a, b);
0816: }
0817:
0818: /**
0819: * Returns the index of the median of the three indexed chars.
0820: */
0821: private static int med3(char x[], int a, int b, int c) {
0822: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0823: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0824: }
0825:
0826: /**
0827: * Sorts the specified sub-array of bytes into ascending order.
0828: */
0829: private static void sort1(byte x[], int off, int len) {
0830: // Insertion sort on smallest arrays
0831: if (len < 7) {
0832: for (int i = off; i < len + off; i++)
0833: for (int j = i; j > off && x[j - 1] > x[j]; j--)
0834: swap(x, j, j - 1);
0835: return;
0836: }
0837:
0838: // Choose a partition element, v
0839: int m = off + (len >> 1); // Small arrays, middle element
0840: if (len > 7) {
0841: int l = off;
0842: int n = off + len - 1;
0843: if (len > 40) { // Big arrays, pseudomedian of 9
0844: int s = len / 8;
0845: l = med3(x, l, l + s, l + 2 * s);
0846: m = med3(x, m - s, m, m + s);
0847: n = med3(x, n - 2 * s, n - s, n);
0848: }
0849: m = med3(x, l, m, n); // Mid-size, med of 3
0850: }
0851: byte v = x[m];
0852:
0853: // Establish Invariant: v* (<v)* (>v)* v*
0854: int a = off, b = a, c = off + len - 1, d = c;
0855: while (true) {
0856: while (b <= c && x[b] <= v) {
0857: if (x[b] == v)
0858: swap(x, a++, b);
0859: b++;
0860: }
0861: while (c >= b && x[c] >= v) {
0862: if (x[c] == v)
0863: swap(x, c, d--);
0864: c--;
0865: }
0866: if (b > c)
0867: break;
0868: swap(x, b++, c--);
0869: }
0870:
0871: // Swap partition elements back to middle
0872: int s, n = off + len;
0873: s = Math.min(a - off, b - a);
0874: vecswap(x, off, b - s, s);
0875: s = Math.min(d - c, n - d - 1);
0876: vecswap(x, b, n - s, s);
0877:
0878: // Recursively sort non-partition-elements
0879: if ((s = b - a) > 1)
0880: sort1(x, off, s);
0881: if ((s = d - c) > 1)
0882: sort1(x, n - s, s);
0883: }
0884:
0885: /**
0886: * Swaps x[a] with x[b].
0887: */
0888: private static void swap(byte x[], int a, int b) {
0889: byte t = x[a];
0890: x[a] = x[b];
0891: x[b] = t;
0892: }
0893:
0894: /**
0895: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0896: */
0897: private static void vecswap(byte x[], int a, int b, int n) {
0898: for (int i = 0; i < n; i++, a++, b++)
0899: swap(x, a, b);
0900: }
0901:
0902: /**
0903: * Returns the index of the median of the three indexed bytes.
0904: */
0905: private static int med3(byte x[], int a, int b, int c) {
0906: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0907: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0908: }
0909:
0910: /**
0911: * Sorts the specified sub-array of doubles into ascending order.
0912: */
0913: private static void sort1(double x[], int off, int len) {
0914: // Insertion sort on smallest arrays
0915: if (len < 7) {
0916: for (int i = off; i < len + off; i++)
0917: for (int j = i; j > off && x[j - 1] > x[j]; j--)
0918: swap(x, j, j - 1);
0919: return;
0920: }
0921:
0922: // Choose a partition element, v
0923: int m = off + (len >> 1); // Small arrays, middle element
0924: if (len > 7) {
0925: int l = off;
0926: int n = off + len - 1;
0927: if (len > 40) { // Big arrays, pseudomedian of 9
0928: int s = len / 8;
0929: l = med3(x, l, l + s, l + 2 * s);
0930: m = med3(x, m - s, m, m + s);
0931: n = med3(x, n - 2 * s, n - s, n);
0932: }
0933: m = med3(x, l, m, n); // Mid-size, med of 3
0934: }
0935: double v = x[m];
0936:
0937: // Establish Invariant: v* (<v)* (>v)* v*
0938: int a = off, b = a, c = off + len - 1, d = c;
0939: while (true) {
0940: while (b <= c && x[b] <= v) {
0941: if (x[b] == v)
0942: swap(x, a++, b);
0943: b++;
0944: }
0945: while (c >= b && x[c] >= v) {
0946: if (x[c] == v)
0947: swap(x, c, d--);
0948: c--;
0949: }
0950: if (b > c)
0951: break;
0952: swap(x, b++, c--);
0953: }
0954:
0955: // Swap partition elements back to middle
0956: int s, n = off + len;
0957: s = Math.min(a - off, b - a);
0958: vecswap(x, off, b - s, s);
0959: s = Math.min(d - c, n - d - 1);
0960: vecswap(x, b, n - s, s);
0961:
0962: // Recursively sort non-partition-elements
0963: if ((s = b - a) > 1)
0964: sort1(x, off, s);
0965: if ((s = d - c) > 1)
0966: sort1(x, n - s, s);
0967: }
0968:
0969: /**
0970: * Swaps x[a] with x[b].
0971: */
0972: private static void swap(double x[], int a, int b) {
0973: double t = x[a];
0974: x[a] = x[b];
0975: x[b] = t;
0976: }
0977:
0978: /**
0979: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0980: */
0981: private static void vecswap(double x[], int a, int b, int n) {
0982: for (int i = 0; i < n; i++, a++, b++)
0983: swap(x, a, b);
0984: }
0985:
0986: /**
0987: * Returns the index of the median of the three indexed doubles.
0988: */
0989: private static int med3(double x[], int a, int b, int c) {
0990: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0991: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0992: }
0993:
0994: /**
0995: * Sorts the specified sub-array of floats into ascending order.
0996: */
0997: private static void sort1(float x[], int off, int len) {
0998: // Insertion sort on smallest arrays
0999: if (len < 7) {
1000: for (int i = off; i < len + off; i++)
1001: for (int j = i; j > off && x[j - 1] > x[j]; j--)
1002: swap(x, j, j - 1);
1003: return;
1004: }
1005:
1006: // Choose a partition element, v
1007: int m = off + (len >> 1); // Small arrays, middle element
1008: if (len > 7) {
1009: int l = off;
1010: int n = off + len - 1;
1011: if (len > 40) { // Big arrays, pseudomedian of 9
1012: int s = len / 8;
1013: l = med3(x, l, l + s, l + 2 * s);
1014: m = med3(x, m - s, m, m + s);
1015: n = med3(x, n - 2 * s, n - s, n);
1016: }
1017: m = med3(x, l, m, n); // Mid-size, med of 3
1018: }
1019: float v = x[m];
1020:
1021: // Establish Invariant: v* (<v)* (>v)* v*
1022: int a = off, b = a, c = off + len - 1, d = c;
1023: while (true) {
1024: while (b <= c && x[b] <= v) {
1025: if (x[b] == v)
1026: swap(x, a++, b);
1027: b++;
1028: }
1029: while (c >= b && x[c] >= v) {
1030: if (x[c] == v)
1031: swap(x, c, d--);
1032: c--;
1033: }
1034: if (b > c)
1035: break;
1036: swap(x, b++, c--);
1037: }
1038:
1039: // Swap partition elements back to middle
1040: int s, n = off + len;
1041: s = Math.min(a - off, b - a);
1042: vecswap(x, off, b - s, s);
1043: s = Math.min(d - c, n - d - 1);
1044: vecswap(x, b, n - s, s);
1045:
1046: // Recursively sort non-partition-elements
1047: if ((s = b - a) > 1)
1048: sort1(x, off, s);
1049: if ((s = d - c) > 1)
1050: sort1(x, n - s, s);
1051: }
1052:
1053: /**
1054: * Swaps x[a] with x[b].
1055: */
1056: private static void swap(float x[], int a, int b) {
1057: float t = x[a];
1058: x[a] = x[b];
1059: x[b] = t;
1060: }
1061:
1062: /**
1063: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
1064: */
1065: private static void vecswap(float x[], int a, int b, int n) {
1066: for (int i = 0; i < n; i++, a++, b++)
1067: swap(x, a, b);
1068: }
1069:
1070: /**
1071: * Returns the index of the median of the three indexed floats.
1072: */
1073: private static int med3(float x[], int a, int b, int c) {
1074: return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
1075: : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
1076: }
1077:
1078: /**
1079: * Sorts the specified array of objects into ascending order, according to
1080: * the <i>natural ordering</i> of its elements. All elements in the array
1081: * must implement the <tt>Comparable</tt> interface. Furthermore, all
1082: * elements in the array must be <i>mutually comparable</i> (that is,
1083: * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
1084: * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1085: *
1086: * This sort is guaranteed to be <i>stable</i>: equal elements will
1087: * not be reordered as a result of the sort.<p>
1088: *
1089: * The sorting algorithm is a modified mergesort (in which the merge is
1090: * omitted if the highest element in the low sublist is less than the
1091: * lowest element in the high sublist). This algorithm offers guaranteed
1092: * n*log(n) performance.
1093: *
1094: * @param a the array to be sorted.
1095: * @throws ClassCastException if the array contains elements that are not
1096: * <i>mutually comparable</i> (for example, strings and integers).
1097: * @see Comparable
1098: */
1099: public static void sort(Object[] a) {
1100: Object aux[] = (Object[]) a.clone();
1101: mergeSort(aux, a, 0, a.length, 0);
1102: }
1103:
1104: /**
1105: * Sorts the specified range of the specified array of objects into
1106: * ascending order, according to the <i>natural ordering</i> of its
1107: * elements. The range to be sorted extends from index
1108: * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
1109: * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All
1110: * elements in this range must implement the <tt>Comparable</tt>
1111: * interface. Furthermore, all elements in this range must be <i>mutually
1112: * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
1113: * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1114: * <tt>e2</tt> in the array).<p>
1115: *
1116: * This sort is guaranteed to be <i>stable</i>: equal elements will
1117: * not be reordered as a result of the sort.<p>
1118: *
1119: * The sorting algorithm is a modified mergesort (in which the merge is
1120: * omitted if the highest element in the low sublist is less than the
1121: * lowest element in the high sublist). This algorithm offers guaranteed
1122: * n*log(n) performance.
1123: *
1124: * @param a the array to be sorted.
1125: * @param fromIndex the index of the first element (inclusive) to be
1126: * sorted.
1127: * @param toIndex the index of the last element (exclusive) to be sorted.
1128: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1129: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1130: * <tt>toIndex > a.length</tt>
1131: * @throws ClassCastException if the array contains elements that are
1132: * not <i>mutually comparable</i> (for example, strings and
1133: * integers).
1134: * @see Comparable
1135: */
1136: public static void sort(Object[] a, int fromIndex, int toIndex) {
1137: rangeCheck(a.length, fromIndex, toIndex);
1138: Object aux[] = (Object[]) cloneSubarray(a, fromIndex, toIndex);
1139: mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1140: }
1141:
1142: /**
1143: * Tuning parameter: list size at or below which insertion sort will be
1144: * used in preference to mergesort or quicksort.
1145: */
1146: private static final int INSERTIONSORT_THRESHOLD = 7;
1147:
1148: /**
1149: * Clones an array within the specified bounds.
1150: * This method assumes that a is an array.
1151: */
1152: private static Object cloneSubarray(Object[] a, int from, int to) {
1153: int n = to - from;
1154: Object result = Array.newInstance(a.getClass()
1155: .getComponentType(), n);
1156: System.arraycopy(a, from, result, 0, n);
1157: return result;
1158: }
1159:
1160: /**
1161: * Src is the source array that starts at index 0
1162: * Dest is the (possibly larger) array destination with a possible offset
1163: * low is the index in dest to start sorting
1164: * high is the end index in dest to end sorting
1165: * off is the offset to generate corresponding low, high in src
1166: */
1167: private static void mergeSort(Object src[], Object dest[], int low,
1168: int high, int off) {
1169: int length = high - low;
1170:
1171: // Insertion sort on smallest arrays
1172: if (length < INSERTIONSORT_THRESHOLD) {
1173: for (int i = low; i < high; i++)
1174: for (int j = i; j > low
1175: && ((Comparable) dest[j - 1])
1176: .compareTo((Comparable) dest[j]) > 0; j--)
1177: swap(dest, j, j - 1);
1178: return;
1179: }
1180:
1181: // Recursively sort halves of dest into src
1182: int destLow = low;
1183: int destHigh = high;
1184: low += off;
1185: high += off;
1186: int mid = (low + high) >> 1;
1187: mergeSort(dest, src, low, mid, -off);
1188: mergeSort(dest, src, mid, high, -off);
1189:
1190: // If list is already sorted, just copy from src to dest. This is an
1191: // optimization that results in faster sorts for nearly ordered lists.
1192: if (((Comparable) src[mid - 1])
1193: .compareTo((Comparable) src[mid]) <= 0) {
1194: System.arraycopy(src, low, dest, destLow, length);
1195: return;
1196: }
1197:
1198: // Merge sorted halves (now in src) into dest
1199: for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
1200: if (q >= high || p < mid
1201: && ((Comparable) src[p]).compareTo(src[q]) <= 0)
1202: dest[i] = src[p++];
1203: else
1204: dest[i] = src[q++];
1205: }
1206: }
1207:
1208: /**
1209: * Swaps x[a] with x[b].
1210: */
1211: private static void swap(Object x[], int a, int b) {
1212: Object t = x[a];
1213: x[a] = x[b];
1214: x[b] = t;
1215: }
1216:
1217: /**
1218: * Sorts the specified array of objects according to the order induced by
1219: * the specified comparator. All elements in the array must be
1220: * <i>mutually comparable</i> by the specified comparator (that is,
1221: * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1222: * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1223: *
1224: * This sort is guaranteed to be <i>stable</i>: equal elements will
1225: * not be reordered as a result of the sort.<p>
1226: *
1227: * The sorting algorithm is a modified mergesort (in which the merge is
1228: * omitted if the highest element in the low sublist is less than the
1229: * lowest element in the high sublist). This algorithm offers guaranteed
1230: * n*log(n) performance.
1231: *
1232: * @param a the array to be sorted.
1233: * @param c the comparator to determine the order of the array. A
1234: * <tt>null</tt> value indicates that the elements' <i>natural
1235: * ordering</i> should be used.
1236: * @throws ClassCastException if the array contains elements that are
1237: * not <i>mutually comparable</i> using the specified comparator.
1238: * @see Comparator
1239: */
1240: public static void sort(Object[] a, Comparator c) {
1241: Object aux[] = (Object[]) a.clone();
1242: if (c == null)
1243: mergeSort(aux, a, 0, a.length, 0);
1244: else
1245: mergeSort(aux, a, 0, a.length, 0, c);
1246: }
1247:
1248: /**
1249: * Sorts the specified range of the specified array of objects according
1250: * to the order induced by the specified comparator. The range to be
1251: * sorted extends from index <tt>fromIndex</tt>, inclusive, to index
1252: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1253: * range to be sorted is empty.) All elements in the range must be
1254: * <i>mutually comparable</i> by the specified comparator (that is,
1255: * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1256: * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
1257: *
1258: * This sort is guaranteed to be <i>stable</i>: equal elements will
1259: * not be reordered as a result of the sort.<p>
1260: *
1261: * The sorting algorithm is a modified mergesort (in which the merge is
1262: * omitted if the highest element in the low sublist is less than the
1263: * lowest element in the high sublist). This algorithm offers guaranteed
1264: * n*log(n) performance.
1265: *
1266: * @param a the array to be sorted.
1267: * @param fromIndex the index of the first element (inclusive) to be
1268: * sorted.
1269: * @param toIndex the index of the last element (exclusive) to be sorted.
1270: * @param c the comparator to determine the order of the array. A
1271: * <tt>null</tt> value indicates that the elements' <i>natural
1272: * ordering</i> should be used.
1273: * @throws ClassCastException if the array contains elements that are not
1274: * <i>mutually comparable</i> using the specified comparator.
1275: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1276: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1277: * <tt>toIndex > a.length</tt>
1278: * @see Comparator
1279: */
1280: public static void sort(Object[] a, int fromIndex, int toIndex,
1281: Comparator c) {
1282: rangeCheck(a.length, fromIndex, toIndex);
1283: Object aux[] = (Object[]) cloneSubarray(a, fromIndex, toIndex);
1284: if (c == null)
1285: mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1286: else
1287: mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1288: }
1289:
1290: /**
1291: * Src is the source array that starts at index 0
1292: * Dest is the (possibly larger) array destination with a possible offset
1293: * low is the index in dest to start sorting
1294: * high is the end index in dest to end sorting
1295: * off is the offset into src corresponding to low in dest
1296: */
1297: private static void mergeSort(Object src[], Object dest[], int low,
1298: int high, int off, Comparator c) {
1299: int length = high - low;
1300:
1301: // Insertion sort on smallest arrays
1302: if (length < INSERTIONSORT_THRESHOLD) {
1303: for (int i = low; i < high; i++)
1304: for (int j = i; j > low
1305: && c.compare(dest[j - 1], dest[j]) > 0; j--)
1306: swap(dest, j, j - 1);
1307: return;
1308: }
1309:
1310: // Recursively sort halves of dest into src
1311: int destLow = low;
1312: int destHigh = high;
1313: low += off;
1314: high += off;
1315: int mid = (low + high) >> 1;
1316: mergeSort(dest, src, low, mid, -off, c);
1317: mergeSort(dest, src, mid, high, -off, c);
1318:
1319: // If list is already sorted, just copy from src to dest. This is an
1320: // optimization that results in faster sorts for nearly ordered lists.
1321: if (c.compare(src[mid - 1], src[mid]) <= 0) {
1322: System.arraycopy(src, low, dest, destLow, length);
1323: return;
1324: }
1325:
1326: // Merge sorted halves (now in src) into dest
1327: for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
1328: if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1329: dest[i] = src[p++];
1330: else
1331: dest[i] = src[q++];
1332: }
1333: }
1334:
1335: /**
1336: * Check that fromIndex and toIndex are in range, and throw an
1337: * appropriate exception if they aren't.
1338: */
1339: private static void rangeCheck(int arrayLen, int fromIndex,
1340: int toIndex) {
1341: if (fromIndex > toIndex)
1342: throw new IllegalArgumentException("fromIndex(" + fromIndex
1343: + ") > toIndex(" + toIndex + ")");
1344: if (fromIndex < 0)
1345: throw new ArrayIndexOutOfBoundsException(fromIndex);
1346: if (toIndex > arrayLen)
1347: throw new ArrayIndexOutOfBoundsException(toIndex);
1348: }
1349:
1350: // Searching
1351:
1352: /**
1353: * Searches the specified array of longs for the specified value using the
1354: * binary search algorithm. The array <strong>must</strong> be sorted (as
1355: * by the <tt>sort</tt> method, above) prior to making this call. If it
1356: * is not sorted, the results are undefined. If the array contains
1357: * multiple elements with the specified value, there is no guarantee which
1358: * one will be found.
1359: *
1360: * @param a the array to be searched.
1361: * @param key the value to be searched for.
1362: * @return index of the search key, if it is contained in the list;
1363: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1364: * <i>insertion point</i> is defined as the point at which the
1365: * key would be inserted into the list: the index of the first
1366: * element greater than the key, or <tt>list.size()</tt>, if all
1367: * elements in the list are less than the specified key. Note
1368: * that this guarantees that the return value will be >= 0 if
1369: * and only if the key is found.
1370: * @see #sort(long[])
1371: */
1372: public static int binarySearch(long[] a, long key) {
1373: int low = 0;
1374: int high = a.length - 1;
1375:
1376: while (low <= high) {
1377: int mid = (low + high) >> 1;
1378: long midVal = a[mid];
1379:
1380: if (midVal < key)
1381: low = mid + 1;
1382: else if (midVal > key)
1383: high = mid - 1;
1384: else
1385: return mid; // key found
1386: }
1387: return -(low + 1); // key not found.
1388: }
1389:
1390: /**
1391: * Searches the specified array of ints for the specified value using the
1392: * binary search algorithm. The array <strong>must</strong> be sorted (as
1393: * by the <tt>sort</tt> method, above) prior to making this call. If it
1394: * is not sorted, the results are undefined. If the array contains
1395: * multiple elements with the specified value, there is no guarantee which
1396: * one will be found.
1397: *
1398: * @param a the array to be searched.
1399: * @param key the value to be searched for.
1400: * @return index of the search key, if it is contained in the list;
1401: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1402: * <i>insertion point</i> is defined as the point at which the
1403: * key would be inserted into the list: the index of the first
1404: * element greater than the key, or <tt>list.size()</tt>, if all
1405: * elements in the list are less than the specified key. Note
1406: * that this guarantees that the return value will be >= 0 if
1407: * and only if the key is found.
1408: * @see #sort(int[])
1409: */
1410: public static int binarySearch(int[] a, int key) {
1411: int low = 0;
1412: int high = a.length - 1;
1413:
1414: while (low <= high) {
1415: int mid = (low + high) >> 1;
1416: int midVal = a[mid];
1417:
1418: if (midVal < key)
1419: low = mid + 1;
1420: else if (midVal > key)
1421: high = mid - 1;
1422: else
1423: return mid; // key found
1424: }
1425: return -(low + 1); // key not found.
1426: }
1427:
1428: /**
1429: * Searches the specified array of shorts for the specified value using
1430: * the binary search algorithm. The array <strong>must</strong> be sorted
1431: * (as by the <tt>sort</tt> method, above) prior to making this call. If
1432: * it is not sorted, the results are undefined. If the array contains
1433: * multiple elements with the specified value, there is no guarantee which
1434: * one will be found.
1435: *
1436: * @param a the array to be searched.
1437: * @param key the value to be searched for.
1438: * @return index of the search key, if it is contained in the list;
1439: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1440: * <i>insertion point</i> is defined as the point at which the
1441: * key would be inserted into the list: the index of the first
1442: * element greater than the key, or <tt>list.size()</tt>, if all
1443: * elements in the list are less than the specified key. Note
1444: * that this guarantees that the return value will be >= 0 if
1445: * and only if the key is found.
1446: * @see #sort(short[])
1447: */
1448: public static int binarySearch(short[] a, short key) {
1449: int low = 0;
1450: int high = a.length - 1;
1451:
1452: while (low <= high) {
1453: int mid = (low + high) >> 1;
1454: short midVal = a[mid];
1455:
1456: if (midVal < key)
1457: low = mid + 1;
1458: else if (midVal > key)
1459: high = mid - 1;
1460: else
1461: return mid; // key found
1462: }
1463: return -(low + 1); // key not found.
1464: }
1465:
1466: /**
1467: * Searches the specified array of chars for the specified value using the
1468: * binary search algorithm. The array <strong>must</strong> be sorted (as
1469: * by the <tt>sort</tt> method, above) prior to making this call. If it
1470: * is not sorted, the results are undefined. If the array contains
1471: * multiple elements with the specified value, there is no guarantee which
1472: * one will be found.
1473: *
1474: * @param a the array to be searched.
1475: * @param key the value to be searched for.
1476: * @return index of the search key, if it is contained in the list;
1477: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1478: * <i>insertion point</i> is defined as the point at which the
1479: * key would be inserted into the list: the index of the first
1480: * element greater than the key, or <tt>list.size()</tt>, if all
1481: * elements in the list are less than the specified key. Note
1482: * that this guarantees that the return value will be >= 0 if
1483: * and only if the key is found.
1484: * @see #sort(char[])
1485: */
1486: public static int binarySearch(char[] a, char key) {
1487: int low = 0;
1488: int high = a.length - 1;
1489:
1490: while (low <= high) {
1491: int mid = (low + high) >> 1;
1492: char midVal = a[mid];
1493:
1494: if (midVal < key)
1495: low = mid + 1;
1496: else if (midVal > key)
1497: high = mid - 1;
1498: else
1499: return mid; // key found
1500: }
1501: return -(low + 1); // key not found.
1502: }
1503:
1504: /**
1505: * Searches the specified array of bytes for the specified value using the
1506: * binary search algorithm. The array <strong>must</strong> be sorted (as
1507: * by the <tt>sort</tt> method, above) prior to making this call. If it
1508: * is not sorted, the results are undefined. If the array contains
1509: * multiple elements with the specified value, there is no guarantee which
1510: * one will be found.
1511: *
1512: * @param a the array to be searched.
1513: * @param key the value to be searched for.
1514: * @return index of the search key, if it is contained in the list;
1515: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1516: * <i>insertion point</i> is defined as the point at which the
1517: * key would be inserted into the list: the index of the first
1518: * element greater than the key, or <tt>list.size()</tt>, if all
1519: * elements in the list are less than the specified key. Note
1520: * that this guarantees that the return value will be >= 0 if
1521: * and only if the key is found.
1522: * @see #sort(byte[])
1523: */
1524: public static int binarySearch(byte[] a, byte key) {
1525: int low = 0;
1526: int high = a.length - 1;
1527:
1528: while (low <= high) {
1529: int mid = (low + high) >> 1;
1530: byte midVal = a[mid];
1531:
1532: if (midVal < key)
1533: low = mid + 1;
1534: else if (midVal > key)
1535: high = mid - 1;
1536: else
1537: return mid; // key found
1538: }
1539: return -(low + 1); // key not found.
1540: }
1541:
1542: /**
1543: * Searches the specified array of doubles for the specified value using
1544: * the binary search algorithm. The array <strong>must</strong> be sorted
1545: * (as by the <tt>sort</tt> method, above) prior to making this call. If
1546: * it is not sorted, the results are undefined. If the array contains
1547: * multiple elements with the specified value, there is no guarantee which
1548: * one will be found. This method considers all NaN values to be
1549: * equivalent and equal.
1550: *
1551: * @param a the array to be searched.
1552: * @param key the value to be searched for.
1553: * @return index of the search key, if it is contained in the list;
1554: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1555: * <i>insertion point</i> is defined as the point at which the
1556: * key would be inserted into the list: the index of the first
1557: * element greater than the key, or <tt>list.size()</tt>, if all
1558: * elements in the list are less than the specified key. Note
1559: * that this guarantees that the return value will be >= 0 if
1560: * and only if the key is found.
1561: * @see #sort(double[])
1562: */
1563: public static int binarySearch(double[] a, double key) {
1564: return binarySearch(a, key, 0, a.length - 1);
1565: }
1566:
1567: private static int binarySearch(double[] a, double key, int low,
1568: int high) {
1569: while (low <= high) {
1570: int mid = (low + high) >> 1;
1571: double midVal = a[mid];
1572:
1573: int cmp;
1574: if (midVal < key) {
1575: cmp = -1; // Neither val is NaN, thisVal is smaller
1576: } else if (midVal > key) {
1577: cmp = 1; // Neither val is NaN, thisVal is larger
1578: } else {
1579: long midBits = Double.doubleToLongBits(midVal);
1580: long keyBits = Double.doubleToLongBits(key);
1581: cmp = (midBits == keyBits ? 0 : // Values are equal
1582: (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
1583: 1)); // (0.0, -0.0) or (NaN, !NaN)
1584: }
1585:
1586: if (cmp < 0)
1587: low = mid + 1;
1588: else if (cmp > 0)
1589: high = mid - 1;
1590: else
1591: return mid; // key found
1592: }
1593: return -(low + 1); // key not found.
1594: }
1595:
1596: /**
1597: * Searches the specified array of floats for the specified value using
1598: * the binary search algorithm. The array <strong>must</strong> be sorted
1599: * (as by the <tt>sort</tt> method, above) prior to making this call. If
1600: * it is not sorted, the results are undefined. If the array contains
1601: * multiple elements with the specified value, there is no guarantee which
1602: * one will be found. This method considers all NaN values to be
1603: * equivalent and equal.
1604: *
1605: * @param a the array to be searched.
1606: * @param key the value to be searched for.
1607: * @return index of the search key, if it is contained in the list;
1608: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1609: * <i>insertion point</i> is defined as the point at which the
1610: * key would be inserted into the list: the index of the first
1611: * element greater than the key, or <tt>list.size()</tt>, if all
1612: * elements in the list are less than the specified key. Note
1613: * that this guarantees that the return value will be >= 0 if
1614: * and only if the key is found.
1615: * @see #sort(float[])
1616: */
1617: public static int binarySearch(float[] a, float key) {
1618: return binarySearch(a, key, 0, a.length - 1);
1619: }
1620:
1621: private static int binarySearch(float[] a, float key, int low,
1622: int high) {
1623: while (low <= high) {
1624: int mid = (low + high) >> 1;
1625: float midVal = a[mid];
1626:
1627: int cmp;
1628: if (midVal < key) {
1629: cmp = -1; // Neither val is NaN, thisVal is smaller
1630: } else if (midVal > key) {
1631: cmp = 1; // Neither val is NaN, thisVal is larger
1632: } else {
1633: int midBits = Float.floatToIntBits(midVal);
1634: int keyBits = Float.floatToIntBits(key);
1635: cmp = (midBits == keyBits ? 0 : // Values are equal
1636: (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
1637: 1)); // (0.0, -0.0) or (NaN, !NaN)
1638: }
1639:
1640: if (cmp < 0)
1641: low = mid + 1;
1642: else if (cmp > 0)
1643: high = mid - 1;
1644: else
1645: return mid; // key found
1646: }
1647: return -(low + 1); // key not found.
1648: }
1649:
1650: /**
1651: * Searches the specified array for the specified object using the binary
1652: * search algorithm. The array must be sorted into ascending order
1653: * according to the <i>natural ordering</i> of its elements (as by
1654: * <tt>Sort(Object[]</tt>), above) prior to making this call. If it is
1655: * not sorted, the results are undefined.
1656: * (If the array contains elements that are not mutually comparable (for
1657: * example,strings and integers), it <i>cannot</i> be sorted according
1658: * to the natural order of its elements, hence results are undefined.)
1659: * If the array contains multiple
1660: * elements equal to the specified object, there is no guarantee which
1661: * one will be found.
1662: *
1663: * @param a the array to be searched.
1664: * @param key the value to be searched for.
1665: * @return index of the search key, if it is contained in the list;
1666: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1667: * <i>insertion point</i> is defined as the point at which the
1668: * key would be inserted into the list: the index of the first
1669: * element greater than the key, or <tt>list.size()</tt>, if all
1670: * elements in the list are less than the specified key. Note
1671: * that this guarantees that the return value will be >= 0 if
1672: * and only if the key is found.
1673: * @throws ClassCastException if the search key in not comparable to the
1674: * elements of the array.
1675: * @see Comparable
1676: * @see #sort(Object[])
1677: */
1678: public static int binarySearch(Object[] a, Object key) {
1679: int low = 0;
1680: int high = a.length - 1;
1681:
1682: while (low <= high) {
1683: int mid = (low + high) >> 1;
1684: Object midVal = a[mid];
1685: int cmp = ((Comparable) midVal).compareTo(key);
1686:
1687: if (cmp < 0)
1688: low = mid + 1;
1689: else if (cmp > 0)
1690: high = mid - 1;
1691: else
1692: return mid; // key found
1693: }
1694: return -(low + 1); // key not found.
1695: }
1696:
1697: /**
1698: * Searches the specified array for the specified object using the binary
1699: * search algorithm. The array must be sorted into ascending order
1700: * according to the specified comparator (as by the <tt>Sort(Object[],
1701: * Comparator)</tt> method, above), prior to making this call. If it is
1702: * not sorted, the results are undefined.
1703: * If the array contains multiple
1704: * elements equal to the specified object, there is no guarantee which one
1705: * will be found.
1706: *
1707: * @param a the array to be searched.
1708: * @param key the value to be searched for.
1709: * @param c the comparator by which the array is ordered. A
1710: * <tt>null</tt> value indicates that the elements' <i>natural
1711: * ordering</i> should be used.
1712: * @return index of the search key, if it is contained in the list;
1713: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1714: * <i>insertion point</i> is defined as the point at which the
1715: * key would be inserted into the list: the index of the first
1716: * element greater than the key, or <tt>list.size()</tt>, if all
1717: * elements in the list are less than the specified key. Note
1718: * that this guarantees that the return value will be >= 0 if
1719: * and only if the key is found.
1720: * @throws ClassCastException if the array contains elements that are not
1721: * <i>mutually comparable</i> using the specified comparator,
1722: * or the search key in not mutually comparable with the
1723: * elements of the array using this comparator.
1724: * @see Comparable
1725: * @see #sort(Object[], Comparator)
1726: */
1727: public static int binarySearch(Object[] a, Object key, Comparator c) {
1728: if (c == null)
1729: return binarySearch(a, key);
1730:
1731: int low = 0;
1732: int high = a.length - 1;
1733:
1734: while (low <= high) {
1735: int mid = (low + high) >> 1;
1736: Object midVal = a[mid];
1737: int cmp = c.compare(midVal, key);
1738:
1739: if (cmp < 0)
1740: low = mid + 1;
1741: else if (cmp > 0)
1742: high = mid - 1;
1743: else
1744: return mid; // key found
1745: }
1746: return -(low + 1); // key not found.
1747: }
1748:
1749: // Equality Testing
1750:
1751: /**
1752: * Returns <tt>true</tt> if the two specified arrays of longs are
1753: * <i>equal</i> to one another. Two arrays are considered equal if both
1754: * arrays contain the same number of elements, and all corresponding pairs
1755: * of elements in the two arrays are equal. In other words, two arrays
1756: * are equal if they contain the same elements in the same order. Also,
1757: * two array references are considered equal if both are <tt>null</tt>.<p>
1758: *
1759: * @param a one array to be tested for equality.
1760: * @param a2 the other array to be tested for equality.
1761: * @return <tt>true</tt> if the two arrays are equal.
1762: */
1763: public static boolean equals(long[] a, long[] a2) {
1764: if (a == a2)
1765: return true;
1766: if (a == null || a2 == null)
1767: return false;
1768:
1769: int length = a.length;
1770: if (a2.length != length)
1771: return false;
1772:
1773: for (int i = 0; i < length; i++)
1774: if (a[i] != a2[i])
1775: return false;
1776:
1777: return true;
1778: }
1779:
1780: /**
1781: * Returns <tt>true</tt> if the two specified arrays of ints are
1782: * <i>equal</i> to one another. Two arrays are considered equal if both
1783: * arrays contain the same number of elements, and all corresponding pairs
1784: * of elements in the two arrays are equal. In other words, two arrays
1785: * are equal if they contain the same elements in the same order. Also,
1786: * two array references are considered equal if both are <tt>null</tt>.<p>
1787: *
1788: * @param a one array to be tested for equality.
1789: * @param a2 the other array to be tested for equality.
1790: * @return <tt>true</tt> if the two arrays are equal.
1791: */
1792: public static boolean equals(int[] a, int[] a2) {
1793: if (a == a2)
1794: return true;
1795: if (a == null || a2 == null)
1796: return false;
1797:
1798: int length = a.length;
1799: if (a2.length != length)
1800: return false;
1801:
1802: for (int i = 0; i < length; i++)
1803: if (a[i] != a2[i])
1804: return false;
1805:
1806: return true;
1807: }
1808:
1809: /**
1810: * Returns <tt>true</tt> if the two specified arrays of shorts are
1811: * <i>equal</i> to one another. Two arrays are considered equal if both
1812: * arrays contain the same number of elements, and all corresponding pairs
1813: * of elements in the two arrays are equal. In other words, two arrays
1814: * are equal if they contain the same elements in the same order. Also,
1815: * two array references are considered equal if both are <tt>null</tt>.<p>
1816: *
1817: * @param a one array to be tested for equality.
1818: * @param a2 the other array to be tested for equality.
1819: * @return <tt>true</tt> if the two arrays are equal.
1820: */
1821: public static boolean equals(short[] a, short a2[]) {
1822: if (a == a2)
1823: return true;
1824: if (a == null || a2 == null)
1825: return false;
1826:
1827: int length = a.length;
1828: if (a2.length != length)
1829: return false;
1830:
1831: for (int i = 0; i < length; i++)
1832: if (a[i] != a2[i])
1833: return false;
1834:
1835: return true;
1836: }
1837:
1838: /**
1839: * Returns <tt>true</tt> if the two specified arrays of chars are
1840: * <i>equal</i> to one another. Two arrays are considered equal if both
1841: * arrays contain the same number of elements, and all corresponding pairs
1842: * of elements in the two arrays are equal. In other words, two arrays
1843: * are equal if they contain the same elements in the same order. Also,
1844: * two array references are considered equal if both are <tt>null</tt>.<p>
1845: *
1846: * @param a one array to be tested for equality.
1847: * @param a2 the other array to be tested for equality.
1848: * @return <tt>true</tt> if the two arrays are equal.
1849: */
1850: public static boolean equals(char[] a, char[] a2) {
1851: if (a == a2)
1852: return true;
1853: if (a == null || a2 == null)
1854: return false;
1855:
1856: int length = a.length;
1857: if (a2.length != length)
1858: return false;
1859:
1860: for (int i = 0; i < length; i++)
1861: if (a[i] != a2[i])
1862: return false;
1863:
1864: return true;
1865: }
1866:
1867: /**
1868: * Returns <tt>true</tt> if the two specified arrays of bytes are
1869: * <i>equal</i> to one another. Two arrays are considered equal if both
1870: * arrays contain the same number of elements, and all corresponding pairs
1871: * of elements in the two arrays are equal. In other words, two arrays
1872: * are equal if they contain the same elements in the same order. Also,
1873: * two array references are considered equal if both are <tt>null</tt>.<p>
1874: *
1875: * @param a one array to be tested for equality.
1876: * @param a2 the other array to be tested for equality.
1877: * @return <tt>true</tt> if the two arrays are equal.
1878: */
1879: public static boolean equals(byte[] a, byte[] a2) {
1880: if (a == a2)
1881: return true;
1882: if (a == null || a2 == null)
1883: return false;
1884:
1885: int length = a.length;
1886: if (a2.length != length)
1887: return false;
1888:
1889: for (int i = 0; i < length; i++)
1890: if (a[i] != a2[i])
1891: return false;
1892:
1893: return true;
1894: }
1895:
1896: /**
1897: * Returns <tt>true</tt> if the two specified arrays of booleans are
1898: * <i>equal</i> to one another. Two arrays are considered equal if both
1899: * arrays contain the same number of elements, and all corresponding pairs
1900: * of elements in the two arrays are equal. In other words, two arrays
1901: * are equal if they contain the same elements in the same order. Also,
1902: * two array references are considered equal if both are <tt>null</tt>.<p>
1903: *
1904: * @param a one array to be tested for equality.
1905: * @param a2 the other array to be tested for equality.
1906: * @return <tt>true</tt> if the two arrays are equal.
1907: */
1908: public static boolean equals(boolean[] a, boolean[] a2) {
1909: if (a == a2)
1910: return true;
1911: if (a == null || a2 == null)
1912: return false;
1913:
1914: int length = a.length;
1915: if (a2.length != length)
1916: return false;
1917:
1918: for (int i = 0; i < length; i++)
1919: if (a[i] != a2[i])
1920: return false;
1921:
1922: return true;
1923: }
1924:
1925: /**
1926: * Returns <tt>true</tt> if the two specified arrays of doubles are
1927: * <i>equal</i> to one another. Two arrays are considered equal if both
1928: * arrays contain the same number of elements, and all corresponding pairs
1929: * of elements in the two arrays are equal. In other words, two arrays
1930: * are equal if they contain the same elements in the same order. Also,
1931: * two array references are considered equal if both are <tt>null</tt>.<p>
1932: *
1933: * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
1934: * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
1935: * (Unlike the <tt>==</tt> operator, this method considers
1936: * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
1937: *
1938: * @param a one array to be tested for equality.
1939: * @param a2 the other array to be tested for equality.
1940: * @return <tt>true</tt> if the two arrays are equal.
1941: * @see Double#equals(Object)
1942: */
1943: public static boolean equals(double[] a, double[] a2) {
1944: if (a == a2)
1945: return true;
1946: if (a == null || a2 == null)
1947: return false;
1948:
1949: int length = a.length;
1950: if (a2.length != length)
1951: return false;
1952:
1953: for (int i = 0; i < length; i++)
1954: if (Double.doubleToLongBits(a[i]) != Double
1955: .doubleToLongBits(a2[i]))
1956: return false;
1957:
1958: return true;
1959: }
1960:
1961: /**
1962: * Returns <tt>true</tt> if the two specified arrays of floats are
1963: * <i>equal</i> to one another. Two arrays are considered equal if both
1964: * arrays contain the same number of elements, and all corresponding pairs
1965: * of elements in the two arrays are equal. In other words, two arrays
1966: * are equal if they contain the same elements in the same order. Also,
1967: * two array references are considered equal if both are <tt>null</tt>.<p>
1968: *
1969: * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
1970: * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
1971: * (Unlike the <tt>==</tt> operator, this method considers
1972: * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
1973: *
1974: * @param a one array to be tested for equality.
1975: * @param a2 the other array to be tested for equality.
1976: * @return <tt>true</tt> if the two arrays are equal.
1977: * @see Float#equals(Object)
1978: */
1979: public static boolean equals(float[] a, float[] a2) {
1980: if (a == a2)
1981: return true;
1982: if (a == null || a2 == null)
1983: return false;
1984:
1985: int length = a.length;
1986: if (a2.length != length)
1987: return false;
1988:
1989: for (int i = 0; i < length; i++)
1990: if (Float.floatToIntBits(a[i]) != Float
1991: .floatToIntBits(a2[i]))
1992: return false;
1993:
1994: return true;
1995: }
1996:
1997: /**
1998: * Returns <tt>true</tt> if the two specified arrays of Objects are
1999: * <i>equal</i> to one another. The two arrays are considered equal if
2000: * both arrays contain the same number of elements, and all corresponding
2001: * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
2002: * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
2003: * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
2004: * they contain the same elements in the same order. Also, two array
2005: * references are considered equal if both are <tt>null</tt>.<p>
2006: *
2007: * @param a one array to be tested for equality.
2008: * @param a2 the other array to be tested for equality.
2009: * @return <tt>true</tt> if the two arrays are equal.
2010: */
2011: public static boolean equals(Object[] a, Object[] a2) {
2012: if (a == a2)
2013: return true;
2014: if (a == null || a2 == null)
2015: return false;
2016:
2017: int length = a.length;
2018: if (a2.length != length)
2019: return false;
2020:
2021: for (int i = 0; i < length; i++) {
2022: Object o1 = a[i];
2023: Object o2 = a2[i];
2024: if (!(o1 == null ? o2 == null : o1.equals(o2)))
2025: return false;
2026: }
2027:
2028: return true;
2029: }
2030:
2031: // Filling
2032:
2033: /**
2034: * Assigns the specified long value to each element of the specified array
2035: * of longs.
2036: *
2037: * @param a the array to be filled.
2038: * @param val the value to be stored in all elements of the array.
2039: */
2040: public static void fill(long[] a, long val) {
2041: fill(a, 0, a.length, val);
2042: }
2043:
2044: /**
2045: * Assigns the specified long value to each element of the specified
2046: * range of the specified array of longs. The range to be filled
2047: * extends from index <tt>fromIndex</tt>, inclusive, to index
2048: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2049: * range to be filled is empty.)
2050: *
2051: * @param a the array to be filled.
2052: * @param fromIndex the index of the first element (inclusive) to be
2053: * filled with the specified value.
2054: * @param toIndex the index of the last element (exclusive) to be
2055: * filled with the specified value.
2056: * @param val the value to be stored in all elements of the array.
2057: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2058: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2059: * <tt>toIndex > a.length</tt>
2060: */
2061: public static void fill(long[] a, int fromIndex, int toIndex,
2062: long val) {
2063: rangeCheck(a.length, fromIndex, toIndex);
2064: for (int i = fromIndex; i < toIndex; i++)
2065: a[i] = val;
2066: }
2067:
2068: /**
2069: * Assigns the specified int value to each element of the specified array
2070: * of ints.
2071: *
2072: * @param a the array to be filled.
2073: * @param val the value to be stored in all elements of the array.
2074: */
2075: public static void fill(int[] a, int val) {
2076: fill(a, 0, a.length, val);
2077: }
2078:
2079: /**
2080: * Assigns the specified int value to each element of the specified
2081: * range of the specified array of ints. The range to be filled
2082: * extends from index <tt>fromIndex</tt>, inclusive, to index
2083: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2084: * range to be filled is empty.)
2085: *
2086: * @param a the array to be filled.
2087: * @param fromIndex the index of the first element (inclusive) to be
2088: * filled with the specified value.
2089: * @param toIndex the index of the last element (exclusive) to be
2090: * filled with the specified value.
2091: * @param val the value to be stored in all elements of the array.
2092: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2093: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2094: * <tt>toIndex > a.length</tt>
2095: */
2096: public static void fill(int[] a, int fromIndex, int toIndex, int val) {
2097: rangeCheck(a.length, fromIndex, toIndex);
2098: for (int i = fromIndex; i < toIndex; i++)
2099: a[i] = val;
2100: }
2101:
2102: /**
2103: * Assigns the specified short value to each element of the specified array
2104: * of shorts.
2105: *
2106: * @param a the array to be filled.
2107: * @param val the value to be stored in all elements of the array.
2108: */
2109: public static void fill(short[] a, short val) {
2110: fill(a, 0, a.length, val);
2111: }
2112:
2113: /**
2114: * Assigns the specified short value to each element of the specified
2115: * range of the specified array of shorts. The range to be filled
2116: * extends from index <tt>fromIndex</tt>, inclusive, to index
2117: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2118: * range to be filled is empty.)
2119: *
2120: * @param a the array to be filled.
2121: * @param fromIndex the index of the first element (inclusive) to be
2122: * filled with the specified value.
2123: * @param toIndex the index of the last element (exclusive) to be
2124: * filled with the specified value.
2125: * @param val the value to be stored in all elements of the array.
2126: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2127: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2128: * <tt>toIndex > a.length</tt>
2129: */
2130: public static void fill(short[] a, int fromIndex, int toIndex,
2131: short val) {
2132: rangeCheck(a.length, fromIndex, toIndex);
2133: for (int i = fromIndex; i < toIndex; i++)
2134: a[i] = val;
2135: }
2136:
2137: /**
2138: * Assigns the specified char value to each element of the specified array
2139: * of chars.
2140: *
2141: * @param a the array to be filled.
2142: * @param val the value to be stored in all elements of the array.
2143: */
2144: public static void fill(char[] a, char val) {
2145: fill(a, 0, a.length, val);
2146: }
2147:
2148: /**
2149: * Assigns the specified char value to each element of the specified
2150: * range of the specified array of chars. The range to be filled
2151: * extends from index <tt>fromIndex</tt>, inclusive, to index
2152: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2153: * range to be filled is empty.)
2154: *
2155: * @param a the array to be filled.
2156: * @param fromIndex the index of the first element (inclusive) to be
2157: * filled with the specified value.
2158: * @param toIndex the index of the last element (exclusive) to be
2159: * filled with the specified value.
2160: * @param val the value to be stored in all elements of the array.
2161: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2162: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2163: * <tt>toIndex > a.length</tt>
2164: */
2165: public static void fill(char[] a, int fromIndex, int toIndex,
2166: char val) {
2167: rangeCheck(a.length, fromIndex, toIndex);
2168: for (int i = fromIndex; i < toIndex; i++)
2169: a[i] = val;
2170: }
2171:
2172: /**
2173: * Assigns the specified byte value to each element of the specified array
2174: * of bytes.
2175: *
2176: * @param a the array to be filled.
2177: * @param val the value to be stored in all elements of the array.
2178: */
2179: public static void fill(byte[] a, byte val) {
2180: fill(a, 0, a.length, val);
2181: }
2182:
2183: /**
2184: * Assigns the specified byte value to each element of the specified
2185: * range of the specified array of bytes. The range to be filled
2186: * extends from index <tt>fromIndex</tt>, inclusive, to index
2187: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2188: * range to be filled is empty.)
2189: *
2190: * @param a the array to be filled.
2191: * @param fromIndex the index of the first element (inclusive) to be
2192: * filled with the specified value.
2193: * @param toIndex the index of the last element (exclusive) to be
2194: * filled with the specified value.
2195: * @param val the value to be stored in all elements of the array.
2196: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2197: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2198: * <tt>toIndex > a.length</tt>
2199: */
2200: public static void fill(byte[] a, int fromIndex, int toIndex,
2201: byte val) {
2202: rangeCheck(a.length, fromIndex, toIndex);
2203: for (int i = fromIndex; i < toIndex; i++)
2204: a[i] = val;
2205: }
2206:
2207: /**
2208: * Assigns the specified boolean value to each element of the specified
2209: * array of booleans.
2210: *
2211: * @param a the array to be filled.
2212: * @param val the value to be stored in all elements of the array.
2213: */
2214: public static void fill(boolean[] a, boolean val) {
2215: fill(a, 0, a.length, val);
2216: }
2217:
2218: /**
2219: * Assigns the specified boolean value to each element of the specified
2220: * range of the specified array of booleans. The range to be filled
2221: * extends from index <tt>fromIndex</tt>, inclusive, to index
2222: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2223: * range to be filled is empty.)
2224: *
2225: * @param a the array to be filled.
2226: * @param fromIndex the index of the first element (inclusive) to be
2227: * filled with the specified value.
2228: * @param toIndex the index of the last element (exclusive) to be
2229: * filled with the specified value.
2230: * @param val the value to be stored in all elements of the array.
2231: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2232: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2233: * <tt>toIndex > a.length</tt>
2234: */
2235: public static void fill(boolean[] a, int fromIndex, int toIndex,
2236: boolean val) {
2237: rangeCheck(a.length, fromIndex, toIndex);
2238: for (int i = fromIndex; i < toIndex; i++)
2239: a[i] = val;
2240: }
2241:
2242: /**
2243: * Assigns the specified double value to each element of the specified
2244: * array of doubles.
2245: *
2246: * @param a the array to be filled.
2247: * @param val the value to be stored in all elements of the array.
2248: */
2249: public static void fill(double[] a, double val) {
2250: fill(a, 0, a.length, val);
2251: }
2252:
2253: /**
2254: * Assigns the specified double value to each element of the specified
2255: * range of the specified array of doubles. The range to be filled
2256: * extends from index <tt>fromIndex</tt>, inclusive, to index
2257: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2258: * range to be filled is empty.)
2259: *
2260: * @param a the array to be filled.
2261: * @param fromIndex the index of the first element (inclusive) to be
2262: * filled with the specified value.
2263: * @param toIndex the index of the last element (exclusive) to be
2264: * filled with the specified value.
2265: * @param val the value to be stored in all elements of the array.
2266: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2267: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2268: * <tt>toIndex > a.length</tt>
2269: */
2270: public static void fill(double[] a, int fromIndex, int toIndex,
2271: double val) {
2272: rangeCheck(a.length, fromIndex, toIndex);
2273: for (int i = fromIndex; i < toIndex; i++)
2274: a[i] = val;
2275: }
2276:
2277: /**
2278: * Assigns the specified float value to each element of the specified array
2279: * of floats.
2280: *
2281: * @param a the array to be filled.
2282: * @param val the value to be stored in all elements of the array.
2283: */
2284: public static void fill(float[] a, float val) {
2285: fill(a, 0, a.length, val);
2286: }
2287:
2288: /**
2289: * Assigns the specified float value to each element of the specified
2290: * range of the specified array of floats. The range to be filled
2291: * extends from index <tt>fromIndex</tt>, inclusive, to index
2292: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2293: * range to be filled is empty.)
2294: *
2295: * @param a the array to be filled.
2296: * @param fromIndex the index of the first element (inclusive) to be
2297: * filled with the specified value.
2298: * @param toIndex the index of the last element (exclusive) to be
2299: * filled with the specified value.
2300: * @param val the value to be stored in all elements of the array.
2301: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2302: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2303: * <tt>toIndex > a.length</tt>
2304: */
2305: public static void fill(float[] a, int fromIndex, int toIndex,
2306: float val) {
2307: rangeCheck(a.length, fromIndex, toIndex);
2308: for (int i = fromIndex; i < toIndex; i++)
2309: a[i] = val;
2310: }
2311:
2312: /**
2313: * Assigns the specified Object reference to each element of the specified
2314: * array of Objects.
2315: *
2316: * @param a the array to be filled.
2317: * @param val the value to be stored in all elements of the array.
2318: */
2319: public static void fill(Object[] a, Object val) {
2320: fill(a, 0, a.length, val);
2321: }
2322:
2323: /**
2324: * Assigns the specified Object reference to each element of the specified
2325: * range of the specified array of Objects. The range to be filled
2326: * extends from index <tt>fromIndex</tt>, inclusive, to index
2327: * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2328: * range to be filled is empty.)
2329: *
2330: * @param a the array to be filled.
2331: * @param fromIndex the index of the first element (inclusive) to be
2332: * filled with the specified value.
2333: * @param toIndex the index of the last element (exclusive) to be
2334: * filled with the specified value.
2335: * @param val the value to be stored in all elements of the array.
2336: * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2337: * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2338: * <tt>toIndex > a.length</tt>
2339: */
2340: public static void fill(Object[] a, int fromIndex, int toIndex,
2341: Object val) {
2342: rangeCheck(a.length, fromIndex, toIndex);
2343: for (int i = fromIndex; i < toIndex; i++)
2344: a[i] = val;
2345: }
2346:
2347: // Misc
2348:
2349: /**
2350: * Returns a fixed-size list backed by the specified array. (Changes to
2351: * the returned list "write through" to the array.) This method acts
2352: * as bridge between array-based and collection-based APIs, in
2353: * combination with <tt>Collection.toArray</tt>. The returned list is
2354: * serializable and implements {@link RandomAccess}.
2355: *
2356: * @param a the array by which the list will be backed.
2357: * @return a list view of the specified array.
2358: * @see Collection#toArray()
2359: */
2360: public static List asList(Object[] a) {
2361: return new ArrayList(a);
2362: }
2363:
2364: /**
2365: * @serial include
2366: */
2367: private static class ArrayList extends AbstractList implements
2368: RandomAccess, java.io.Serializable {
2369: private static final long serialVersionUID = -2764017481108945198L;
2370: private Object[] a;
2371:
2372: ArrayList(Object[] array) {
2373: if (array == null)
2374: throw new NullPointerException();
2375: a = array;
2376: }
2377:
2378: public int size() {
2379: return a.length;
2380: }
2381:
2382: public Object[] toArray() {
2383: return (Object[]) a.clone();
2384: }
2385:
2386: public Object get(int index) {
2387: return a[index];
2388: }
2389:
2390: public Object set(int index, Object element) {
2391: Object oldValue = a[index];
2392: a[index] = element;
2393: return oldValue;
2394: }
2395:
2396: public int indexOf(Object o) {
2397: if (o == null) {
2398: for (int i = 0; i < a.length; i++)
2399: if (a[i] == null)
2400: return i;
2401: } else {
2402: for (int i = 0; i < a.length; i++)
2403: if (o.equals(a[i]))
2404: return i;
2405: }
2406: return -1;
2407: }
2408:
2409: public boolean contains(Object o) {
2410: return indexOf(o) != -1;
2411: }
2412: }
2413: }
|