1 /*
   2  * Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @bug     6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464
  27  *          4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753
  28  *          6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215
  29  *          4802647 7123424
  30  * @summary Run many tests on many Collection and Map implementations
  31  * @author  Martin Buchholz
  32  * @run main MOAT
  33  */
  34 
  35 /* Mother Of All (Collection) Tests
  36  *
  37  * Testing of collection classes is often spotty, because many tests
  38  * need to be performed on many implementations, but the onus on
  39  * writing the tests falls on the engineer introducing the new
  40  * implementation.
  41  *
  42  * The idea of this mega-test is that:
  43  *
  44  * An engineer adding a new collection implementation could simply add
  45  * their new implementation to a list of implementations in this
  46  * test's main method.  Any general purpose Collection<Integer> or
  47  * Map<Integer,Integer> class is appropriate.
  48  *
  49  * An engineer fixing a regression could add their regression test here and
  50  * simultaneously test all other implementations.
  51  */
  52 
  53 import java.io.*;
  54 import java.util.*;
  55 import java.util.concurrent.*;
  56 import static java.util.Collections.*;
  57 
  58 public class MOAT {
  59     public static void realMain(String[] args) {
  60 
  61         testCollection(new NewAbstractCollection<Integer>());
  62         testCollection(new NewAbstractSet<Integer>());
  63         testCollection(new LinkedHashSet<Integer>());
  64         testCollection(new HashSet<Integer>());
  65         testCollection(new Vector<Integer>());
  66         testCollection(new Vector<Integer>().subList(0,0));
  67         testCollection(new ArrayDeque<Integer>());
  68         testCollection(new ArrayList<Integer>());
  69         testCollection(new ArrayList<Integer>().subList(0,0));
  70         testCollection(new LinkedList<Integer>());
  71         testCollection(new LinkedList<Integer>().subList(0,0));
  72         testCollection(new TreeSet<Integer>());
  73         testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
  74         testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
  75         testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
  76         testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
  77         testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
  78         testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
  79         testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));
  80         testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>()));
  81 
  82         testCollection(new CopyOnWriteArrayList<Integer>());
  83         testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
  84         testCollection(new CopyOnWriteArraySet<Integer>());
  85         testCollection(new PriorityQueue<Integer>());
  86         testCollection(new PriorityBlockingQueue<Integer>());
  87         testCollection(new ArrayBlockingQueue<Integer>(20));
  88         testCollection(new LinkedBlockingQueue<Integer>(20));
  89         testCollection(new LinkedBlockingDeque<Integer>(20));
  90         testCollection(new ConcurrentLinkedDeque<Integer>());
  91         testCollection(new ConcurrentLinkedQueue<Integer>());
  92         testCollection(new LinkedTransferQueue<Integer>());
  93         testCollection(new ConcurrentSkipListSet<Integer>());
  94         testCollection(Arrays.asList(new Integer(42)));
  95         testCollection(Arrays.asList(1,2,3));
  96         testCollection(nCopies(25,1));
  97         testImmutableList(nCopies(25,1));
  98         testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
  99 
 100         testMap(new HashMap<Integer,Integer>());
 101         testMap(new LinkedHashMap<Integer,Integer>());
 102         testMap(new WeakHashMap<Integer,Integer>());
 103         testMap(new IdentityHashMap<Integer,Integer>());
 104         testMap(new TreeMap<Integer,Integer>());
 105         testMap(new Hashtable<Integer,Integer>());
 106         testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
 107         testMap(new ConcurrentSkipListMap<Integer,Integer>());
 108         testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));
 109         testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
 110         testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
 111         testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));
 112         testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));
 113         testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));
 114 
 115         // Empty collections
 116         final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
 117         testCollection(emptyArray);
 118         testEmptyList(emptyArray);
 119         THROWS(IndexOutOfBoundsException.class,
 120                new Fun(){void f(){ emptyArray.set(0,1); }});
 121         THROWS(UnsupportedOperationException.class,
 122                new Fun(){void f(){ emptyArray.add(0,1); }});
 123 
 124         List<Integer> noOne = nCopies(0,1);
 125         testCollection(noOne);
 126         testEmptyList(noOne);
 127         testImmutableList(noOne);
 128 
 129         Set<Integer> emptySet = emptySet();
 130         testCollection(emptySet);
 131         testEmptySet(emptySet);
 132         testEmptySet(EMPTY_SET);
 133         testEmptySet(Collections.emptySet());
 134         testEmptySet(Collections.emptySortedSet());
 135         testEmptySet(Collections.emptyNavigableSet());
 136         testImmutableSet(emptySet);
 137 
 138         List<Integer> emptyList = emptyList();
 139         testCollection(emptyList);
 140         testEmptyList(emptyList);
 141         testEmptyList(EMPTY_LIST);
 142         testEmptyList(Collections.emptyList());
 143         testImmutableList(emptyList);
 144 
 145         Map<Integer,Integer> emptyMap = emptyMap();
 146         testMap(emptyMap);
 147         testEmptyMap(emptyMap);
 148         testEmptyMap(EMPTY_MAP);
 149         testEmptyMap(Collections.emptyMap());
 150         testEmptyMap(Collections.emptySortedMap());
 151         testEmptyMap(Collections.emptyNavigableMap());
 152         testImmutableMap(emptyMap);
 153         testImmutableMap(Collections.emptyMap());
 154         testImmutableMap(Collections.emptySortedMap());
 155         testImmutableMap(Collections.emptyNavigableMap());
 156 
 157         // Singleton collections
 158         Set<Integer> singletonSet = singleton(1);
 159         equal(singletonSet.size(), 1);
 160         testCollection(singletonSet);
 161         testImmutableSet(singletonSet);
 162 
 163         List<Integer> singletonList = singletonList(1);
 164         equal(singletonList.size(), 1);
 165         testCollection(singletonList);
 166         testImmutableList(singletonList);
 167         testImmutableList(singletonList.subList(0,1));
 168         testImmutableList(singletonList.subList(0,1).subList(0,1));
 169         testEmptyList(singletonList.subList(0,0));
 170         testEmptyList(singletonList.subList(0,0).subList(0,0));
 171 
 172         Map<Integer,Integer> singletonMap = singletonMap(1,2);
 173         equal(singletonMap.size(), 1);
 174         testMap(singletonMap);
 175         testImmutableMap(singletonMap);
 176     }
 177 
 178     private static void checkContainsSelf(Collection<Integer> c) {
 179         check(c.containsAll(c));
 180         check(c.containsAll(Arrays.asList(c.toArray())));
 181         check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
 182     }
 183 
 184     private static void checkContainsEmpty(Collection<Integer> c) {
 185         check(c.containsAll(new ArrayList<Integer>()));
 186     }
 187 
 188     private static <T> void testEmptyCollection(Collection<T> c) {
 189         check(c.isEmpty());
 190         equal(c.size(), 0);
 191         equal(c.toString(),"[]");
 192         equal(c.toArray().length, 0);
 193         equal(c.toArray(new Object[0]).length, 0);
 194         check(c.toArray(new Object[]{42})[0] == null);
 195 
 196         Object[] a = new Object[1]; a[0] = Boolean.TRUE;
 197         equal(c.toArray(a), a);
 198         equal(a[0], null);
 199         testEmptyIterator(c.iterator());
 200     }
 201 
 202     static <T> void testEmptyIterator(final Iterator<T> it) {
 203         if (rnd.nextBoolean())
 204             check(! it.hasNext());
 205 
 206         THROWS(NoSuchElementException.class,
 207                new Fun(){void f(){ it.next(); }});
 208 
 209         try { it.remove(); }
 210         catch (IllegalStateException ignored) { pass(); }
 211         catch (UnsupportedOperationException ignored) { pass(); }
 212         catch (Throwable t) { unexpected(t); }
 213 
 214         if (rnd.nextBoolean())
 215             check(! it.hasNext());
 216     }
 217 
 218     private static void testEmptyList(List<?> c) {
 219         testEmptyCollection(c);
 220         equal(c.hashCode(), 1);
 221         equal2(c, Collections.<Integer>emptyList());
 222     }
 223 
 224     private static <T> void testEmptySet(Set<T> c) {
 225         testEmptyCollection(c);
 226         equal(c.hashCode(), 0);
 227         equal2(c, Collections.<Integer>emptySet());
 228         if (c instanceof NavigableSet<?>)
 229             testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
 230     }
 231 
 232     private static void testImmutableCollection(final Collection<Integer> c) {
 233         THROWS(UnsupportedOperationException.class,
 234                new Fun(){void f(){ c.add(99); }},
 235                new Fun(){void f(){ c.addAll(singleton(99)); }});
 236         if (! c.isEmpty()) {
 237             final Integer first = c.iterator().next();
 238             THROWS(UnsupportedOperationException.class,
 239                    new Fun(){void f(){ c.clear(); }},
 240                    new Fun(){void f(){ c.remove(first); }},
 241                    new Fun(){void f(){ c.removeAll(singleton(first)); }},
 242                    new Fun(){void f(){ c.retainAll(emptyList()); }}
 243                    );
 244         }
 245     }
 246 
 247     private static void testImmutableSet(final Set<Integer> c) {
 248         testImmutableCollection(c);
 249     }
 250 
 251     private static void testImmutableList(final List<Integer> c) {
 252         testList(c);
 253         testImmutableCollection(c);
 254         THROWS(UnsupportedOperationException.class,
 255                new Fun(){void f(){ c.set(0,42); }},
 256                new Fun(){void f(){ c.add(0,42); }},
 257                new Fun(){void f(){ c.addAll(0,singleton(86)); }});
 258         if (! c.isEmpty())
 259             THROWS(UnsupportedOperationException.class,
 260                    new Fun(){void f(){
 261                            Iterator<Integer> it = c.iterator();
 262                            it.next(); it.remove();}},
 263                    new Fun(){void f(){
 264                            ListIterator<Integer> it = c.listIterator();
 265                            it.next(); it.remove();}});
 266     }
 267 
 268     private static void clear(Collection<Integer> c) {
 269         try { c.clear(); }
 270         catch (Throwable t) { unexpected(t); }
 271         testEmptyCollection(c);
 272     }
 273 
 274     private static <K,V> void testEmptyMap(final Map<K,V> m) {
 275         check(m.isEmpty());
 276         equal(m.size(), 0);
 277         equal(m.toString(),"{}");
 278         testEmptySet(m.keySet());
 279         testEmptySet(m.entrySet());
 280         testEmptyCollection(m.values());
 281 
 282         try { check(! m.containsValue(null)); }
 283         catch (NullPointerException ignored) { /* OK */ }
 284         try { check(! m.containsKey(null)); }
 285         catch (NullPointerException ignored) { /* OK */ }
 286         check(! m.containsValue(1));
 287         check(! m.containsKey(1));
 288     }
 289 
 290     private static void testImmutableMap(final Map<Integer,Integer> m) {
 291         THROWS(UnsupportedOperationException.class,
 292                new Fun(){void f(){ m.put(1,1); }},
 293                new Fun(){void f(){ m.putAll(singletonMap(1,1)); }});
 294         if (! m.isEmpty()) {
 295             final Integer first = m.keySet().iterator().next();
 296             THROWS(UnsupportedOperationException.class,
 297                    new Fun(){void f(){ m.remove(first); }},
 298                    new Fun(){void f(){ m.clear(); }});
 299             final Map.Entry<Integer,Integer> me
 300                 = m.entrySet().iterator().next();
 301             Integer key = me.getKey();
 302             Integer val = me.getValue();
 303             THROWS(UnsupportedOperationException.class,
 304                    new Fun(){void f(){ me.setValue(3); }});
 305             equal(key, me.getKey());
 306             equal(val, me.getValue());
 307         }
 308         testImmutableSet(m.keySet());
 309         testImmutableCollection(m.values());
 310         //testImmutableSet(m.entrySet());
 311     }
 312 
 313     private static void clear(Map<?,?> m) {
 314         try { m.clear(); }
 315         catch (Throwable t) { unexpected(t); }
 316         testEmptyMap(m);
 317     }
 318 
 319     private static void oneElement(Collection<Integer> c) {
 320         clear(c);
 321         try {
 322             check(c.add(-42));
 323             equal(c.toString(), "[-42]");
 324             if (c instanceof Set) check(! c.add(-42));
 325         } catch (Throwable t) { unexpected(t); }
 326         check(! c.isEmpty()); check(c.size() == 1);
 327     }
 328 
 329     private static boolean supportsAdd(Collection<Integer> c) {
 330         try { check(c.add(778347983)); }
 331         catch (UnsupportedOperationException t) { return false; }
 332         catch (Throwable t) { unexpected(t); }
 333 
 334         try {
 335             check(c.contains(778347983));
 336             check(c.remove(778347983));
 337         } catch (Throwable t) { unexpected(t); }
 338         return true;
 339     }
 340 
 341     private static boolean supportsRemove(Collection<Integer> c) {
 342         try { check(! c.remove(19134032)); }
 343         catch (UnsupportedOperationException t) { return false; }
 344         catch (Throwable t) { unexpected(t); }
 345         return true;
 346     }
 347 
 348     private static void checkFunctionalInvariants(Collection<Integer> c) {
 349         try {
 350             checkContainsSelf(c);
 351             checkContainsEmpty(c);
 352             check(c.size() != 0 ^ c.isEmpty());
 353 
 354             {
 355                 int size = 0;
 356                 for (Integer i : c) size++;
 357                 check(c.size() == size);
 358             }
 359 
 360             check(c.toArray().length == c.size());
 361             check(c.toArray().getClass() == Object[].class
 362                   ||
 363                   // !!!!
 364                   // 6260652: (coll) Arrays.asList(x).toArray().getClass()
 365                   // should be Object[].class
 366                   (c.getClass().getName().equals("java.util.Arrays$ArrayList"))
 367                   );
 368             for (int size : new int[]{0,1,c.size(), c.size()+1}) {
 369                 Integer[] a = c.toArray(new Integer[size]);
 370                 check((size > c.size()) || a.length == c.size());
 371                 int i = 0; for (Integer j : c) check(a[i++] == j);
 372                 check((size <= c.size()) || (a[c.size()] == null));
 373                 check(a.getClass() == Integer[].class);
 374             }
 375 
 376             check(c.equals(c));
 377             if (c instanceof Serializable) {
 378                 //System.out.printf("Serializing %s%n", c.getClass().getName());
 379                 try {
 380                     Object clone = serialClone(c);
 381                     equal(c instanceof Serializable,
 382                           clone instanceof Serializable);
 383                     equal(c instanceof RandomAccess,
 384                           clone instanceof RandomAccess);
 385                     if ((c instanceof List) || (c instanceof Set))
 386                         equal(c, clone);
 387                     else
 388                         equal(new HashSet<Integer>(c),
 389                               new HashSet<Integer>(serialClone(c)));
 390                 } catch (Error xxx) {
 391                     if (! (xxx.getCause() instanceof NotSerializableException))
 392                         throw xxx;
 393                 }
 394             }
 395         }
 396         catch (Throwable t) { unexpected(t); }
 397     }
 398 
 399     //----------------------------------------------------------------
 400     // If add(null) succeeds, contains(null) & remove(null) should succeed
 401     //----------------------------------------------------------------
 402     private static void testNullElement(Collection<Integer> c) {
 403 
 404         try {
 405             check(c.add(null));
 406             if (c.size() == 1)
 407                 equal(c.toString(), "[null]");
 408             try {
 409                 checkFunctionalInvariants(c);
 410                 check(c.contains(null));
 411                 check(c.remove(null));
 412             }
 413             catch (Throwable t) { unexpected(t); }
 414         }
 415         catch (NullPointerException e) { /* OK */ }
 416         catch (Throwable t) { unexpected(t); }
 417     }
 418 
 419 
 420     //----------------------------------------------------------------
 421     // If add("x") succeeds, contains("x") & remove("x") should succeed
 422     //----------------------------------------------------------------
 423     @SuppressWarnings("unchecked")
 424     private static void testStringElement(Collection<Integer> c) {
 425         Collection x = (Collection)c; // Make type-unsafe
 426         try {
 427             check(x.add("x"));
 428             try {
 429                 check(x.contains("x"));
 430                 check(x.remove("x"));
 431             } catch (Throwable t) { unexpected(t); }
 432         }
 433         catch (ClassCastException e) { /* OK */ }
 434         catch (Throwable t) { unexpected(t); }
 435     }
 436 
 437     private static void testConcurrentCollection(Collection<Integer> c) {
 438         try {
 439             c.add(1);
 440             Iterator<Integer> it = c.iterator();
 441             check(it.hasNext());
 442             clear(c);
 443             check(it.next() instanceof Integer); // No CME
 444             check(c.isEmpty());
 445         }
 446         catch (Throwable t) { unexpected(t); }
 447     }
 448 
 449     private static void testQueue(Queue<Integer> q) {
 450         q.clear();
 451         for (int i = 0; i < 5; i++) {
 452             testQueueAddRemove(q, null);
 453             testQueueAddRemove(q, 537);
 454             q.add(i);
 455         }
 456         equal(q.size(), 5);
 457         checkFunctionalInvariants(q);
 458         q.poll();
 459         equal(q.size(), 4);
 460         checkFunctionalInvariants(q);
 461         if ((q instanceof LinkedBlockingQueue)   ||
 462             (q instanceof LinkedBlockingDeque)   ||
 463             (q instanceof ConcurrentLinkedDeque) ||
 464             (q instanceof ConcurrentLinkedQueue)) {
 465             testQueueIteratorRemove(q);
 466         }
 467     }
 468 
 469     private static void testQueueAddRemove(final Queue<Integer> q,
 470                                            final Integer e) {
 471         final List<Integer> originalContents = new ArrayList<Integer>(q);
 472         final boolean isEmpty = q.isEmpty();
 473         final boolean isList = (q instanceof List);
 474         final List asList = isList ? (List) q : null;
 475         check(!q.contains(e));
 476         try {
 477             q.add(e);
 478         } catch (NullPointerException npe) {
 479             check(e == null);
 480             return;                     // Null elements not supported
 481         }
 482         check(q.contains(e));
 483         check(q.remove(e));
 484         check(!q.contains(e));
 485         equal(new ArrayList<Integer>(q), originalContents);
 486 
 487         if (q instanceof Deque<?>) {
 488             final Deque<Integer> deq = (Deque<Integer>) q;
 489             final List<Integer> singleton = Collections.singletonList(e);
 490 
 491             // insert, query, remove element at head
 492             if (isEmpty) {
 493                 THROWS(NoSuchElementException.class,
 494                        new Fun(){void f(){ deq.getFirst(); }},
 495                        new Fun(){void f(){ deq.element(); }},
 496                        new Fun(){void f(){ deq.iterator().next(); }});
 497                 check(deq.peekFirst() == null);
 498                 check(deq.peek() == null);
 499             } else {
 500                 check(deq.getFirst() != e);
 501                 check(deq.element() != e);
 502                 check(deq.iterator().next() != e);
 503                 check(deq.peekFirst() != e);
 504                 check(deq.peek() != e);
 505             }
 506             check(!deq.contains(e));
 507             check(!deq.removeFirstOccurrence(e));
 508             check(!deq.removeLastOccurrence(e));
 509             if (isList) {
 510                 check(asList.indexOf(e) == -1);
 511                 check(asList.lastIndexOf(e) == -1);
 512             }
 513             switch (rnd.nextInt(isList ? 4 : 3)) {
 514             case 0: deq.addFirst(e); break;
 515             case 1: check(deq.offerFirst(e)); break;
 516             case 2: deq.push(e); break;
 517             case 3: asList.add(0, e); break;
 518             default: throw new AssertionError();
 519             }
 520             check(deq.peekFirst() == e);
 521             check(deq.getFirst() == e);
 522             check(deq.element() == e);
 523             check(deq.peek() == e);
 524             check(deq.iterator().next() == e);
 525             check(deq.contains(e));
 526             if (isList) {
 527                 check(asList.get(0) == e);
 528                 check(asList.indexOf(e) == 0);
 529                 check(asList.lastIndexOf(e) == 0);
 530                 check(asList.subList(0, 1).equals(singleton));
 531             }
 532             switch (rnd.nextInt(isList ? 11 : 9)) {
 533             case 0: check(deq.pollFirst() == e); break;
 534             case 1: check(deq.removeFirst() == e); break;
 535             case 2: check(deq.remove() == e); break;
 536             case 3: check(deq.pop() == e); break;
 537             case 4: check(deq.removeFirstOccurrence(e)); break;
 538             case 5: check(deq.removeLastOccurrence(e)); break;
 539             case 6: check(deq.remove(e)); break;
 540             case 7: check(deq.removeAll(singleton)); break;
 541             case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
 542             case 9: asList.remove(0); break;
 543             case 10: asList.subList(0, 1).clear(); break;
 544             default: throw new AssertionError();
 545             }
 546             if (isEmpty) {
 547                 THROWS(NoSuchElementException.class,
 548                        new Fun(){void f(){ deq.getFirst(); }},
 549                        new Fun(){void f(){ deq.element(); }},
 550                        new Fun(){void f(){ deq.iterator().next(); }});
 551                 check(deq.peekFirst() == null);
 552                 check(deq.peek() == null);
 553             } else {
 554                 check(deq.getFirst() != e);
 555                 check(deq.element() != e);
 556                 check(deq.iterator().next() != e);
 557                 check(deq.peekFirst() != e);
 558                 check(deq.peek() != e);
 559             }
 560             check(!deq.contains(e));
 561             check(!deq.removeFirstOccurrence(e));
 562             check(!deq.removeLastOccurrence(e));
 563             if (isList) {
 564                 check(isEmpty || asList.get(0) != e);
 565                 check(asList.indexOf(e) == -1);
 566                 check(asList.lastIndexOf(e) == -1);
 567             }
 568             equal(new ArrayList<Integer>(deq), originalContents);
 569 
 570             // insert, query, remove element at tail
 571             if (isEmpty) {
 572                 check(deq.peekLast() == null);
 573                 THROWS(NoSuchElementException.class,
 574                        new Fun(){void f(){ deq.getLast(); }});
 575             } else {
 576                 check(deq.peekLast() != e);
 577                 check(deq.getLast() != e);
 578             }
 579             switch (rnd.nextInt(isList ? 6 : 4)) {
 580             case 0: deq.addLast(e); break;
 581             case 1: check(deq.offerLast(e)); break;
 582             case 2: check(deq.add(e)); break;
 583             case 3: deq.addAll(singleton); break;
 584             case 4: asList.addAll(deq.size(), singleton); break;
 585             case 5: asList.add(deq.size(), e); break;
 586             default: throw new AssertionError();
 587             }
 588             check(deq.peekLast() == e);
 589             check(deq.getLast() == e);
 590             check(deq.contains(e));
 591             if (isList) {
 592                 ListIterator it = asList.listIterator(asList.size());
 593                 check(it.previous() == e);
 594                 check(asList.get(asList.size() - 1) == e);
 595                 check(asList.indexOf(e) == asList.size() - 1);
 596                 check(asList.lastIndexOf(e) == asList.size() - 1);
 597                 int size = asList.size();
 598                 check(asList.subList(size - 1, size).equals(singleton));
 599             }
 600             switch (rnd.nextInt(isList ? 8 : 6)) {
 601             case 0: check(deq.pollLast() == e); break;
 602             case 1: check(deq.removeLast() == e); break;
 603             case 2: check(deq.removeFirstOccurrence(e)); break;
 604             case 3: check(deq.removeLastOccurrence(e)); break;
 605             case 4: check(deq.remove(e)); break;
 606             case 5: check(deq.removeAll(singleton)); break;
 607             case 6: asList.remove(asList.size() - 1); break;
 608             case 7:
 609                 ListIterator it = asList.listIterator(asList.size());
 610                 it.previous();
 611                 it.remove();
 612                 break;
 613             default: throw new AssertionError();
 614             }
 615             if (isEmpty) {
 616                 check(deq.peekLast() == null);
 617                 THROWS(NoSuchElementException.class,
 618                        new Fun(){void f(){ deq.getLast(); }});
 619             } else {
 620                 check(deq.peekLast() != e);
 621                 check(deq.getLast() != e);
 622             }
 623             check(!deq.contains(e));
 624             equal(new ArrayList<Integer>(deq), originalContents);
 625 
 626             // Test operations on empty deque
 627             switch (rnd.nextInt(isList ? 4 : 2)) {
 628             case 0: deq.clear(); break;
 629             case 1:
 630                 Iterator it = deq.iterator();
 631                 while (it.hasNext()) {
 632                     it.next();
 633                     it.remove();
 634                 }
 635                 break;
 636             case 2: asList.subList(0, asList.size()).clear(); break;
 637             case 3:
 638                 ListIterator lit = asList.listIterator(asList.size());
 639                 while (lit.hasPrevious()) {
 640                     lit.previous();
 641                     lit.remove();
 642                 }
 643                 break;
 644             default: throw new AssertionError();
 645             }
 646             testEmptyCollection(deq);
 647             check(!deq.iterator().hasNext());
 648             if (isList) {
 649                 check(!asList.listIterator().hasPrevious());
 650                 THROWS(NoSuchElementException.class,
 651                        new Fun(){void f(){ asList.listIterator().previous(); }});
 652             }
 653             THROWS(NoSuchElementException.class,
 654                    new Fun(){void f(){ deq.iterator().next(); }},
 655                    new Fun(){void f(){ deq.element(); }},
 656                    new Fun(){void f(){ deq.getFirst(); }},
 657                    new Fun(){void f(){ deq.getLast(); }},
 658                    new Fun(){void f(){ deq.pop(); }},
 659                    new Fun(){void f(){ deq.remove(); }},
 660                    new Fun(){void f(){ deq.removeFirst(); }},
 661                    new Fun(){void f(){ deq.removeLast(); }});
 662 
 663             check(deq.poll() == null);
 664             check(deq.pollFirst() == null);
 665             check(deq.pollLast() == null);
 666             check(deq.peek() == null);
 667             check(deq.peekFirst() == null);
 668             check(deq.peekLast() == null);
 669             check(!deq.removeFirstOccurrence(e));
 670             check(!deq.removeLastOccurrence(e));
 671 
 672             check(deq.addAll(originalContents) == !isEmpty);
 673             equal(new ArrayList<Integer>(deq), originalContents);
 674             check(!deq.addAll(Collections.<Integer>emptyList()));
 675             equal(new ArrayList<Integer>(deq), originalContents);
 676         }
 677     }
 678 
 679     private static void testQueueIteratorRemove(Queue<Integer> q) {
 680         System.err.printf("testQueueIteratorRemove %s%n",
 681                           q.getClass().getSimpleName());
 682         q.clear();
 683         for (int i = 0; i < 5; i++)
 684             q.add(i);
 685         Iterator<Integer> it = q.iterator();
 686         check(it.hasNext());
 687         for (int i = 3; i >= 0; i--)
 688             q.remove(i);
 689         equal(it.next(), 0);
 690         equal(it.next(), 4);
 691 
 692         q.clear();
 693         for (int i = 0; i < 5; i++)
 694             q.add(i);
 695         it = q.iterator();
 696         equal(it.next(), 0);
 697         check(it.hasNext());
 698         for (int i = 1; i < 4; i++)
 699             q.remove(i);
 700         equal(it.next(), 1);
 701         equal(it.next(), 4);
 702     }
 703 
 704     private static void testList(final List<Integer> l) {
 705         //----------------------------------------------------------------
 706         // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
 707         // doesn't throw IndexOutOfBoundsException
 708         //----------------------------------------------------------------
 709         try {
 710             l.addAll(-1, Collections.<Integer>emptyList());
 711             fail("Expected IndexOutOfBoundsException not thrown");
 712         }
 713         catch (UnsupportedOperationException ignored) {/* OK */}
 714         catch (IndexOutOfBoundsException ignored) {/* OK */}
 715         catch (Throwable t) { unexpected(t); }
 716 
 717 //      equal(l instanceof Serializable,
 718 //            l.subList(0,0) instanceof Serializable);
 719         if (l.subList(0,0) instanceof Serializable)
 720             check(l instanceof Serializable);
 721 
 722         equal(l instanceof RandomAccess,
 723               l.subList(0,0) instanceof RandomAccess);
 724     }
 725 
 726     private static void testCollection(Collection<Integer> c) {
 727         try { testCollection1(c); }
 728         catch (Throwable t) { unexpected(t); }
 729     }
 730 
 731     private static void testCollection1(Collection<Integer> c) {
 732 
 733         System.out.println("\n==> " + c.getClass().getName());
 734 
 735         checkFunctionalInvariants(c);
 736 
 737         if (! supportsAdd(c)) return;
 738         //System.out.println("add() supported");
 739 
 740         if (c instanceof NavigableSet) {
 741             System.out.println("NavigableSet tests...");
 742 
 743             NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
 744             testNavigableSet(ns);
 745             testNavigableSet(ns.headSet(6, false));
 746             testNavigableSet(ns.headSet(5, true));
 747             testNavigableSet(ns.tailSet(0, false));
 748             testNavigableSet(ns.tailSet(1, true));
 749             testNavigableSet(ns.subSet(0, false, 5, true));
 750             testNavigableSet(ns.subSet(1, true, 6, false));
 751         }
 752 
 753         if (c instanceof Queue)
 754             testQueue((Queue<Integer>)c);
 755 
 756         if (c instanceof List)
 757             testList((List<Integer>)c);
 758 
 759         check(supportsRemove(c));
 760 
 761         try {
 762             oneElement(c);
 763             checkFunctionalInvariants(c);
 764         }
 765         catch (Throwable t) { unexpected(t); }
 766 
 767         clear(c);      testNullElement(c);
 768         oneElement(c); testNullElement(c);
 769 
 770         clear(c);      testStringElement(c);
 771         oneElement(c); testStringElement(c);
 772 
 773         if (c.getClass().getName().matches(".*concurrent.*"))
 774             testConcurrentCollection(c);
 775 
 776         //----------------------------------------------------------------
 777         // The "all" operations should throw NPE when passed null
 778         //----------------------------------------------------------------
 779         {
 780             clear(c);
 781             try {
 782                 c.removeAll(null);
 783                 fail("Expected NullPointerException");
 784             }
 785             catch (NullPointerException e) { pass(); }
 786             catch (Throwable t) { unexpected(t); }
 787 
 788             oneElement(c);
 789             try {
 790                 c.removeAll(null);
 791                 fail("Expected NullPointerException");
 792             }
 793             catch (NullPointerException e) { pass(); }
 794             catch (Throwable t) { unexpected(t); }
 795 
 796             clear(c);
 797             try {
 798                 c.retainAll(null);
 799                 fail("Expected NullPointerException");
 800             }
 801             catch (NullPointerException e) { pass(); }
 802             catch (Throwable t) { unexpected(t); }
 803 
 804             oneElement(c);
 805             try {
 806                 c.retainAll(null);
 807                 fail("Expected NullPointerException");
 808             }
 809             catch (NullPointerException e) { pass(); }
 810             catch (Throwable t) { unexpected(t); }
 811 
 812             oneElement(c);
 813             try {
 814                 c.addAll(null);
 815                 fail("Expected NullPointerException");
 816             }
 817             catch (NullPointerException e) { pass(); }
 818             catch (Throwable t) { unexpected(t); }
 819 
 820             oneElement(c);
 821             try {
 822                 c.containsAll(null);
 823                 fail("Expected NullPointerException");
 824             }
 825             catch (NullPointerException e) { pass(); }
 826             catch (Throwable t) { unexpected(t); }
 827         }
 828     }
 829 
 830     //----------------------------------------------------------------
 831     // Map
 832     //----------------------------------------------------------------
 833     private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
 834         check(m.keySet().size() == m.entrySet().size());
 835         check(m.keySet().size() == m.size());
 836         checkFunctionalInvariants(m.keySet());
 837         checkFunctionalInvariants(m.values());
 838         check(m.size() != 0 ^ m.isEmpty());
 839     }
 840 
 841     private static void testMap(Map<Integer,Integer> m) {
 842         System.out.println("\n==> " + m.getClass().getName());
 843 
 844         if (m instanceof ConcurrentMap)
 845             testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
 846 
 847         if (m instanceof NavigableMap) {
 848             System.out.println("NavigableMap tests...");
 849 
 850             NavigableMap<Integer,Integer> nm =
 851                 (NavigableMap<Integer,Integer>) m;
 852             testNavigableMapRemovers(nm);
 853             testNavigableMap(nm);
 854             testNavigableMap(nm.headMap(6, false));
 855             testNavigableMap(nm.headMap(5, true));
 856             testNavigableMap(nm.tailMap(0, false));
 857             testNavigableMap(nm.tailMap(1, true));
 858             testNavigableMap(nm.subMap(1, true, 6, false));
 859             testNavigableMap(nm.subMap(0, false, 5, true));
 860         }
 861 
 862         checkFunctionalInvariants(m);
 863 
 864         if (supportsClear(m)) {
 865             try { clear(m); }
 866             catch (Throwable t) { unexpected(t); }
 867         }
 868 
 869         if (supportsPut(m)) {
 870             try {
 871                 check(m.put(3333, 77777) == null);
 872                 check(m.put(9134, 74982) == null);
 873                 check(m.get(9134) == 74982);
 874                 check(m.put(9134, 1382) == 74982);
 875                 check(m.get(9134) == 1382);
 876                 check(m.size() == 2);
 877                 checkFunctionalInvariants(m);
 878                 checkNPEConsistency(m);
 879             }
 880             catch (Throwable t) { unexpected(t); }
 881         }
 882     }
 883 
 884     private static boolean supportsPut(Map<Integer,Integer> m) {
 885         // We're asking for .equals(...) semantics
 886         if (m instanceof IdentityHashMap) return false;
 887 
 888         try { check(m.put(778347983,12735) == null); }
 889         catch (UnsupportedOperationException t) { return false; }
 890         catch (Throwable t) { unexpected(t); }
 891 
 892         try {
 893             check(m.containsKey(778347983));
 894             check(m.remove(778347983) != null);
 895         } catch (Throwable t) { unexpected(t); }
 896         return true;
 897     }
 898 
 899     private static boolean supportsClear(Map<?,?> m) {
 900         try { m.clear(); }
 901         catch (UnsupportedOperationException t) { return false; }
 902         catch (Throwable t) { unexpected(t); }
 903         return true;
 904     }
 905 
 906     //----------------------------------------------------------------
 907     // ConcurrentMap
 908     //----------------------------------------------------------------
 909     private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
 910         System.out.println("ConcurrentMap tests...");
 911 
 912         try {
 913             clear(m);
 914 
 915             check(m.putIfAbsent(18357,7346) == null);
 916             check(m.containsKey(18357));
 917             check(m.putIfAbsent(18357,8263) == 7346);
 918             try { m.putIfAbsent(18357,null); fail("NPE"); }
 919             catch (NullPointerException t) { }
 920             check(m.containsKey(18357));
 921 
 922             check(! m.replace(18357,8888,7777));
 923             check(m.containsKey(18357));
 924             try { m.replace(18357,null,7777); fail("NPE"); }
 925             catch (NullPointerException t) { }
 926             check(m.containsKey(18357));
 927             check(m.get(18357) == 7346);
 928             check(m.replace(18357,7346,5555));
 929             check(m.replace(18357,5555,7346));
 930             check(m.get(18357) == 7346);
 931 
 932             check(m.replace(92347,7834) == null);
 933             try { m.replace(18357,null); fail("NPE"); }
 934             catch (NullPointerException t) { }
 935             check(m.replace(18357,7346) == 7346);
 936             check(m.replace(18357,5555) == 7346);
 937             check(m.get(18357) == 5555);
 938             check(m.replace(18357,7346) == 5555);
 939             check(m.get(18357) == 7346);
 940 
 941             check(! m.remove(18357,9999));
 942             check(m.get(18357) == 7346);
 943             check(m.containsKey(18357));
 944             check(! m.remove(18357,null)); // 6272521
 945             check(m.get(18357) == 7346);
 946             check(m.remove(18357,7346));
 947             check(m.get(18357) == null);
 948             check(! m.containsKey(18357));
 949             check(m.isEmpty());
 950 
 951             m.putIfAbsent(1,2);
 952             check(m.size() == 1);
 953             check(! m.remove(1,null));
 954             check(! m.remove(1,null));
 955             check(! m.remove(1,1));
 956             check(m.remove(1,2));
 957             check(m.isEmpty());
 958 
 959             testEmptyMap(m);
 960         }
 961         catch (Throwable t) { unexpected(t); }
 962     }
 963 
 964     private static void throwsConsistently(Class<? extends Throwable> k,
 965                                            Iterable<Fun> fs) {
 966         List<Class<? extends Throwable>> threw
 967             = new ArrayList<Class<? extends Throwable>>();
 968         for (Fun f : fs)
 969             try { f.f(); threw.add(null); }
 970             catch (Throwable t) {
 971                 check(k.isAssignableFrom(t.getClass()));
 972                 threw.add(t.getClass());
 973             }
 974         if (new HashSet<Object>(threw).size() != 1)
 975             fail(threw.toString());
 976     }
 977 
 978     private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
 979         m.clear();
 980         final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
 981             ? (ConcurrentMap<T,Integer>) m
 982             : null;
 983         List<Fun> fs = new ArrayList<Fun>();
 984         fs.add(new Fun(){void f(){ check(! m.containsKey(null));}});
 985         fs.add(new Fun(){void f(){ equal(m.remove(null), null);}});
 986         fs.add(new Fun(){void f(){ equal(m.get(null), null);}});
 987         if (cm != null) {
 988             fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});}
 989         throwsConsistently(NullPointerException.class, fs);
 990 
 991         fs.clear();
 992         final Map<T,Integer> sm = singletonMap(null,1);
 993         fs.add(new Fun(){void f(){ equal(m.put(null,1), null); m.clear();}});
 994         fs.add(new Fun(){void f(){ m.putAll(sm); m.clear();}});
 995         if (cm != null) {
 996             fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});
 997             fs.add(new Fun(){void f(){ equal(cm.putIfAbsent(null,1), 1);}});
 998             fs.add(new Fun(){void f(){ equal(cm.replace(null,1), null);}});
 999             fs.add(new Fun(){void f(){ equal(cm.replace(null,1, 1), 1);}});
1000         }
1001         throwsConsistently(NullPointerException.class, fs);
1002     }
1003 
1004     //----------------------------------------------------------------
1005     // NavigableMap
1006     //----------------------------------------------------------------
1007     private static void
1008         checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1009                               Integer i,
1010                               Integer lower,
1011                               Integer floor,
1012                               Integer ceiling,
1013                               Integer higher) {
1014         equal(m.lowerKey(i),   lower);
1015         equal(m.floorKey(i),   floor);
1016         equal(m.ceilingKey(i), ceiling);
1017         equal(m.higherKey(i),  higher);
1018     }
1019 
1020     private static void
1021         checkNavigableSetKeys(NavigableSet<Integer> m,
1022                               Integer i,
1023                               Integer lower,
1024                               Integer floor,
1025                               Integer ceiling,
1026                               Integer higher) {
1027         equal(m.lower(i),   lower);
1028         equal(m.floor(i),   floor);
1029         equal(m.ceiling(i), ceiling);
1030         equal(m.higher(i),  higher);
1031     }
1032 
1033     static final Random rnd = new Random();
1034     static void equalNext(final Iterator<?> it, Object expected) {
1035         if (rnd.nextBoolean())
1036             check(it.hasNext());
1037         equal(it.next(), expected);
1038     }
1039 
1040     static void equalMaps(Map m1, Map m2) {
1041         equal(m1, m2);
1042         equal(m2, m1);
1043         equal(m1.size(), m2.size());
1044         equal(m1.isEmpty(), m2.isEmpty());
1045         equal(m1.toString(), m2.toString());
1046         check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1047     }
1048 
1049     @SuppressWarnings({"unchecked", "rawtypes"})
1050     static void testNavigableMapRemovers(NavigableMap m)
1051     {
1052         final Map emptyMap = new HashMap();
1053 
1054         final Map singletonMap = new HashMap();
1055         singletonMap.put(1, 2);
1056 
1057         abstract class NavigableMapView {
1058             abstract NavigableMap view(NavigableMap m);
1059         }
1060 
1061         NavigableMapView[] views = {
1062             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1063                 return m; }},
1064             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1065                 return m.headMap(99, true); }},
1066             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1067                 return m.tailMap(-99, false); }},
1068             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1069                 return m.subMap(-99, true, 99, false); }},
1070         };
1071 
1072         abstract class Remover {
1073             abstract void remove(NavigableMap m, Object k, Object v);
1074         }
1075 
1076         Remover[] removers = {
1077             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1078                 equal(m.remove(k), v); }},
1079 
1080             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1081                 equal(m.descendingMap().remove(k), v); }},
1082             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1083                 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1084             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1085                 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1086 
1087             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1088                 equal(m.headMap(86, true).remove(k), v); }},
1089             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1090                 equal(m.tailMap(-86, true).remove(k), v); }},
1091             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1092                 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1093 
1094             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1095                 check(m.keySet().remove(k)); }},
1096             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1097                 check(m.navigableKeySet().remove(k)); }},
1098 
1099             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1100                 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1101             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1102                 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1103             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1104                 check(m.navigableKeySet().subSet(-86, true, 86, false)
1105                       .remove(k)); }},
1106 
1107             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1108                 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1109             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1110                 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1111             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1112                 check(m.descendingKeySet().subSet(86, true, -86, false)
1113                       .remove(k)); }},
1114         };
1115 
1116         for (NavigableMapView view : views) {
1117             for (Remover remover : removers) {
1118                 try {
1119                     m.clear();
1120                     equalMaps(m, emptyMap);
1121                     equal(m.put(1, 2), null);
1122                     equalMaps(m, singletonMap);
1123                     NavigableMap v = view.view(m);
1124                     remover.remove(v, 1, 2);
1125                     equalMaps(m, emptyMap);
1126                 } catch (Throwable t) { unexpected(t); }
1127             }
1128         }
1129     }
1130 
1131     private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1132     {
1133         clear(m);
1134         checkNavigableMapKeys(m, 1, null, null, null, null);
1135 
1136         equal(m.put(1, 2), null);
1137         equal(m.put(3, 4), null);
1138         equal(m.put(5, 9), null);
1139 
1140         equal(m.put(1, 2), 2);
1141         equal(m.put(3, 4), 4);
1142         equal(m.put(5, 6), 9);
1143 
1144         checkNavigableMapKeys(m, 0, null, null,    1,    1);
1145         checkNavigableMapKeys(m, 1, null,    1,    1,    3);
1146         checkNavigableMapKeys(m, 2,    1,    1,    3,    3);
1147         checkNavigableMapKeys(m, 3,    1,    3,    3,    5);
1148         checkNavigableMapKeys(m, 5,    3,    5,    5, null);
1149         checkNavigableMapKeys(m, 6,    5,    5, null, null);
1150 
1151         for (final Iterator<Integer> it :
1152                  (Iterator<Integer>[])
1153                  new Iterator<?>[] {
1154                      m.descendingKeySet().iterator(),
1155                      m.navigableKeySet().descendingIterator()}) {
1156             equalNext(it, 5);
1157             equalNext(it, 3);
1158             equalNext(it, 1);
1159             check(! it.hasNext());
1160             THROWS(NoSuchElementException.class,
1161                    new Fun(){void f(){it.next();}});
1162         }
1163 
1164         {
1165             final Iterator<Map.Entry<Integer,Integer>> it
1166                 = m.descendingMap().entrySet().iterator();
1167             check(it.hasNext()); equal(it.next().getKey(), 5);
1168             check(it.hasNext()); equal(it.next().getKey(), 3);
1169             check(it.hasNext()); equal(it.next().getKey(), 1);
1170             check(! it.hasNext());
1171             THROWS(NoSuchElementException.class,
1172                    new Fun(){void f(){it.next();}});
1173         }
1174     }
1175 
1176 
1177     private static void testNavigableSet(NavigableSet<Integer> s) {
1178         clear(s);
1179         checkNavigableSetKeys(s, 1, null, null, null, null);
1180 
1181         check(s.add(1));
1182         check(s.add(3));
1183         check(s.add(5));
1184 
1185         check(! s.add(1));
1186         check(! s.add(3));
1187         check(! s.add(5));
1188 
1189         checkNavigableSetKeys(s, 0, null, null,    1,    1);
1190         checkNavigableSetKeys(s, 1, null,    1,    1,    3);
1191         checkNavigableSetKeys(s, 2,    1,    1,    3,    3);
1192         checkNavigableSetKeys(s, 3,    1,    3,    3,    5);
1193         checkNavigableSetKeys(s, 5,    3,    5,    5, null);
1194         checkNavigableSetKeys(s, 6,    5,    5, null, null);
1195 
1196         for (final Iterator<Integer> it :
1197                  (Iterator<Integer>[])
1198                  new Iterator<?>[] {
1199                      s.descendingIterator(),
1200                      s.descendingSet().iterator()}) {
1201             equalNext(it, 5);
1202             equalNext(it, 3);
1203             equalNext(it, 1);
1204             check(! it.hasNext());
1205             THROWS(NoSuchElementException.class,
1206                    new Fun(){void f(){it.next();}});
1207         }
1208     }
1209 
1210     //--------------------- Infrastructure ---------------------------
1211     static volatile int passed = 0, failed = 0;
1212     static void pass() { passed++; }
1213     static void fail() { failed++; Thread.dumpStack(); }
1214     static void fail(String msg) { System.out.println(msg); fail(); }
1215     static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1216     static void check(boolean cond) { if (cond) pass(); else fail(); }
1217     static void equal(Object x, Object y) {
1218         if (x == null ? y == null : x.equals(y)) pass();
1219         else {System.out.println(x + " not equal to " + y); fail();}}
1220     static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1221     public static void main(String[] args) throws Throwable {
1222         try { realMain(args); } catch (Throwable t) { unexpected(t); }
1223 
1224         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1225         if (failed > 0) throw new Exception("Some tests failed");
1226     }
1227     private static abstract class Fun {abstract void f() throws Throwable;}
1228     private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1229           for (Fun f : fs)
1230               try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1231               catch (Throwable t) {
1232                   if (k.isAssignableFrom(t.getClass())) pass();
1233                   else unexpected(t);}}
1234     static byte[] serializedForm(Object obj) {
1235         try {
1236             ByteArrayOutputStream baos = new ByteArrayOutputStream();
1237             new ObjectOutputStream(baos).writeObject(obj);
1238             return baos.toByteArray();
1239         } catch (IOException e) { throw new Error(e); }}
1240     static Object readObject(byte[] bytes)
1241         throws IOException, ClassNotFoundException {
1242         InputStream is = new ByteArrayInputStream(bytes);
1243         return new ObjectInputStream(is).readObject();}
1244     @SuppressWarnings("unchecked")
1245     static <T> T serialClone(T obj) {
1246         try { return (T) readObject(serializedForm(obj)); }
1247         catch (Exception e) { throw new Error(e); }}
1248     private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1249         ArrayList<E> list = new ArrayList<>();
1250         public boolean remove(Object obj) {
1251             return list.remove(obj);
1252         }
1253         public boolean add(E e) {
1254             return list.add(e);
1255         }
1256         public Iterator<E> iterator() {
1257             return list.iterator();
1258         }
1259         public int size() {
1260             return list.size();
1261         }
1262     }
1263     private static class NewAbstractSet<E> extends AbstractSet<E> {
1264         HashSet<E> set = new HashSet<>();
1265         public boolean remove(Object obj) {
1266             return set.remove(obj);
1267         }
1268         public boolean add(E e) {
1269             return set.add(e);
1270         }
1271         public Iterator<E> iterator() {
1272             return set.iterator();
1273         }
1274         public int size() {
1275             return set.size();
1276         }
1277     }
1278 
1279 }