001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package com.google.gwt.emultest.java.util;
017:
018: import java.util.Arrays;
019: import java.util.Comparator;
020: import java.util.List;
021:
022: /**
023: * Tests {@link Arrays}.
024: */
025: public class ArraysTest extends EmulTestBase {
026: /**
027: * Helper class to use in sorted objects test.
028: */
029: private static class TestObject {
030: private static int count = 0;
031: private int value;
032: private int index;
033:
034: public TestObject(int value) {
035: this .value = value;
036: index = count++;
037: }
038:
039: public int getIndex() {
040: return index;
041: }
042:
043: public int getValue() {
044: return value;
045: }
046:
047: public void setIndex(int val) {
048: index = val;
049: }
050:
051: public String toString() {
052: return value + "@" + index;
053: }
054: }
055:
056: public String getModuleName() {
057: return "com.google.gwt.emultest.EmulSuite";
058: }
059:
060: /**
061: * Tests {@link Arrays#asList(Object[])}.
062: */
063: public void testAsList() {
064: // 0
065: Object[] test = {};
066: List result = Arrays.asList(test);
067: assertEquals(test, result);
068: // n
069: Object[] test2 = { new Integer(0), new Integer(1),
070: new Integer(2) };
071: List result2 = Arrays.asList(test2);
072: assertEquals(test2, result2);
073: // 1
074: Object[] test3 = { "Hello" };
075: List result3 = Arrays.asList(test3);
076: assertEquals(test3, result3);
077: }
078:
079: /**
080: * Test Arrays.binarySearch(byte[], byte).
081: *
082: * <pre>
083: * Verify the following cases:
084: * empty array
085: * odd numbers of elements
086: * even numbers of elements
087: * not found value larger than all elements
088: * not found value smaller than all elements
089: * negative values
090: * </pre>
091: */
092: public void testBinarySearchByte() {
093: byte[] a1 = {};
094: int ret = Arrays.binarySearch(a1, (byte) 0);
095: assertEquals(-1, ret);
096: byte[] a2 = { 1, 7, 31 };
097: ret = Arrays.binarySearch(a2, (byte) 3);
098: assertEquals(-2, ret);
099: ret = Arrays.binarySearch(a2, (byte) 31);
100: assertEquals(2, ret);
101: byte[] a3 = { -71, 0, 35, 36 };
102: ret = Arrays.binarySearch(a3, (byte) 42);
103: assertEquals(-5, ret);
104: ret = Arrays.binarySearch(a3, (byte) -80);
105: assertEquals(-1, ret);
106: ret = Arrays.binarySearch(a3, (byte) -71);
107: assertEquals(0, ret);
108: }
109:
110: /**
111: * Test Arrays.binarySearch(char[], char).
112: *
113: * <pre>
114: * Verify the following cases:
115: * empty array
116: * odd numbers of elements
117: * even numbers of elements
118: * not found value larger than all elements
119: * not found value smaller than all elements
120: * </pre>
121: */
122: public void testBinarySearchChar() {
123: char[] a1 = {};
124: int ret = Arrays.binarySearch(a1, (char) 0);
125: assertEquals(-1, ret);
126: char[] a2 = { 1, 7, 31 };
127: ret = Arrays.binarySearch(a2, (char) 3);
128: assertEquals(-2, ret);
129: ret = Arrays.binarySearch(a2, (char) 31);
130: assertEquals(2, ret);
131: char[] a3 = { 1, 2, 35, 36 };
132: ret = Arrays.binarySearch(a3, (char) 42);
133: assertEquals(-5, ret);
134: ret = Arrays.binarySearch(a3, (char) 0);
135: assertEquals(-1, ret);
136: ret = Arrays.binarySearch(a3, (char) 1);
137: assertEquals(0, ret);
138: }
139:
140: /**
141: * Test Arrays.binarySearch(double[], double).
142: *
143: * <pre>
144: * Verify the following cases:
145: * empty array
146: * odd numbers of elements
147: * even numbers of elements
148: * not found value larger than all elements
149: * not found value smaller than all elements
150: * negative values
151: * </pre>
152: */
153: public void testBinarySearchDouble() {
154: double[] a1 = {};
155: int ret = Arrays.binarySearch(a1, 0);
156: assertEquals(-1, ret);
157: double[] a2 = { 1, 7, 31 };
158: ret = Arrays.binarySearch(a2, 3);
159: assertEquals(-2, ret);
160: ret = Arrays.binarySearch(a2, 31);
161: assertEquals(2, ret);
162: double[] a3 = { -71, 0, 35, 36 };
163: ret = Arrays.binarySearch(a3, 42);
164: assertEquals(-5, ret);
165: ret = Arrays.binarySearch(a3, -80);
166: assertEquals(-1, ret);
167: ret = Arrays.binarySearch(a3, -71);
168: assertEquals(0, ret);
169: }
170:
171: /**
172: * Test Arrays.binarySearch(float[], float).
173: *
174: * <pre>
175: * Verify the following cases:
176: * empty array
177: * odd numbers of elements
178: * even numbers of elements
179: * not found value larger than all elements
180: * not found value smaller than all elements
181: * negative values
182: * </pre>
183: */
184: public void testBinarySearchFloat() {
185: float[] a1 = {};
186: int ret = Arrays.binarySearch(a1, 0);
187: assertEquals(-1, ret);
188: float[] a2 = { 1, 7, 31 };
189: ret = Arrays.binarySearch(a2, 3);
190: assertEquals(-2, ret);
191: ret = Arrays.binarySearch(a2, 31);
192: assertEquals(2, ret);
193: float[] a3 = { -71, 0, 35, 36 };
194: ret = Arrays.binarySearch(a3, 42);
195: assertEquals(-5, ret);
196: ret = Arrays.binarySearch(a3, -80);
197: assertEquals(-1, ret);
198: ret = Arrays.binarySearch(a3, -71);
199: assertEquals(0, ret);
200: }
201:
202: /**
203: * Test Arrays.binarySearch(int[], int).
204: *
205: * <pre>
206: * Verify the following cases:
207: * empty array
208: * odd numbers of elements
209: * even numbers of elements
210: * not found value larger than all elements
211: * not found value smaller than all elements
212: * negative values
213: * </pre>
214: */
215: public void testBinarySearchInt() {
216: int[] a1 = {};
217: int ret = Arrays.binarySearch(a1, 0);
218: assertEquals(-1, ret);
219: int[] a2 = { 1, 7, 31 };
220: ret = Arrays.binarySearch(a2, 3);
221: assertEquals(-2, ret);
222: ret = Arrays.binarySearch(a2, 31);
223: assertEquals(2, ret);
224: int[] a3 = { -71, 0, 35, 36 };
225: ret = Arrays.binarySearch(a3, 42);
226: assertEquals(-5, ret);
227: ret = Arrays.binarySearch(a3, -80);
228: assertEquals(-1, ret);
229: ret = Arrays.binarySearch(a3, -71);
230: assertEquals(0, ret);
231: }
232:
233: /**
234: * Test Arrays.binarySearch(long[], long).
235: *
236: * <pre>
237: * Verify the following cases:
238: * empty array
239: * odd numbers of elements
240: * even numbers of elements
241: * not found value larger than all elements
242: * not found value smaller than all elements
243: * negative values
244: * </pre>
245: */
246: public void testBinarySearchLong() {
247: long[] a1 = {};
248: int ret = Arrays.binarySearch(a1, 0L);
249: assertEquals(-1, ret);
250: long[] a2 = { 1, 7, 31 };
251: ret = Arrays.binarySearch(a2, 3L);
252: assertEquals(-2, ret);
253: ret = Arrays.binarySearch(a2, 31L);
254: assertEquals(2, ret);
255: long[] a3 = { -71, 0, 35, 36 };
256: ret = Arrays.binarySearch(a3, 42L);
257: assertEquals(-5, ret);
258: ret = Arrays.binarySearch(a3, -80L);
259: assertEquals(-1, ret);
260: ret = Arrays.binarySearch(a3, -71L);
261: assertEquals(0, ret);
262: }
263:
264: /**
265: * Test Arrays.binarySearch(Object[], Object).
266: *
267: * <pre>
268: * Verify the following cases:
269: * empty array
270: * odd numbers of elements
271: * even numbers of elements
272: * not found value larger than all elements
273: * not found value smaller than all elements
274: * </pre>
275: */
276: public void testBinarySearchObject() {
277: Object[] a1 = {};
278: int ret = Arrays.binarySearch(a1, "");
279: assertEquals(-1, ret);
280: Object[] a2 = { "a", "g", "y" };
281: ret = Arrays.binarySearch(a2, "c");
282: assertEquals(-2, ret);
283: ret = Arrays.binarySearch(a2, "y");
284: assertEquals(2, ret);
285: Object[] a3 = { "b", "c", "x", "y" };
286: ret = Arrays.binarySearch(a3, "z");
287: assertEquals(-5, ret);
288: ret = Arrays.binarySearch(a3, "a");
289: assertEquals(-1, ret);
290: ret = Arrays.binarySearch(a3, "b");
291: assertEquals(0, ret);
292: }
293:
294: /**
295: * Test Arrays.binarySearch(Object[], Object, Comparator).
296: *
297: * <pre>
298: * Verify the following cases:
299: * empty array
300: * odd numbers of elements
301: * even numbers of elements
302: * not found value larger than all elements
303: * not found value smaller than all elements
304: * Comparator uses natural ordering as a default
305: * </pre>
306: */
307: public void testBinarySearchObjectComparator() {
308: Comparator inverseSort = new Comparator() {
309: public int compare(Object o1, Object o2) {
310: return ((Comparable) o2).compareTo(o1);
311: }
312: };
313: Object[] a1 = {};
314: int ret = Arrays.binarySearch(a1, "", inverseSort);
315: assertEquals(-1, ret);
316: Object[] a2 = { "y", "g", "a" };
317: ret = Arrays.binarySearch(a2, "c", inverseSort);
318: assertEquals(-3, ret);
319: ret = Arrays.binarySearch(a2, "a", inverseSort);
320: assertEquals(2, ret);
321: Object[] a3 = { "y", "x", "c", "b" };
322: ret = Arrays.binarySearch(a3, "a", inverseSort);
323: assertEquals(-5, ret);
324: ret = Arrays.binarySearch(a3, "z", inverseSort);
325: assertEquals(-1, ret);
326: ret = Arrays.binarySearch(a3, "y", inverseSort);
327: assertEquals(0, ret);
328:
329: Object[] a4 = { "a", "b", "c", "d", "e" };
330: ret = Arrays.binarySearch(a4, "d", null); // should not NPE
331: assertEquals(3, ret);
332: }
333:
334: /**
335: * Test Arrays.binarySearch(short[], short).
336: *
337: * <pre>
338: * Verify the following cases:
339: * empty array
340: * odd numbers of elements
341: * even numbers of elements
342: * not found value larger than all elements
343: * not found value smaller than all elements
344: * negative values
345: * </pre>
346: */
347: public void testBinarySearchShort() {
348: short[] a1 = {};
349: int ret = Arrays.binarySearch(a1, (short) 0);
350: assertEquals(-1, ret);
351: short[] a2 = { 1, 7, 31 };
352: ret = Arrays.binarySearch(a2, (short) 3);
353: assertEquals(-2, ret);
354: ret = Arrays.binarySearch(a2, (short) 31);
355: assertEquals(2, ret);
356: short[] a3 = { -71, 0, 35, 36 };
357: ret = Arrays.binarySearch(a3, (short) 42);
358: assertEquals(-5, ret);
359: ret = Arrays.binarySearch(a3, (short) -80);
360: assertEquals(-1, ret);
361: ret = Arrays.binarySearch(a3, (short) -71);
362: assertEquals(0, ret);
363: }
364:
365: /**
366: * Verifies that values are sorted numerically rather than as strings.
367: */
368: public void testNumericSort() {
369: Integer[] x = new Integer[] { new Integer(3), new Integer(11),
370: new Integer(2), new Integer(1) };
371: Arrays.sort(x);
372: assertEquals(2, x[1].intValue());
373: assertEquals(11, x[3].intValue());
374: }
375:
376: /**
377: * Tests sorting primitives.
378: */
379: public void testPrimitiveSort() {
380: int[] x = new int[] { 3, 11, 2, 1, 22, 3 };
381: Arrays.sort(x);
382: assertEquals(1, x[0]);
383: assertEquals(2, x[1]);
384: assertEquals(3, x[2]);
385: assertEquals(3, x[3]);
386: assertEquals(11, x[4]);
387: assertEquals(22, x[5]);
388: }
389:
390: /**
391: * Tests sorting a subrange of a primitive array.
392: */
393: public void testPrimitiveSubrangeSort() {
394: int[] x = new int[] { 3, 11, 2, 1, 22, 3 };
395: Arrays.sort(x, 1, 5);
396: assertEquals(3, x[0]);
397: assertEquals(1, x[1]);
398: assertEquals(2, x[2]);
399: assertEquals(11, x[3]);
400: assertEquals(22, x[4]);
401: assertEquals(3, x[5]);
402: }
403:
404: /**
405: * Tests simple use cases for {@link Arrays#sort(Object[])}.
406: */
407: public void testSimpleSort() {
408: // empty array
409: Object[] test = {};
410: Arrays.sort(test);
411: assertEquals(test.length, 0);
412: // array with one element
413: Integer[] test2 = { new Integer(1) };
414: Arrays.sort(test2);
415: assertEquals(1, test2[0].intValue());
416: // multiple elements
417: Number[] test3 = { new Integer(3), new Integer(0),
418: new Integer(2), new Integer(4), new Integer(1) };
419: Arrays.sort(test3);
420: for (int i = 0; i < test3.length; i++) {
421: assertEquals(i, test3[i].intValue());
422: }
423: }
424:
425: /**
426: * Tests {@link Arrays#sort(Object[], Comparator)}.
427: */
428: public void testSort() {
429: Object[] x = { "c", "b", "b", "a" };
430: int hash = x[1].hashCode();
431: Arrays.sort(x);
432: int hash2 = x[1].hashCode();
433: assertEquals(hash, hash2);
434: Object[] sorted = { "a", "b", "b", "c" };
435: assertEquals(x, sorted);
436: Comparator<Object> t = new Comparator<Object>() {
437: public int compare(Object o1, Object o2) {
438: return ((Comparable<Object>) o2).compareTo(o1);
439: }
440: };
441: Arrays.sort(x, t);
442: int hash3 = x[1].hashCode();
443: assertEquals(hash, hash3);
444: Object[] reverseSorted = { "c", "b", "b", "a" };
445: assertEquals(x, reverseSorted);
446: }
447:
448: /**
449: * Verifies that equal values retain their original order. This is done by
450: * trying all possible permutations of a small test array to make sure the
451: * sort algorithm properly handles any ordering.
452: *
453: * The current test is 6 elements, so there are 6! = 720 possible orderings to
454: * test.
455: */
456: public void testStableSort() {
457: TestObject[] origData = new TestObject[] { new TestObject(3),
458: new TestObject(11), new TestObject(2),
459: new TestObject(3), new TestObject(1),
460: new TestObject(3), new TestObject(22) };
461: int[] permutation = new int[origData.length];
462: while (validPermutation(permutation, origData.length)) {
463: TestObject[] permutedArray = getPermutation(origData,
464: permutation);
465: Arrays.sort(permutedArray, new Comparator<TestObject>() {
466: public int compare(TestObject a, TestObject b) {
467: return a.getValue() - b.getValue();
468: }
469: });
470: for (int i = 1; i < permutedArray.length; ++i) {
471: if (permutedArray[i - 1].getValue() > permutedArray[i]
472: .getValue()
473: || (permutedArray[i - 1].getValue() == permutedArray[i]
474: .getValue() && permutedArray[i - 1]
475: .getIndex() > permutedArray[i]
476: .getIndex())) {
477: String msg = "Permutation "
478: + Arrays.toString(permutation) + ": "
479: + Arrays.toString(permutedArray);
480: permutedArray = getPermutation(origData,
481: permutation);
482: msg += " (orig: " + Arrays.toString(permutedArray)
483: + ")";
484: fail(msg);
485: }
486: }
487: nextPermutation(permutation);
488: }
489: }
490:
491: /**
492: * Returns a permuted array given the original array and a permutation. The
493: * permutation is an array of indices which select which possible source goes
494: * into the output slot of the same position. Note that previously used
495: * sources are not counted, so the first permutation of a three-element array
496: * [a,b,c] is [0,0,0], which maps to [a,b,c]. [1,0,0] maps to [b,a,c] since
497: * the range of index[1] is from 0-1 and excludes the value b since it has
498: * already been chosen. The permutation array may be shorter than the source
499: * array, in which case it is choosing any m elements out of n.
500: *
501: * Thus the range of index i is 0 <= permutation[i] < n-i where n is the
502: * number of elements in the source array.
503: *
504: * @param origData original array to permute
505: * @param permutation array of indices, as described above
506: * @return permuted array
507: */
508: private TestObject[] getPermutation(TestObject[] origData,
509: int[] permutation) {
510: TestObject[] array = new TestObject[permutation.length];
511: for (int i = 0; i < permutation.length; ++i) {
512: int idx = permutation[i];
513: // adjust for source elements already used
514: for (int j = i; j-- > 0;) {
515: if (permutation[j] <= idx) {
516: idx++;
517: }
518: }
519: array[i] = origData[idx];
520: // update position in output array for stability test
521: array[i].setIndex(i);
522: }
523: return array;
524: }
525:
526: /**
527: * Advance the permutation to the next value. It leaves the first index set to
528: * -1 if the range has been exceeded.
529: *
530: * @param permutation array of indices -- see {@link getPermutation} for
531: * details.
532: */
533: private void nextPermutation(int[] permutation) {
534: for (int i = 0; i < permutation.length; ++i) {
535: if (++permutation[i] < permutation.length - i) {
536: return;
537: }
538: permutation[i] = 0;
539: }
540: permutation[0] = -1;
541: }
542:
543: /**
544: * Checks to see if this permutation is valid; ie, if all of the indices are
545: * between 0 and n-i (see {@link getPermutation} for details).
546: *
547: * @param permutations array of indices
548: * @param n length of source array.
549: * @return true if the permutation is valid
550: */
551: private boolean validPermutation(int[] permutations, int n) {
552: if (permutations[0] < 0) {
553: return false;
554: }
555: for (int i = 0; i < permutations.length; ++i) {
556: if (permutations[i] >= n - i) {
557: return false;
558: }
559: }
560: return true;
561: }
562:
563: }
|