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