1 /*
2 * Copyright (C) 2009 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect.testing;
18
19 import static java.util.Collections.sort;
20 import static junit.framework.Assert.assertEquals;
21 import static junit.framework.Assert.assertFalse;
22 import static junit.framework.Assert.assertTrue;
23
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.annotations.GwtIncompatible;
26 import java.io.Serializable;
27 import java.lang.reflect.Method;
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Collection;
31 import java.util.Collections;
32 import java.util.Comparator;
33 import java.util.Iterator;
34 import java.util.LinkedHashSet;
35 import java.util.List;
36 import java.util.ListIterator;
37 import java.util.Map;
38 import java.util.Map.Entry;
39 import java.util.Set;
40 import junit.framework.Assert;
41 import junit.framework.AssertionFailedError;
42
43 @GwtCompatible(emulated = true)
44 public class Helpers {
45 // Clone of Objects.equal
46 static boolean equal(Object a, Object b) {
47 return a == b || (a != null && a.equals(b));
48 }
49
50 // Clone of Lists.newArrayList
51 public static <E> List<E> copyToList(Iterable<? extends E> elements) {
52 List<E> list = new ArrayList<E>();
53 addAll(list, elements);
54 return list;
55 }
56
57 public static <E> List<E> copyToList(E[] elements) {
58 return copyToList(Arrays.asList(elements));
59 }
60
61 // Clone of Sets.newLinkedHashSet
62 public static <E> Set<E> copyToSet(Iterable<? extends E> elements) {
63 Set<E> set = new LinkedHashSet<E>();
64 addAll(set, elements);
65 return set;
66 }
67
68 public static <E> Set<E> copyToSet(E[] elements) {
69 return copyToSet(Arrays.asList(elements));
70 }
71
72 // Would use Maps.immutableEntry
73 public static <K, V> Entry<K, V> mapEntry(K key, V value) {
74 return Collections.singletonMap(key, value).entrySet().iterator().next();
75 }
76
77 private static boolean isEmpty(Iterable<?> iterable) {
78 return iterable instanceof Collection
79 ? ((Collection<?>) iterable).isEmpty()
80 : !iterable.iterator().hasNext();
81 }
82
83 public static void assertEmpty(Iterable<?> iterable) {
84 if (!isEmpty(iterable)) {
85 Assert.fail("Not true that " + iterable + " is empty");
86 }
87 }
88
89 public static void assertEmpty(Map<?, ?> map) {
90 if (!map.isEmpty()) {
91 Assert.fail("Not true that " + map + " is empty");
92 }
93 }
94
95 public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
96 Iterator<?> expectedIter = expected.iterator();
97 Iterator<?> actualIter = actual.iterator();
98
99 while (expectedIter.hasNext() && actualIter.hasNext()) {
100 if (!equal(expectedIter.next(), actualIter.next())) {
101 Assert.fail(
102 "contents were not equal and in the same order: "
103 + "expected = "
104 + expected
105 + ", actual = "
106 + actual);
107 }
108 }
109
110 if (expectedIter.hasNext() || actualIter.hasNext()) {
111 // actual either had too few or too many elements
112 Assert.fail(
113 "contents were not equal and in the same order: "
114 + "expected = "
115 + expected
116 + ", actual = "
117 + actual);
118 }
119 }
120
121 public static void assertContentsInOrder(Iterable<?> actual, Object... expected) {
122 assertEqualInOrder(Arrays.asList(expected), actual);
123 }
124
125 public static void assertEqualIgnoringOrder(Iterable<?> expected, Iterable<?> actual) {
126 List<?> exp = copyToList(expected);
127 List<?> act = copyToList(actual);
128 String actString = act.toString();
129
130 // Of course we could take pains to give the complete description of the
131 // problem on any failure.
132
133 // Yeah it's n^2.
134 for (Object object : exp) {
135 if (!act.remove(object)) {
136 Assert.fail(
137 "did not contain expected element "
138 + object
139 + ", "
140 + "expected = "
141 + exp
142 + ", actual = "
143 + actString);
144 }
145 }
146 assertTrue("unexpected elements: " + act, act.isEmpty());
147 }
148
149 public static void assertContentsAnyOrder(Iterable<?> actual, Object... expected) {
150 assertEqualIgnoringOrder(Arrays.asList(expected), actual);
151 }
152
153 public static void assertContains(Iterable<?> actual, Object expected) {
154 boolean contained = false;
155 if (actual instanceof Collection) {
156 contained = ((Collection<?>) actual).contains(expected);
157 } else {
158 for (Object o : actual) {
159 if (equal(o, expected)) {
160 contained = true;
161 break;
162 }
163 }
164 }
165
166 if (!contained) {
167 Assert.fail("Not true that " + actual + " contains " + expected);
168 }
169 }
170
171 public static void assertContainsAllOf(Iterable<?> actual, Object... expected) {
172 List<Object> expectedList = new ArrayList<>(Arrays.asList(expected));
173
174 for (Object o : actual) {
175 expectedList.remove(o);
176 }
177
178 if (!expectedList.isEmpty()) {
179 Assert.fail("Not true that " + actual + " contains all of " + Arrays.asList(expected));
180 }
181 }
182
183 public static <E> boolean addAll(Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
184 boolean modified = false;
185 for (E e : elementsToAdd) {
186 modified |= addTo.add(e);
187 }
188 return modified;
189 }
190
191 static <T> Iterable<T> reverse(final List<T> list) {
192 return new Iterable<T>() {
193 @Override
194 public Iterator<T> iterator() {
195 final ListIterator<T> listIter = list.listIterator(list.size());
196 return new Iterator<T>() {
197 @Override
198 public boolean hasNext() {
199 return listIter.hasPrevious();
200 }
201
202 @Override
203 public T next() {
204 return listIter.previous();
205 }
206
207 @Override
208 public void remove() {
209 listIter.remove();
210 }
211 };
212 }
213 };
214 }
215
216 static <T> Iterator<T> cycle(final Iterable<T> iterable) {
217 return new Iterator<T>() {
218 Iterator<T> iterator = Collections.<T>emptySet().iterator();
219
220 @Override
221 public boolean hasNext() {
222 return true;
223 }
224
225 @Override
226 public T next() {
227 if (!iterator.hasNext()) {
228 iterator = iterable.iterator();
229 }
230 return iterator.next();
231 }
232
233 @Override
234 public void remove() {
235 throw new UnsupportedOperationException();
236 }
237 };
238 }
239
240 static <T> T get(Iterator<T> iterator, int position) {
241 for (int i = 0; i < position; i++) {
242 iterator.next();
243 }
244 return iterator.next();
245 }
246
247 static void fail(Throwable cause, Object message) {
248 AssertionFailedError assertionFailedError = new AssertionFailedError(String.valueOf(message));
249 assertionFailedError.initCause(cause);
250 throw assertionFailedError;
251 }
252
253 public static <K, V> Comparator<Entry<K, V>> entryComparator(
254 final Comparator<? super K> keyComparator) {
255 return new Comparator<Entry<K, V>>() {
256 @Override
257 @SuppressWarnings("unchecked") // no less safe than putting it in the map!
258 public int compare(Entry<K, V> a, Entry<K, V> b) {
259 return (keyComparator == null)
260 ? ((Comparable) a.getKey()).compareTo(b.getKey())
261 : keyComparator.compare(a.getKey(), b.getKey());
262 }
263 };
264 }
265
266 /**
267 * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
268 * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
269 * the given {@code comparator}.
270 *
271 * @see #testComparator(Comparator, List)
272 */
273 public static <T> void testComparator(
274 Comparator<? super T> comparator, T... valuesInExpectedOrder) {
275 testComparator(comparator, Arrays.asList(valuesInExpectedOrder));
276 }
277
278 /**
279 * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
280 * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
281 * the given {@code comparator}.
282 *
283 * <p>In detail, this method asserts
284 *
285 * <ul>
286 * <li><i>reflexivity</i>: {@code comparator.compare(t, t) = 0} for all {@code t} in {@code
287 * valuesInExpectedOrder}; and
288 * <li><i>consistency</i>: {@code comparator.compare(ti, tj) < 0} and {@code
289 * comparator.compare(tj, ti) > 0} for {@code i < j}, where {@code ti =
290 * valuesInExpectedOrder.get(i)} and {@code tj = valuesInExpectedOrder.get(j)}.
291 * </ul>
292 */
293 public static <T> void testComparator(
294 Comparator<? super T> comparator, List<T> valuesInExpectedOrder) {
295 // This does an O(n^2) test of all pairs of values in both orders
296 for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
297 T t = valuesInExpectedOrder.get(i);
298
299 for (int j = 0; j < i; j++) {
300 T lesser = valuesInExpectedOrder.get(j);
301 assertTrue(
302 comparator + ".compare(" + lesser + ", " + t + ")", comparator.compare(lesser, t) < 0);
303 }
304
305 assertEquals(comparator + ".compare(" + t + ", " + t + ")", 0, comparator.compare(t, t));
306
307 for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
308 T greater = valuesInExpectedOrder.get(j);
309 assertTrue(
310 comparator + ".compare(" + greater + ", " + t + ")",
311 comparator.compare(greater, t) > 0);
312 }
313 }
314 }
315
316 @SuppressWarnings({"SelfComparison", "SelfEquals"})
317 public static <T extends Comparable<? super T>> void testCompareToAndEquals(
318 List<T> valuesInExpectedOrder) {
319 // This does an O(n^2) test of all pairs of values in both orders
320 for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
321 T t = valuesInExpectedOrder.get(i);
322
323 for (int j = 0; j < i; j++) {
324 T lesser = valuesInExpectedOrder.get(j);
325 assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0);
326 assertFalse(lesser.equals(t));
327 }
328
329 assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t));
330 assertTrue(t.equals(t));
331
332 for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
333 T greater = valuesInExpectedOrder.get(j);
334 assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0);
335 assertFalse(greater.equals(t));
336 }
337 }
338 }
339
340 /**
341 * Returns a collection that simulates concurrent modification by having its size method return
342 * incorrect values. This is useful for testing methods that must treat the return value from
343 * size() as a hint only.
344 *
345 * @param delta the difference between the true size of the collection and the values returned by
346 * the size method
347 */
348 public static <T> Collection<T> misleadingSizeCollection(final int delta) {
349 // It would be nice to be able to return a real concurrent
350 // collection like ConcurrentLinkedQueue, so that e.g. concurrent
351 // iteration would work, but that would not be GWT-compatible.
352 return new ArrayList<T>() {
353 @Override
354 public int size() {
355 return Math.max(0, super.size() + delta);
356 }
357 };
358 }
359
360 /**
361 * Returns a "nefarious" map entry with the specified key and value, meaning an entry that is
362 * suitable for testing that map entries cannot be modified via a nefarious implementation of
363 * equals. This is used for testing unmodifiable collections of map entries; for example, it
364 * should not be possible to access the raw (modifiable) map entry via a nefarious equals method.
365 */
366 public static <K, V> Entry<K, V> nefariousMapEntry(final K key, final V value) {
367 return new Entry<K, V>() {
368 @Override
369 public K getKey() {
370 return key;
371 }
372
373 @Override
374 public V getValue() {
375 return value;
376 }
377
378 @Override
379 public V setValue(V value) {
380 throw new UnsupportedOperationException();
381 }
382
383 @SuppressWarnings("unchecked")
384 @Override
385 public boolean equals(Object o) {
386 if (o instanceof Entry) {
387 Entry<K, V> e = (Entry<K, V>) o;
388 e.setValue(value); // muhahaha!
389
390 return equal(this.getKey(), e.getKey()) && equal(this.getValue(), e.getValue());
391 }
392 return false;
393 }
394
395 @Override
396 public int hashCode() {
397 K k = getKey();
398 V v = getValue();
399 return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
400 }
401
402 @Override
403 public String toString() {
404 return getKey() + "=" + getValue();
405 }
406 };
407 }
408
409 static <E> List<E> castOrCopyToList(Iterable<E> iterable) {
410 if (iterable instanceof List) {
411 return (List<E>) iterable;
412 }
413 List<E> list = new ArrayList<E>();
414 for (E e : iterable) {
415 list.add(e);
416 }
417 return list;
418 }
419
420 private static final Comparator<Comparable> NATURAL_ORDER =
421 new Comparator<Comparable>() {
422 @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
423 @Override
424 public int compare(Comparable left, Comparable right) {
425 return left.compareTo(right);
426 }
427 };
428
429 public static <K extends Comparable, V> Iterable<Entry<K, V>> orderEntriesByKey(
430 List<Entry<K, V>> insertionOrder) {
431 sort(insertionOrder, Helpers.<K, V>entryComparator(NATURAL_ORDER));
432 return insertionOrder;
433 }
434
435 /**
436 * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around
437 * build-system quirks.
438 */
439 private @interface GwtTransient {}
440
441 /**
442 * Compares strings in natural order except that null comes immediately before a given value. This
443 * works better than Ordering.natural().nullsFirst() because, if null comes before all other
444 * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
445 * exercise null handling fail on those subcollections.
446 */
447 public abstract static class NullsBefore implements Comparator<String>, Serializable {
448 /*
449 * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this
450 * field.
451 */
452 @GwtTransient private final String justAfterNull;
453
454 protected NullsBefore(String justAfterNull) {
455 if (justAfterNull == null) {
456 throw new NullPointerException();
457 }
458
459 this.justAfterNull = justAfterNull;
460 }
461
462 @Override
463 public int compare(String lhs, String rhs) {
464 if (lhs == rhs) {
465 return 0;
466 }
467 if (lhs == null) {
468 // lhs (null) comes just before justAfterNull.
469 // If rhs is b, lhs comes first.
470 if (rhs.equals(justAfterNull)) {
471 return -1;
472 }
473 return justAfterNull.compareTo(rhs);
474 }
475 if (rhs == null) {
476 // rhs (null) comes just before justAfterNull.
477 // If lhs is b, rhs comes first.
478 if (lhs.equals(justAfterNull)) {
479 return 1;
480 }
481 return lhs.compareTo(justAfterNull);
482 }
483 return lhs.compareTo(rhs);
484 }
485
486 @Override
487 public boolean equals(Object obj) {
488 if (obj instanceof NullsBefore) {
489 NullsBefore other = (NullsBefore) obj;
490 return justAfterNull.equals(other.justAfterNull);
491 }
492 return false;
493 }
494
495 @Override
496 public int hashCode() {
497 return justAfterNull.hashCode();
498 }
499 }
500
501 public static final class NullsBeforeB extends NullsBefore {
502 public static final NullsBeforeB INSTANCE = new NullsBeforeB();
503
504 private NullsBeforeB() {
505 super("b");
506 }
507 }
508
509 public static final class NullsBeforeTwo extends NullsBefore {
510 public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
511
512 private NullsBeforeTwo() {
513 super("two"); // from TestStringSortedMapGenerator's sample keys
514 }
515 }
516
517 @GwtIncompatible // reflection
518 public static Method getMethod(Class<?> clazz, String name) {
519 try {
520 return clazz.getMethod(name);
521 } catch (Exception e) {
522 throw new IllegalArgumentException(e);
523 }
524 }
525 }