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