2
* Copyright (C) 2009 The Guava Authors
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
8
* http://www.apache.org/licenses/LICENSE-2.0
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.
17
package com.google.common.collect.testing;
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
import static junit.framework.Assert.fail;
25
import com.google.common.annotations.GwtCompatible;
26
import com.google.common.annotations.GwtIncompatible;
27
import com.google.common.annotations.J2ktIncompatible;
28
import com.google.errorprone.annotations.CanIgnoreReturnValue;
29
import java.io.Serializable;
30
import java.lang.reflect.Method;
31
import java.util.AbstractList;
32
import java.util.ArrayList;
33
import java.util.Arrays;
34
import java.util.Collection;
35
import java.util.Collections;
36
import java.util.Comparator;
37
import java.util.Iterator;
38
import java.util.LinkedHashSet;
40
import java.util.ListIterator;
42
import java.util.Map.Entry;
44
import org.checkerframework.checker.nullness.qual.Nullable;
46
@GwtCompatible(emulated = true)
47
@ElementTypesAreNonnullByDefault
49
// Clone of Objects.equal
50
static boolean equal(@Nullable Object a, @Nullable Object b) {
51
return a == b || (a != null && a.equals(b));
54
// Clone of Lists.newArrayList
55
public static <E extends @Nullable Object> List<E> copyToList(Iterable<? extends E> elements) {
56
List<E> list = new ArrayList<>();
57
addAll(list, elements);
61
public static <E extends @Nullable Object> List<E> copyToList(E[] elements) {
62
return copyToList(Arrays.asList(elements));
65
// Clone of Sets.newLinkedHashSet
66
public static <E extends @Nullable Object> Set<E> copyToSet(Iterable<? extends E> elements) {
67
Set<E> set = new LinkedHashSet<>();
68
addAll(set, elements);
72
public static <E extends @Nullable Object> Set<E> copyToSet(E[] elements) {
73
return copyToSet(Arrays.asList(elements));
76
// Would use Maps.immutableEntry
77
public static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> mapEntry(
79
return Collections.singletonMap(key, value).entrySet().iterator().next();
82
private static boolean isEmpty(Iterable<?> iterable) {
83
return iterable instanceof Collection
84
? ((Collection<?>) iterable).isEmpty()
85
: !iterable.iterator().hasNext();
88
public static void assertEmpty(Iterable<?> iterable) {
89
if (!isEmpty(iterable)) {
90
fail("Not true that " + iterable + " is empty");
94
public static void assertEmpty(Map<?, ?> map) {
96
fail("Not true that " + map + " is empty");
100
public static void assertEqualInOrder(Iterable<?> expected, Iterable<?> actual) {
101
Iterator<?> expectedIter = expected.iterator();
102
Iterator<?> actualIter = actual.iterator();
104
while (expectedIter.hasNext() && actualIter.hasNext()) {
105
if (!equal(expectedIter.next(), actualIter.next())) {
107
"contents were not equal and in the same order: "
115
if (expectedIter.hasNext() || actualIter.hasNext()) {
116
// actual either had too few or too many elements
118
"contents were not equal and in the same order: "
126
public static void assertContentsInOrder(Iterable<?> actual, Object... expected) {
127
assertEqualInOrder(Arrays.asList(expected), actual);
130
public static void assertEqualIgnoringOrder(Iterable<?> expected, Iterable<?> actual) {
131
List<?> exp = copyToList(expected);
132
List<?> act = copyToList(actual);
133
String actString = act.toString();
135
// Of course we could take pains to give the complete description of the
136
// problem on any failure.
139
for (Object object : exp) {
140
if (!act.remove(object)) {
142
"did not contain expected element "
151
assertTrue("unexpected elements: " + act, act.isEmpty());
154
public static void assertContentsAnyOrder(Iterable<?> actual, Object... expected) {
155
assertEqualIgnoringOrder(Arrays.asList(expected), actual);
158
public static void assertContains(Iterable<?> actual, Object expected) {
159
boolean contained = false;
160
if (actual instanceof Collection) {
161
contained = ((Collection<?>) actual).contains(expected);
163
for (Object o : actual) {
164
if (equal(o, expected)) {
172
fail("Not true that " + actual + " contains " + expected);
176
public static void assertContainsAllOf(Iterable<?> actual, Object... expected) {
177
List<Object> expectedList = new ArrayList<>(Arrays.asList(expected));
179
for (Object o : actual) {
180
expectedList.remove(o);
183
if (!expectedList.isEmpty()) {
184
fail("Not true that " + actual + " contains all of " + Arrays.asList(expected));
188
@CanIgnoreReturnValue
189
public static <E extends @Nullable Object> boolean addAll(
190
Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
191
boolean modified = false;
192
for (E e : elementsToAdd) {
193
modified |= addTo.add(e);
198
static <T extends @Nullable Object> Iterable<T> reverse(List<T> list) {
199
return new Iterable<T>() {
201
public Iterator<T> iterator() {
202
ListIterator<T> listIter = list.listIterator(list.size());
203
return new Iterator<T>() {
205
public boolean hasNext() {
206
return listIter.hasPrevious();
211
return listIter.previous();
215
public void remove() {
223
static <T extends @Nullable Object> Iterator<T> cycle(Iterable<T> iterable) {
224
return new Iterator<T>() {
225
Iterator<T> iterator = Collections.<T>emptySet().iterator();
228
public boolean hasNext() {
234
if (!iterator.hasNext()) {
235
iterator = iterable.iterator();
237
return iterator.next();
241
public void remove() {
242
throw new UnsupportedOperationException();
247
static <T extends @Nullable Object> T get(Iterator<T> iterator, int position) {
248
for (int i = 0; i < position; i++) {
251
return iterator.next();
254
private static class EntryComparator<K extends @Nullable Object, V extends @Nullable Object>
255
implements Comparator<Entry<K, V>> {
256
final @Nullable Comparator<? super K> keyComparator;
258
public EntryComparator(@Nullable Comparator<? super K> keyComparator) {
259
this.keyComparator = keyComparator;
263
@SuppressWarnings("unchecked") // no less safe than putting it in the map!
264
public int compare(Entry<K, V> a, Entry<K, V> b) {
265
return (keyComparator == null)
266
? ((Comparable) a.getKey()).compareTo(b.getKey())
267
: keyComparator.compare(a.getKey(), b.getKey());
271
public static <K extends @Nullable Object, V extends @Nullable Object>
272
Comparator<Entry<K, V>> entryComparator(@Nullable Comparator<? super K> keyComparator) {
273
return new EntryComparator<K, V>(keyComparator);
277
* Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
278
* consistently between their order within {@code valuesInExpectedOrder} and the order implied by
279
* the given {@code comparator}.
281
* @see #testComparator(Comparator, List)
283
public static <T extends @Nullable Object> void testComparator(
284
Comparator<? super T> comparator, T... valuesInExpectedOrder) {
285
testComparator(comparator, Arrays.asList(valuesInExpectedOrder));
289
* Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
290
* consistently between their order within {@code valuesInExpectedOrder} and the order implied by
291
* the given {@code comparator}.
293
* <p>In detail, this method asserts
296
* <li><i>reflexivity</i>: {@code comparator.compare(t, t) = 0} for all {@code t} in {@code
297
* valuesInExpectedOrder}; and
298
* <li><i>consistency</i>: {@code comparator.compare(ti, tj) < 0} and {@code
299
* comparator.compare(tj, ti) > 0} for {@code i < j}, where {@code ti =
300
* valuesInExpectedOrder.get(i)} and {@code tj = valuesInExpectedOrder.get(j)}.
303
public static <T extends @Nullable Object> void testComparator(
304
Comparator<? super T> comparator, List<T> valuesInExpectedOrder) {
305
// This does an O(n^2) test of all pairs of values in both orders
306
for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
307
T t = valuesInExpectedOrder.get(i);
309
for (int j = 0; j < i; j++) {
310
T lesser = valuesInExpectedOrder.get(j);
312
comparator + ".compare(" + lesser + ", " + t + ")", comparator.compare(lesser, t) < 0);
315
assertEquals(comparator + ".compare(" + t + ", " + t + ")", 0, comparator.compare(t, t));
317
for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
318
T greater = valuesInExpectedOrder.get(j);
320
comparator + ".compare(" + greater + ", " + t + ")",
321
comparator.compare(greater, t) > 0);
326
@SuppressWarnings({"SelfComparison", "SelfEquals"})
327
public static <T extends Comparable<? super T>> void testCompareToAndEquals(
328
List<T> valuesInExpectedOrder) {
329
// This does an O(n^2) test of all pairs of values in both orders
330
for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
331
T t = valuesInExpectedOrder.get(i);
333
for (int j = 0; j < i; j++) {
334
T lesser = valuesInExpectedOrder.get(j);
335
assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0);
336
assertFalse(lesser.equals(t));
339
assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t));
340
assertTrue(t.equals(t));
342
for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
343
T greater = valuesInExpectedOrder.get(j);
344
assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0);
345
assertFalse(greater.equals(t));
351
* Returns a collection that simulates concurrent modification by having its size method return
352
* incorrect values. This is useful for testing methods that must treat the return value from
353
* size() as a hint only.
355
* @param delta the difference between the true size of the collection and the values returned by
358
public static <T extends @Nullable Object> Collection<T> misleadingSizeCollection(int delta) {
359
// It would be nice to be able to return a real concurrent
360
// collection like ConcurrentLinkedQueue, so that e.g. concurrent
361
// iteration would work, but that would not be GWT-compatible.
362
// We are not "just" inheriting from ArrayList here as this doesn't work for J2kt.
363
return new AbstractList<T>() {
364
ArrayList<T> data = new ArrayList<>();
368
return Math.max(0, data.size() + delta);
372
public T get(int index) {
373
return data.get(index);
377
public T set(int index, T element) {
378
return data.set(index, element);
382
public boolean add(T element) {
383
return data.add(element);
387
public void add(int index, T element) {
388
data.add(index, element);
392
public T remove(int index) {
393
return data.remove(index);
397
public @Nullable Object[] toArray() {
398
return data.toArray();
404
* Returns a "nefarious" map entry with the specified key and value, meaning an entry that is
405
* suitable for testing that map entries cannot be modified via a nefarious implementation of
406
* equals. This is used for testing unmodifiable collections of map entries; for example, it
407
* should not be possible to access the raw (modifiable) map entry via a nefarious equals method.
409
public static <K extends @Nullable Object, V extends @Nullable Object>
410
Entry<K, V> nefariousMapEntry(K key, V value) {
411
return new Entry<K, V>() {
418
public V getValue() {
423
public V setValue(V value) {
424
throw new UnsupportedOperationException();
427
@SuppressWarnings("unchecked")
429
public boolean equals(@Nullable Object o) {
430
if (o instanceof Entry) {
431
Entry<K, V> e = (Entry<K, V>) o;
432
e.setValue(value); // muhahaha!
434
return equal(this.getKey(), e.getKey()) && equal(this.getValue(), e.getValue());
440
public int hashCode() {
443
return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
447
public String toString() {
448
return getKey() + "=" + getValue();
453
static <E extends @Nullable Object> List<E> castOrCopyToList(Iterable<E> iterable) {
454
if (iterable instanceof List) {
455
return (List<E>) iterable;
457
List<E> list = new ArrayList<>();
458
for (E e : iterable) {
464
@SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
465
public static <K extends Comparable, V extends @Nullable Object>
466
Iterable<Entry<K, V>> orderEntriesByKey(List<Entry<K, V>> insertionOrder) {
467
@SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
468
Comparator<? super K> keyComparator = (Comparator<? super K>) Comparable::compareTo;
469
sort(insertionOrder, Helpers.entryComparator(keyComparator));
470
return insertionOrder;
474
* Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around
475
* build-system quirks.
477
private @interface GwtTransient {}
480
* Compares strings in natural order except that null comes immediately before a given value. This
481
* works better than Ordering.natural().nullsFirst() because, if null comes before all other
482
* values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
483
* exercise null handling fail on those subcollections.
485
public abstract static class NullsBefore implements Comparator<@Nullable String>, Serializable {
487
* We don't serialize this class in GWT, so we don't care about whether GWT will serialize this
490
@GwtTransient private final String justAfterNull;
492
protected NullsBefore(String justAfterNull) {
493
if (justAfterNull == null) {
494
throw new NullPointerException();
497
this.justAfterNull = justAfterNull;
501
public int compare(@Nullable String lhs, @Nullable String rhs) {
506
// lhs (null) comes just before justAfterNull.
507
// If rhs is b, lhs comes first.
508
if (rhs.equals(justAfterNull)) {
511
return justAfterNull.compareTo(rhs);
514
// rhs (null) comes just before justAfterNull.
515
// If lhs is b, rhs comes first.
516
if (lhs.equals(justAfterNull)) {
519
return lhs.compareTo(justAfterNull);
521
return lhs.compareTo(rhs);
525
public boolean equals(@Nullable Object obj) {
526
if (obj instanceof NullsBefore) {
527
NullsBefore other = (NullsBefore) obj;
528
return justAfterNull.equals(other.justAfterNull);
534
public int hashCode() {
535
return justAfterNull.hashCode();
539
public static final class NullsBeforeB extends NullsBefore {
540
public static final NullsBeforeB INSTANCE = new NullsBeforeB();
542
private NullsBeforeB() {
547
public static final class NullsBeforeTwo extends NullsBefore {
548
public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
550
private NullsBeforeTwo() {
551
super("two"); // from TestStringSortedMapGenerator's sample keys
556
@GwtIncompatible // reflection
557
public static Method getMethod(Class<?> clazz, String name) {
559
return clazz.getMethod(name);
560
} catch (Exception e) {
561
throw new IllegalArgumentException(e);