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