1. /*
  2. * @(#)Arrays.java 1.48 03/01/23
  3. *
  4. * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util;
  8. import java.lang.reflect.*;
  9. /**
  10. * This class contains various methods for manipulating arrays (such as
  11. * sorting and searching). This class also contains a static factory
  12. * that allows arrays to be viewed as lists.
  13. *
  14. * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
  15. * the specified array reference is null.
  16. *
  17. * <p>The documentation for the methods contained in this class includes
  18. * briefs description of the <i>implementations</i>. Such descriptions should
  19. * be regarded as <i>implementation notes</i>, rather than parts of the
  20. * <i>specification</i>. Implementors should feel free to substitute other
  21. * algorithms, so long as the specification itself is adhered to. (For
  22. * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
  23. * a mergesort, but it does have to be <i>stable</i>.)
  24. *
  25. * <p>This class is a member of the
  26. * <a href="{@docRoot}/../guide/collections/index.html">
  27. * Java Collections Framework</a>.
  28. *
  29. * @author Josh Bloch
  30. * @version 1.48, 01/23/03
  31. * @see Comparable
  32. * @see Comparator
  33. * @since 1.2
  34. */
  35. public class Arrays {
  36. // Suppresses default constructor, ensuring non-instantiability.
  37. private Arrays() {
  38. }
  39. // Sorting
  40. /**
  41. * Sorts the specified array of longs into ascending numerical order.
  42. * The sorting algorithm is a tuned quicksort, adapted from Jon
  43. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  44. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  45. * 1993). This algorithm offers n*log(n) performance on many data sets
  46. * that cause other quicksorts to degrade to quadratic performance.
  47. *
  48. * @param a the array to be sorted.
  49. */
  50. public static void sort(long[] a) {
  51. sort1(a, 0, a.length);
  52. }
  53. /**
  54. * Sorts the specified range of the specified array of longs into
  55. * ascending numerical order. The range to be sorted extends from index
  56. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  57. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
  58. *
  59. * <p>The sorting algorithm is a tuned quicksort, adapted from Jon
  60. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  61. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  62. * 1993). This algorithm offers n*log(n) performance on many data sets
  63. * that cause other quicksorts to degrade to quadratic performance.
  64. *
  65. * @param a the array to be sorted.
  66. * @param fromIndex the index of the first element (inclusive) to be
  67. * sorted.
  68. * @param toIndex the index of the last element (exclusive) to be sorted.
  69. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  70. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  71. * <tt>toIndex > a.length</tt>
  72. */
  73. public static void sort(long[] a, int fromIndex, int toIndex) {
  74. rangeCheck(a.length, fromIndex, toIndex);
  75. sort1(a, fromIndex, toIndex-fromIndex);
  76. }
  77. /**
  78. * Sorts the specified array of ints into ascending numerical order.
  79. * The sorting algorithm is a tuned quicksort, adapted from Jon
  80. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  81. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  82. * 1993). This algorithm offers n*log(n) performance on many data sets
  83. * that cause other quicksorts to degrade to quadratic performance.
  84. *
  85. * @param a the array to be sorted.
  86. */
  87. public static void sort(int[] a) {
  88. sort1(a, 0, a.length);
  89. }
  90. /**
  91. * Sorts the specified range of the specified array of ints into
  92. * ascending numerical order. The range to be sorted extends from index
  93. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  94. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
  95. *
  96. * The sorting algorithm is a tuned quicksort, adapted from Jon
  97. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  98. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  99. * 1993). This algorithm offers n*log(n) performance on many data sets
  100. * that cause other quicksorts to degrade to quadratic performance.
  101. *
  102. * @param a the array to be sorted.
  103. * @param fromIndex the index of the first element (inclusive) to be
  104. * sorted.
  105. * @param toIndex the index of the last element (exclusive) to be sorted.
  106. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  107. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  108. * <tt>toIndex > a.length</tt>
  109. */
  110. public static void sort(int[] a, int fromIndex, int toIndex) {
  111. rangeCheck(a.length, fromIndex, toIndex);
  112. sort1(a, fromIndex, toIndex-fromIndex);
  113. }
  114. /**
  115. * Sorts the specified array of shorts into ascending numerical order.
  116. * The sorting algorithm is a tuned quicksort, adapted from Jon
  117. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  118. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  119. * 1993). This algorithm offers n*log(n) performance on many data sets
  120. * that cause other quicksorts to degrade to quadratic performance.
  121. *
  122. * @param a the array to be sorted.
  123. */
  124. public static void sort(short[] a) {
  125. sort1(a, 0, a.length);
  126. }
  127. /**
  128. * Sorts the specified range of the specified array of shorts into
  129. * ascending numerical order. The range to be sorted extends from index
  130. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  131. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
  132. *
  133. * The sorting algorithm is a tuned quicksort, adapted from Jon
  134. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  135. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  136. * 1993). This algorithm offers n*log(n) performance on many data sets
  137. * that cause other quicksorts to degrade to quadratic performance.
  138. *
  139. * @param a the array to be sorted.
  140. * @param fromIndex the index of the first element (inclusive) to be
  141. * sorted.
  142. * @param toIndex the index of the last element (exclusive) to be sorted.
  143. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  144. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  145. * <tt>toIndex > a.length</tt>
  146. */
  147. public static void sort(short[] a, int fromIndex, int toIndex) {
  148. rangeCheck(a.length, fromIndex, toIndex);
  149. sort1(a, fromIndex, toIndex-fromIndex);
  150. }
  151. /**
  152. * Sorts the specified array of chars into ascending numerical order.
  153. * The sorting algorithm is a tuned quicksort, adapted from Jon
  154. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  155. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  156. * 1993). This algorithm offers n*log(n) performance on many data sets
  157. * that cause other quicksorts to degrade to quadratic performance.
  158. *
  159. * @param a the array to be sorted.
  160. */
  161. public static void sort(char[] a) {
  162. sort1(a, 0, a.length);
  163. }
  164. /**
  165. * Sorts the specified range of the specified array of chars into
  166. * ascending numerical order. The range to be sorted extends from index
  167. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  168. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
  169. *
  170. * The sorting algorithm is a tuned quicksort, adapted from Jon
  171. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  172. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  173. * 1993). This algorithm offers n*log(n) performance on many data sets
  174. * that cause other quicksorts to degrade to quadratic performance.
  175. *
  176. * @param a the array to be sorted.
  177. * @param fromIndex the index of the first element (inclusive) to be
  178. * sorted.
  179. * @param toIndex the index of the last element (exclusive) to be sorted.
  180. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  181. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  182. * <tt>toIndex > a.length</tt>
  183. */
  184. public static void sort(char[] a, int fromIndex, int toIndex) {
  185. rangeCheck(a.length, fromIndex, toIndex);
  186. sort1(a, fromIndex, toIndex-fromIndex);
  187. }
  188. /**
  189. * Sorts the specified array of bytes into ascending numerical order.
  190. * The sorting algorithm is a tuned quicksort, adapted from Jon
  191. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  192. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  193. * 1993). This algorithm offers n*log(n) performance on many data sets
  194. * that cause other quicksorts to degrade to quadratic performance.
  195. *
  196. * @param a the array to be sorted.
  197. */
  198. public static void sort(byte[] a) {
  199. sort1(a, 0, a.length);
  200. }
  201. /**
  202. * Sorts the specified range of the specified array of bytes into
  203. * ascending numerical order. The range to be sorted extends from index
  204. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  205. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
  206. *
  207. * The sorting algorithm is a tuned quicksort, adapted from Jon
  208. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  209. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  210. * 1993). This algorithm offers n*log(n) performance on many data sets
  211. * that cause other quicksorts to degrade to quadratic performance.
  212. *
  213. * @param a the array to be sorted.
  214. * @param fromIndex the index of the first element (inclusive) to be
  215. * sorted.
  216. * @param toIndex the index of the last element (exclusive) to be sorted.
  217. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  218. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  219. * <tt>toIndex > a.length</tt>
  220. */
  221. public static void sort(byte[] a, int fromIndex, int toIndex) {
  222. rangeCheck(a.length, fromIndex, toIndex);
  223. sort1(a, fromIndex, toIndex-fromIndex);
  224. }
  225. /**
  226. * Sorts the specified array of doubles into ascending numerical order.
  227. * <p>
  228. * The <code><</code> relation does not provide a total order on
  229. * all floating-point values; although they are distinct numbers
  230. * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
  231. * compares neither less than, greater than, nor equal to any
  232. * floating-point value, even itself. To allow the sort to
  233. * proceed, instead of using the <code><</code> relation to
  234. * determine ascending numerical order, this method uses the total
  235. * order imposed by {@link Double#compareTo}. This ordering
  236. * differs from the <code><</code> relation in that
  237. * <code>-0.0</code> is treated as less than <code>0.0</code> and
  238. * NaN is considered greater than any other floating-point value.
  239. * For the purposes of sorting, all NaN values are considered
  240. * equivalent and equal.
  241. * <p>
  242. * The sorting algorithm is a tuned quicksort, adapted from Jon
  243. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  244. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  245. * 1993). This algorithm offers n*log(n) performance on many data sets
  246. * that cause other quicksorts to degrade to quadratic performance.
  247. *
  248. * @param a the array to be sorted.
  249. */
  250. public static void sort(double[] a) {
  251. sort2(a, 0, a.length);
  252. }
  253. /**
  254. * Sorts the specified range of the specified array of doubles into
  255. * ascending numerical order. The range to be sorted extends from index
  256. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  257. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
  258. * <p>
  259. * The <code><</code> relation does not provide a total order on
  260. * all floating-point values; although they are distinct numbers
  261. * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
  262. * compares neither less than, greater than, nor equal to any
  263. * floating-point value, even itself. To allow the sort to
  264. * proceed, instead of using the <code><</code> relation to
  265. * determine ascending numerical order, this method uses the total
  266. * order imposed by {@link Double#compareTo}. This ordering
  267. * differs from the <code><</code> relation in that
  268. * <code>-0.0</code> is treated as less than <code>0.0</code> and
  269. * NaN is considered greater than any other floating-point value.
  270. * For the purposes of sorting, all NaN values are considered
  271. * equivalent and equal.
  272. * <p>
  273. * The sorting algorithm is a tuned quicksort, adapted from Jon
  274. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  275. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  276. * 1993). This algorithm offers n*log(n) performance on many data sets
  277. * that cause other quicksorts to degrade to quadratic performance.
  278. *
  279. * @param a the array to be sorted.
  280. * @param fromIndex the index of the first element (inclusive) to be
  281. * sorted.
  282. * @param toIndex the index of the last element (exclusive) to be sorted.
  283. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  284. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  285. * <tt>toIndex > a.length</tt>
  286. */
  287. public static void sort(double[] a, int fromIndex, int toIndex) {
  288. rangeCheck(a.length, fromIndex, toIndex);
  289. sort2(a, fromIndex, toIndex);
  290. }
  291. /**
  292. * Sorts the specified array of floats into ascending numerical order.
  293. * <p>
  294. * The <code><</code> relation does not provide a total order on
  295. * all floating-point values; although they are distinct numbers
  296. * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
  297. * compares neither less than, greater than, nor equal to any
  298. * floating-point value, even itself. To allow the sort to
  299. * proceed, instead of using the <code><</code> relation to
  300. * determine ascending numerical order, this method uses the total
  301. * order imposed by {@link Float#compareTo}. This ordering
  302. * differs from the <code><</code> relation in that
  303. * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
  304. * NaN is considered greater than any other floating-point value.
  305. * For the purposes of sorting, all NaN values are considered
  306. * equivalent and equal.
  307. * <p>
  308. * The sorting algorithm is a tuned quicksort, adapted from Jon
  309. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  310. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  311. * 1993). This algorithm offers n*log(n) performance on many data sets
  312. * that cause other quicksorts to degrade to quadratic performance.
  313. *
  314. * @param a the array to be sorted.
  315. */
  316. public static void sort(float[] a) {
  317. sort2(a, 0, a.length);
  318. }
  319. /**
  320. * Sorts the specified range of the specified array of floats into
  321. * ascending numerical order. The range to be sorted extends from index
  322. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  323. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
  324. * <p>
  325. * The <code><</code> relation does not provide a total order on
  326. * all floating-point values; although they are distinct numbers
  327. * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
  328. * compares neither less than, greater than, nor equal to any
  329. * floating-point value, even itself. To allow the sort to
  330. * proceed, instead of using the <code><</code> relation to
  331. * determine ascending numerical order, this method uses the total
  332. * order imposed by {@link Float#compareTo}. This ordering
  333. * differs from the <code><</code> relation in that
  334. * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
  335. * NaN is considered greater than any other floating-point value.
  336. * For the purposes of sorting, all NaN values are considered
  337. * equivalent and equal.
  338. * <p>
  339. * The sorting algorithm is a tuned quicksort, adapted from Jon
  340. * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  341. * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  342. * 1993). This algorithm offers n*log(n) performance on many data sets
  343. * that cause other quicksorts to degrade to quadratic performance.
  344. *
  345. * @param a the array to be sorted.
  346. * @param fromIndex the index of the first element (inclusive) to be
  347. * sorted.
  348. * @param toIndex the index of the last element (exclusive) to be sorted.
  349. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  350. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  351. * <tt>toIndex > a.length</tt>
  352. */
  353. public static void sort(float[] a, int fromIndex, int toIndex) {
  354. rangeCheck(a.length, fromIndex, toIndex);
  355. sort2(a, fromIndex, toIndex);
  356. }
  357. private static void sort2(double a[], int fromIndex, int toIndex) {
  358. final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
  359. /*
  360. * The sort is done in three phases to avoid the expense of using
  361. * NaN and -0.0 aware comparisons during the main sort.
  362. */
  363. /*
  364. * Preprocessing phase: Move any NaN's to end of array, count the
  365. * number of -0.0's, and turn them into 0.0's.
  366. */
  367. int numNegZeros = 0;
  368. int i = fromIndex, n = toIndex;
  369. while(i < n) {
  370. if (a[i] != a[i]) {
  371. double swap = a[i];
  372. a[i] = a[--n];
  373. a[n] = swap;
  374. } else {
  375. if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
  376. a[i] = 0.0d;
  377. numNegZeros++;
  378. }
  379. i++;
  380. }
  381. }
  382. // Main sort phase: quicksort everything but the NaN's
  383. sort1(a, fromIndex, n-fromIndex);
  384. // Postprocessing phase: change 0.0's to -0.0's as required
  385. if (numNegZeros != 0) {
  386. int j = binarySearch(a, 0.0d, fromIndex, n-1); // posn of ANY zero
  387. do {
  388. j--;
  389. } while (j>=0 && a[j]==0.0d);
  390. // j is now one less than the index of the FIRST zero
  391. for (int k=0; k<numNegZeros; k++)
  392. a[++j] = -0.0d;
  393. }
  394. }
  395. private static void sort2(float a[], int fromIndex, int toIndex) {
  396. final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
  397. /*
  398. * The sort is done in three phases to avoid the expense of using
  399. * NaN and -0.0 aware comparisons during the main sort.
  400. */
  401. /*
  402. * Preprocessing phase: Move any NaN's to end of array, count the
  403. * number of -0.0's, and turn them into 0.0's.
  404. */
  405. int numNegZeros = 0;
  406. int i = fromIndex, n = toIndex;
  407. while(i < n) {
  408. if (a[i] != a[i]) {
  409. float swap = a[i];
  410. a[i] = a[--n];
  411. a[n] = swap;
  412. } else {
  413. if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {
  414. a[i] = 0.0f;
  415. numNegZeros++;
  416. }
  417. i++;
  418. }
  419. }
  420. // Main sort phase: quicksort everything but the NaN's
  421. sort1(a, fromIndex, n-fromIndex);
  422. // Postprocessing phase: change 0.0's to -0.0's as required
  423. if (numNegZeros != 0) {
  424. int j = binarySearch(a, 0.0f, fromIndex, n-1); // posn of ANY zero
  425. do {
  426. j--;
  427. } while (j>=0 && a[j]==0.0f);
  428. // j is now one less than the index of the FIRST zero
  429. for (int k=0; k<numNegZeros; k++)
  430. a[++j] = -0.0f;
  431. }
  432. }
  433. /*
  434. * The code for each of the seven primitive types is largely identical.
  435. * C'est la vie.
  436. */
  437. /**
  438. * Sorts the specified sub-array of longs into ascending order.
  439. */
  440. private static void sort1(long x[], int off, int len) {
  441. // Insertion sort on smallest arrays
  442. if (len < 7) {
  443. for (int i=off; i<len+off; i++)
  444. for (int j=i; j>off && x[j-1]>x[j]; j--)
  445. swap(x, j, j-1);
  446. return;
  447. }
  448. // Choose a partition element, v
  449. int m = off + (len >> 1); // Small arrays, middle element
  450. if (len > 7) {
  451. int l = off;
  452. int n = off + len - 1;
  453. if (len > 40) { // Big arrays, pseudomedian of 9
  454. int s = len8;
  455. l = med3(x, l, l+s, l+2*s);
  456. m = med3(x, m-s, m, m+s);
  457. n = med3(x, n-2*s, n-s, n);
  458. }
  459. m = med3(x, l, m, n); // Mid-size, med of 3
  460. }
  461. long v = x[m];
  462. // Establish Invariant: v* (<v)* (>v)* v*
  463. int a = off, b = a, c = off + len - 1, d = c;
  464. while(true) {
  465. while (b <= c && x[b] <= v) {
  466. if (x[b] == v)
  467. swap(x, a++, b);
  468. b++;
  469. }
  470. while (c >= b && x[c] >= v) {
  471. if (x[c] == v)
  472. swap(x, c, d--);
  473. c--;
  474. }
  475. if (b > c)
  476. break;
  477. swap(x, b++, c--);
  478. }
  479. // Swap partition elements back to middle
  480. int s, n = off + len;
  481. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  482. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  483. // Recursively sort non-partition-elements
  484. if ((s = b-a) > 1)
  485. sort1(x, off, s);
  486. if ((s = d-c) > 1)
  487. sort1(x, n-s, s);
  488. }
  489. /**
  490. * Swaps x[a] with x[b].
  491. */
  492. private static void swap(long x[], int a, int b) {
  493. long t = x[a];
  494. x[a] = x[b];
  495. x[b] = t;
  496. }
  497. /**
  498. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  499. */
  500. private static void vecswap(long x[], int a, int b, int n) {
  501. for (int i=0; i<n; i++, a++, b++)
  502. swap(x, a, b);
  503. }
  504. /**
  505. * Returns the index of the median of the three indexed longs.
  506. */
  507. private static int med3(long x[], int a, int b, int c) {
  508. return (x[a] < x[b] ?
  509. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  510. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  511. }
  512. /**
  513. * Sorts the specified sub-array of integers into ascending order.
  514. */
  515. private static void sort1(int x[], int off, int len) {
  516. // Insertion sort on smallest arrays
  517. if (len < 7) {
  518. for (int i=off; i<len+off; i++)
  519. for (int j=i; j>off && x[j-1]>x[j]; j--)
  520. swap(x, j, j-1);
  521. return;
  522. }
  523. // Choose a partition element, v
  524. int m = off + (len >> 1); // Small arrays, middle element
  525. if (len > 7) {
  526. int l = off;
  527. int n = off + len - 1;
  528. if (len > 40) { // Big arrays, pseudomedian of 9
  529. int s = len8;
  530. l = med3(x, l, l+s, l+2*s);
  531. m = med3(x, m-s, m, m+s);
  532. n = med3(x, n-2*s, n-s, n);
  533. }
  534. m = med3(x, l, m, n); // Mid-size, med of 3
  535. }
  536. int v = x[m];
  537. // Establish Invariant: v* (<v)* (>v)* v*
  538. int a = off, b = a, c = off + len - 1, d = c;
  539. while(true) {
  540. while (b <= c && x[b] <= v) {
  541. if (x[b] == v)
  542. swap(x, a++, b);
  543. b++;
  544. }
  545. while (c >= b && x[c] >= v) {
  546. if (x[c] == v)
  547. swap(x, c, d--);
  548. c--;
  549. }
  550. if (b > c)
  551. break;
  552. swap(x, b++, c--);
  553. }
  554. // Swap partition elements back to middle
  555. int s, n = off + len;
  556. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  557. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  558. // Recursively sort non-partition-elements
  559. if ((s = b-a) > 1)
  560. sort1(x, off, s);
  561. if ((s = d-c) > 1)
  562. sort1(x, n-s, s);
  563. }
  564. /**
  565. * Swaps x[a] with x[b].
  566. */
  567. private static void swap(int x[], int a, int b) {
  568. int t = x[a];
  569. x[a] = x[b];
  570. x[b] = t;
  571. }
  572. /**
  573. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  574. */
  575. private static void vecswap(int x[], int a, int b, int n) {
  576. for (int i=0; i<n; i++, a++, b++)
  577. swap(x, a, b);
  578. }
  579. /**
  580. * Returns the index of the median of the three indexed integers.
  581. */
  582. private static int med3(int x[], int a, int b, int c) {
  583. return (x[a] < x[b] ?
  584. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  585. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  586. }
  587. /**
  588. * Sorts the specified sub-array of shorts into ascending order.
  589. */
  590. private static void sort1(short x[], int off, int len) {
  591. // Insertion sort on smallest arrays
  592. if (len < 7) {
  593. for (int i=off; i<len+off; i++)
  594. for (int j=i; j>off && x[j-1]>x[j]; j--)
  595. swap(x, j, j-1);
  596. return;
  597. }
  598. // Choose a partition element, v
  599. int m = off + (len >> 1); // Small arrays, middle element
  600. if (len > 7) {
  601. int l = off;
  602. int n = off + len - 1;
  603. if (len > 40) { // Big arrays, pseudomedian of 9
  604. int s = len8;
  605. l = med3(x, l, l+s, l+2*s);
  606. m = med3(x, m-s, m, m+s);
  607. n = med3(x, n-2*s, n-s, n);
  608. }
  609. m = med3(x, l, m, n); // Mid-size, med of 3
  610. }
  611. short v = x[m];
  612. // Establish Invariant: v* (<v)* (>v)* v*
  613. int a = off, b = a, c = off + len - 1, d = c;
  614. while(true) {
  615. while (b <= c && x[b] <= v) {
  616. if (x[b] == v)
  617. swap(x, a++, b);
  618. b++;
  619. }
  620. while (c >= b && x[c] >= v) {
  621. if (x[c] == v)
  622. swap(x, c, d--);
  623. c--;
  624. }
  625. if (b > c)
  626. break;
  627. swap(x, b++, c--);
  628. }
  629. // Swap partition elements back to middle
  630. int s, n = off + len;
  631. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  632. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  633. // Recursively sort non-partition-elements
  634. if ((s = b-a) > 1)
  635. sort1(x, off, s);
  636. if ((s = d-c) > 1)
  637. sort1(x, n-s, s);
  638. }
  639. /**
  640. * Swaps x[a] with x[b].
  641. */
  642. private static void swap(short x[], int a, int b) {
  643. short t = x[a];
  644. x[a] = x[b];
  645. x[b] = t;
  646. }
  647. /**
  648. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  649. */
  650. private static void vecswap(short x[], int a, int b, int n) {
  651. for (int i=0; i<n; i++, a++, b++)
  652. swap(x, a, b);
  653. }
  654. /**
  655. * Returns the index of the median of the three indexed shorts.
  656. */
  657. private static int med3(short x[], int a, int b, int c) {
  658. return (x[a] < x[b] ?
  659. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  660. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  661. }
  662. /**
  663. * Sorts the specified sub-array of chars into ascending order.
  664. */
  665. private static void sort1(char x[], int off, int len) {
  666. // Insertion sort on smallest arrays
  667. if (len < 7) {
  668. for (int i=off; i<len+off; i++)
  669. for (int j=i; j>off && x[j-1]>x[j]; j--)
  670. swap(x, j, j-1);
  671. return;
  672. }
  673. // Choose a partition element, v
  674. int m = off + (len >> 1); // Small arrays, middle element
  675. if (len > 7) {
  676. int l = off;
  677. int n = off + len - 1;
  678. if (len > 40) { // Big arrays, pseudomedian of 9
  679. int s = len8;
  680. l = med3(x, l, l+s, l+2*s);
  681. m = med3(x, m-s, m, m+s);
  682. n = med3(x, n-2*s, n-s, n);
  683. }
  684. m = med3(x, l, m, n); // Mid-size, med of 3
  685. }
  686. char v = x[m];
  687. // Establish Invariant: v* (<v)* (>v)* v*
  688. int a = off, b = a, c = off + len - 1, d = c;
  689. while(true) {
  690. while (b <= c && x[b] <= v) {
  691. if (x[b] == v)
  692. swap(x, a++, b);
  693. b++;
  694. }
  695. while (c >= b && x[c] >= v) {
  696. if (x[c] == v)
  697. swap(x, c, d--);
  698. c--;
  699. }
  700. if (b > c)
  701. break;
  702. swap(x, b++, c--);
  703. }
  704. // Swap partition elements back to middle
  705. int s, n = off + len;
  706. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  707. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  708. // Recursively sort non-partition-elements
  709. if ((s = b-a) > 1)
  710. sort1(x, off, s);
  711. if ((s = d-c) > 1)
  712. sort1(x, n-s, s);
  713. }
  714. /**
  715. * Swaps x[a] with x[b].
  716. */
  717. private static void swap(char x[], int a, int b) {
  718. char t = x[a];
  719. x[a] = x[b];
  720. x[b] = t;
  721. }
  722. /**
  723. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  724. */
  725. private static void vecswap(char x[], int a, int b, int n) {
  726. for (int i=0; i<n; i++, a++, b++)
  727. swap(x, a, b);
  728. }
  729. /**
  730. * Returns the index of the median of the three indexed chars.
  731. */
  732. private static int med3(char x[], int a, int b, int c) {
  733. return (x[a] < x[b] ?
  734. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  735. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  736. }
  737. /**
  738. * Sorts the specified sub-array of bytes into ascending order.
  739. */
  740. private static void sort1(byte x[], int off, int len) {
  741. // Insertion sort on smallest arrays
  742. if (len < 7) {
  743. for (int i=off; i<len+off; i++)
  744. for (int j=i; j>off && x[j-1]>x[j]; j--)
  745. swap(x, j, j-1);
  746. return;
  747. }
  748. // Choose a partition element, v
  749. int m = off + (len >> 1); // Small arrays, middle element
  750. if (len > 7) {
  751. int l = off;
  752. int n = off + len - 1;
  753. if (len > 40) { // Big arrays, pseudomedian of 9
  754. int s = len8;
  755. l = med3(x, l, l+s, l+2*s);
  756. m = med3(x, m-s, m, m+s);
  757. n = med3(x, n-2*s, n-s, n);
  758. }
  759. m = med3(x, l, m, n); // Mid-size, med of 3
  760. }
  761. byte v = x[m];
  762. // Establish Invariant: v* (<v)* (>v)* v*
  763. int a = off, b = a, c = off + len - 1, d = c;
  764. while(true) {
  765. while (b <= c && x[b] <= v) {
  766. if (x[b] == v)
  767. swap(x, a++, b);
  768. b++;
  769. }
  770. while (c >= b && x[c] >= v) {
  771. if (x[c] == v)
  772. swap(x, c, d--);
  773. c--;
  774. }
  775. if (b > c)
  776. break;
  777. swap(x, b++, c--);
  778. }
  779. // Swap partition elements back to middle
  780. int s, n = off + len;
  781. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  782. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  783. // Recursively sort non-partition-elements
  784. if ((s = b-a) > 1)
  785. sort1(x, off, s);
  786. if ((s = d-c) > 1)
  787. sort1(x, n-s, s);
  788. }
  789. /**
  790. * Swaps x[a] with x[b].
  791. */
  792. private static void swap(byte x[], int a, int b) {
  793. byte t = x[a];
  794. x[a] = x[b];
  795. x[b] = t;
  796. }
  797. /**
  798. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  799. */
  800. private static void vecswap(byte x[], int a, int b, int n) {
  801. for (int i=0; i<n; i++, a++, b++)
  802. swap(x, a, b);
  803. }
  804. /**
  805. * Returns the index of the median of the three indexed bytes.
  806. */
  807. private static int med3(byte x[], int a, int b, int c) {
  808. return (x[a] < x[b] ?
  809. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  810. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  811. }
  812. /**
  813. * Sorts the specified sub-array of doubles into ascending order.
  814. */
  815. private static void sort1(double x[], int off, int len) {
  816. // Insertion sort on smallest arrays
  817. if (len < 7) {
  818. for (int i=off; i<len+off; i++)
  819. for (int j=i; j>off && x[j-1]>x[j]; j--)
  820. swap(x, j, j-1);
  821. return;
  822. }
  823. // Choose a partition element, v
  824. int m = off + (len >> 1); // Small arrays, middle element
  825. if (len > 7) {
  826. int l = off;
  827. int n = off + len - 1;
  828. if (len > 40) { // Big arrays, pseudomedian of 9
  829. int s = len8;
  830. l = med3(x, l, l+s, l+2*s);
  831. m = med3(x, m-s, m, m+s);
  832. n = med3(x, n-2*s, n-s, n);
  833. }
  834. m = med3(x, l, m, n); // Mid-size, med of 3
  835. }
  836. double v = x[m];
  837. // Establish Invariant: v* (<v)* (>v)* v*
  838. int a = off, b = a, c = off + len - 1, d = c;
  839. while(true) {
  840. while (b <= c && x[b] <= v) {
  841. if (x[b] == v)
  842. swap(x, a++, b);
  843. b++;
  844. }
  845. while (c >= b && x[c] >= v) {
  846. if (x[c] == v)
  847. swap(x, c, d--);
  848. c--;
  849. }
  850. if (b > c)
  851. break;
  852. swap(x, b++, c--);
  853. }
  854. // Swap partition elements back to middle
  855. int s, n = off + len;
  856. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  857. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  858. // Recursively sort non-partition-elements
  859. if ((s = b-a) > 1)
  860. sort1(x, off, s);
  861. if ((s = d-c) > 1)
  862. sort1(x, n-s, s);
  863. }
  864. /**
  865. * Swaps x[a] with x[b].
  866. */
  867. private static void swap(double x[], int a, int b) {
  868. double t = x[a];
  869. x[a] = x[b];
  870. x[b] = t;
  871. }
  872. /**
  873. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  874. */
  875. private static void vecswap(double x[], int a, int b, int n) {
  876. for (int i=0; i<n; i++, a++, b++)
  877. swap(x, a, b);
  878. }
  879. /**
  880. * Returns the index of the median of the three indexed doubles.
  881. */
  882. private static int med3(double x[], int a, int b, int c) {
  883. return (x[a] < x[b] ?
  884. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  885. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  886. }
  887. /**
  888. * Sorts the specified sub-array of floats into ascending order.
  889. */
  890. private static void sort1(float x[], int off, int len) {
  891. // Insertion sort on smallest arrays
  892. if (len < 7) {
  893. for (int i=off; i<len+off; i++)
  894. for (int j=i; j>off && x[j-1]>x[j]; j--)
  895. swap(x, j, j-1);
  896. return;
  897. }
  898. // Choose a partition element, v
  899. int m = off + (len >> 1); // Small arrays, middle element
  900. if (len > 7) {
  901. int l = off;
  902. int n = off + len - 1;
  903. if (len > 40) { // Big arrays, pseudomedian of 9
  904. int s = len8;
  905. l = med3(x, l, l+s, l+2*s);
  906. m = med3(x, m-s, m, m+s);
  907. n = med3(x, n-2*s, n-s, n);
  908. }
  909. m = med3(x, l, m, n); // Mid-size, med of 3
  910. }
  911. float v = x[m];
  912. // Establish Invariant: v* (<v)* (>v)* v*
  913. int a = off, b = a, c = off + len - 1, d = c;
  914. while(true) {
  915. while (b <= c && x[b] <= v) {
  916. if (x[b] == v)
  917. swap(x, a++, b);
  918. b++;
  919. }
  920. while (c >= b && x[c] >= v) {
  921. if (x[c] == v)
  922. swap(x, c, d--);
  923. c--;
  924. }
  925. if (b > c)
  926. break;
  927. swap(x, b++, c--);
  928. }
  929. // Swap partition elements back to middle
  930. int s, n = off + len;
  931. s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
  932. s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
  933. // Recursively sort non-partition-elements
  934. if ((s = b-a) > 1)
  935. sort1(x, off, s);
  936. if ((s = d-c) > 1)
  937. sort1(x, n-s, s);
  938. }
  939. /**
  940. * Swaps x[a] with x[b].
  941. */
  942. private static void swap(float x[], int a, int b) {
  943. float t = x[a];
  944. x[a] = x[b];
  945. x[b] = t;
  946. }
  947. /**
  948. * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  949. */
  950. private static void vecswap(float x[], int a, int b, int n) {
  951. for (int i=0; i<n; i++, a++, b++)
  952. swap(x, a, b);
  953. }
  954. /**
  955. * Returns the index of the median of the three indexed floats.
  956. */
  957. private static int med3(float x[], int a, int b, int c) {
  958. return (x[a] < x[b] ?
  959. (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  960. (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  961. }
  962. /**
  963. * Sorts the specified array of objects into ascending order, according to
  964. * the <i>natural ordering</i> of its elements. All elements in the array
  965. * must implement the <tt>Comparable</tt> interface. Furthermore, all
  966. * elements in the array must be <i>mutually comparable</i> (that is,
  967. * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
  968. * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
  969. *
  970. * This sort is guaranteed to be <i>stable</i>: equal elements will
  971. * not be reordered as a result of the sort.<p>
  972. *
  973. * The sorting algorithm is a modified mergesort (in which the merge is
  974. * omitted if the highest element in the low sublist is less than the
  975. * lowest element in the high sublist). This algorithm offers guaranteed
  976. * n*log(n) performance.
  977. *
  978. * @param a the array to be sorted.
  979. * @throws ClassCastException if the array contains elements that are not
  980. * <i>mutually comparable</i> (for example, strings and integers).
  981. * @see Comparable
  982. */
  983. public static void sort(Object[] a) {
  984. Object aux[] = (Object[])a.clone();
  985. mergeSort(aux, a, 0, a.length, 0);
  986. }
  987. /**
  988. * Sorts the specified range of the specified array of objects into
  989. * ascending order, according to the <i>natural ordering</i> of its
  990. * elements. The range to be sorted extends from index
  991. * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
  992. * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All
  993. * elements in this range must implement the <tt>Comparable</tt>
  994. * interface. Furthermore, all elements in this range must be <i>mutually
  995. * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
  996. * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
  997. * <tt>e2</tt> in the array).<p>
  998. *
  999. * This sort is guaranteed to be <i>stable</i>: equal elements will
  1000. * not be reordered as a result of the sort.<p>
  1001. *
  1002. * The sorting algorithm is a modified mergesort (in which the merge is
  1003. * omitted if the highest element in the low sublist is less than the
  1004. * lowest element in the high sublist). This algorithm offers guaranteed
  1005. * n*log(n) performance.
  1006. *
  1007. * @param a the array to be sorted.
  1008. * @param fromIndex the index of the first element (inclusive) to be
  1009. * sorted.
  1010. * @param toIndex the index of the last element (exclusive) to be sorted.
  1011. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1012. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1013. * <tt>toIndex > a.length</tt>
  1014. * @throws ClassCastException if the array contains elements that are
  1015. * not <i>mutually comparable</i> (for example, strings and
  1016. * integers).
  1017. * @see Comparable
  1018. */
  1019. public static void sort(Object[] a, int fromIndex, int toIndex) {
  1020. rangeCheck(a.length, fromIndex, toIndex);
  1021. Object aux[] = (Object[])cloneSubarray(a, fromIndex, toIndex);
  1022. mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
  1023. }
  1024. /**
  1025. * Tuning parameter: list size at or below which insertion sort will be
  1026. * used in preference to mergesort or quicksort.
  1027. */
  1028. private static final int INSERTIONSORT_THRESHOLD = 7;
  1029. /**
  1030. * Clones an array within the specified bounds.
  1031. * This method assumes that a is an array.
  1032. */
  1033. private static Object cloneSubarray(Object[] a, int from, int to) {
  1034. int n = to - from;
  1035. Object result = Array.newInstance(a.getClass().getComponentType(), n);
  1036. System.arraycopy(a, from, result, 0, n);
  1037. return result;
  1038. }
  1039. /**
  1040. * Src is the source array that starts at index 0
  1041. * Dest is the (possibly larger) array destination with a possible offset
  1042. * low is the index in dest to start sorting
  1043. * high is the end index in dest to end sorting
  1044. * off is the offset to generate corresponding low, high in src
  1045. */
  1046. private static void mergeSort(Object src[], Object dest[],
  1047. int low, int high, int off) {
  1048. int length = high - low;
  1049. // Insertion sort on smallest arrays
  1050. if (length < INSERTIONSORT_THRESHOLD) {
  1051. for (int i=low; i<high; i++)
  1052. for (int j=i; j>low &&
  1053. ((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--)
  1054. swap(dest, j, j-1);
  1055. return;
  1056. }
  1057. // Recursively sort halves of dest into src
  1058. int destLow = low;
  1059. int destHigh = high;
  1060. low += off;
  1061. high += off;
  1062. int mid = (low + high) >> 1;
  1063. mergeSort(dest, src, low, mid, -off);
  1064. mergeSort(dest, src, mid, high, -off);
  1065. // If list is already sorted, just copy from src to dest. This is an
  1066. // optimization that results in faster sorts for nearly ordered lists.
  1067. if (((Comparable)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) {
  1068. System.arraycopy(src, low, dest, destLow, length);
  1069. return;
  1070. }
  1071. // Merge sorted halves (now in src) into dest
  1072. for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
  1073. if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
  1074. dest[i] = src[p++];
  1075. else
  1076. dest[i] = src[q++];
  1077. }
  1078. }
  1079. /**
  1080. * Swaps x[a] with x[b].
  1081. */
  1082. private static void swap(Object x[], int a, int b) {
  1083. Object t = x[a];
  1084. x[a] = x[b];
  1085. x[b] = t;
  1086. }
  1087. /**
  1088. * Sorts the specified array of objects according to the order induced by
  1089. * the specified comparator. All elements in the array must be
  1090. * <i>mutually comparable</i> by the specified comparator (that is,
  1091. * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
  1092. * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
  1093. *
  1094. * This sort is guaranteed to be <i>stable</i>: equal elements will
  1095. * not be reordered as a result of the sort.<p>
  1096. *
  1097. * The sorting algorithm is a modified mergesort (in which the merge is
  1098. * omitted if the highest element in the low sublist is less than the
  1099. * lowest element in the high sublist). This algorithm offers guaranteed
  1100. * n*log(n) performance.
  1101. *
  1102. * @param a the array to be sorted.
  1103. * @param c the comparator to determine the order of the array. A
  1104. * <tt>null</tt> value indicates that the elements' <i>natural
  1105. * ordering</i> should be used.
  1106. * @throws ClassCastException if the array contains elements that are
  1107. * not <i>mutually comparable</i> using the specified comparator.
  1108. * @see Comparator
  1109. */
  1110. public static void sort(Object[] a, Comparator c) {
  1111. Object aux[] = (Object[])a.clone();
  1112. if (c==null)
  1113. mergeSort(aux, a, 0, a.length, 0);
  1114. else
  1115. mergeSort(aux, a, 0, a.length, 0, c);
  1116. }
  1117. /**
  1118. * Sorts the specified range of the specified array of objects according
  1119. * to the order induced by the specified comparator. The range to be
  1120. * sorted extends from index <tt>fromIndex</tt>, inclusive, to index
  1121. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1122. * range to be sorted is empty.) All elements in the range must be
  1123. * <i>mutually comparable</i> by the specified comparator (that is,
  1124. * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
  1125. * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
  1126. *
  1127. * This sort is guaranteed to be <i>stable</i>: equal elements will
  1128. * not be reordered as a result of the sort.<p>
  1129. *
  1130. * The sorting algorithm is a modified mergesort (in which the merge is
  1131. * omitted if the highest element in the low sublist is less than the
  1132. * lowest element in the high sublist). This algorithm offers guaranteed
  1133. * n*log(n) performance.
  1134. *
  1135. * @param a the array to be sorted.
  1136. * @param fromIndex the index of the first element (inclusive) to be
  1137. * sorted.
  1138. * @param toIndex the index of the last element (exclusive) to be sorted.
  1139. * @param c the comparator to determine the order of the array. A
  1140. * <tt>null</tt> value indicates that the elements' <i>natural
  1141. * ordering</i> should be used.
  1142. * @throws ClassCastException if the array contains elements that are not
  1143. * <i>mutually comparable</i> using the specified comparator.
  1144. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1145. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1146. * <tt>toIndex > a.length</tt>
  1147. * @see Comparator
  1148. */
  1149. public static void sort(Object[] a, int fromIndex, int toIndex,
  1150. Comparator c) {
  1151. rangeCheck(a.length, fromIndex, toIndex);
  1152. Object aux[] = (Object[])cloneSubarray(a, fromIndex, toIndex);
  1153. if (c==null)
  1154. mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
  1155. else
  1156. mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
  1157. }
  1158. /**
  1159. * Src is the source array that starts at index 0
  1160. * Dest is the (possibly larger) array destination with a possible offset
  1161. * low is the index in dest to start sorting
  1162. * high is the end index in dest to end sorting
  1163. * off is the offset into src corresponding to low in dest
  1164. */
  1165. private static void mergeSort(Object src[], Object dest[],
  1166. int low, int high, int off, Comparator c) {
  1167. int length = high - low;
  1168. // Insertion sort on smallest arrays
  1169. if (length < INSERTIONSORT_THRESHOLD) {
  1170. for (int i=low; i<high; i++)
  1171. for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
  1172. swap(dest, j, j-1);
  1173. return;
  1174. }
  1175. // Recursively sort halves of dest into src
  1176. int destLow = low;
  1177. int destHigh = high;
  1178. low += off;
  1179. high += off;
  1180. int mid = (low + high) >> 1;
  1181. mergeSort(dest, src, low, mid, -off, c);
  1182. mergeSort(dest, src, mid, high, -off, c);
  1183. // If list is already sorted, just copy from src to dest. This is an
  1184. // optimization that results in faster sorts for nearly ordered lists.
  1185. if (c.compare(src[mid-1], src[mid]) <= 0) {
  1186. System.arraycopy(src, low, dest, destLow, length);
  1187. return;
  1188. }
  1189. // Merge sorted halves (now in src) into dest
  1190. for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
  1191. if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
  1192. dest[i] = src[p++];
  1193. else
  1194. dest[i] = src[q++];
  1195. }
  1196. }
  1197. /**
  1198. * Check that fromIndex and toIndex are in range, and throw an
  1199. * appropriate exception if they aren't.
  1200. */
  1201. private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
  1202. if (fromIndex > toIndex)
  1203. throw new IllegalArgumentException("fromIndex(" + fromIndex +
  1204. ") > toIndex(" + toIndex+")");
  1205. if (fromIndex < 0)
  1206. throw new ArrayIndexOutOfBoundsException(fromIndex);
  1207. if (toIndex > arrayLen)
  1208. throw new ArrayIndexOutOfBoundsException(toIndex);
  1209. }
  1210. // Searching
  1211. /**
  1212. * Searches the specified array of longs for the specified value using the
  1213. * binary search algorithm. The array <strong>must</strong> be sorted (as
  1214. * by the <tt>sort</tt> method, above) prior to making this call. If it
  1215. * is not sorted, the results are undefined. If the array contains
  1216. * multiple elements with the specified value, there is no guarantee which
  1217. * one will be found.
  1218. *
  1219. * @param a the array to be searched.
  1220. * @param key the value to be searched for.
  1221. * @return index of the search key, if it is contained in the list;
  1222. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1223. * <i>insertion point</i> is defined as the point at which the
  1224. * key would be inserted into the list: the index of the first
  1225. * element greater than the key, or <tt>list.size()</tt>, if all
  1226. * elements in the list are less than the specified key. Note
  1227. * that this guarantees that the return value will be >= 0 if
  1228. * and only if the key is found.
  1229. * @see #sort(long[])
  1230. */
  1231. public static int binarySearch(long[] a, long key) {
  1232. int low = 0;
  1233. int high = a.length-1;
  1234. while (low <= high) {
  1235. int mid = (low + high) >> 1;
  1236. long midVal = a[mid];
  1237. if (midVal < key)
  1238. low = mid + 1;
  1239. else if (midVal > key)
  1240. high = mid - 1;
  1241. else
  1242. return mid; // key found
  1243. }
  1244. return -(low + 1); // key not found.
  1245. }
  1246. /**
  1247. * Searches the specified array of ints for the specified value using the
  1248. * binary search algorithm. The array <strong>must</strong> be sorted (as
  1249. * by the <tt>sort</tt> method, above) prior to making this call. If it
  1250. * is not sorted, the results are undefined. If the array contains
  1251. * multiple elements with the specified value, there is no guarantee which
  1252. * one will be found.
  1253. *
  1254. * @param a the array to be searched.
  1255. * @param key the value to be searched for.
  1256. * @return index of the search key, if it is contained in the list;
  1257. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1258. * <i>insertion point</i> is defined as the point at which the
  1259. * key would be inserted into the list: the index of the first
  1260. * element greater than the key, or <tt>list.size()</tt>, if all
  1261. * elements in the list are less than the specified key. Note
  1262. * that this guarantees that the return value will be >= 0 if
  1263. * and only if the key is found.
  1264. * @see #sort(int[])
  1265. */
  1266. public static int binarySearch(int[] a, int key) {
  1267. int low = 0;
  1268. int high = a.length-1;
  1269. while (low <= high) {
  1270. int mid = (low + high) >> 1;
  1271. int midVal = a[mid];
  1272. if (midVal < key)
  1273. low = mid + 1;
  1274. else if (midVal > key)
  1275. high = mid - 1;
  1276. else
  1277. return mid; // key found
  1278. }
  1279. return -(low + 1); // key not found.
  1280. }
  1281. /**
  1282. * Searches the specified array of shorts for the specified value using
  1283. * the binary search algorithm. The array <strong>must</strong> be sorted
  1284. * (as by the <tt>sort</tt> method, above) prior to making this call. If
  1285. * it is not sorted, the results are undefined. If the array contains
  1286. * multiple elements with the specified value, there is no guarantee which
  1287. * one will be found.
  1288. *
  1289. * @param a the array to be searched.
  1290. * @param key the value to be searched for.
  1291. * @return index of the search key, if it is contained in the list;
  1292. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1293. * <i>insertion point</i> is defined as the point at which the
  1294. * key would be inserted into the list: the index of the first
  1295. * element greater than the key, or <tt>list.size()</tt>, if all
  1296. * elements in the list are less than the specified key. Note
  1297. * that this guarantees that the return value will be >= 0 if
  1298. * and only if the key is found.
  1299. * @see #sort(short[])
  1300. */
  1301. public static int binarySearch(short[] a, short key) {
  1302. int low = 0;
  1303. int high = a.length-1;
  1304. while (low <= high) {
  1305. int mid = (low + high) >> 1;
  1306. short midVal = a[mid];
  1307. if (midVal < key)
  1308. low = mid + 1;
  1309. else if (midVal > key)
  1310. high = mid - 1;
  1311. else
  1312. return mid; // key found
  1313. }
  1314. return -(low + 1); // key not found.
  1315. }
  1316. /**
  1317. * Searches the specified array of chars for the specified value using the
  1318. * binary search algorithm. The array <strong>must</strong> be sorted (as
  1319. * by the <tt>sort</tt> method, above) prior to making this call. If it
  1320. * is not sorted, the results are undefined. If the array contains
  1321. * multiple elements with the specified value, there is no guarantee which
  1322. * one will be found.
  1323. *
  1324. * @param a the array to be searched.
  1325. * @param key the value to be searched for.
  1326. * @return index of the search key, if it is contained in the list;
  1327. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1328. * <i>insertion point</i> is defined as the point at which the
  1329. * key would be inserted into the list: the index of the first
  1330. * element greater than the key, or <tt>list.size()</tt>, if all
  1331. * elements in the list are less than the specified key. Note
  1332. * that this guarantees that the return value will be >= 0 if
  1333. * and only if the key is found.
  1334. * @see #sort(char[])
  1335. */
  1336. public static int binarySearch(char[] a, char key) {
  1337. int low = 0;
  1338. int high = a.length-1;
  1339. while (low <= high) {
  1340. int mid = (low + high) >> 1;
  1341. char midVal = a[mid];
  1342. if (midVal < key)
  1343. low = mid + 1;
  1344. else if (midVal > key)
  1345. high = mid - 1;
  1346. else
  1347. return mid; // key found
  1348. }
  1349. return -(low + 1); // key not found.
  1350. }
  1351. /**
  1352. * Searches the specified array of bytes for the specified value using the
  1353. * binary search algorithm. The array <strong>must</strong> be sorted (as
  1354. * by the <tt>sort</tt> method, above) prior to making this call. If it
  1355. * is not sorted, the results are undefined. If the array contains
  1356. * multiple elements with the specified value, there is no guarantee which
  1357. * one will be found.
  1358. *
  1359. * @param a the array to be searched.
  1360. * @param key the value to be searched for.
  1361. * @return index of the search key, if it is contained in the list;
  1362. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1363. * <i>insertion point</i> is defined as the point at which the
  1364. * key would be inserted into the list: the index of the first
  1365. * element greater than the key, or <tt>list.size()</tt>, if all
  1366. * elements in the list are less than the specified key. Note
  1367. * that this guarantees that the return value will be >= 0 if
  1368. * and only if the key is found.
  1369. * @see #sort(byte[])
  1370. */
  1371. public static int binarySearch(byte[] a, byte key) {
  1372. int low = 0;
  1373. int high = a.length-1;
  1374. while (low <= high) {
  1375. int mid = (low + high) >> 1;
  1376. byte midVal = a[mid];
  1377. if (midVal < key)
  1378. low = mid + 1;
  1379. else if (midVal > key)
  1380. high = mid - 1;
  1381. else
  1382. return mid; // key found
  1383. }
  1384. return -(low + 1); // key not found.
  1385. }
  1386. /**
  1387. * Searches the specified array of doubles for the specified value using
  1388. * the binary search algorithm. The array <strong>must</strong> be sorted
  1389. * (as by the <tt>sort</tt> method, above) prior to making this call. If
  1390. * it is not sorted, the results are undefined. If the array contains
  1391. * multiple elements with the specified value, there is no guarantee which
  1392. * one will be found. This method considers all NaN values to be
  1393. * equivalent and equal.
  1394. *
  1395. * @param a the array to be searched.
  1396. * @param key the value to be searched for.
  1397. * @return index of the search key, if it is contained in the list;
  1398. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1399. * <i>insertion point</i> is defined as the point at which the
  1400. * key would be inserted into the list: the index of the first
  1401. * element greater than the key, or <tt>list.size()</tt>, if all
  1402. * elements in the list are less than the specified key. Note
  1403. * that this guarantees that the return value will be >= 0 if
  1404. * and only if the key is found.
  1405. * @see #sort(double[])
  1406. */
  1407. public static int binarySearch(double[] a, double key) {
  1408. return binarySearch(a, key, 0, a.length-1);
  1409. }
  1410. private static int binarySearch(double[] a, double key, int low,int high) {
  1411. while (low <= high) {
  1412. int mid = (low + high) >> 1;
  1413. double midVal = a[mid];
  1414. int cmp;
  1415. if (midVal < key) {
  1416. cmp = -1; // Neither val is NaN, thisVal is smaller
  1417. } else if (midVal > key) {
  1418. cmp = 1; // Neither val is NaN, thisVal is larger
  1419. } else {
  1420. long midBits = Double.doubleToLongBits(midVal);
  1421. long keyBits = Double.doubleToLongBits(key);
  1422. cmp = (midBits == keyBits ? 0 : // Values are equal
  1423. (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
  1424. 1)); // (0.0, -0.0) or (NaN, !NaN)
  1425. }
  1426. if (cmp < 0)
  1427. low = mid + 1;
  1428. else if (cmp > 0)
  1429. high = mid - 1;
  1430. else
  1431. return mid; // key found
  1432. }
  1433. return -(low + 1); // key not found.
  1434. }
  1435. /**
  1436. * Searches the specified array of floats for the specified value using
  1437. * the binary search algorithm. The array <strong>must</strong> be sorted
  1438. * (as by the <tt>sort</tt> method, above) prior to making this call. If
  1439. * it is not sorted, the results are undefined. If the array contains
  1440. * multiple elements with the specified value, there is no guarantee which
  1441. * one will be found. This method considers all NaN values to be
  1442. * equivalent and equal.
  1443. *
  1444. * @param a the array to be searched.
  1445. * @param key the value to be searched for.
  1446. * @return index of the search key, if it is contained in the list;
  1447. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1448. * <i>insertion point</i> is defined as the point at which the
  1449. * key would be inserted into the list: the index of the first
  1450. * element greater than the key, or <tt>list.size()</tt>, if all
  1451. * elements in the list are less than the specified key. Note
  1452. * that this guarantees that the return value will be >= 0 if
  1453. * and only if the key is found.
  1454. * @see #sort(float[])
  1455. */
  1456. public static int binarySearch(float[] a, float key) {
  1457. return binarySearch(a, key, 0, a.length-1);
  1458. }
  1459. private static int binarySearch(float[] a, float key, int low,int high) {
  1460. while (low <= high) {
  1461. int mid = (low + high) >> 1;
  1462. float midVal = a[mid];
  1463. int cmp;
  1464. if (midVal < key) {
  1465. cmp = -1; // Neither val is NaN, thisVal is smaller
  1466. } else if (midVal > key) {
  1467. cmp = 1; // Neither val is NaN, thisVal is larger
  1468. } else {
  1469. int midBits = Float.floatToIntBits(midVal);
  1470. int keyBits = Float.floatToIntBits(key);
  1471. cmp = (midBits == keyBits ? 0 : // Values are equal
  1472. (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
  1473. 1)); // (0.0, -0.0) or (NaN, !NaN)
  1474. }
  1475. if (cmp < 0)
  1476. low = mid + 1;
  1477. else if (cmp > 0)
  1478. high = mid - 1;
  1479. else
  1480. return mid; // key found
  1481. }
  1482. return -(low + 1); // key not found.
  1483. }
  1484. /**
  1485. * Searches the specified array for the specified object using the binary
  1486. * search algorithm. The array must be sorted into ascending order
  1487. * according to the <i>natural ordering</i> of its elements (as by
  1488. * <tt>Sort(Object[]</tt>), above) prior to making this call. If it is
  1489. * not sorted, the results are undefined.
  1490. * (If the array contains elements that are not mutually comparable (for
  1491. * example,strings and integers), it <i>cannot</i> be sorted according
  1492. * to the natural order of its elements, hence results are undefined.)
  1493. * If the array contains multiple
  1494. * elements equal to the specified object, there is no guarantee which
  1495. * one will be found.
  1496. *
  1497. * @param a the array to be searched.
  1498. * @param key the value to be searched for.
  1499. * @return index of the search key, if it is contained in the list;
  1500. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1501. * <i>insertion point</i> is defined as the point at which the
  1502. * key would be inserted into the list: the index of the first
  1503. * element greater than the key, or <tt>list.size()</tt>, if all
  1504. * elements in the list are less than the specified key. Note
  1505. * that this guarantees that the return value will be >= 0 if
  1506. * and only if the key is found.
  1507. * @throws ClassCastException if the search key in not comparable to the
  1508. * elements of the array.
  1509. * @see Comparable
  1510. * @see #sort(Object[])
  1511. */
  1512. public static int binarySearch(Object[] a, Object key) {
  1513. int low = 0;
  1514. int high = a.length-1;
  1515. while (low <= high) {
  1516. int mid = (low + high) >> 1;
  1517. Object midVal = a[mid];
  1518. int cmp = ((Comparable)midVal).compareTo(key);
  1519. if (cmp < 0)
  1520. low = mid + 1;
  1521. else if (cmp > 0)
  1522. high = mid - 1;
  1523. else
  1524. return mid; // key found
  1525. }
  1526. return -(low + 1); // key not found.
  1527. }
  1528. /**
  1529. * Searches the specified array for the specified object using the binary
  1530. * search algorithm. The array must be sorted into ascending order
  1531. * according to the specified comparator (as by the <tt>Sort(Object[],
  1532. * Comparator)</tt> method, above), prior to making this call. If it is
  1533. * not sorted, the results are undefined.
  1534. * If the array contains multiple
  1535. * elements equal to the specified object, there is no guarantee which one
  1536. * will be found.
  1537. *
  1538. * @param a the array to be searched.
  1539. * @param key the value to be searched for.
  1540. * @param c the comparator by which the array is ordered. A
  1541. * <tt>null</tt> value indicates that the elements' <i>natural
  1542. * ordering</i> should be used.
  1543. * @return index of the search key, if it is contained in the list;
  1544. * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
  1545. * <i>insertion point</i> is defined as the point at which the
  1546. * key would be inserted into the list: the index of the first
  1547. * element greater than the key, or <tt>list.size()</tt>, if all
  1548. * elements in the list are less than the specified key. Note
  1549. * that this guarantees that the return value will be >= 0 if
  1550. * and only if the key is found.
  1551. * @throws ClassCastException if the array contains elements that are not
  1552. * <i>mutually comparable</i> using the specified comparator,
  1553. * or the search key in not mutually comparable with the
  1554. * elements of the array using this comparator.
  1555. * @see Comparable
  1556. * @see #sort(Object[], Comparator)
  1557. */
  1558. public static int binarySearch(Object[] a, Object key, Comparator c) {
  1559. if (c==null)
  1560. return binarySearch(a, key);
  1561. int low = 0;
  1562. int high = a.length-1;
  1563. while (low <= high) {
  1564. int mid = (low + high) >> 1;
  1565. Object midVal = a[mid];
  1566. int cmp = c.compare(midVal, key);
  1567. if (cmp < 0)
  1568. low = mid + 1;
  1569. else if (cmp > 0)
  1570. high = mid - 1;
  1571. else
  1572. return mid; // key found
  1573. }
  1574. return -(low + 1); // key not found.
  1575. }
  1576. // Equality Testing
  1577. /**
  1578. * Returns <tt>true</tt> if the two specified arrays of longs are
  1579. * <i>equal</i> to one another. Two arrays are considered equal if both
  1580. * arrays contain the same number of elements, and all corresponding pairs
  1581. * of elements in the two arrays are equal. In other words, two arrays
  1582. * are equal if they contain the same elements in the same order. Also,
  1583. * two array references are considered equal if both are <tt>null</tt>.<p>
  1584. *
  1585. * @param a one array to be tested for equality.
  1586. * @param a2 the other array to be tested for equality.
  1587. * @return <tt>true</tt> if the two arrays are equal.
  1588. */
  1589. public static boolean equals(long[] a, long[] a2) {
  1590. if (a==a2)
  1591. return true;
  1592. if (a==null || a2==null)
  1593. return false;
  1594. int length = a.length;
  1595. if (a2.length != length)
  1596. return false;
  1597. for (int i=0; i<length; i++)
  1598. if (a[i] != a2[i])
  1599. return false;
  1600. return true;
  1601. }
  1602. /**
  1603. * Returns <tt>true</tt> if the two specified arrays of ints are
  1604. * <i>equal</i> to one another. Two arrays are considered equal if both
  1605. * arrays contain the same number of elements, and all corresponding pairs
  1606. * of elements in the two arrays are equal. In other words, two arrays
  1607. * are equal if they contain the same elements in the same order. Also,
  1608. * two array references are considered equal if both are <tt>null</tt>.<p>
  1609. *
  1610. * @param a one array to be tested for equality.
  1611. * @param a2 the other array to be tested for equality.
  1612. * @return <tt>true</tt> if the two arrays are equal.
  1613. */
  1614. public static boolean equals(int[] a, int[] a2) {
  1615. if (a==a2)
  1616. return true;
  1617. if (a==null || a2==null)
  1618. return false;
  1619. int length = a.length;
  1620. if (a2.length != length)
  1621. return false;
  1622. for (int i=0; i<length; i++)
  1623. if (a[i] != a2[i])
  1624. return false;
  1625. return true;
  1626. }
  1627. /**
  1628. * Returns <tt>true</tt> if the two specified arrays of shorts are
  1629. * <i>equal</i> to one another. Two arrays are considered equal if both
  1630. * arrays contain the same number of elements, and all corresponding pairs
  1631. * of elements in the two arrays are equal. In other words, two arrays
  1632. * are equal if they contain the same elements in the same order. Also,
  1633. * two array references are considered equal if both are <tt>null</tt>.<p>
  1634. *
  1635. * @param a one array to be tested for equality.
  1636. * @param a2 the other array to be tested for equality.
  1637. * @return <tt>true</tt> if the two arrays are equal.
  1638. */
  1639. public static boolean equals(short[] a, short a2[]) {
  1640. if (a==a2)
  1641. return true;
  1642. if (a==null || a2==null)
  1643. return false;
  1644. int length = a.length;
  1645. if (a2.length != length)
  1646. return false;
  1647. for (int i=0; i<length; i++)
  1648. if (a[i] != a2[i])
  1649. return false;
  1650. return true;
  1651. }
  1652. /**
  1653. * Returns <tt>true</tt> if the two specified arrays of chars are
  1654. * <i>equal</i> to one another. Two arrays are considered equal if both
  1655. * arrays contain the same number of elements, and all corresponding pairs
  1656. * of elements in the two arrays are equal. In other words, two arrays
  1657. * are equal if they contain the same elements in the same order. Also,
  1658. * two array references are considered equal if both are <tt>null</tt>.<p>
  1659. *
  1660. * @param a one array to be tested for equality.
  1661. * @param a2 the other array to be tested for equality.
  1662. * @return <tt>true</tt> if the two arrays are equal.
  1663. */
  1664. public static boolean equals(char[] a, char[] a2) {
  1665. if (a==a2)
  1666. return true;
  1667. if (a==null || a2==null)
  1668. return false;
  1669. int length = a.length;
  1670. if (a2.length != length)
  1671. return false;
  1672. for (int i=0; i<length; i++)
  1673. if (a[i] != a2[i])
  1674. return false;
  1675. return true;
  1676. }
  1677. /**
  1678. * Returns <tt>true</tt> if the two specified arrays of bytes are
  1679. * <i>equal</i> to one another. Two arrays are considered equal if both
  1680. * arrays contain the same number of elements, and all corresponding pairs
  1681. * of elements in the two arrays are equal. In other words, two arrays
  1682. * are equal if they contain the same elements in the same order. Also,
  1683. * two array references are considered equal if both are <tt>null</tt>.<p>
  1684. *
  1685. * @param a one array to be tested for equality.
  1686. * @param a2 the other array to be tested for equality.
  1687. * @return <tt>true</tt> if the two arrays are equal.
  1688. */
  1689. public static boolean equals(byte[] a, byte[] a2) {
  1690. if (a==a2)
  1691. return true;
  1692. if (a==null || a2==null)
  1693. return false;
  1694. int length = a.length;
  1695. if (a2.length != length)
  1696. return false;
  1697. for (int i=0; i<length; i++)
  1698. if (a[i] != a2[i])
  1699. return false;
  1700. return true;
  1701. }
  1702. /**
  1703. * Returns <tt>true</tt> if the two specified arrays of booleans are
  1704. * <i>equal</i> to one another. Two arrays are considered equal if both
  1705. * arrays contain the same number of elements, and all corresponding pairs
  1706. * of elements in the two arrays are equal. In other words, two arrays
  1707. * are equal if they contain the same elements in the same order. Also,
  1708. * two array references are considered equal if both are <tt>null</tt>.<p>
  1709. *
  1710. * @param a one array to be tested for equality.
  1711. * @param a2 the other array to be tested for equality.
  1712. * @return <tt>true</tt> if the two arrays are equal.
  1713. */
  1714. public static boolean equals(boolean[] a, boolean[] a2) {
  1715. if (a==a2)
  1716. return true;
  1717. if (a==null || a2==null)
  1718. return false;
  1719. int length = a.length;
  1720. if (a2.length != length)
  1721. return false;
  1722. for (int i=0; i<length; i++)
  1723. if (a[i] != a2[i])
  1724. return false;
  1725. return true;
  1726. }
  1727. /**
  1728. * Returns <tt>true</tt> if the two specified arrays of doubles are
  1729. * <i>equal</i> to one another. Two arrays are considered equal if both
  1730. * arrays contain the same number of elements, and all corresponding pairs
  1731. * of elements in the two arrays are equal. In other words, two arrays
  1732. * are equal if they contain the same elements in the same order. Also,
  1733. * two array references are considered equal if both are <tt>null</tt>.<p>
  1734. *
  1735. * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
  1736. * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
  1737. * (Unlike the <tt>==</tt> operator, this method considers
  1738. * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
  1739. *
  1740. * @param a one array to be tested for equality.
  1741. * @param a2 the other array to be tested for equality.
  1742. * @return <tt>true</tt> if the two arrays are equal.
  1743. * @see Double#equals(Object)
  1744. */
  1745. public static boolean equals(double[] a, double[] a2) {
  1746. if (a==a2)
  1747. return true;
  1748. if (a==null || a2==null)
  1749. return false;
  1750. int length = a.length;
  1751. if (a2.length != length)
  1752. return false;
  1753. for (int i=0; i<length; i++)
  1754. if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))
  1755. return false;
  1756. return true;
  1757. }
  1758. /**
  1759. * Returns <tt>true</tt> if the two specified arrays of floats are
  1760. * <i>equal</i> to one another. Two arrays are considered equal if both
  1761. * arrays contain the same number of elements, and all corresponding pairs
  1762. * of elements in the two arrays are equal. In other words, two arrays
  1763. * are equal if they contain the same elements in the same order. Also,
  1764. * two array references are considered equal if both are <tt>null</tt>.<p>
  1765. *
  1766. * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
  1767. * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
  1768. * (Unlike the <tt>==</tt> operator, this method considers
  1769. * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
  1770. *
  1771. * @param a one array to be tested for equality.
  1772. * @param a2 the other array to be tested for equality.
  1773. * @return <tt>true</tt> if the two arrays are equal.
  1774. * @see Float#equals(Object)
  1775. */
  1776. public static boolean equals(float[] a, float[] a2) {
  1777. if (a==a2)
  1778. return true;
  1779. if (a==null || a2==null)
  1780. return false;
  1781. int length = a.length;
  1782. if (a2.length != length)
  1783. return false;
  1784. for (int i=0; i<length; i++)
  1785. if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))
  1786. return false;
  1787. return true;
  1788. }
  1789. /**
  1790. * Returns <tt>true</tt> if the two specified arrays of Objects are
  1791. * <i>equal</i> to one another. The two arrays are considered equal if
  1792. * both arrays contain the same number of elements, and all corresponding
  1793. * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
  1794. * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
  1795. * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
  1796. * they contain the same elements in the same order. Also, two array
  1797. * references are considered equal if both are <tt>null</tt>.<p>
  1798. *
  1799. * @param a one array to be tested for equality.
  1800. * @param a2 the other array to be tested for equality.
  1801. * @return <tt>true</tt> if the two arrays are equal.
  1802. */
  1803. public static boolean equals(Object[] a, Object[] a2) {
  1804. if (a==a2)
  1805. return true;
  1806. if (a==null || a2==null)
  1807. return false;
  1808. int length = a.length;
  1809. if (a2.length != length)
  1810. return false;
  1811. for (int i=0; i<length; i++) {
  1812. Object o1 = a[i];
  1813. Object o2 = a2[i];
  1814. if (!(o1==null ? o2==null : o1.equals(o2)))
  1815. return false;
  1816. }
  1817. return true;
  1818. }
  1819. // Filling
  1820. /**
  1821. * Assigns the specified long value to each element of the specified array
  1822. * of longs.
  1823. *
  1824. * @param a the array to be filled.
  1825. * @param val the value to be stored in all elements of the array.
  1826. */
  1827. public static void fill(long[] a, long val) {
  1828. fill(a, 0, a.length, val);
  1829. }
  1830. /**
  1831. * Assigns the specified long value to each element of the specified
  1832. * range of the specified array of longs. The range to be filled
  1833. * extends from index <tt>fromIndex</tt>, inclusive, to index
  1834. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1835. * range to be filled is empty.)
  1836. *
  1837. * @param a the array to be filled.
  1838. * @param fromIndex the index of the first element (inclusive) to be
  1839. * filled with the specified value.
  1840. * @param toIndex the index of the last element (exclusive) to be
  1841. * filled with the specified value.
  1842. * @param val the value to be stored in all elements of the array.
  1843. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1844. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1845. * <tt>toIndex > a.length</tt>
  1846. */
  1847. public static void fill(long[] a, int fromIndex, int toIndex, long val) {
  1848. rangeCheck(a.length, fromIndex, toIndex);
  1849. for (int i=fromIndex; i<toIndex; i++)
  1850. a[i] = val;
  1851. }
  1852. /**
  1853. * Assigns the specified int value to each element of the specified array
  1854. * of ints.
  1855. *
  1856. * @param a the array to be filled.
  1857. * @param val the value to be stored in all elements of the array.
  1858. */
  1859. public static void fill(int[] a, int val) {
  1860. fill(a, 0, a.length, val);
  1861. }
  1862. /**
  1863. * Assigns the specified int value to each element of the specified
  1864. * range of the specified array of ints. The range to be filled
  1865. * extends from index <tt>fromIndex</tt>, inclusive, to index
  1866. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1867. * range to be filled is empty.)
  1868. *
  1869. * @param a the array to be filled.
  1870. * @param fromIndex the index of the first element (inclusive) to be
  1871. * filled with the specified value.
  1872. * @param toIndex the index of the last element (exclusive) to be
  1873. * filled with the specified value.
  1874. * @param val the value to be stored in all elements of the array.
  1875. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1876. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1877. * <tt>toIndex > a.length</tt>
  1878. */
  1879. public static void fill(int[] a, int fromIndex, int toIndex, int val) {
  1880. rangeCheck(a.length, fromIndex, toIndex);
  1881. for (int i=fromIndex; i<toIndex; i++)
  1882. a[i] = val;
  1883. }
  1884. /**
  1885. * Assigns the specified short value to each element of the specified array
  1886. * of shorts.
  1887. *
  1888. * @param a the array to be filled.
  1889. * @param val the value to be stored in all elements of the array.
  1890. */
  1891. public static void fill(short[] a, short val) {
  1892. fill(a, 0, a.length, val);
  1893. }
  1894. /**
  1895. * Assigns the specified short value to each element of the specified
  1896. * range of the specified array of shorts. The range to be filled
  1897. * extends from index <tt>fromIndex</tt>, inclusive, to index
  1898. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1899. * range to be filled is empty.)
  1900. *
  1901. * @param a the array to be filled.
  1902. * @param fromIndex the index of the first element (inclusive) to be
  1903. * filled with the specified value.
  1904. * @param toIndex the index of the last element (exclusive) to be
  1905. * filled with the specified value.
  1906. * @param val the value to be stored in all elements of the array.
  1907. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1908. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1909. * <tt>toIndex > a.length</tt>
  1910. */
  1911. public static void fill(short[] a, int fromIndex, int toIndex, short val) {
  1912. rangeCheck(a.length, fromIndex, toIndex);
  1913. for (int i=fromIndex; i<toIndex; i++)
  1914. a[i] = val;
  1915. }
  1916. /**
  1917. * Assigns the specified char value to each element of the specified array
  1918. * of chars.
  1919. *
  1920. * @param a the array to be filled.
  1921. * @param val the value to be stored in all elements of the array.
  1922. */
  1923. public static void fill(char[] a, char val) {
  1924. fill(a, 0, a.length, val);
  1925. }
  1926. /**
  1927. * Assigns the specified char value to each element of the specified
  1928. * range of the specified array of chars. The range to be filled
  1929. * extends from index <tt>fromIndex</tt>, inclusive, to index
  1930. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1931. * range to be filled is empty.)
  1932. *
  1933. * @param a the array to be filled.
  1934. * @param fromIndex the index of the first element (inclusive) to be
  1935. * filled with the specified value.
  1936. * @param toIndex the index of the last element (exclusive) to be
  1937. * filled with the specified value.
  1938. * @param val the value to be stored in all elements of the array.
  1939. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1940. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1941. * <tt>toIndex > a.length</tt>
  1942. */
  1943. public static void fill(char[] a, int fromIndex, int toIndex, char val) {
  1944. rangeCheck(a.length, fromIndex, toIndex);
  1945. for (int i=fromIndex; i<toIndex; i++)
  1946. a[i] = val;
  1947. }
  1948. /**
  1949. * Assigns the specified byte value to each element of the specified array
  1950. * of bytes.
  1951. *
  1952. * @param a the array to be filled.
  1953. * @param val the value to be stored in all elements of the array.
  1954. */
  1955. public static void fill(byte[] a, byte val) {
  1956. fill(a, 0, a.length, val);
  1957. }
  1958. /**
  1959. * Assigns the specified byte value to each element of the specified
  1960. * range of the specified array of bytes. The range to be filled
  1961. * extends from index <tt>fromIndex</tt>, inclusive, to index
  1962. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1963. * range to be filled is empty.)
  1964. *
  1965. * @param a the array to be filled.
  1966. * @param fromIndex the index of the first element (inclusive) to be
  1967. * filled with the specified value.
  1968. * @param toIndex the index of the last element (exclusive) to be
  1969. * filled with the specified value.
  1970. * @param val the value to be stored in all elements of the array.
  1971. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  1972. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  1973. * <tt>toIndex > a.length</tt>
  1974. */
  1975. public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
  1976. rangeCheck(a.length, fromIndex, toIndex);
  1977. for (int i=fromIndex; i<toIndex; i++)
  1978. a[i] = val;
  1979. }
  1980. /**
  1981. * Assigns the specified boolean value to each element of the specified
  1982. * array of booleans.
  1983. *
  1984. * @param a the array to be filled.
  1985. * @param val the value to be stored in all elements of the array.
  1986. */
  1987. public static void fill(boolean[] a, boolean val) {
  1988. fill(a, 0, a.length, val);
  1989. }
  1990. /**
  1991. * Assigns the specified boolean value to each element of the specified
  1992. * range of the specified array of booleans. The range to be filled
  1993. * extends from index <tt>fromIndex</tt>, inclusive, to index
  1994. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  1995. * range to be filled is empty.)
  1996. *
  1997. * @param a the array to be filled.
  1998. * @param fromIndex the index of the first element (inclusive) to be
  1999. * filled with the specified value.
  2000. * @param toIndex the index of the last element (exclusive) to be
  2001. * filled with the specified value.
  2002. * @param val the value to be stored in all elements of the array.
  2003. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  2004. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  2005. * <tt>toIndex > a.length</tt>
  2006. */
  2007. public static void fill(boolean[] a, int fromIndex, int toIndex,
  2008. boolean val) {
  2009. rangeCheck(a.length, fromIndex, toIndex);
  2010. for (int i=fromIndex; i<toIndex; i++)
  2011. a[i] = val;
  2012. }
  2013. /**
  2014. * Assigns the specified double value to each element of the specified
  2015. * array of doubles.
  2016. *
  2017. * @param a the array to be filled.
  2018. * @param val the value to be stored in all elements of the array.
  2019. */
  2020. public static void fill(double[] a, double val) {
  2021. fill(a, 0, a.length, val);
  2022. }
  2023. /**
  2024. * Assigns the specified double value to each element of the specified
  2025. * range of the specified array of doubles. The range to be filled
  2026. * extends from index <tt>fromIndex</tt>, inclusive, to index
  2027. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  2028. * range to be filled is empty.)
  2029. *
  2030. * @param a the array to be filled.
  2031. * @param fromIndex the index of the first element (inclusive) to be
  2032. * filled with the specified value.
  2033. * @param toIndex the index of the last element (exclusive) to be
  2034. * filled with the specified value.
  2035. * @param val the value to be stored in all elements of the array.
  2036. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  2037. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  2038. * <tt>toIndex > a.length</tt>
  2039. */
  2040. public static void fill(double[] a, int fromIndex, int toIndex,double val){
  2041. rangeCheck(a.length, fromIndex, toIndex);
  2042. for (int i=fromIndex; i<toIndex; i++)
  2043. a[i] = val;
  2044. }
  2045. /**
  2046. * Assigns the specified float value to each element of the specified array
  2047. * of floats.
  2048. *
  2049. * @param a the array to be filled.
  2050. * @param val the value to be stored in all elements of the array.
  2051. */
  2052. public static void fill(float[] a, float val) {
  2053. fill(a, 0, a.length, val);
  2054. }
  2055. /**
  2056. * Assigns the specified float value to each element of the specified
  2057. * range of the specified array of floats. The range to be filled
  2058. * extends from index <tt>fromIndex</tt>, inclusive, to index
  2059. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  2060. * range to be filled is empty.)
  2061. *
  2062. * @param a the array to be filled.
  2063. * @param fromIndex the index of the first element (inclusive) to be
  2064. * filled with the specified value.
  2065. * @param toIndex the index of the last element (exclusive) to be
  2066. * filled with the specified value.
  2067. * @param val the value to be stored in all elements of the array.
  2068. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  2069. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  2070. * <tt>toIndex > a.length</tt>
  2071. */
  2072. public static void fill(float[] a, int fromIndex, int toIndex, float val) {
  2073. rangeCheck(a.length, fromIndex, toIndex);
  2074. for (int i=fromIndex; i<toIndex; i++)
  2075. a[i] = val;
  2076. }
  2077. /**
  2078. * Assigns the specified Object reference to each element of the specified
  2079. * array of Objects.
  2080. *
  2081. * @param a the array to be filled.
  2082. * @param val the value to be stored in all elements of the array.
  2083. */
  2084. public static void fill(Object[] a, Object val) {
  2085. fill(a, 0, a.length, val);
  2086. }
  2087. /**
  2088. * Assigns the specified Object reference to each element of the specified
  2089. * range of the specified array of Objects. The range to be filled
  2090. * extends from index <tt>fromIndex</tt>, inclusive, to index
  2091. * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
  2092. * range to be filled is empty.)
  2093. *
  2094. * @param a the array to be filled.
  2095. * @param fromIndex the index of the first element (inclusive) to be
  2096. * filled with the specified value.
  2097. * @param toIndex the index of the last element (exclusive) to be
  2098. * filled with the specified value.
  2099. * @param val the value to be stored in all elements of the array.
  2100. * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
  2101. * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
  2102. * <tt>toIndex > a.length</tt>
  2103. */
  2104. public static void fill(Object[] a, int fromIndex, int toIndex,Object val){
  2105. rangeCheck(a.length, fromIndex, toIndex);
  2106. for (int i=fromIndex; i<toIndex; i++)
  2107. a[i] = val;
  2108. }
  2109. // Misc
  2110. /**
  2111. * Returns a fixed-size list backed by the specified array. (Changes to
  2112. * the returned list "write through" to the array.) This method acts
  2113. * as bridge between array-based and collection-based APIs, in
  2114. * combination with <tt>Collection.toArray</tt>. The returned list is
  2115. * serializable and implements {@link RandomAccess}.
  2116. *
  2117. * @param a the array by which the list will be backed.
  2118. * @return a list view of the specified array.
  2119. * @see Collection#toArray()
  2120. */
  2121. public static List asList(Object[] a) {
  2122. return new ArrayList(a);
  2123. }
  2124. /**
  2125. * @serial include
  2126. */
  2127. private static class ArrayList extends AbstractList
  2128. implements RandomAccess, java.io.Serializable
  2129. {
  2130. private static final long serialVersionUID = -2764017481108945198L;
  2131. private Object[] a;
  2132. ArrayList(Object[] array) {
  2133. if (array==null)
  2134. throw new NullPointerException();
  2135. a = array;
  2136. }
  2137. public int size() {
  2138. return a.length;
  2139. }
  2140. public Object[] toArray() {
  2141. return (Object[]) a.clone();
  2142. }
  2143. public Object get(int index) {
  2144. return a[index];
  2145. }
  2146. public Object set(int index, Object element) {
  2147. Object oldValue = a[index];
  2148. a[index] = element;
  2149. return oldValue;
  2150. }
  2151. public int indexOf(Object o) {
  2152. if (o==null) {
  2153. for (int i=0; i<a.length; i++)
  2154. if (a[i]==null)
  2155. return i;
  2156. } else {
  2157. for (int i=0; i<a.length; i++)
  2158. if (o.equals(a[i]))
  2159. return i;
  2160. }
  2161. return -1;
  2162. }
  2163. public boolean contains(Object o) {
  2164. return indexOf(o) != -1;
  2165. }
  2166. }
  2167. }