11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2009 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect.testing; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static java.util.Collections.sort; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static junit.framework.Assert.assertEquals; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static junit.framework.Assert.assertFalse; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static junit.framework.Assert.assertTrue; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 247dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.GwtCompatible; 257dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.GwtIncompatible; 267dd252788645e940eada959bdde927426e2531c9Paul Duffin 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport junit.framework.Assert; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport junit.framework.AssertionFailedError; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 307dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.io.Serializable; 317dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.lang.reflect.Method; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.ArrayList; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Arrays; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collection; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.LinkedHashSet; 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.ListIterator; 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map.Entry; 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Set; 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 457dd252788645e940eada959bdde927426e2531c9Paul Duffin@GwtCompatible(emulated = true) 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class Helpers { 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Clone of Objects.equal 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static boolean equal(Object a, Object b) { 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return a == b || (a != null && a.equals(b)); 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Clone of Lists.newArrayList 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> List<E> copyToList(Iterable<? extends E> elements) { 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<E> list = new ArrayList<E>(); 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert addAll(list, elements); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return list; 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> List<E> copyToList(E[] elements) { 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyToList(Arrays.asList(elements)); 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Clone of Sets.newLinkedHashSet 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> Set<E> copyToSet(Iterable<? extends E> elements) { 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<E> set = new LinkedHashSet<E>(); 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert addAll(set, elements); 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return set; 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> Set<E> copyToSet(E[] elements) { 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyToSet(Arrays.asList(elements)); 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Would use Maps.immutableEntry 757dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <K, V> Entry<K, V> mapEntry(K key, V value) { 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Collections.singletonMap(key, value).entrySet().iterator().next(); 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static void assertEqualIgnoringOrder( 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterable<?> expected, Iterable<?> actual) { 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<?> exp = copyToList(expected); 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<?> act = copyToList(actual); 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert String actString = act.toString(); 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Of course we could take pains to give the complete description of the 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // problem on any failure. 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Yeah it's n^2. 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Object object : exp) { 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!act.remove(object)) { 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Assert.fail("did not contain expected element " + object + ", " 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert + "expected = " + exp + ", actual = " + actString); 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("unexpected elements: " + act, act.isEmpty()); 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static void assertContentsAnyOrder( 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterable<?> actual, Object... expected) { 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEqualIgnoringOrder(Arrays.asList(expected), actual); 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> boolean addAll( 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collection<E> addTo, Iterable<? extends E> elementsToAdd) { 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean modified = false; 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (E e : elementsToAdd) { 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert modified |= addTo.add(e); 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return modified; 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <T> Iterable<T> reverse(final List<T> list) { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Iterable<T>() { 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Iterator<T> iterator() { 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ListIterator<T> listIter = list.listIterator(list.size()); 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Iterator<T>() { 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasNext() { 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return listIter.hasPrevious(); 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public T next() { 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return listIter.previous(); 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void remove() { 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert listIter.remove(); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <T> Iterator<T> cycle(final Iterable<T> iterable) { 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Iterator<T>() { 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<T> iterator = Collections.<T>emptySet().iterator(); 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasNext() { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public T next() { 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!iterator.hasNext()) { 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert iterator = iterable.iterator(); 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return iterator.next(); 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void remove() { 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <T> T get(Iterator<T> iterator, int position) { 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < position; i++) { 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert iterator.next(); 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return iterator.next(); 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static void fail(Throwable cause, Object message) { 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AssertionFailedError assertionFailedError = 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new AssertionFailedError(String.valueOf(message)); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertionFailedError.initCause(cause); 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw assertionFailedError; 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <K, V> Comparator<Entry<K, V>> entryComparator( 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Comparator<? super K> keyComparator) { 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Comparator<Entry<K, V>>() { 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1747dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unchecked") // no less safe than putting it in the map! 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int compare(Entry<K, V> a, Entry<K, V> b) { 1767dd252788645e940eada959bdde927426e2531c9Paul Duffin return (keyComparator == null) 1777dd252788645e940eada959bdde927426e2531c9Paul Duffin ? ((Comparable) a.getKey()).compareTo(b.getKey()) 1787dd252788645e940eada959bdde927426e2531c9Paul Duffin : keyComparator.compare(a.getKey(), b.getKey()); 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <T> void testComparator( 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super T> comparator, T... valuesInExpectedOrder) { 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert testComparator(comparator, Arrays.asList(valuesInExpectedOrder)); 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <T> void testComparator( 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super T> comparator, List<T> valuesInExpectedOrder) { 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This does an O(n^2) test of all pairs of values in both orders 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < valuesInExpectedOrder.size(); i++) { 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T t = valuesInExpectedOrder.get(i); 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int j = 0; j < i; j++) { 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T lesser = valuesInExpectedOrder.get(j); 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(comparator + ".compare(" + lesser + ", " + t + ")", 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert comparator.compare(lesser, t) < 0); 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(comparator + ".compare(" + t + ", " + t + ")", 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 0, comparator.compare(t, t)); 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) { 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T greater = valuesInExpectedOrder.get(j); 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(comparator + ".compare(" + greater + ", " + t + ")", 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert comparator.compare(greater, t) > 0); 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <T extends Comparable<? super T>> void testCompareToAndEquals( 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<T> valuesInExpectedOrder) { 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This does an O(n^2) test of all pairs of values in both orders 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < valuesInExpectedOrder.size(); i++) { 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T t = valuesInExpectedOrder.get(i); 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int j = 0; j < i; j++) { 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T lesser = valuesInExpectedOrder.get(j); 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(lesser + ".compareTo(" + t + ')', lesser.compareTo(t) < 0); 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(lesser.equals(t)); 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(t + ".compareTo(" + t + ')', 0, t.compareTo(t)); 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(t.equals(t)); 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int j = i + 1; j < valuesInExpectedOrder.size(); j++) { 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert T greater = valuesInExpectedOrder.get(j); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(greater + ".compareTo(" + t + ')', greater.compareTo(t) > 0); 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(greater.equals(t)); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a collection that simulates concurrent modification by 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * having its size method return incorrect values. This is useful 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * for testing methods that must treat the return value from size() 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as a hint only. 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param delta the difference between the true size of the 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * collection and the values returned by the size method 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <T> Collection<T> misleadingSizeCollection(final int delta) { 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // It would be nice to be able to return a real concurrent 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // collection like ConcurrentLinkedQueue, so that e.g. concurrent 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // iteration would work, but that would not be GWT-compatible. 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ArrayList<T>() { 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int size() { return Math.max(0, super.size() + delta); } 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a "nefarious" map entry with the specified key and value, 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * meaning an entry that is suitable for testing that map entries cannot be 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * modified via a nefarious implementation of equals. This is used for testing 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unmodifiable collections of map entries; for example, it should not be 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * possible to access the raw (modifiable) map entry via a nefarious equals 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * method. 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2607dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <K, V> Map.Entry<K, V> nefariousMapEntry(final K key, 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final V value) { 2627dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Map.Entry<K, V>() { 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public K getKey() { 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return key; 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V getValue() { 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return value; 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V setValue(V value) { 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean equals(Object o) { 2747dd252788645e940eada959bdde927426e2531c9Paul Duffin if (o instanceof Map.Entry) { 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<K, V> e = (Map.Entry<K, V>) o; 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert e.setValue(value); // muhahaha! 2777dd252788645e940eada959bdde927426e2531c9Paul Duffin 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return equal(this.getKey(), e.getKey()) 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert && equal(this.getValue(), e.getValue()); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int hashCode() { 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert K k = getKey(); 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert V v = getValue(); 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k == null) ? 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 0 : k.hashCode()) ^ ((v == null) ? 0 : v.hashCode()); 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a string representation of the form <code>{key}={value}</code>. 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public String toString() { 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return getKey() + "=" + getValue(); 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 2987dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2997dd252788645e940eada959bdde927426e2531c9Paul Duffin 3007dd252788645e940eada959bdde927426e2531c9Paul Duffin static <E> List<E> castOrCopyToList(Iterable<E> iterable) { 3017dd252788645e940eada959bdde927426e2531c9Paul Duffin if (iterable instanceof List) { 3027dd252788645e940eada959bdde927426e2531c9Paul Duffin return (List<E>) iterable; 3037dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3047dd252788645e940eada959bdde927426e2531c9Paul Duffin List<E> list = new ArrayList<E>(); 3057dd252788645e940eada959bdde927426e2531c9Paul Duffin for (E e : iterable) { 3067dd252788645e940eada959bdde927426e2531c9Paul Duffin list.add(e); 3077dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3087dd252788645e940eada959bdde927426e2531c9Paul Duffin return list; 3097dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3107dd252788645e940eada959bdde927426e2531c9Paul Duffin 3117dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() { 3127dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unchecked") // assume any Comparable is Comparable<Self> 3137dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public int compare(Comparable left, Comparable right) { 3147dd252788645e940eada959bdde927426e2531c9Paul Duffin return left.compareTo(right); 3157dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3167dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 3177dd252788645e940eada959bdde927426e2531c9Paul Duffin 3187dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <K extends Comparable, V> Iterable<Entry<K, V>> orderEntriesByKey( 3197dd252788645e940eada959bdde927426e2531c9Paul Duffin List<Entry<K, V>> insertionOrder) { 3207dd252788645e940eada959bdde927426e2531c9Paul Duffin sort(insertionOrder, Helpers.<K, V>entryComparator(NATURAL_ORDER)); 3217dd252788645e940eada959bdde927426e2531c9Paul Duffin return insertionOrder; 3227dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3237dd252788645e940eada959bdde927426e2531c9Paul Duffin 3247dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3257dd252788645e940eada959bdde927426e2531c9Paul Duffin * Private replacement for {@link com.google.gwt.user.client.rpc.GwtTransient} to work around 3267dd252788645e940eada959bdde927426e2531c9Paul Duffin * build-system quirks. 3277dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3287dd252788645e940eada959bdde927426e2531c9Paul Duffin private @interface GwtTransient {} 3297dd252788645e940eada959bdde927426e2531c9Paul Duffin 3307dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3317dd252788645e940eada959bdde927426e2531c9Paul Duffin * Compares strings in natural order except that null comes immediately before a given value. This 3327dd252788645e940eada959bdde927426e2531c9Paul Duffin * works better than Ordering.natural().nullsFirst() because, if null comes before all other 3337dd252788645e940eada959bdde927426e2531c9Paul Duffin * values, it lies outside the submap/submultiset ranges we test, and the variety of tests that 3347dd252788645e940eada959bdde927426e2531c9Paul Duffin * exercise null handling fail on those subcollections. 3357dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3367dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract static class NullsBefore implements Comparator<String>, Serializable { 3377dd252788645e940eada959bdde927426e2531c9Paul Duffin /* 3387dd252788645e940eada959bdde927426e2531c9Paul Duffin * We don't serialize this class in GWT, so we don't care about whether GWT will serialize this 3397dd252788645e940eada959bdde927426e2531c9Paul Duffin * field. 3407dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3417dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtTransient private final String justAfterNull; 3427dd252788645e940eada959bdde927426e2531c9Paul Duffin 3437dd252788645e940eada959bdde927426e2531c9Paul Duffin protected NullsBefore(String justAfterNull) { 3447dd252788645e940eada959bdde927426e2531c9Paul Duffin if (justAfterNull == null) { 3457dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new NullPointerException(); 3467dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin 3487dd252788645e940eada959bdde927426e2531c9Paul Duffin this.justAfterNull = justAfterNull; 3497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3507dd252788645e940eada959bdde927426e2531c9Paul Duffin 3517dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3527dd252788645e940eada959bdde927426e2531c9Paul Duffin public int compare(String lhs, String rhs) { 3537dd252788645e940eada959bdde927426e2531c9Paul Duffin if (lhs == rhs) { 3547dd252788645e940eada959bdde927426e2531c9Paul Duffin return 0; 3557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3567dd252788645e940eada959bdde927426e2531c9Paul Duffin if (lhs == null) { 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin // lhs (null) comes just before justAfterNull. 3587dd252788645e940eada959bdde927426e2531c9Paul Duffin // If rhs is b, lhs comes first. 3597dd252788645e940eada959bdde927426e2531c9Paul Duffin if (rhs.equals(justAfterNull)) { 3607dd252788645e940eada959bdde927426e2531c9Paul Duffin return -1; 3617dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3627dd252788645e940eada959bdde927426e2531c9Paul Duffin return justAfterNull.compareTo(rhs); 3637dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3647dd252788645e940eada959bdde927426e2531c9Paul Duffin if (rhs == null) { 3657dd252788645e940eada959bdde927426e2531c9Paul Duffin // rhs (null) comes just before justAfterNull. 3667dd252788645e940eada959bdde927426e2531c9Paul Duffin // If lhs is b, rhs comes first. 3677dd252788645e940eada959bdde927426e2531c9Paul Duffin if (lhs.equals(justAfterNull)) { 3687dd252788645e940eada959bdde927426e2531c9Paul Duffin return 1; 3697dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3707dd252788645e940eada959bdde927426e2531c9Paul Duffin return lhs.compareTo(justAfterNull); 3717dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3727dd252788645e940eada959bdde927426e2531c9Paul Duffin return lhs.compareTo(rhs); 3737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3747dd252788645e940eada959bdde927426e2531c9Paul Duffin 3757dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3767dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean equals(Object obj) { 3777dd252788645e940eada959bdde927426e2531c9Paul Duffin if (obj instanceof NullsBefore) { 3787dd252788645e940eada959bdde927426e2531c9Paul Duffin NullsBefore other = (NullsBefore) obj; 3797dd252788645e940eada959bdde927426e2531c9Paul Duffin return justAfterNull.equals(other.justAfterNull); 3807dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3817dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 3827dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3837dd252788645e940eada959bdde927426e2531c9Paul Duffin 3847dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3857dd252788645e940eada959bdde927426e2531c9Paul Duffin public int hashCode() { 3867dd252788645e940eada959bdde927426e2531c9Paul Duffin return justAfterNull.hashCode(); 3877dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3887dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3897dd252788645e940eada959bdde927426e2531c9Paul Duffin 3907dd252788645e940eada959bdde927426e2531c9Paul Duffin public static final class NullsBeforeB extends NullsBefore { 3917dd252788645e940eada959bdde927426e2531c9Paul Duffin public static final NullsBeforeB INSTANCE = new NullsBeforeB(); 3927dd252788645e940eada959bdde927426e2531c9Paul Duffin 3937dd252788645e940eada959bdde927426e2531c9Paul Duffin private NullsBeforeB() { 3947dd252788645e940eada959bdde927426e2531c9Paul Duffin super("b"); 3957dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3967dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3977dd252788645e940eada959bdde927426e2531c9Paul Duffin 3987dd252788645e940eada959bdde927426e2531c9Paul Duffin public static final class NullsBeforeTwo extends NullsBefore { 3997dd252788645e940eada959bdde927426e2531c9Paul Duffin public static final NullsBeforeTwo INSTANCE = new NullsBeforeTwo(); 4007dd252788645e940eada959bdde927426e2531c9Paul Duffin 4017dd252788645e940eada959bdde927426e2531c9Paul Duffin private NullsBeforeTwo() { 4027dd252788645e940eada959bdde927426e2531c9Paul Duffin super("two"); // from TestStringSortedMapGenerator's sample keys 4037dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4047dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4057dd252788645e940eada959bdde927426e2531c9Paul Duffin 4067dd252788645e940eada959bdde927426e2531c9Paul Duffin @GwtIncompatible("reflection") 4077dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Method getMethod(Class<?> clazz, String name) { 4087dd252788645e940eada959bdde927426e2531c9Paul Duffin try { 4097dd252788645e940eada959bdde927426e2531c9Paul Duffin return clazz.getMethod(name); 4107dd252788645e940eada959bdde927426e2531c9Paul Duffin } catch (Exception e) { 4117dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new IllegalArgumentException(e); 4127dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4137dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 415