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