View Javadoc
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<>();
173     expectedList.addAll(Arrays.asList(expected));
174 
175     for (Object o : actual) {
176       expectedList.remove(o);
177     }
178 
179     if (!expectedList.isEmpty()) {
180       Assert.fail("Not true that " + actual + " contains all of " + Arrays.asList(expected));
181     }
182   }
183 
184   public static <E> boolean addAll(Collection<E> addTo, Iterable<? extends E> elementsToAdd) {
185     boolean modified = false;
186     for (E e : elementsToAdd) {
187       modified |= addTo.add(e);
188     }
189     return modified;
190   }
191 
192   static <T> Iterable<T> reverse(final List<T> list) {
193     return new Iterable<T>() {
194       @Override
195       public Iterator<T> iterator() {
196         final ListIterator<T> listIter = list.listIterator(list.size());
197         return new Iterator<T>() {
198           @Override
199           public boolean hasNext() {
200             return listIter.hasPrevious();
201           }
202 
203           @Override
204           public T next() {
205             return listIter.previous();
206           }
207 
208           @Override
209           public void remove() {
210             listIter.remove();
211           }
212         };
213       }
214     };
215   }
216 
217   static <T> Iterator<T> cycle(final Iterable<T> iterable) {
218     return new Iterator<T>() {
219       Iterator<T> iterator = Collections.<T>emptySet().iterator();
220 
221       @Override
222       public boolean hasNext() {
223         return true;
224       }
225 
226       @Override
227       public T next() {
228         if (!iterator.hasNext()) {
229           iterator = iterable.iterator();
230         }
231         return iterator.next();
232       }
233 
234       @Override
235       public void remove() {
236         throw new UnsupportedOperationException();
237       }
238     };
239   }
240 
241   static <T> T get(Iterator<T> iterator, int position) {
242     for (int i = 0; i < position; i++) {
243       iterator.next();
244     }
245     return iterator.next();
246   }
247 
248   static void fail(Throwable cause, Object message) {
249     AssertionFailedError assertionFailedError = new AssertionFailedError(String.valueOf(message));
250     assertionFailedError.initCause(cause);
251     throw assertionFailedError;
252   }
253 
254   public static <K, V> Comparator<Entry<K, V>> entryComparator(
255       final Comparator<? super K> keyComparator) {
256     return new Comparator<Entry<K, V>>() {
257       @Override
258       @SuppressWarnings("unchecked") // no less safe than putting it in the map!
259       public int compare(Entry<K, V> a, Entry<K, V> b) {
260         return (keyComparator == null)
261             ? ((Comparable) a.getKey()).compareTo(b.getKey())
262             : keyComparator.compare(a.getKey(), b.getKey());
263       }
264     };
265   }
266 
267   /**
268    * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
269    * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
270    * the given {@code comparator}.
271    *
272    * @see #testComparator(Comparator, List)
273    */
274   public static <T> void testComparator(
275       Comparator<? super T> comparator, T... valuesInExpectedOrder) {
276     testComparator(comparator, Arrays.asList(valuesInExpectedOrder));
277   }
278 
279   /**
280    * Asserts that all pairs of {@code T} values within {@code valuesInExpectedOrder} are ordered
281    * consistently between their order within {@code valuesInExpectedOrder} and the order implied by
282    * the given {@code comparator}.
283    *
284    * <p>In detail, this method asserts
285    *
286    * <ul>
287    *   <li><i>reflexivity</i>: {@code comparator.compare(t, t) = 0} for all {@code t} in {@code
288    *       valuesInExpectedOrder}; and
289    *   <li><i>consistency</i>: {@code comparator.compare(ti, tj) < 0} and {@code
290    *       comparator.compare(tj, ti) > 0} for {@code i < j}, where {@code ti =
291    *       valuesInExpectedOrder.get(i)} and {@code tj = valuesInExpectedOrder.get(j)}.
292    * </ul>
293    */
294   public static <T> void testComparator(
295       Comparator<? super T> comparator, List<T> valuesInExpectedOrder) {
296     // This does an O(n^2) test of all pairs of values in both orders
297     for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
298       T t = valuesInExpectedOrder.get(i);
299 
300       for (int j = 0; j < i; j++) {
301         T lesser = valuesInExpectedOrder.get(j);
302         assertTrue(
303             comparator + ".compare(" + lesser + ", " + t + ")", comparator.compare(lesser, t) < 0);
304       }
305 
306       assertEquals(comparator + ".compare(" + t + ", " + t + ")", 0, comparator.compare(t, t));
307 
308       for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
309         T greater = valuesInExpectedOrder.get(j);
310         assertTrue(
311             comparator + ".compare(" + greater + ", " + t + ")",
312             comparator.compare(greater, t) > 0);
313       }
314     }
315   }
316 
317   @SuppressWarnings({"SelfComparison", "SelfEquals"})
318   public static <T extends Comparable<? super T>> void testCompareToAndEquals(
319       List<T> valuesInExpectedOrder) {
320     // This does an O(n^2) test of all pairs of values in both orders
321     for (int i = 0; i < valuesInExpectedOrder.size(); i++) {
322       T t = valuesInExpectedOrder.get(i);
323 
324       for (int j = 0; j < i; j++) {
325         T lesser = valuesInExpectedOrder.get(j);
326         assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0);
327         assertFalse(lesser.equals(t));
328       }
329 
330       assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t));
331       assertTrue(t.equals(t));
332 
333       for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) {
334         T greater = valuesInExpectedOrder.get(j);
335         assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0);
336         assertFalse(greater.equals(t));
337       }
338     }
339   }
340 
341   /**
342    * Returns a collection that simulates concurrent modification by
343    * having its size method return incorrect values.  This is useful
344    * for testing methods that must treat the return value from size()
345    * as a hint only.
346    *
347    * @param delta the difference between the true size of the
348    * collection and the values returned by the size method
349    */
350   public static <T> Collection<T> misleadingSizeCollection(final int delta) {
351     // It would be nice to be able to return a real concurrent
352     // collection like ConcurrentLinkedQueue, so that e.g. concurrent
353     // iteration would work, but that would not be GWT-compatible.
354     return new ArrayList<T>() {
355       @Override
356       public int size() {
357         return Math.max(0, super.size() + delta);
358       }
359     };
360   }
361 
362   /**
363    * Returns a "nefarious" map entry with the specified key and value,
364    * meaning an entry that is suitable for testing that map entries cannot be
365    * modified via a nefarious implementation of equals. This is used for testing
366    * unmodifiable collections of map entries; for example, it should not be
367    * possible to access the raw (modifiable) map entry via a nefarious equals
368    * method.
369    */
370   public static <K, V> Map.Entry<K, V> nefariousMapEntry(final K key, final V value) {
371     return new Map.Entry<K, V>() {
372       @Override
373       public K getKey() {
374         return key;
375       }
376 
377       @Override
378       public V getValue() {
379         return value;
380       }
381 
382       @Override
383       public V setValue(V value) {
384         throw new UnsupportedOperationException();
385       }
386 
387       @SuppressWarnings("unchecked")
388       @Override
389       public boolean equals(Object o) {
390         if (o instanceof Map.Entry) {
391           Map.Entry<K, V> e = (Map.Entry<K, V>) o;
392           e.setValue(value); // muhahaha!
393 
394           return equal(this.getKey(), e.getKey()) && equal(this.getValue(), e.getValue());
395         }
396         return false;
397       }
398 
399       @Override
400       public int hashCode() {
401         K k = getKey();
402         V v = getValue();
403         return ((k == null) ? 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode());
404       }
405 
406       @Override
407       public String toString() {
408         return getKey() + "=" + getValue();
409       }
410     };
411   }
412 
413   static <E> List<E> castOrCopyToList(Iterable<E> iterable) {
414     if (iterable instanceof List) {
415       return (List<E>) iterable;
416     }
417     List<E> list = new ArrayList<E>();
418     for (E e : iterable) {
419       list.add(e);
420     }
421     return list;
422   }
423 
424   private static final Comparator<Comparable> NATURAL_ORDER =
425       new Comparator<Comparable>() {
426         @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self>
427         @Override
428         public int compare(Comparable left, Comparable right) {
429           return left.compareTo(right);
430         }
431       };
432 
433   public static <K extends Comparable, V> Iterable<Entry<K, V>> orderEntriesByKey(
434       List<Entry<K, V>> insertionOrder) {
435     sort(insertionOrder, Helpers.<K, V>entryComparator(NATURAL_ORDER));
436     return insertionOrder;
437   }
438 
439   /**
440    * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around
441    * build-system quirks.
442    */
443   private @interface GwtTransient {}
444 
445   /**
446    * Compares strings in natural order except that null comes immediately before a given value. This
447    * works better than Ordering.natural().nullsFirst() because, if null comes before all other
448    * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that
449    * exercise null handling fail on those subcollections.
450    */
451   public abstract static class NullsBefore implements Comparator<String>, Serializable {
452     /*
453      * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this
454      * field.
455      */
456     @GwtTransient private final String justAfterNull;
457 
458     protected NullsBefore(String justAfterNull) {
459       if (justAfterNull == null) {
460         throw new NullPointerException();
461       }
462 
463       this.justAfterNull = justAfterNull;
464     }
465 
466     @Override
467     public int compare(String lhs, String rhs) {
468       if (lhs == rhs) {
469         return 0;
470       }
471       if (lhs == null) {
472         // lhs (null) comes just before justAfterNull.
473         // If rhs is b, lhs comes first.
474         if (rhs.equals(justAfterNull)) {
475           return -1;
476         }
477         return justAfterNull.compareTo(rhs);
478       }
479       if (rhs == null) {
480         // rhs (null) comes just before justAfterNull.
481         // If lhs is b, rhs comes first.
482         if (lhs.equals(justAfterNull)) {
483           return 1;
484         }
485         return lhs.compareTo(justAfterNull);
486       }
487       return lhs.compareTo(rhs);
488     }
489 
490     @Override
491     public boolean equals(Object obj) {
492       if (obj instanceof NullsBefore) {
493         NullsBefore other = (NullsBefore) obj;
494         return justAfterNull.equals(other.justAfterNull);
495       }
496       return false;
497     }
498 
499     @Override
500     public int hashCode() {
501       return justAfterNull.hashCode();
502     }
503   }
504 
505   public static final class NullsBeforeB extends NullsBefore {
506     public static final NullsBeforeB INSTANCE = new NullsBeforeB();
507 
508     private NullsBeforeB() {
509       super("b");
510     }
511   }
512 
513   public static final class NullsBeforeTwo extends NullsBefore {
514     public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo();
515 
516     private NullsBeforeTwo() {
517       super("two"); // from TestStringSortedMapGenerator's sample keys
518     }
519   }
520 
521   @GwtIncompatible // reflection
522   public static Method getMethod(Class<?> clazz, String name) {
523     try {
524       return clazz.getMethod(name);
525     } catch (Exception e) {
526       throw new IllegalArgumentException(e);
527     }
528   }
529 }