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