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 }