--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Collection/MOAT.java Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,814 @@
+/*
+ * Copyright 2005-2007 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * @test
+ * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464
+ * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753
+ * 6431845 4802633 6570566 6570575 6570631 6570924
+ * @summary Run many tests on many Collection and Map implementations
+ * @author Martin Buchholz
+ */
+
+/* Mother Of All (Collection) Tests
+ *
+ * Testing of collection classes is often spotty, because many tests
+ * need to be performed on many implementations, but the onus on
+ * writing the tests falls on the engineer introducing the new
+ * implementation.
+ *
+ * The idea of this mega-test is that:
+ *
+ * An engineer adding a new collection implementation could simply add
+ * their new implementation to a list of implementations in this
+ * test's main method. Any general purpose Collection<Integer> or
+ * Map<Integer,Integer> class is appropriate.
+ *
+ * An engineer fixing a regression could add their regression test here and
+ * simultaneously test all other implementations.
+ */
+
+import java.io.*;
+import java.util.*;
+import java.util.concurrent.*;
+import static java.util.Collections.*;
+
+public class MOAT {
+ public static void realMain(String[] args) {
+
+ testCollection(new LinkedHashSet<Integer>());
+ testCollection(new HashSet<Integer>());
+ testCollection(new Vector<Integer>());
+ testCollection(new Vector<Integer>().subList(0,0));
+ testCollection(new ArrayDeque<Integer>());
+ testCollection(new ArrayList<Integer>());
+ testCollection(new ArrayList<Integer>().subList(0,0));
+ testCollection(new LinkedList<Integer>());
+ testCollection(new LinkedList<Integer>().subList(0,0));
+ testCollection(new TreeSet<Integer>());
+
+ testCollection(new CopyOnWriteArrayList<Integer>());
+ testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
+ testCollection(new CopyOnWriteArraySet<Integer>());
+ testCollection(new PriorityQueue<Integer>());
+ testCollection(new PriorityBlockingQueue<Integer>());
+ testCollection(new ArrayBlockingQueue<Integer>(20));
+ testCollection(new LinkedBlockingQueue<Integer>(20));
+ testCollection(new LinkedBlockingDeque<Integer>(20));
+ testCollection(new ConcurrentLinkedQueue<Integer>());
+ testCollection(new ConcurrentSkipListSet<Integer>());
+ testCollection(Arrays.asList(new Integer(42)));
+ testCollection(Arrays.asList(1,2,3));
+ testCollection(nCopies(25,1));
+ testImmutableList(nCopies(25,1));
+ testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
+
+ testMap(new HashMap<Integer,Integer>());
+ testMap(new LinkedHashMap<Integer,Integer>());
+ testMap(new WeakHashMap<Integer,Integer>());
+ testMap(new IdentityHashMap<Integer,Integer>());
+ testMap(new TreeMap<Integer,Integer>());
+ testMap(new Hashtable<Integer,Integer>());
+ testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
+ testMap(new ConcurrentSkipListMap<Integer,Integer>());
+
+ // Empty collections
+ final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
+ testCollection(emptyArray);
+ testEmptyList(emptyArray);
+ THROWS(IndexOutOfBoundsException.class,
+ new Fun(){void f(){ emptyArray.set(0,1); }});
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ emptyArray.add(0,1); }});
+
+ List<Integer> noOne = nCopies(0,1);
+ testCollection(noOne);
+ testEmptyList(noOne);
+ testImmutableList(noOne);
+
+ Set<Integer> emptySet = emptySet();
+ testCollection(emptySet);
+ testEmptySet(emptySet);
+ testEmptySet(EMPTY_SET);
+ testImmutableSet(emptySet);
+
+ List<Integer> emptyList = emptyList();
+ testCollection(emptyList);
+ testEmptyList(emptyList);
+ testEmptyList(EMPTY_LIST);
+ testImmutableList(emptyList);
+
+ Map<Integer,Integer> emptyMap = emptyMap();
+ testMap(emptyMap);
+ testEmptyMap(emptyMap);
+ testEmptyMap(EMPTY_MAP);
+ testImmutableMap(emptyMap);
+
+ // Singleton collections
+ Set<Integer> singletonSet = singleton(1);
+ equal(singletonSet.size(), 1);
+ testCollection(singletonSet);
+ testImmutableSet(singletonSet);
+
+ List<Integer> singletonList = singletonList(1);
+ equal(singletonList.size(), 1);
+ testCollection(singletonList);
+ testImmutableList(singletonList);
+ testImmutableList(singletonList.subList(0,1));
+ testImmutableList(singletonList.subList(0,1).subList(0,1));
+ testEmptyList(singletonList.subList(0,0));
+ testEmptyList(singletonList.subList(0,0).subList(0,0));
+
+ Map<Integer,Integer> singletonMap = singletonMap(1,2);
+ equal(singletonMap.size(), 1);
+ testMap(singletonMap);
+ testImmutableMap(singletonMap);
+ }
+
+ private static void checkContainsSelf(Collection<Integer> c) {
+ check(c.containsAll(c));
+ check(c.containsAll(Arrays.asList(c.toArray())));
+ check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
+ }
+
+ private static void checkContainsEmpty(Collection<Integer> c) {
+ check(c.containsAll(new ArrayList<Integer>()));
+ }
+
+ private static void testEmptyCollection(Collection<?> c) {
+ check(c.isEmpty());
+ equal(c.size(), 0);
+ equal(c.toString(),"[]");
+ equal(c.toArray().length, 0);
+ equal(c.toArray(new Object[0]).length, 0);
+
+ Object[] a = new Object[1]; a[0] = Boolean.TRUE;
+ equal(c.toArray(a), a);
+ equal(a[0], null);
+ }
+
+ private static void testEmptyList(List<?> c) {
+ testEmptyCollection(c);
+ equal(c.hashCode(), 1);
+ equal2(c, Collections.<Integer>emptyList());
+ }
+
+ private static void testEmptySet(Set<?> c) {
+ testEmptyCollection(c);
+ equal(c.hashCode(), 0);
+ equal2(c, Collections.<Integer>emptySet());
+ }
+
+ private static void testImmutableCollection(final Collection<Integer> c) {
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ c.add(99); }},
+ new Fun(){void f(){ c.addAll(singleton(99)); }});
+ if (! c.isEmpty()) {
+ final Integer first = c.iterator().next();
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ c.clear(); }},
+ new Fun(){void f(){ c.remove(first); }},
+ new Fun(){void f(){ c.removeAll(singleton(first)); }},
+ new Fun(){void f(){ c.retainAll(emptyList()); }}
+ );
+ }
+ }
+
+ private static void testImmutableSet(final Set<Integer> c) {
+ testImmutableCollection(c);
+ }
+
+ private static void testImmutableList(final List<Integer> c) {
+ testList(c);
+ testImmutableCollection(c);
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ c.set(0,42); }},
+ new Fun(){void f(){ c.add(0,42); }},
+ new Fun(){void f(){ c.addAll(0,singleton(86)); }});
+ if (! c.isEmpty())
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){
+ Iterator<Integer> it = c.iterator();
+ it.next(); it.remove();}},
+ new Fun(){void f(){
+ ListIterator<Integer> it = c.listIterator();
+ it.next(); it.remove();}});
+ }
+
+ private static void clear(Collection<Integer> c) {
+ try { c.clear(); }
+ catch (Throwable t) { unexpected(t); }
+ testEmptyCollection(c);
+ }
+
+ private static void testEmptyMap(final Map<?,?> m) {
+ check(m.isEmpty());
+ equal(m.size(), 0);
+ equal(m.toString(),"{}");
+ testEmptySet(m.keySet());
+ testEmptySet(m.entrySet());
+ testEmptyCollection(m.values());
+ }
+
+ private static void testImmutableMap(final Map<Integer,Integer> m) {
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ m.put(1,1); }},
+ new Fun(){void f(){ m.putAll(singletonMap(1,1)); }});
+ if (! m.isEmpty()) {
+ final Integer first = m.keySet().iterator().next();
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ m.remove(first); }},
+ new Fun(){void f(){ m.clear(); }});
+ final Map.Entry<Integer,Integer> me
+ = m.entrySet().iterator().next();
+ Integer key = me.getKey();
+ Integer val = me.getValue();
+ THROWS(UnsupportedOperationException.class,
+ new Fun(){void f(){ me.setValue(3); }});
+ equal(key, me.getKey());
+ equal(val, me.getValue());
+ }
+ testImmutableSet(m.keySet());
+ testImmutableCollection(m.values());
+ //testImmutableSet(m.entrySet());
+ }
+
+ private static void clear(Map<?,?> m) {
+ try { m.clear(); }
+ catch (Throwable t) { unexpected(t); }
+ testEmptyMap(m);
+ }
+
+ private static void oneElement(Collection<Integer> c) {
+ clear(c);
+ try {
+ check(c.add(-42));
+ equal(c.toString(), "[-42]");
+ if (c instanceof Set) check(! c.add(-42));
+ } catch (Throwable t) { unexpected(t); }
+ check(! c.isEmpty()); check(c.size() == 1);
+ }
+
+ private static boolean supportsAdd(Collection<Integer> c) {
+ try { check(c.add(778347983)); }
+ catch (UnsupportedOperationException t) { return false; }
+ catch (Throwable t) { unexpected(t); }
+
+ try {
+ check(c.contains(778347983));
+ check(c.remove(778347983));
+ } catch (Throwable t) { unexpected(t); }
+ return true;
+ }
+
+ private static boolean supportsRemove(Collection<Integer> c) {
+ try { check(! c.remove(19134032)); }
+ catch (UnsupportedOperationException t) { return false; }
+ catch (Throwable t) { unexpected(t); }
+ return true;
+ }
+
+ private static void checkFunctionalInvariants(Collection<Integer> c) {
+ try {
+ checkContainsSelf(c);
+ checkContainsEmpty(c);
+ check(c.size() != 0 ^ c.isEmpty());
+
+ {
+ int size = 0;
+ for (Integer i : c) size++;
+ check(c.size() == size);
+ }
+
+ check(c.toArray().length == c.size());
+ check(c.toArray().getClass() == Object[].class
+ ||
+ // !!!!
+ // 6260652: (coll) Arrays.asList(x).toArray().getClass()
+ // should be Object[].class
+ (c.getClass().getName().equals("java.util.Arrays$ArrayList"))
+ );
+ for (int size : new int[]{0,1,c.size(), c.size()+1}) {
+ Integer[] a = c.toArray(new Integer[size]);
+ check((size > c.size()) || a.length == c.size());
+ int i = 0; for (Integer j : c) check(a[i++] == j);
+ check((size <= c.size()) || (a[c.size()] == null));
+ check(a.getClass() == Integer[].class);
+ }
+
+ check(c.equals(c));
+ if (c instanceof Serializable) {
+ //System.out.printf("Serializing %s%n", c.getClass().getName());
+ try {
+ Object clone = serialClone(c);
+ equal(c instanceof Serializable,
+ clone instanceof Serializable);
+ equal(c instanceof RandomAccess,
+ clone instanceof RandomAccess);
+ if ((c instanceof List) || (c instanceof Set))
+ equal(c, clone);
+ else
+ equal(new HashSet<Integer>(c),
+ new HashSet<Integer>(serialClone(c)));
+ } catch (Error xxx) {
+ if (! (xxx.getCause() instanceof NotSerializableException))
+ throw xxx;
+ }
+ }
+ }
+ catch (Throwable t) { unexpected(t); }
+ }
+
+ //----------------------------------------------------------------
+ // If add(null) succeeds, contains(null) & remove(null) should succeed
+ //----------------------------------------------------------------
+ private static void testNullElement(Collection<Integer> c) {
+ // !!!! 5018849: (coll) TreeSet.contains(null) does not agree with Javadoc
+ if (c instanceof TreeSet) return;
+
+ try {
+ check(c.add(null));
+ if (c.size() == 1)
+ equal(c.toString(), "[null]");
+ try {
+ checkFunctionalInvariants(c);
+ check(c.contains(null));
+ check(c.remove(null));
+ }
+ catch (Throwable t) { unexpected(t); }
+ }
+ catch (NullPointerException e) { /* OK */ }
+ catch (Throwable t) { unexpected(t); }
+ }
+
+
+ //----------------------------------------------------------------
+ // If add("x") succeeds, contains("x") & remove("x") should succeed
+ //----------------------------------------------------------------
+ @SuppressWarnings("unchecked")
+ private static void testStringElement(Collection<Integer> c) {
+ Collection x = (Collection)c; // Make type-unsafe
+ try {
+ check(x.add("x"));
+ try {
+ check(x.contains("x"));
+ check(x.remove("x"));
+ } catch (Throwable t) { unexpected(t); }
+ }
+ catch (ClassCastException e) { /* OK */ }
+ catch (Throwable t) { unexpected(t); }
+ }
+
+ private static void testConcurrentCollection(Collection<Integer> c) {
+ try {
+ c.add(1);
+ Iterator<Integer> it = c.iterator();
+ check(it.hasNext());
+ clear(c);
+ check(it.next() instanceof Integer); // No CME
+ check(c.isEmpty());
+ }
+ catch (Throwable t) { unexpected(t); }
+ }
+
+ private static void testQueue(Queue<Integer> q) {
+ q.clear();
+ for (int i = 0; i < 5; i++)
+ q.add(i);
+ equal(q.size(), 5);
+ checkFunctionalInvariants(q);
+ q.poll();
+ equal(q.size(), 4);
+ checkFunctionalInvariants(q);
+ }
+
+ private static void testList(final List<Integer> l) {
+ //----------------------------------------------------------------
+ // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
+ // doesn't throw IndexOutOfBoundsException
+ //----------------------------------------------------------------
+ try {
+ l.addAll(-1, Collections.<Integer>emptyList());
+ fail("Expected IndexOutOfBoundsException not thrown");
+ }
+ catch (UnsupportedOperationException _) {/* OK */}
+ catch (IndexOutOfBoundsException _) {/* OK */}
+ catch (Throwable t) { unexpected(t); }
+
+// equal(l instanceof Serializable,
+// l.subList(0,0) instanceof Serializable);
+ if (l.subList(0,0) instanceof Serializable)
+ check(l instanceof Serializable);
+
+ equal(l instanceof RandomAccess,
+ l.subList(0,0) instanceof RandomAccess);
+ }
+
+ private static void testCollection(Collection<Integer> c) {
+
+ System.out.println("\n==> " + c.getClass().getName());
+
+ checkFunctionalInvariants(c);
+
+ if (! supportsAdd(c)) return;
+ //System.out.println("add() supported");
+
+ if (c instanceof NavigableSet)
+ testNavigableSet((NavigableSet<Integer>)c);
+
+ if (c instanceof Queue)
+ testQueue((Queue<Integer>)c);
+
+ if (c instanceof List)
+ testList((List<Integer>)c);
+
+ check(supportsRemove(c));
+
+ try {
+ oneElement(c);
+ checkFunctionalInvariants(c);
+ }
+ catch (Throwable t) { unexpected(t); }
+
+ clear(c); testNullElement(c);
+ oneElement(c); testNullElement(c);
+
+ clear(c); testStringElement(c);
+ oneElement(c); testStringElement(c);
+
+ if (c.getClass().getName().matches(".*concurrent.*"))
+ testConcurrentCollection(c);
+
+ //----------------------------------------------------------------
+ // The "all" operations should throw NPE when passed null
+ //----------------------------------------------------------------
+ {
+ oneElement(c);
+ try {
+ c.removeAll(null);
+ fail("Expected NullPointerException");
+ }
+ catch (NullPointerException e) { pass(); }
+ catch (Throwable t) { unexpected(t); }
+
+ oneElement(c);
+ try {
+ c.retainAll(null);
+ fail("Expected NullPointerException");
+ }
+ catch (NullPointerException e) { pass(); }
+ catch (Throwable t) { unexpected(t); }
+
+ oneElement(c);
+ try {
+ c.addAll(null);
+ fail("Expected NullPointerException");
+ }
+ catch (NullPointerException e) { pass(); }
+ catch (Throwable t) { unexpected(t); }
+
+ oneElement(c);
+ try {
+ c.containsAll(null);
+ fail("Expected NullPointerException");
+ }
+ catch (NullPointerException e) { pass(); }
+ catch (Throwable t) { unexpected(t); }
+ }
+ }
+
+ //----------------------------------------------------------------
+ // Map
+ //----------------------------------------------------------------
+ private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
+ check(m.keySet().size() == m.entrySet().size());
+ check(m.keySet().size() == m.size());
+ checkFunctionalInvariants(m.keySet());
+ checkFunctionalInvariants(m.values());
+ check(m.size() != 0 ^ m.isEmpty());
+ }
+
+ private static void testMap(Map<Integer,Integer> m) {
+ System.out.println("\n==> " + m.getClass().getName());
+
+ if (m instanceof ConcurrentMap)
+ testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
+
+ if (m instanceof NavigableMap)
+ testNavigableMap((NavigableMap<Integer,Integer>) m);
+
+ checkFunctionalInvariants(m);
+
+ if (supportsClear(m)) {
+ try { clear(m); }
+ catch (Throwable t) { unexpected(t); }
+ }
+
+ if (supportsPut(m)) {
+ try {
+ check(m.put(3333, 77777) == null);
+ check(m.put(9134, 74982) == null);
+ check(m.get(9134) == 74982);
+ check(m.put(9134, 1382) == 74982);
+ check(m.get(9134) == 1382);
+ check(m.size() == 2);
+ checkFunctionalInvariants(m);
+ checkNPEConsistency(m);
+ }
+ catch (Throwable t) { unexpected(t); }
+ }
+ }
+
+ private static boolean supportsPut(Map<Integer,Integer> m) {
+ // We're asking for .equals(...) semantics
+ if (m instanceof IdentityHashMap) return false;
+
+ try { check(m.put(778347983,12735) == null); }
+ catch (UnsupportedOperationException t) { return false; }
+ catch (Throwable t) { unexpected(t); }
+
+ try {
+ check(m.containsKey(778347983));
+ check(m.remove(778347983) != null);
+ } catch (Throwable t) { unexpected(t); }
+ return true;
+ }
+
+ private static boolean supportsClear(Map<?,?> m) {
+ try { m.clear(); }
+ catch (UnsupportedOperationException t) { return false; }
+ catch (Throwable t) { unexpected(t); }
+ return true;
+ }
+
+ //----------------------------------------------------------------
+ // ConcurrentMap
+ //----------------------------------------------------------------
+ private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
+ System.out.println("ConcurrentMap tests...");
+
+ try {
+ clear(m);
+
+ check(m.putIfAbsent(18357,7346) == null);
+ check(m.containsKey(18357));
+ check(m.putIfAbsent(18357,8263) == 7346);
+ try { m.putIfAbsent(18357,null); fail("NPE"); }
+ catch (NullPointerException t) { }
+ check(m.containsKey(18357));
+
+ check(! m.replace(18357,8888,7777));
+ check(m.containsKey(18357));
+ try { m.replace(18357,null,7777); fail("NPE"); }
+ catch (NullPointerException t) { }
+ check(m.containsKey(18357));
+ check(m.get(18357) == 7346);
+ check(m.replace(18357,7346,5555));
+ check(m.replace(18357,5555,7346));
+ check(m.get(18357) == 7346);
+
+ check(m.replace(92347,7834) == null);
+ try { m.replace(18357,null); fail("NPE"); }
+ catch (NullPointerException t) { }
+ check(m.replace(18357,7346) == 7346);
+ check(m.replace(18357,5555) == 7346);
+ check(m.get(18357) == 5555);
+ check(m.replace(18357,7346) == 5555);
+ check(m.get(18357) == 7346);
+
+ check(! m.remove(18357,9999));
+ check(m.get(18357) == 7346);
+ check(m.containsKey(18357));
+ check(! m.remove(18357,null)); // 6272521
+ check(m.get(18357) == 7346);
+ check(m.remove(18357,7346));
+ check(m.get(18357) == null);
+ check(! m.containsKey(18357));
+ check(m.isEmpty());
+
+ m.putIfAbsent(1,2);
+ check(m.size() == 1);
+ check(! m.remove(1,null));
+ check(! m.remove(1,null));
+ check(! m.remove(1,1));
+ check(m.remove(1,2));
+ check(m.isEmpty());
+
+ testEmptyMap(m);
+ }
+ catch (Throwable t) { unexpected(t); }
+ }
+
+ private static void throwsConsistently(Class<? extends Throwable> k,
+ Iterable<Fun> fs) {
+ List<Class<? extends Throwable>> threw
+ = new ArrayList<Class<? extends Throwable>>();
+ for (Fun f : fs)
+ try { f.f(); threw.add(null); }
+ catch (Throwable t) {
+ check(k.isAssignableFrom(t.getClass()));
+ threw.add(t.getClass());
+ }
+ if (new HashSet<Object>(threw).size() != 1)
+ fail(threw.toString());
+ }
+
+ private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
+ m.clear();
+ final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
+ ? (ConcurrentMap<T,Integer>) m
+ : null;
+ List<Fun> fs = new ArrayList<Fun>();
+ fs.add(new Fun(){void f(){ check(! m.containsKey(null));}});
+ fs.add(new Fun(){void f(){ equal(m.remove(null), null);}});
+ fs.add(new Fun(){void f(){ equal(m.get(null), null);}});
+ if (cm != null) {
+ fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});}
+ throwsConsistently(NullPointerException.class, fs);
+
+ fs.clear();
+ final Map<T,Integer> sm = singletonMap(null,1);
+ fs.add(new Fun(){void f(){ equal(m.put(null,1), null); m.clear();}});
+ fs.add(new Fun(){void f(){ m.putAll(sm); m.clear();}});
+ if (cm != null) {
+ fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});
+ fs.add(new Fun(){void f(){ equal(cm.putIfAbsent(null,1), 1);}});
+ fs.add(new Fun(){void f(){ equal(cm.replace(null,1), null);}});
+ fs.add(new Fun(){void f(){ equal(cm.replace(null,1, 1), 1);}});
+ }
+ throwsConsistently(NullPointerException.class, fs);
+ }
+
+ //----------------------------------------------------------------
+ // NavigableMap
+ //----------------------------------------------------------------
+ private static void
+ checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
+ Integer i,
+ Integer lower,
+ Integer floor,
+ Integer ceiling,
+ Integer higher) {
+ equal(m.lowerKey(i), lower);
+ equal(m.floorKey(i), floor);
+ equal(m.ceilingKey(i), ceiling);
+ equal(m.higherKey(i), higher);
+ }
+
+ private static void
+ checkNavigableSetKeys(NavigableSet<Integer> m,
+ Integer i,
+ Integer lower,
+ Integer floor,
+ Integer ceiling,
+ Integer higher) {
+ equal(m.lower(i), lower);
+ equal(m.floor(i), floor);
+ equal(m.ceiling(i), ceiling);
+ equal(m.higher(i), higher);
+ }
+
+ static final Random rnd = new Random();
+ static void equalNext(final Iterator<?> it, Object expected) {
+ if (rnd.nextBoolean())
+ check(it.hasNext());
+ equal(it.next(), expected);
+ }
+
+ private static void testNavigableMap(NavigableMap<Integer,Integer> m)
+ {
+ System.out.println("NavigableMap tests...");
+
+ clear(m);
+ checkNavigableMapKeys(m, 1, null, null, null, null);
+
+ equal(m.put(1, 2), null);
+ equal(m.put(3, 4), null);
+ equal(m.put(5, 9), null);
+
+ equal(m.put(1, 2), 2);
+ equal(m.put(3, 4), 4);
+ equal(m.put(5, 6), 9);
+
+ checkNavigableMapKeys(m, 0, null, null, 1, 1);
+ checkNavigableMapKeys(m, 1, null, 1, 1, 3);
+ checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
+ checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
+ checkNavigableMapKeys(m, 5, 3, 5, 5, null);
+ checkNavigableMapKeys(m, 6, 5, 5, null, null);
+
+ {
+ final Iterator<Integer> it
+ = m.descendingKeySet().iterator();
+ equalNext(it, 5);
+ equalNext(it, 3);
+ equalNext(it, 1);
+ check(! it.hasNext());
+ THROWS(NoSuchElementException.class,
+ new Fun(){void f(){it.next();}});
+ }
+
+ {
+ final Iterator<Map.Entry<Integer,Integer>> it
+ = m.descendingMap().entrySet().iterator();
+ check(it.hasNext()); equal(it.next().getKey(), 5);
+ check(it.hasNext()); equal(it.next().getKey(), 3);
+ check(it.hasNext()); equal(it.next().getKey(), 1);
+ check(! it.hasNext());
+ THROWS(NoSuchElementException.class,
+ new Fun(){void f(){it.next();}});
+ }
+ }
+
+
+ private static void testNavigableSet(NavigableSet<Integer> s) {
+ System.out.println("NavigableSet tests...");
+
+ clear(s);
+ checkNavigableSetKeys(s, 1, null, null, null, null);
+
+ check(s.add(1));
+ check(s.add(3));
+ check(s.add(5));
+
+ check(! s.add(1));
+ check(! s.add(3));
+ check(! s.add(5));
+
+ checkNavigableSetKeys(s, 0, null, null, 1, 1);
+ checkNavigableSetKeys(s, 1, null, 1, 1, 3);
+ checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
+ checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
+ checkNavigableSetKeys(s, 5, 3, 5, 5, null);
+ checkNavigableSetKeys(s, 6, 5, 5, null, null);
+
+ {
+ final Iterator<Integer> it = s.descendingIterator();
+ equalNext(it, 5);
+ equalNext(it, 3);
+ equalNext(it, 1);
+ check(! it.hasNext());
+ THROWS(NoSuchElementException.class,
+ new Fun(){void f(){it.next();}});
+ }
+ }
+
+ //--------------------- Infrastructure ---------------------------
+ static volatile int passed = 0, failed = 0;
+ static void pass() { passed++; }
+ static void fail() { failed++; Thread.dumpStack(); }
+ static void fail(String msg) { System.out.println(msg); fail(); }
+ static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
+ static void check(boolean cond) { if (cond) pass(); else fail(); }
+ static void equal(Object x, Object y) {
+ if (x == null ? y == null : x.equals(y)) pass();
+ else {System.out.println(x + " not equal to " + y); fail();}}
+ static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
+ public static void main(String[] args) throws Throwable {
+ try { realMain(args); } catch (Throwable t) { unexpected(t); }
+
+ System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+ if (failed > 0) throw new Exception("Some tests failed");
+ }
+ private static abstract class Fun {abstract void f() throws Throwable;}
+ private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
+ for (Fun f : fs)
+ try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
+ catch (Throwable t) {
+ if (k.isAssignableFrom(t.getClass())) pass();
+ else unexpected(t);}}
+ static byte[] serializedForm(Object obj) {
+ try {
+ ByteArrayOutputStream baos = new ByteArrayOutputStream();
+ new ObjectOutputStream(baos).writeObject(obj);
+ return baos.toByteArray();
+ } catch (IOException e) { throw new Error(e); }}
+ static Object readObject(byte[] bytes)
+ throws IOException, ClassNotFoundException {
+ InputStream is = new ByteArrayInputStream(bytes);
+ return new ObjectInputStream(is).readObject();}
+ @SuppressWarnings("unchecked")
+ static <T> T serialClone(T obj) {
+ try { return (T) readObject(serializedForm(obj)); }
+ catch (Exception e) { throw new Error(e); }}
+}