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 26 import junit.framework.Assert; 27 import junit.framework.AssertionFailedError; 28 29 import java.io.Serializable; 30 import java.util.ArrayList; 31 import java.util.Arrays; 32 import java.util.Collection; 33 import java.util.Collections; 34 import java.util.Comparator; 35 import java.util.Iterator; 36 import java.util.LinkedHashSet; 37 import java.util.List; 38 import java.util.ListIterator; 39 import java.util.Map; 40 import java.util.Map.Entry; 41 import java.util.Set; 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 public static void assertEqualIgnoringOrder( 78 Iterable<?> expected, Iterable<?> actual) { 79 List<?> exp = copyToList(expected); 80 List<?> act = copyToList(actual); 81 String actString = act.toString(); 82 83 // Of course we could take pains to give the complete description of the 84 // problem on any failure. 85 86 // Yeah it's n^2. 87 for (Object object : exp) { 88 if (!act.remove(object)) { 89 Assert.fail("did not contain expected element " + object + ", " 90 + "expected = " + exp + ", actual = " + actString); 91 } 92 } 93 assertTrue("unexpected elements: " + act, act.isEmpty()); 94 } 95 96 public static void assertContentsAnyOrder( 97 Iterable<?> actual, Object... expected) { 98 assertEqualIgnoringOrder(Arrays.asList(expected), actual); 99 } 100 101 public static <E> boolean addAll( 102 Collection<E> addTo, Iterable<? extends E> elementsToAdd) { 103 boolean modified = false; 104 for (E e : elementsToAdd) { 105 modified |= addTo.add(e); 106 } 107 return modified; 108 } 109 110 static <T> Iterable<T> reverse(final List<T> list) { 111 return new Iterable<T>() { 112 @Override 113 public Iterator<T> iterator() { 114 final ListIterator<T> listIter = list.listIterator(list.size()); 115 return new Iterator<T>() { 116 @Override 117 public boolean hasNext() { 118 return listIter.hasPrevious(); 119 } 120 @Override 121 public T next() { 122 return listIter.previous(); 123 } 124 @Override 125 public void remove() { 126 listIter.remove(); 127 } 128 }; 129 } 130 }; 131 } 132 133 static <T> Iterator<T> cycle(final Iterable<T> iterable) { 134 return new Iterator<T>() { 135 Iterator<T> iterator = Collections.<T>emptySet().iterator(); 136 @Override 137 public boolean hasNext() { 138 return true; 139 } 140 @Override 141 public T next() { 142 if (!iterator.hasNext()) { 143 iterator = iterable.iterator(); 144 } 145 return iterator.next(); 146 } 147 @Override 148 public void remove() { 149 throw new UnsupportedOperationException(); 150 } 151 }; 152 } 153 154 static <T> T get(Iterator<T> iterator, int position) { 155 for (int i = 0; i < position; i++) { 156 iterator.next(); 157 } 158 return iterator.next(); 159 } 160 161 static void fail(Throwable cause, Object message) { 162 AssertionFailedError assertionFailedError = 163 new AssertionFailedError(String.valueOf(message)); 164 assertionFailedError.initCause(cause); 165 throw assertionFailedError; 166 } 167 168 public static <K, V> Comparator<Entry<K, V>> entryComparator( 169 final Comparator<? super K> keyComparator) { 170 return new Comparator<Entry<K, V>>() { 171 @Override 172 @SuppressWarnings("unchecked") // no less safe than putting it in the map! 173 public int compare(Entry<K, V> a, Entry<K, V> b) { 174 return (keyComparator == null) 175 ? ((Comparable) a.getKey()).compareTo(b.getKey()) 176 : keyComparator.compare(a.getKey(), b.getKey()); 177 } 178 }; 179 } 180 181 public static <T> void testComparator( 182 Comparator<? super T> comparator, T... valuesInExpectedOrder) { 183 testComparator(comparator, Arrays.asList(valuesInExpectedOrder)); 184 } 185 186 public static <T> void testComparator( 187 Comparator<? super T> comparator, List<T> valuesInExpectedOrder) { 188 // This does an O(n^2) test of all pairs of values in both orders 189 for (int i = 0; i < valuesInExpectedOrder.size(); i++) { 190 T t = valuesInExpectedOrder.get(i); 191 192 for (int j = 0; j < i; j++) { 193 T lesser = valuesInExpectedOrder.get(j); 194 assertTrue(comparator + ".compare(" + lesser + ", " + t + ")", 195 comparator.compare(lesser, t) < 0); 196 } 197 198 assertEquals(comparator + ".compare(" + t + ", " + t + ")", 199 0, comparator.compare(t, t)); 200 201 for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) { 202 T greater = valuesInExpectedOrder.get(j); 203 assertTrue(comparator + ".compare(" + greater + ", " + t + ")", 204 comparator.compare(greater, t) > 0); 205 } 206 } 207 } 208 209 public static <T extends Comparable<? super T>> void testCompareToAndEquals( 210 List<T> valuesInExpectedOrder) { 211 // This does an O(n^2) test of all pairs of values in both orders 212 for (int i = 0; i < valuesInExpectedOrder.size(); i++) { 213 T t = valuesInExpectedOrder.get(i); 214 215 for (int j = 0; j < i; j++) { 216 T lesser = valuesInExpectedOrder.get(j); 217 assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0); 218 assertFalse(lesser.equals(t)); 219 } 220 221 assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t)); 222 assertTrue(t.equals(t)); 223 224 for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) { 225 T greater = valuesInExpectedOrder.get(j); 226 assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0); 227 assertFalse(greater.equals(t)); 228 } 229 } 230 } 231 232 /** 233 * Returns a collection that simulates concurrent modification by 234 * having its size method return incorrect values. This is useful 235 * for testing methods that must treat the return value from size() 236 * as a hint only. 237 * 238 * @param delta the difference between the true size of the 239 * collection and the values returned by the size method 240 */ 241 public static <T> Collection<T> misleadingSizeCollection(final int delta) { 242 // It would be nice to be able to return a real concurrent 243 // collection like ConcurrentLinkedQueue, so that e.g. concurrent 244 // iteration would work, but that would not be GWT-compatible. 245 return new ArrayList<T>() { 246 @Override public int size() { return Math.max(0, super.size() + delta); } 247 }; 248 } 249 250 /** 251 * Returns a "nefarious" map entry with the specified key and value, 252 * meaning an entry that is suitable for testing that map entries cannot be 253 * modified via a nefarious implementation of equals. This is used for testing 254 * unmodifiable collections of map entries; for example, it should not be 255 * possible to access the raw (modifiable) map entry via a nefarious equals 256 * method. 257 */ 258 public static <K, V> Map.Entry<K, V> nefariousMapEntry(final K key, 259 final V value) { 260 return new Map.Entry<K, V>() { 261 @Override public K getKey() { 262 return key; 263 } 264 @Override public V getValue() { 265 return value; 266 } 267 @Override public V setValue(V value) { 268 throw new UnsupportedOperationException(); 269 } 270 @SuppressWarnings("unchecked") 271 @Override public boolean equals(Object o) { 272 if (o instanceof Map.Entry) { 273 Map.Entry<K, V> e = (Map.Entry<K, V>) o; 274 e.setValue(value); // muhahaha! 275 276 return equal(this.getKey(), e.getKey()) 277 && equal(this.getValue(), e.getValue()); 278 } 279 return false; 280 } 281 282 @Override public int hashCode() { 283 K k = getKey(); 284 V v = getValue(); 285 return ((k == null) ? 286 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode()); 287 } 288 289 /** 290 * Returns a string representation of the form <code>{key}={value}</code>. 291 */ 292 @Override public String toString() { 293 return getKey() + "=" + getValue(); 294 } 295 }; 296 } 297 298 static <E> List<E> castOrCopyToList(Iterable<E> iterable) { 299 if (iterable instanceof List) { 300 return (List<E>) iterable; 301 } 302 List<E> list = new ArrayList<E>(); 303 for (E e : iterable) { 304 list.add(e); 305 } 306 return list; 307 } 308 309 private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() { 310 @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self> 311 @Override public int compare(Comparable left, Comparable right) { 312 return left.compareTo(right); 313 } 314 }; 315 316 public static <K extends Comparable, V> Iterable<Entry<K, V>> orderEntriesByKey( 317 List<Entry<K, V>> insertionOrder) { 318 sort(insertionOrder, Helpers.<K, V>entryComparator(NATURAL_ORDER)); 319 return insertionOrder; 320 } 321 322 /** 323 * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around 324 * build-system quirks. 325 */ 326 private @interface GwtTransient {} 327 328 /** 329 * Compares strings in natural order except that null comes immediately before a given value. This 330 * works better than Ordering.natural().nullsFirst() because, if null comes before all other 331 * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that 332 * exercise null handling fail on those subcollections. 333 */ 334 public abstract static class NullsBefore implements Comparator<String>, Serializable { 335 /* 336 * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this 337 * field. 338 */ 339 @GwtTransient private final String justAfterNull; 340 341 protected NullsBefore(String justAfterNull) { 342 if (justAfterNull == null) { 343 throw new NullPointerException(); 344 } 345 346 this.justAfterNull = justAfterNull; 347 } 348 349 @Override 350 public int compare(String lhs, String rhs) { 351 if (lhs == rhs) { 352 return 0; 353 } 354 if (lhs == null) { 355 // lhs (null) comes just before justAfterNull. 356 // If rhs is b, lhs comes first. 357 if (rhs.equals(justAfterNull)) { 358 return -1; 359 } 360 return justAfterNull.compareTo(rhs); 361 } 362 if (rhs == null) { 363 // rhs (null) comes just before justAfterNull. 364 // If lhs is b, rhs comes first. 365 if (lhs.equals(justAfterNull)) { 366 return 1; 367 } 368 return lhs.compareTo(justAfterNull); 369 } 370 return lhs.compareTo(rhs); 371 } 372 373 @Override 374 public boolean equals(Object obj) { 375 if (obj instanceof NullsBefore) { 376 NullsBefore other = (NullsBefore) obj; 377 return justAfterNull.equals(other.justAfterNull); 378 } 379 return false; 380 } 381 382 @Override 383 public int hashCode() { 384 return justAfterNull.hashCode(); 385 } 386 } 387 388 public static final class NullsBeforeB extends NullsBefore { 389 public static final NullsBeforeB INSTANCE = new NullsBeforeB(); 390 391 private NullsBeforeB() { 392 super("b"); 393 } 394 } 395 396 public static final class NullsBeforeTwo extends NullsBefore { 397 public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo(); 398 399 private NullsBeforeTwo() { 400 super("two"); // from TestStringSortedMapGenerator's sample keys 401 } 402 } 403 } 404 405