1 /*
2 * Copyright (c) 2005, 2025, 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 8193128 8327858 8368178 8371164
30 * @summary Run many tests on many Collection and Map implementations
31 * @author Martin Buchholz
32 * @modules java.base/java.util:open
33 * @enablePreview
34 * @run main MOAT
35 * @key randomness
36 */
37
38 /* Mother Of All (Collection) Tests
39 *
40 * Testing of collection classes is often spotty, because many tests
41 * need to be performed on many implementations, but the onus on
42 * writing the tests falls on the engineer introducing the new
43 * implementation.
44 *
45 * The idea of this mega-test is that:
46 *
47 * An engineer adding a new collection implementation could simply add
48 * their new implementation to a list of implementations in this
49 * test's main method. Any general purpose Collection<Integer> or
50 * Map<Integer,Integer> class is appropriate.
51 *
52 * An engineer fixing a regression could add their regression test here and
53 * simultaneously test all other implementations.
54 */
55
56 import java.io.*;
57 import java.util.*;
58 import java.util.concurrent.*;
59 import static java.util.Collections.*;
60 import java.lang.reflect.*;
61 import java.util.stream.Collectors;
62 import java.util.stream.Stream;
63
64 public class MOAT {
65 // Collections under test must not be initialized to contain this value,
66 // and maps under test must not contain this value as a key.
67 // It's used as a sentinel for absent-element testing.
68 static final int ABSENT_VALUE = 778347983;
69
70 static final Integer[] integerArray;
71 static {
72 Integer[] ia = new Integer[20];
73 // fill with 1..20 inclusive
74 for (int i = 0; i < ia.length; i++) {
75 ia[i] = i + 1;
76 }
77 integerArray = ia;
78 }
79
80 public static void realMain(String[] args) {
81
82 testCollection(new NewAbstractCollection<Integer>());
83 testCollection(new NewAbstractSet<Integer>());
84 testCollection(new LinkedHashSet<Integer>());
85 testCollection(new HashSet<Integer>());
86 testCollection(new Vector<Integer>());
87 testCollection(new Vector<Integer>().subList(0,0));
88 testCollection(new ArrayDeque<Integer>());
89 testCollection(new ArrayList<Integer>());
90 testCollection(new ArrayList<Integer>().subList(0,0));
91 testCollection(new LinkedList<Integer>());
92 testCollection(new LinkedList<Integer>().subList(0,0));
93 testCollection(new TreeSet<Integer>());
94 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
95 testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
96 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
97 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
98 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
99 testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
100 testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));
101 testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>()));
102
103 testCollection(new CopyOnWriteArrayList<Integer>());
104 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
105 testCollection(new CopyOnWriteArraySet<Integer>());
106 testCollection(new PriorityQueue<Integer>());
107 testCollection(new PriorityBlockingQueue<Integer>());
108 testCollection(new ArrayBlockingQueue<Integer>(20));
109 testCollection(new LinkedBlockingQueue<Integer>(20));
110 testCollection(new LinkedBlockingDeque<Integer>(20));
111 testCollection(new ConcurrentLinkedDeque<Integer>());
112 testCollection(new ConcurrentLinkedQueue<Integer>());
113 testCollection(new LinkedTransferQueue<Integer>());
114 testCollection(new ConcurrentSkipListSet<Integer>());
115 testCollection(Arrays.asList(new Integer(42)));
116 testCollection(Arrays.asList(1,2,3));
117 testCollection(nCopies(25,1));
118 testImmutableList(nCopies(25,1));
119
120 testMap(new HashMap<Integer,Integer>());
121 testMap(new LinkedHashMap<Integer,Integer>());
122
123 // TODO: Add reliable support for WeakHashMap.
124 // This test is subject to very rare failures because the GC
125 // may remove unreferenced-keys from the map at any time.
126 // testMap(new WeakHashMap<Integer,Integer>());
127
128 testMap(new IdentityHashMap<Integer,Integer>());
129 testMap(new TreeMap<Integer,Integer>());
130 testMap(new Hashtable<Integer,Integer>());
131 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
132 testMap(new ConcurrentSkipListMap<Integer,Integer>());
133 testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));
134 testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
135 testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
136 testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));
137 testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));
138 testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));
139
140 // Unmodifiable wrappers
141 testImmutableSet(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))), 99);
142 testImmutableSet(AccessFlag.maskToAccessFlags(0, AccessFlag.Location.CLASS), AccessFlag.ABSTRACT);
143 testImmutableSet(AccessFlag.maskToAccessFlags(Modifier.PUBLIC | Modifier.STATIC | Modifier.SYNCHRONIZED, AccessFlag.Location.METHOD), AccessFlag.ABSTRACT);
144 testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
145 testImmutableMap(unmodifiableMap(Collections.singletonMap(1,2)));
146 testImmutableSeqColl(unmodifiableSequencedCollection(Arrays.asList(1,2,3)), 99);
147 testImmutableSeqColl(unmodifiableSequencedSet(new LinkedHashSet<>(Arrays.asList(1,2,3))), 99);
148 var lhm = new LinkedHashMap<Integer,Integer>(); lhm.put(1,2); lhm.put(3, 4);
149 testImmutableSeqMap(unmodifiableSequencedMap(lhm));
150 testCollMutatorsAlwaysThrow(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))));
151 testCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));
152 testEmptyCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));
153 testListMutatorsAlwaysThrow(unmodifiableList(Arrays.asList(1,2,3)));
154 testListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));
155 testEmptyListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));
156 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.singletonMap(1,2)));
157 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));
158 testEmptyMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));
159
160 // Empty collections
161 final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
162 testCollection(emptyArray);
163 testEmptyList(emptyArray);
164 THROWS(IndexOutOfBoundsException.class, () -> emptyArray.set(0,1));
165 THROWS(UnsupportedOperationException.class, () -> emptyArray.add(0,1));
166
167 List<Integer> noOne = nCopies(0,1);
168 testCollection(noOne);
169 testEmptyList(noOne);
170 testImmutableList(noOne);
171
172 Set<Integer> emptySet = emptySet();
173 testCollection(emptySet);
174 testEmptySet(emptySet);
175 testEmptySet(EMPTY_SET);
176 testEmptySet(Collections.emptySet());
177 testEmptySet(Collections.emptySortedSet());
178 testEmptySet(Collections.emptyNavigableSet());
179 testImmutableSet(emptySet, 99);
180
181 List<Integer> emptyList = emptyList();
182 testCollection(emptyList);
183 testEmptyList(emptyList);
184 testEmptyList(EMPTY_LIST);
185 testEmptyList(Collections.emptyList());
186 testImmutableList(emptyList);
187
188 Map<Integer,Integer> emptyMap = emptyMap();
189 testMap(emptyMap);
190 testEmptyMap(emptyMap);
191 testEmptyMap(EMPTY_MAP);
192 testEmptyMap(Collections.emptyMap());
193 testEmptyMap(Collections.emptySortedMap());
194 testEmptyMap(Collections.emptyNavigableMap());
195 testImmutableMap(emptyMap);
196 testImmutableMap(Collections.emptyMap());
197 testImmutableMap(Collections.emptySortedMap());
198 testImmutableMap(Collections.emptyNavigableMap());
199
200 // Singleton collections
201 Set<Integer> singletonSet = singleton(1);
202 equal(singletonSet.size(), 1);
203 testCollection(singletonSet);
204 testImmutableSet(singletonSet, 99);
205
206 List<Integer> singletonList = singletonList(1);
207 equal(singletonList.size(), 1);
208 testCollection(singletonList);
209 testImmutableList(singletonList);
210 testImmutableList(singletonList.subList(0,1));
211 testImmutableList(singletonList.subList(0,1).subList(0,1));
212 testEmptyList(singletonList.subList(0,0));
213 testEmptyList(singletonList.subList(0,0).subList(0,0));
214
215 Map<Integer,Integer> singletonMap = singletonMap(1,2);
216 equal(singletonMap.size(), 1);
217 testMap(singletonMap);
218 testImmutableMap(singletonMap);
219
220 // Immutable List
221 testEmptyList(List.of());
222 testEmptyList(List.of().subList(0,0));
223 testEmptyList(List.ofLazy(0, i -> i));
224 testEmptyList(List.ofLazy(3, i -> i).subList(0, 0));
225 testListMutatorsAlwaysThrow(List.of());
226 testListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
227 testListMutatorsAlwaysThrow(List.ofLazy(0, i -> i));
228 testEmptyListMutatorsAlwaysThrow(List.of());
229 testEmptyListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
230 testEmptyListMutatorsAlwaysThrow(List.ofLazy(0, i -> i));
231 testEmptyListMutatorsAlwaysThrow(List.ofLazy(3, i -> i).subList(0, 0));
232 for (List<Integer> list : Arrays.asList(
233 List.<Integer>of(),
234 List.of(1),
235 List.of(1, 2),
236 List.of(1, 2, 3),
237 List.of(1, 2, 3, 4),
238 List.of(1, 2, 3, 4, 5),
239 List.of(1, 2, 3, 4, 5, 6),
240 List.of(1, 2, 3, 4, 5, 6, 7),
241 List.of(1, 2, 3, 4, 5, 6, 7, 8),
242 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
243 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
244 List.of(integerArray),
245 Stream.<Integer>empty().toList(),
246 Stream.of(1).toList(),
247 Stream.of(1, 2).toList(),
248 Stream.of(1, 2, 3).toList(),
249 Stream.of(1, 2, 3, 4).toList(),
250 Stream.of((Integer)null).toList(),
251 Stream.of(1, null).toList(),
252 Stream.of(1, null, 3).toList(),
253 Stream.of(1, null, 3, 4).toList(),
254 List.ofLazy(0, i -> i),
255 List.ofLazy(3, i -> i),
256 List.ofLazy(10, i -> i))) {
257 testCollection(list);
258 testImmutableList(list);
259 testListMutatorsAlwaysThrow(list);
260 testImmutableListMutatorsAlwaysThrow(list);
261 if (list.size() >= 1) {
262 // test subLists
263 List<Integer> headList = list.subList(0, list.size() - 1);
264 List<Integer> tailList = list.subList(1, list.size());
265 testCollection(headList);
266 testCollection(tailList);
267 testImmutableList(headList);
268 testImmutableList(tailList);
269 testListMutatorsAlwaysThrow(headList);
270 testListMutatorsAlwaysThrow(tailList);
271 }
272 }
273
274 List<Integer> listCopy = List.copyOf(Arrays.asList(1, 2, 3));
275 testCollection(listCopy);
276 testImmutableList(listCopy);
277 testListMutatorsAlwaysThrow(listCopy);
278
279 List<Integer> listCollected = Stream.of(1, 2, 3).collect(Collectors.toUnmodifiableList());
280 equal(listCollected, List.of(1, 2, 3));
281 testCollection(listCollected);
282 testImmutableList(listCollected);
283 testListMutatorsAlwaysThrow(listCollected);
284
285 // List indexOf / lastIndexOf
286
287 // 0 element
288 System.out.println("testListIndexOf size 0");
289 testListIndexOf(-1, -1);
290
291 System.out.println("testListIndexOf size 1");
292 testListIndexOf(-1, -1, 0);
293 testListIndexOf(0, 0, 1);
294
295 System.out.println("testListIndexOf size 2");
296 testListIndexOf(-1, -1, 0, 0);
297 testListIndexOf(0, 0, 1, 0);
298 testListIndexOf(0, 1, 1, 1);
299 testListIndexOf(1, 1, 0, 1);
300
301
302 System.out.println("testListIndexOf size 3");
303 testListIndexOf(-1, -1, 0, 0, 0);
304 testListIndexOf(0, 0, 1, 0, 0);
305 testListIndexOf(0, 1, 1, 1, 0);
306 testListIndexOf(1, 2, 0, 1, 1);
307 testListIndexOf(2, 2, 0, 0, 1);
308
309 System.out.println("testListIndexOf size N");
310 testListIndexOf(-1, -1, 0, 0, 0, 0, 0, 0, 0);
311 testListIndexOf(2, 6, 0, 0, 1, 0, 1, 0, 1);
312 testListIndexOf(4, 4, 0, 0, 0, 0, 1, 0, 0);
313 testListIndexOf(0, 6, 1, 1, 1, 1, 1, 1, 1);
314 testListIndexOf(0, 7, 1, 1, 1, 1, 1, 1, 1, 1);
315 testListIndexOf(0, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1);
316 testListIndexOf(0, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
317 testListIndexOf(0, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
318 testListIndexOf(0, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
319 testListIndexOf(0, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
320 testListIndexOf(12, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1);
321 testListIndexOf(-1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
322
323 // Immutable Set
324 testEmptySet(Set.of());
325 testCollMutatorsAlwaysThrow(Set.of());
326 testEmptyCollMutatorsAlwaysThrow(Set.of());
327 for (Set<Integer> set : Arrays.asList(
328 Set.<Integer>of(),
329 Set.of(1),
330 Set.of(1, 2),
331 Set.of(1, 2, 3),
332 Set.of(1, 2, 3, 4),
333 Set.of(1, 2, 3, 4, 5),
334 Set.of(1, 2, 3, 4, 5, 6),
335 Set.of(1, 2, 3, 4, 5, 6, 7),
336 Set.of(1, 2, 3, 4, 5, 6, 7, 8),
337 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
338 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
339 Set.of(integerArray))) {
340 testCollection(set);
341 testImmutableSet(set, 99);
342 testCollMutatorsAlwaysThrow(set);
343 }
344
345 Set<Integer> setCopy = Set.copyOf(Arrays.asList(1, 2, 3));
346 testCollection(setCopy);
347 testImmutableSet(setCopy, 99);
348 testCollMutatorsAlwaysThrow(setCopy);
349
350 Set<Integer> setCollected = Stream.of(1, 1, 2, 3, 2, 3)
351 .collect(Collectors.toUnmodifiableSet());
352 equal(setCollected, Set.of(1, 2, 3));
353 testCollection(setCollected);
354 testImmutableSet(setCollected, 99);
355 testCollMutatorsAlwaysThrow(setCollected);
356
357 // Immutable Map
358
359 @SuppressWarnings("unchecked")
360 Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20];
361 for (int i = 0; i < ea.length; i++) {
362 ea[i] = Map.entry(i+1, i+101);
363 }
364
365 testEmptyMap(Map.of());
366 testMapMutatorsAlwaysThrow(Map.of());
367 testEmptyMapMutatorsAlwaysThrow(Map.of());
368 testEmptyMap(Map.ofLazy(Set.of(), k -> k));
369 testMapMutatorsAlwaysThrow(Map.ofLazy(Set.of(), k -> k));
370 testEmptyMapMutatorsAlwaysThrow(Map.ofLazy(Set.of(), k -> k));
371 for (Map<Integer,Integer> map : Arrays.asList(
372 Map.<Integer,Integer>of(),
373 Map.of(1, 101),
374 Map.of(1, 101, 2, 202),
375 Map.of(1, 101, 2, 202, 3, 303),
376 Map.of(1, 101, 2, 202, 3, 303, 4, 404),
377 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505),
378 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606),
379 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707),
380 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808),
381 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909),
382 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010),
383 Map.ofEntries(ea),
384 Map.ofLazy(Set.<Integer>of(), k -> k),
385 Map.ofLazy(Set.of(1), k -> k),
386 Map.ofLazy(Set.of(1, 2, 3), k -> k))) {
387 testMap(map);
388 testImmutableMap(map);
389 testMapMutatorsAlwaysThrow(map);
390 }
391
392 Map<Integer,Integer> mapCopy = Map.copyOf(new HashMap<>(Map.of(1, 101, 2, 202, 3, 303)));
393 testMap(mapCopy);
394 testImmutableMap(mapCopy);
395 testMapMutatorsAlwaysThrow(mapCopy);
396
397 Map<Integer,Integer> mapCollected1 =
398 Stream.of(1, 2, 3)
399 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i));
400 equal(mapCollected1, Map.of(1, 101, 2, 202, 3, 303));
401 testMap(mapCollected1);
402 testImmutableMap(mapCollected1);
403 testMapMutatorsAlwaysThrow(mapCollected1);
404
405 try {
406 Stream.of(1, 1, 2, 3, 2, 3)
407 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i));
408 fail("duplicates should have thrown an exception");
409 } catch (IllegalStateException ise) {
410 pass();
411 }
412
413 Map<Integer,Integer> mapCollected2 =
414 Stream.of(1, 1, 2, 3, 2, 3)
415 .collect(Collectors.toUnmodifiableMap(i -> i, i -> 101 * i, Integer::sum));
416 equal(mapCollected2, Map.of(1, 202, 2, 404, 3, 606));
417 testMap(mapCollected2);
418 testImmutableMap(mapCollected2);
419 testMapMutatorsAlwaysThrow(mapCollected2);
420 }
421
422 private static void checkContainsSelf(Collection<Integer> c) {
423 check(c.containsAll(c));
424 check(c.containsAll(Arrays.asList(c.toArray())));
425 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
426 }
427
428 private static void checkContainsEmpty(Collection<Integer> c) {
429 check(c.containsAll(new ArrayList<Integer>()));
430 }
431
432 private static void checkUnique(Set<Integer> s) {
433 for (Integer i : s) {
434 int count = 0;
435 for (Integer j : s) {
436 if (Objects.equals(i,j))
437 ++count;
438 }
439 check(count == 1);
440 }
441 }
442
443 private static <T> void testEmptyCollection(Collection<T> c) {
444 check(c.isEmpty());
445 equal(c.size(), 0);
446 equal(c.toString(),"[]");
447 equal(c.toArray().length, 0);
448 equal(c.toArray(new Object[0]).length, 0);
449 equal(c.toArray(Object[]::new).length, 0);
450 check(c.toArray(new Object[]{42})[0] == null);
451
452 Object[] a = new Object[1]; a[0] = Boolean.TRUE;
453 equal(c.toArray(a), a);
454 equal(a[0], null);
455 testEmptyIterator(c.iterator());
456 }
457
458 static <T> void testEmptyIterator(final Iterator<T> it) {
459 if (rnd.nextBoolean())
460 check(! it.hasNext());
461
462 THROWS(NoSuchElementException.class, () -> it.next());
463
464 try { it.remove(); }
465 catch (IllegalStateException ignored) { pass(); }
466 catch (UnsupportedOperationException ignored) { pass(); }
467 catch (Throwable t) { unexpected(t); }
468
469 if (rnd.nextBoolean())
470 check(! it.hasNext());
471 }
472
473 private static void testEmptyList(List<?> c) {
474 testEmptyCollection(c);
475 THROWS(NoSuchElementException.class, c::getFirst, c::getLast);
476 equal(c.hashCode(), 1);
477 equal2(c, Collections.<Integer>emptyList());
478 equal2(c, c.reversed());
479 }
480
481 private static <T> void testEmptySet(Set<T> c) {
482 testEmptyCollection(c);
483 equal(c.hashCode(), 0);
484 equal2(c, Collections.<Integer>emptySet());
485 if (c instanceof NavigableSet<?>)
486 testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
487 }
488
489 private static <T> void testImmutableCollection(final Collection<T> c, T t) {
490 THROWS(UnsupportedOperationException.class,
491 () -> c.add(t),
492 () -> c.addAll(singleton(t)));
493 if (! c.isEmpty()) {
494 final T first = c.iterator().next();
495 THROWS(UnsupportedOperationException.class,
496 () -> c.clear(),
497 () -> c.remove(first),
498 () -> c.removeAll(singleton(first)),
499 () -> c.retainAll(emptyList()));
500 } else {
501 testEmptyIterator(c.iterator());
502 }
503 testForEachMatch(c);
504 testSpliteratorMatch(c);
505 }
506
507 private static <T> void testImmutableSeqColl(final SequencedCollection<T> c, T t) {
508 SequencedCollection<T> r = c.reversed();
509 testImmutableCollection(c, t);
510 testImmutableCollection(r, t);
511 THROWS(UnsupportedOperationException.class,
512 () -> c.addFirst(t),
513 () -> c.addLast(t),
514 () -> r.addFirst(t),
515 () -> r.addLast(t));
516 if (! c.isEmpty()) {
517 THROWS(UnsupportedOperationException.class,
518 () -> c.removeFirst(),
519 () -> c.removeLast(),
520 () -> r.removeFirst(),
521 () -> r.removeLast());
522 }
523 }
524
525 private static <T> void testImmutableSet(final Set<T> c, T t) {
526 testImmutableCollection(c, t);
527 }
528
529 private static <T> void testImmutableSeqSet(final SequencedSet<T> c, T t) {
530 testImmutableSeqColl(c, t);
531 }
532
533 private static void testImmutableList(final List<Integer> c) {
534 testList(c);
535 testImmutableCollection(c, 42);
536 testImmutableSeqColl(c, 42);
537 THROWS(UnsupportedOperationException.class,
538 () -> c.set(0,42),
539 () -> c.add(0,42),
540 () -> c.addAll(0,singleton(86)));
541 if (! c.isEmpty())
542 THROWS(UnsupportedOperationException.class,
543 () -> { Iterator<Integer> it = c.iterator();
544 it.next();
545 it.remove(); },
546 () -> { ListIterator<Integer> it = c.listIterator();
547 it.next();
548 it.remove(); });
549 }
550
551 /**
552 * Test that calling a mutator always throws UOE, even if the mutator
553 * wouldn't actually do anything, given its arguments.
554 *
555 * @param c the collection instance to test
556 */
557 private static void testCollMutatorsAlwaysThrow(Collection<Integer> c) {
558 THROWS(UnsupportedOperationException.class,
559 () -> c.addAll(Collections.emptyList()),
560 () -> c.remove(ABSENT_VALUE),
561 () -> c.removeAll(Collections.emptyList()),
562 () -> c.removeIf(x -> false),
563 () -> c.retainAll(c));
564 }
565
566 // Ensures forEach supplies in the same order as the iterator
567 private static <T> void testForEachMatch(Collection<T> c) {
568 var itr = c.iterator();
569 int[] index = {0};
570 c.forEach(item -> {
571 T itrNext = null;
572 if (!itr.hasNext() || !Objects.equals(itrNext = itr.next(), item)) {
573 fail("forEach and iterator mismatch at " + index[0] + " forEach: " + item + ", itr: " + itrNext);
574 }
575 index[0]++;
576 });
577 if (itr.hasNext()) {
578 fail("forEach and iterator mismatch at tail, extras in itr");
579 }
580 }
581
582 // Ensures spliterator returns in the same order as the iterator
583 private static <T> void testSpliteratorMatch(Collection<T> c) {
584 var itr = c.iterator();
585 var split = c.spliterator();
586 int[] index = {0};
587 split.forEachRemaining(item -> {
588 T itrNext = null;
589 if (!itr.hasNext() || !Objects.equals(itrNext = itr.next(), item)) {
590 fail("iterator and spliterator mismatch at " + index[0] + " spliterator: " + item + ", itr: " + itrNext);
591 }
592 index[0]++;
593 });
594 if (itr.hasNext()) {
595 fail("iterator and spliterator mismatch at tail, extra item in itr");
596 }
597 }
598
599 /**
600 * Test that calling a mutator always throws UOE, even if the mutator
601 * wouldn't actually do anything on an empty collection.
602 *
603 * @param c the collection instance to test, must be empty
604 */
605 private static void testEmptyCollMutatorsAlwaysThrow(Collection<Integer> c) {
606 if (! c.isEmpty()) {
607 fail("collection is not empty");
608 }
609 THROWS(UnsupportedOperationException.class,
610 () -> c.clear());
611 }
612
613 /**
614 * As above, for a list.
615 *
616 * @param c the list instance to test
617 */
618 private static void testListMutatorsAlwaysThrow(List<Integer> c) {
619 testCollMutatorsAlwaysThrow(c);
620 THROWS(UnsupportedOperationException.class,
621 () -> c.addAll(0, Collections.emptyList()));
622 }
623
624 private static void testImmutableListMutatorsAlwaysThrow(List<Integer> c) {
625 THROWS(UnsupportedOperationException.class,
626 c::removeFirst,
627 c::removeLast);
628 }
629
630 /**
631 * As above, for an empty list.
632 *
633 * @param c the list instance to test, must be empty
634 */
635 private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) {
636 if (! c.isEmpty()) {
637 fail("list is not empty");
638 }
639 testEmptyCollMutatorsAlwaysThrow(c);
640 THROWS(UnsupportedOperationException.class,
641 () -> c.replaceAll(x -> x),
642 () -> c.sort(null));
643 }
644
645 /**
646 * As above, for a map.
647 *
648 * @param m the map instance to test
649 */
650 private static void testMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
651 THROWS(UnsupportedOperationException.class,
652 () -> m.compute(ABSENT_VALUE, (k, v) -> null),
653 () -> m.computeIfAbsent(ABSENT_VALUE, k -> null),
654 () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null),
655 () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null),
656 () -> m.putAll(Collections.emptyMap()),
657 () -> m.remove(ABSENT_VALUE),
658 () -> m.remove(ABSENT_VALUE, 0),
659 () -> m.replace(ABSENT_VALUE, 0),
660 () -> m.replace(ABSENT_VALUE, 0, 1));
661 }
662
663 /**
664 * As above, for an empty map.
665 *
666 * @param map the map instance to test, must be empty
667 */
668 private static void testEmptyMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
669 if (! m.isEmpty()) {
670 fail("map is not empty");
671 }
672 THROWS(UnsupportedOperationException.class,
673 () -> m.clear(),
674 () -> m.replaceAll((k, v) -> v));
675 }
676
677 private static void clear(Collection<Integer> c) {
678 try { c.clear(); }
679 catch (Throwable t) { unexpected(t); }
680 testEmptyCollection(c);
681 }
682
683 private static <K,V> void testEmptyMap(final Map<K,V> m) {
684 check(m.isEmpty());
685 equal(m.size(), 0);
686 equal(m.toString(),"{}");
687 testEmptySet(m.keySet());
688 testEmptySet(m.entrySet());
689 testEmptyCollection(m.values());
690
691 try { check(! m.containsValue(null)); }
692 catch (NullPointerException ignored) { /* OK */ }
693 try { check(! m.containsKey(null)); }
694 catch (NullPointerException ignored) { /* OK */ }
695 check(! m.containsValue(1));
696 check(! m.containsKey(1));
697 }
698
699 private static void testImmutableMapEntry(final Map.Entry<Integer,Integer> me) {
700 Integer key = me.getKey();
701 Integer val = me.getValue();
702 THROWS(UnsupportedOperationException.class,
703 () -> me.setValue(3));
704 equal(key, me.getKey());
705 equal(val, me.getValue());
706 }
707
708 private static void testImmutableMap(final Map<Integer,Integer> m) {
709 THROWS(UnsupportedOperationException.class,
710 () -> m.put(1,1),
711 () -> m.putAll(singletonMap(1,1)));
712 if (! m.isEmpty()) {
713 final Integer first = m.keySet().iterator().next();
714 THROWS(UnsupportedOperationException.class,
715 () -> m.remove(first),
716 () -> m.clear());
717 testImmutableMapEntry(m.entrySet().iterator().next());
718 }
719 testImmutableSet(m.keySet(), 99);
720 testImmutableCollection(m.values(), 99);
721 testImmutableSet(m.entrySet(), Map.entry(42, 43));
722 }
723
724 private static void testImmutableSeqMap(final SequencedMap<Integer,Integer> m) {
725 SequencedMap<Integer,Integer> r = m.reversed();
726 testImmutableMap(m);
727 testImmutableMap(r);
728 THROWS(UnsupportedOperationException.class,
729 () -> m.putFirst(0, 0),
730 () -> m.putLast(0, 0),
731 () -> r.putFirst(0, 0),
732 () -> r.putLast(0, 0));
733 if (! m.isEmpty()) {
734 THROWS(UnsupportedOperationException.class,
735 () -> m.pollFirstEntry(),
736 () -> m.pollLastEntry(),
737 () -> r.pollFirstEntry(),
738 () -> r.pollLastEntry());
739 testImmutableMapEntry(m.sequencedEntrySet().getFirst());
740 testImmutableMapEntry(r.sequencedEntrySet().getFirst());
741 testImmutableMapEntry(m.sequencedEntrySet().reversed().getFirst());
742 testImmutableMapEntry(r.sequencedEntrySet().reversed().getFirst());
743 }
744 testImmutableSeqSet(m.sequencedKeySet(), 99);
745 testImmutableSeqColl(m.sequencedValues(), 99);
746 testImmutableSeqSet(m.sequencedEntrySet(), Map.entry(42, 43));
747 testImmutableSeqSet(r.sequencedKeySet(), 99);
748 testImmutableSeqColl(r.sequencedValues(), 99);
749 testImmutableSeqSet(r.sequencedEntrySet(), Map.entry(42, 43));
750 }
751
752 private static void clear(Map<?,?> m) {
753 try { m.clear(); }
754 catch (Throwable t) { unexpected(t); }
755 testEmptyMap(m);
756 }
757
758 private static void oneElement(Collection<Integer> c) {
759 clear(c);
760 try {
761 check(c.add(-42));
762 equal(c.toString(), "[-42]");
763 if (c instanceof Set) check(! c.add(-42));
764 } catch (Throwable t) { unexpected(t); }
765 check(! c.isEmpty()); check(c.size() == 1);
766 }
767
768 private static boolean supportsAdd(Collection<Integer> c) {
769 try { check(c.add(ABSENT_VALUE)); }
770 catch (UnsupportedOperationException t) { return false; }
771 catch (Throwable t) { unexpected(t); }
772
773 try {
774 check(c.contains(ABSENT_VALUE));
775 check(c.remove(ABSENT_VALUE));
776 } catch (Throwable t) { unexpected(t); }
777 return true;
778 }
779
780 private static boolean supportsRemove(Collection<Integer> c) {
781 try { check(! c.remove(ABSENT_VALUE)); }
782 catch (UnsupportedOperationException t) { return false; }
783 catch (Throwable t) { unexpected(t); }
784 return true;
785 }
786
787 // 6260652: (coll) Arrays.asList(x).toArray().getClass()
788 // should be Object[].class
789 // Fixed in jdk9, but not jdk8 ...
790 static final boolean needToWorkAround6260652 =
791 Arrays.asList("").toArray().getClass() != Object[].class;
792
793 private static void checkFunctionalInvariants(Collection<Integer> c) {
794 try {
795 checkContainsSelf(c);
796 checkContainsEmpty(c);
797 check(c.size() != 0 ^ c.isEmpty());
798 check(! c.contains(ABSENT_VALUE));
799
800 {
801 int size = 0;
802 for (Integer i : c) size++;
803 check(c.size() == size);
804 }
805
806 if (c instanceof Set) {
807 checkUnique((Set<Integer>)c);
808 }
809
810 check(c.toArray().length == c.size());
811 check(c.toArray().getClass() == Object[].class
812 ||
813 (needToWorkAround6260652 &&
814 c.getClass().getName().equals("java.util.Arrays$ArrayList")));
815 for (int size : new int[]{0,1,c.size(), c.size()+1}) {
816 Integer[] a = c.toArray(new Integer[size]);
817 check((size > c.size()) || a.length == c.size());
818 int i = 0; for (Integer j : c) check(a[i++] == j);
819 check((size <= c.size()) || (a[c.size()] == null));
820 check(a.getClass() == Integer[].class);
821 }
822
823 {
824 Integer[] a = c.toArray(Integer[]::new);
825 equal(c.size(), a.length);
826 check(a.getClass() == Integer[].class);
827 check(Arrays.equals(c.toArray(new Integer[0]), a));
828 }
829
830 check(c.equals(c));
831 if (c instanceof Serializable) {
832 //System.out.printf("Serializing %s%n", c.getClass().getName());
833 try {
834 Object clone = serialClone(c);
835 equal(c instanceof Serializable,
836 clone instanceof Serializable);
837 equal(c instanceof RandomAccess,
838 clone instanceof RandomAccess);
839 if ((c instanceof List) || (c instanceof Set))
840 equal(c, clone);
841 else
842 equal(new HashSet<Integer>(c),
843 new HashSet<Integer>(serialClone(c)));
844 } catch (Error xxx) {
845 if (! (xxx.getCause() instanceof NotSerializableException))
846 throw xxx;
847 }
848 }
849 }
850 catch (Throwable t) { unexpected(t); }
851 }
852
853 //----------------------------------------------------------------
854 // If add(null) succeeds, contains(null) & remove(null) should succeed
855 //----------------------------------------------------------------
856 private static void testNullElement(Collection<Integer> c) {
857
858 try {
859 check(c.add(null));
860 if (c.size() == 1)
861 equal(c.toString(), "[null]");
862 try {
863 checkFunctionalInvariants(c);
864 check(c.contains(null));
865 check(c.remove(null));
866 }
867 catch (Throwable t) { unexpected(t); }
868 }
869 catch (NullPointerException e) { /* OK */ }
870 catch (Throwable t) { unexpected(t); }
871 }
872
873 //----------------------------------------------------------------
874 // If add("x") succeeds, contains("x") & remove("x") should succeed
875 //----------------------------------------------------------------
876 @SuppressWarnings("unchecked")
877 private static void testStringElement(Collection<Integer> c) {
878 Collection x = (Collection)c; // Make type-unsafe
879 try {
880 check(x.add("x"));
881 try {
882 check(x.contains("x"));
883 check(x.remove("x"));
884 } catch (Throwable t) { unexpected(t); }
885 }
886 catch (ClassCastException e) { /* OK */ }
887 catch (Throwable t) { unexpected(t); }
888 }
889
890 private static void testAddAll(Collection<Integer> c) {
891 clear(c);
892
893 // Test ArrayList source
894 ArrayList<Integer> arrayListSource = new ArrayList<>();
895 arrayListSource.add(42);
896 arrayListSource.add(99);
897 check(c.addAll(arrayListSource));
898 equal(c.size(), arrayListSource.size());
899 check(c.containsAll(arrayListSource));
900
901 clear(c);
902
903 // Test non-ArrayList source
904 LinkedList<Integer> linkedListSource = new LinkedList<>();
905 linkedListSource.add(77);
906 linkedListSource.add(88);
907 check(c.addAll(linkedListSource));
908 equal(c.size(), linkedListSource.size());
909 check(c.containsAll(linkedListSource));
910 }
911
912 private static void testConcurrentCollection(Collection<Integer> c) {
913 try {
914 c.add(1);
915 Iterator<Integer> it = c.iterator();
916 check(it.hasNext());
917 clear(c);
918 check(it.next() instanceof Integer); // No CME
919 check(c.isEmpty());
920 }
921 catch (Throwable t) { unexpected(t); }
922 }
923
924 private static void testQueue(Queue<Integer> q) {
925 q.clear();
926 for (int i = 0; i < 5; i++) {
927 testQueueAddRemove(q, null);
928 testQueueAddRemove(q, 537);
929 q.add(i);
930 }
931 equal(q.size(), 5);
932 checkFunctionalInvariants(q);
933 q.poll();
934 equal(q.size(), 4);
935 checkFunctionalInvariants(q);
936 if ((q instanceof LinkedBlockingQueue) ||
937 (q instanceof LinkedBlockingDeque) ||
938 (q instanceof ConcurrentLinkedDeque) ||
939 (q instanceof ConcurrentLinkedQueue)) {
940 testQueueIteratorRemove(q);
941 }
942 }
943
944 private static void testQueueAddRemove(final Queue<Integer> q,
945 final Integer e) {
946 final List<Integer> originalContents = new ArrayList<>(q);
947 final boolean isEmpty = q.isEmpty();
948 final boolean isList = (q instanceof List);
949 final List asList = isList ? (List) q : null;
950 check(!q.contains(e));
951 try {
952 q.add(e);
953 } catch (NullPointerException npe) {
954 check(e == null);
955 return; // Null elements not supported
956 }
957 check(q.contains(e));
958 check(q.remove(e));
959 check(!q.contains(e));
960 equal(new ArrayList<Integer>(q), originalContents);
961
962 if (q instanceof Deque<?>) {
963 final Deque<Integer> deq = (Deque<Integer>) q;
964 final List<Integer> singleton = Collections.singletonList(e);
965
966 // insert, query, remove element at head
967 if (isEmpty) {
968 THROWS(NoSuchElementException.class,
969 () -> deq.getFirst(),
970 () -> deq.element(),
971 () -> deq.iterator().next());
972 check(deq.peekFirst() == null);
973 check(deq.peek() == null);
974 } else {
975 check(deq.getFirst() != e);
976 check(deq.element() != e);
977 check(deq.iterator().next() != e);
978 check(deq.peekFirst() != e);
979 check(deq.peek() != e);
980 }
981 check(!deq.contains(e));
982 check(!deq.removeFirstOccurrence(e));
983 check(!deq.removeLastOccurrence(e));
984 if (isList) {
985 check(asList.indexOf(e) == -1);
986 check(asList.lastIndexOf(e) == -1);
987 }
988 switch (rnd.nextInt(isList ? 4 : 3)) {
989 case 0: deq.addFirst(e); break;
990 case 1: check(deq.offerFirst(e)); break;
991 case 2: deq.push(e); break;
992 case 3: asList.add(0, e); break;
993 default: throw new AssertionError();
994 }
995 check(deq.peekFirst() == e);
996 check(deq.getFirst() == e);
997 check(deq.element() == e);
998 check(deq.peek() == e);
999 check(deq.iterator().next() == e);
1000 check(deq.contains(e));
1001 if (isList) {
1002 check(asList.get(0) == e);
1003 check(asList.indexOf(e) == 0);
1004 check(asList.lastIndexOf(e) == 0);
1005 check(asList.subList(0, 1).equals(singleton));
1006 }
1007 switch (rnd.nextInt(isList ? 11 : 9)) {
1008 case 0: check(deq.pollFirst() == e); break;
1009 case 1: check(deq.removeFirst() == e); break;
1010 case 2: check(deq.remove() == e); break;
1011 case 3: check(deq.pop() == e); break;
1012 case 4: check(deq.removeFirstOccurrence(e)); break;
1013 case 5: check(deq.removeLastOccurrence(e)); break;
1014 case 6: check(deq.remove(e)); break;
1015 case 7: check(deq.removeAll(singleton)); break;
1016 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
1017 case 9: asList.remove(0); break;
1018 case 10: asList.subList(0, 1).clear(); break;
1019 default: throw new AssertionError();
1020 }
1021 if (isEmpty) {
1022 THROWS(NoSuchElementException.class,
1023 () -> deq.getFirst(),
1024 () -> deq.element(),
1025 () -> deq.iterator().next());
1026 check(deq.peekFirst() == null);
1027 check(deq.peek() == null);
1028 } else {
1029 check(deq.getFirst() != e);
1030 check(deq.element() != e);
1031 check(deq.iterator().next() != e);
1032 check(deq.peekFirst() != e);
1033 check(deq.peek() != e);
1034 }
1035 check(!deq.contains(e));
1036 check(!deq.removeFirstOccurrence(e));
1037 check(!deq.removeLastOccurrence(e));
1038 if (isList) {
1039 check(isEmpty || asList.get(0) != e);
1040 check(asList.indexOf(e) == -1);
1041 check(asList.lastIndexOf(e) == -1);
1042 }
1043 equal(new ArrayList<Integer>(deq), originalContents);
1044
1045 // insert, query, remove element at tail
1046 if (isEmpty) {
1047 check(deq.peekLast() == null);
1048 THROWS(NoSuchElementException.class, () -> deq.getLast());
1049 } else {
1050 check(deq.peekLast() != e);
1051 check(deq.getLast() != e);
1052 }
1053 switch (rnd.nextInt(isList ? 6 : 4)) {
1054 case 0: deq.addLast(e); break;
1055 case 1: check(deq.offerLast(e)); break;
1056 case 2: check(deq.add(e)); break;
1057 case 3: deq.addAll(singleton); break;
1058 case 4: asList.addAll(deq.size(), singleton); break;
1059 case 5: asList.add(deq.size(), e); break;
1060 default: throw new AssertionError();
1061 }
1062 check(deq.peekLast() == e);
1063 check(deq.getLast() == e);
1064 check(deq.contains(e));
1065 if (isList) {
1066 ListIterator it = asList.listIterator(asList.size());
1067 check(it.previous() == e);
1068 check(asList.get(asList.size() - 1) == e);
1069 check(asList.indexOf(e) == asList.size() - 1);
1070 check(asList.lastIndexOf(e) == asList.size() - 1);
1071 int size = asList.size();
1072 check(asList.subList(size - 1, size).equals(singleton));
1073 }
1074 switch (rnd.nextInt(isList ? 8 : 6)) {
1075 case 0: check(deq.pollLast() == e); break;
1076 case 1: check(deq.removeLast() == e); break;
1077 case 2: check(deq.removeFirstOccurrence(e)); break;
1078 case 3: check(deq.removeLastOccurrence(e)); break;
1079 case 4: check(deq.remove(e)); break;
1080 case 5: check(deq.removeAll(singleton)); break;
1081 case 6: asList.remove(asList.size() - 1); break;
1082 case 7:
1083 ListIterator it = asList.listIterator(asList.size());
1084 it.previous();
1085 it.remove();
1086 break;
1087 default: throw new AssertionError();
1088 }
1089 if (isEmpty) {
1090 check(deq.peekLast() == null);
1091 THROWS(NoSuchElementException.class, () -> deq.getLast());
1092 } else {
1093 check(deq.peekLast() != e);
1094 check(deq.getLast() != e);
1095 }
1096 check(!deq.contains(e));
1097 equal(new ArrayList<Integer>(deq), originalContents);
1098
1099 // Test operations on empty deque
1100 switch (rnd.nextInt(isList ? 4 : 2)) {
1101 case 0: deq.clear(); break;
1102 case 1:
1103 Iterator it = deq.iterator();
1104 while (it.hasNext()) {
1105 it.next();
1106 it.remove();
1107 }
1108 break;
1109 case 2: asList.subList(0, asList.size()).clear(); break;
1110 case 3:
1111 ListIterator lit = asList.listIterator(asList.size());
1112 while (lit.hasPrevious()) {
1113 lit.previous();
1114 lit.remove();
1115 }
1116 break;
1117 default: throw new AssertionError();
1118 }
1119 testEmptyCollection(deq);
1120 check(!deq.iterator().hasNext());
1121 if (isList) {
1122 check(!asList.listIterator().hasPrevious());
1123 THROWS(NoSuchElementException.class,
1124 () -> asList.listIterator().previous());
1125 }
1126 THROWS(NoSuchElementException.class,
1127 () -> deq.iterator().next(),
1128 () -> deq.element(),
1129 () -> deq.getFirst(),
1130 () -> deq.getLast(),
1131 () -> deq.pop(),
1132 () -> deq.remove(),
1133 () -> deq.removeFirst(),
1134 () -> deq.removeLast());
1135
1136 check(deq.poll() == null);
1137 check(deq.pollFirst() == null);
1138 check(deq.pollLast() == null);
1139 check(deq.peek() == null);
1140 check(deq.peekFirst() == null);
1141 check(deq.peekLast() == null);
1142 check(!deq.removeFirstOccurrence(e));
1143 check(!deq.removeLastOccurrence(e));
1144
1145 check(deq.addAll(originalContents) == !isEmpty);
1146 equal(new ArrayList<Integer>(deq), originalContents);
1147 check(!deq.addAll(Collections.<Integer>emptyList()));
1148 equal(new ArrayList<Integer>(deq), originalContents);
1149 }
1150 }
1151
1152 private static void testQueueIteratorRemove(Queue<Integer> q) {
1153 System.err.printf("testQueueIteratorRemove %s%n",
1154 q.getClass().getSimpleName());
1155 q.clear();
1156 for (int i = 0; i < 5; i++)
1157 q.add(i);
1158 Iterator<Integer> it = q.iterator();
1159 check(it.hasNext());
1160 for (int i = 3; i >= 0; i--)
1161 q.remove(i);
1162 equal(it.next(), 0);
1163 equal(it.next(), 4);
1164
1165 q.clear();
1166 for (int i = 0; i < 5; i++)
1167 q.add(i);
1168 it = q.iterator();
1169 equal(it.next(), 0);
1170 check(it.hasNext());
1171 for (int i = 1; i < 4; i++)
1172 q.remove(i);
1173 equal(it.next(), 1);
1174 equal(it.next(), 4);
1175 }
1176
1177 // for any array of integer values, check that the result of lastIndexOf(1)
1178 // and indexOf(1) match assumptions for all types of List<Integer> we can
1179 // construct
1180 private static void testListIndexOf(final int index,
1181 final int lastIndex,
1182 final Integer ... values) {
1183 if (values.length == 0) {
1184 checkListIndexOf(emptyList(), index, lastIndex);
1185 } else if (values.length == 1) {
1186 checkListIndexOf(singletonList(values[0]), index, lastIndex);
1187 checkListIndexOf(nCopies(25, values[0]), index, lastIndex == 0 ? 24 : -1);
1188 }
1189 List<Integer> l = List.of(values);
1190 checkListIndexOf(l, index, lastIndex);
1191 checkListIndexOf(Arrays.asList(values), index, lastIndex);
1192 checkListIndexOf(new ArrayList(l), index, lastIndex);
1193 checkListIndexOf(new LinkedList(l), index, lastIndex);
1194 checkListIndexOf(new Vector(l), index, lastIndex);
1195 checkListIndexOf(new CopyOnWriteArrayList(l), index, lastIndex);
1196 }
1197
1198 private static void checkListIndexOf(final List<Integer> list,
1199 final int index,
1200 final int lastIndex) {
1201 String msg = list.getClass().toString();
1202 equal(list.indexOf(1), index, msg);
1203 equal(list.lastIndexOf(1), lastIndex, msg);
1204 equal(list.subList(0, list.size()).indexOf(1), index, msg);
1205 equal(list.subList(0, list.size()).lastIndexOf(1), lastIndex, msg);
1206 }
1207
1208 private static void testList(final List<Integer> l) {
1209 //----------------------------------------------------------------
1210 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
1211 // doesn't throw IndexOutOfBoundsException
1212 //----------------------------------------------------------------
1213 try {
1214 l.addAll(-1, Collections.<Integer>emptyList());
1215 fail("Expected IndexOutOfBoundsException not thrown");
1216 }
1217 catch (UnsupportedOperationException ignored) {/* OK */}
1218 catch (IndexOutOfBoundsException ignored) {/* OK */}
1219 catch (Throwable t) { unexpected(t); }
1220
1221 // equal(l instanceof Serializable,
1222 // l.subList(0,0) instanceof Serializable);
1223 if (l.subList(0,0) instanceof Serializable)
1224 check(l instanceof Serializable);
1225
1226 equal(l instanceof RandomAccess,
1227 l.subList(0,0) instanceof RandomAccess);
1228
1229 l.iterator();
1230 l.listIterator();
1231 l.listIterator(0);
1232 l.listIterator(l.size());
1233 THROWS(IndexOutOfBoundsException.class,
1234 () -> l.listIterator(-1),
1235 () -> l.listIterator(l.size() + 1));
1236
1237 if (l instanceof AbstractList) {
1238 try {
1239 int size = l.size();
1240 AbstractList<Integer> abList = (AbstractList<Integer>) l;
1241 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class });
1242 m.setAccessible(true);
1243 m.invoke(abList, new Object[] { 0, 0 });
1244 m.invoke(abList, new Object[] { size, size });
1245 equal(size, l.size());
1246 }
1247 catch (UnsupportedOperationException ignored) {/* OK */}
1248 catch (Throwable t) { unexpected(t); }
1249 }
1250
1251 int hashCode = 1;
1252 for (Integer i : l)
1253 hashCode = 31 * hashCode + (i == null ? 0 : i.hashCode());
1254 check(l.hashCode() == hashCode);
1255
1256 var t = new ArrayList<>(l);
1257 check(t.equals(l));
1258 check(l.equals(t));
1259 if (!l.isEmpty()) {
1260 equal(l.getFirst(), l.get(0));
1261 equal(l.getLast(), l.get(l.size() - 1));
1262 }
1263 }
1264
1265 private static void testCollection(Collection<Integer> c) {
1266 try { testCollection1(c); }
1267 catch (Throwable t) { unexpected(t); }
1268 }
1269
1270 private static void testCollection1(Collection<Integer> c) {
1271
1272 System.out.println("\n==> " + c.getClass().getName());
1273
1274 checkFunctionalInvariants(c);
1275
1276 if (! supportsAdd(c)) return;
1277 //System.out.println("add() supported");
1278
1279 if (c instanceof NavigableSet) {
1280 System.out.println("NavigableSet tests...");
1281
1282 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
1283 testNavigableSet(ns);
1284 testNavigableSet(ns.headSet(6, false));
1285 testNavigableSet(ns.headSet(5, true));
1286 testNavigableSet(ns.tailSet(0, false));
1287 testNavigableSet(ns.tailSet(1, true));
1288 testNavigableSet(ns.subSet(0, false, 5, true));
1289 testNavigableSet(ns.subSet(1, true, 6, false));
1290 }
1291
1292 if (c instanceof Queue)
1293 testQueue((Queue<Integer>)c);
1294
1295 if (c instanceof List)
1296 testList((List<Integer>)c);
1297
1298 if (c instanceof Set) {
1299 int hashCode = 0;
1300 for (Integer i : c)
1301 hashCode = hashCode + (i == null ? 0 : i.hashCode());
1302 check(c.hashCode() == hashCode);
1303 }
1304
1305 check(supportsRemove(c));
1306
1307 try {
1308 oneElement(c);
1309 checkFunctionalInvariants(c);
1310 }
1311 catch (Throwable t) { unexpected(t); }
1312
1313 clear(c); testNullElement(c);
1314 oneElement(c); testNullElement(c);
1315
1316 clear(c); testStringElement(c);
1317 oneElement(c); testStringElement(c);
1318
1319 testAddAll(c);
1320
1321 if (c.getClass().getName().matches(".*concurrent.*"))
1322 testConcurrentCollection(c);
1323
1324 //----------------------------------------------------------------
1325 // The "all" operations should throw NPE when passed null
1326 //----------------------------------------------------------------
1327 {
1328 clear(c);
1329 try {
1330 c.removeAll(null);
1331 fail("Expected NullPointerException");
1332 }
1333 catch (NullPointerException e) { pass(); }
1334 catch (Throwable t) { unexpected(t); }
1335
1336 oneElement(c);
1337 try {
1338 c.removeAll(null);
1339 fail("Expected NullPointerException");
1340 }
1341 catch (NullPointerException e) { pass(); }
1342 catch (Throwable t) { unexpected(t); }
1343
1344 clear(c);
1345 try {
1346 c.retainAll(null);
1347 fail("Expected NullPointerException");
1348 }
1349 catch (NullPointerException e) { pass(); }
1350 catch (Throwable t) { unexpected(t); }
1351
1352 oneElement(c);
1353 try {
1354 c.retainAll(null);
1355 fail("Expected NullPointerException");
1356 }
1357 catch (NullPointerException e) { pass(); }
1358 catch (Throwable t) { unexpected(t); }
1359
1360 oneElement(c);
1361 try {
1362 c.addAll(null);
1363 fail("Expected NullPointerException");
1364 }
1365 catch (NullPointerException e) { pass(); }
1366 catch (Throwable t) { unexpected(t); }
1367
1368 oneElement(c);
1369 try {
1370 c.containsAll(null);
1371 fail("Expected NullPointerException");
1372 }
1373 catch (NullPointerException e) { pass(); }
1374 catch (Throwable t) { unexpected(t); }
1375 }
1376 }
1377
1378 //----------------------------------------------------------------
1379 // Map
1380 //----------------------------------------------------------------
1381 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
1382 check(m.keySet().size() == m.entrySet().size());
1383 check(m.keySet().size() == m.size());
1384 checkFunctionalInvariants(m.keySet());
1385 checkFunctionalInvariants(m.values());
1386 check(m.size() != 0 ^ m.isEmpty());
1387 check(! m.containsKey(ABSENT_VALUE));
1388
1389 if (m instanceof Serializable) {
1390 //System.out.printf("Serializing %s%n", m.getClass().getName());
1391 try {
1392 Object clone = serialClone(m);
1393 equal(m instanceof Serializable,
1394 clone instanceof Serializable);
1395 equal(m, clone);
1396 } catch (Error xxx) {
1397 if (! (xxx.getCause() instanceof NotSerializableException))
1398 throw xxx;
1399 }
1400 }
1401 }
1402
1403 private static void testMap(Map<Integer,Integer> m) {
1404 System.out.println("\n==> " + m.getClass().getName());
1405
1406 int hashCode = 0;
1407 for (var e : m.entrySet()) {
1408 int entryHash = (e.getKey() == null ? 0 : e.getKey().hashCode()) ^
1409 (e.getValue() == null ? 0 : e.getValue().hashCode());
1410 check(e.hashCode() == entryHash);
1411 hashCode += entryHash;
1412 }
1413 check(m.hashCode() == hashCode);
1414
1415 if (m instanceof ConcurrentMap)
1416 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
1417
1418 if (m instanceof NavigableMap) {
1419 System.out.println("NavigableMap tests...");
1420
1421 NavigableMap<Integer,Integer> nm =
1422 (NavigableMap<Integer,Integer>) m;
1423 testNavigableMapRemovers(nm);
1424 testNavigableMap(nm);
1425 testNavigableMap(nm.headMap(6, false));
1426 testNavigableMap(nm.headMap(5, true));
1427 testNavigableMap(nm.tailMap(0, false));
1428 testNavigableMap(nm.tailMap(1, true));
1429 testNavigableMap(nm.subMap(1, true, 6, false));
1430 testNavigableMap(nm.subMap(0, false, 5, true));
1431 }
1432
1433 checkFunctionalInvariants(m);
1434
1435 if (supportsClear(m)) {
1436 try { clear(m); }
1437 catch (Throwable t) { unexpected(t); }
1438 }
1439
1440 if (supportsPut(m)) {
1441 try {
1442 check(m.put(3333, 77777) == null);
1443 check(m.put(9134, 74982) == null);
1444 check(m.get(9134) == 74982);
1445 check(m.put(9134, 1382) == 74982);
1446 check(m.get(9134) == 1382);
1447 check(m.size() == 2);
1448 checkFunctionalInvariants(m);
1449 checkNPEConsistency(m);
1450 }
1451 catch (Throwable t) { unexpected(t); }
1452 }
1453 }
1454
1455 private static boolean supportsPut(Map<Integer,Integer> m) {
1456 // We're asking for .equals(...) semantics
1457 if (m instanceof IdentityHashMap) return false;
1458
1459 try { check(m.put(ABSENT_VALUE,12735) == null); }
1460 catch (UnsupportedOperationException t) { return false; }
1461 catch (Throwable t) { unexpected(t); }
1462
1463 try {
1464 check(m.containsKey(ABSENT_VALUE));
1465 check(m.remove(ABSENT_VALUE) != null);
1466 } catch (Throwable t) { unexpected(t); }
1467 return true;
1468 }
1469
1470 private static boolean supportsClear(Map<?,?> m) {
1471 try { m.clear(); }
1472 catch (UnsupportedOperationException t) { return false; }
1473 catch (Throwable t) { unexpected(t); }
1474 return true;
1475 }
1476
1477 //----------------------------------------------------------------
1478 // ConcurrentMap
1479 //----------------------------------------------------------------
1480 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
1481 System.out.println("ConcurrentMap tests...");
1482
1483 try {
1484 clear(m);
1485
1486 check(m.putIfAbsent(18357,7346) == null);
1487 check(m.containsKey(18357));
1488 check(m.putIfAbsent(18357,8263) == 7346);
1489 try { m.putIfAbsent(18357,null); fail("NPE"); }
1490 catch (NullPointerException t) { }
1491 check(m.containsKey(18357));
1492
1493 check(! m.replace(18357,8888,7777));
1494 check(m.containsKey(18357));
1495 try { m.replace(18357,null,7777); fail("NPE"); }
1496 catch (NullPointerException t) { }
1497 check(m.containsKey(18357));
1498 check(m.get(18357) == 7346);
1499 check(m.replace(18357,7346,5555));
1500 check(m.replace(18357,5555,7346));
1501 check(m.get(18357) == 7346);
1502
1503 check(m.replace(92347,7834) == null);
1504 try { m.replace(18357,null); fail("NPE"); }
1505 catch (NullPointerException t) { }
1506 check(m.replace(18357,7346) == 7346);
1507 check(m.replace(18357,5555) == 7346);
1508 check(m.get(18357) == 5555);
1509 check(m.replace(18357,7346) == 5555);
1510 check(m.get(18357) == 7346);
1511
1512 check(! m.remove(18357,9999));
1513 check(m.get(18357) == 7346);
1514 check(m.containsKey(18357));
1515 check(! m.remove(18357,null)); // 6272521
1516 check(m.get(18357) == 7346);
1517 check(m.remove(18357,7346));
1518 check(m.get(18357) == null);
1519 check(! m.containsKey(18357));
1520 check(m.isEmpty());
1521
1522 m.putIfAbsent(1,2);
1523 check(m.size() == 1);
1524 check(! m.remove(1,null));
1525 check(! m.remove(1,null));
1526 check(! m.remove(1,1));
1527 check(m.remove(1,2));
1528 check(m.isEmpty());
1529
1530 testEmptyMap(m);
1531 }
1532 catch (Throwable t) { unexpected(t); }
1533 }
1534
1535 private static void throwsConsistently(Class<? extends Throwable> k,
1536 Iterable<Fun> fs) {
1537 List<Class<? extends Throwable>> threw = new ArrayList<>();
1538 for (Fun f : fs)
1539 try { f.f(); threw.add(null); }
1540 catch (Throwable t) {
1541 check(k.isAssignableFrom(t.getClass()));
1542 threw.add(t.getClass());
1543 }
1544 if (new HashSet<Object>(threw).size() != 1)
1545 fail(threw.toString());
1546 }
1547
1548 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
1549 m.clear();
1550 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
1551 ? (ConcurrentMap<T,Integer>) m
1552 : null;
1553 List<Fun> fs = new ArrayList<>();
1554 fs.add(() -> check(! m.containsKey(null)));
1555 fs.add(() -> equal(m.remove(null), null));
1556 fs.add(() -> equal(m.get(null), null));
1557 if (cm != null)
1558 fs.add(() -> check(! cm.remove(null,null)));
1559 throwsConsistently(NullPointerException.class, fs);
1560
1561 fs.clear();
1562 final Map<T,Integer> sm = singletonMap(null,1);
1563 fs.add(() -> { equal(m.put(null,1), null); m.clear();});
1564 fs.add(() -> { m.putAll(sm); m.clear();});
1565 if (cm != null) {
1566 fs.add(() -> check(! cm.remove(null,null)));
1567 fs.add(() -> equal(cm.putIfAbsent(null,1), 1));
1568 fs.add(() -> equal(cm.replace(null,1), null));
1569 fs.add(() -> equal(cm.replace(null,1, 1), 1));
1570 }
1571 throwsConsistently(NullPointerException.class, fs);
1572 }
1573
1574 //----------------------------------------------------------------
1575 // NavigableMap
1576 //----------------------------------------------------------------
1577 private static void
1578 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1579 Integer i,
1580 Integer lower,
1581 Integer floor,
1582 Integer ceiling,
1583 Integer higher) {
1584 equal(m.lowerKey(i), lower);
1585 equal(m.floorKey(i), floor);
1586 equal(m.ceilingKey(i), ceiling);
1587 equal(m.higherKey(i), higher);
1588 }
1589
1590 private static void
1591 checkNavigableSetKeys(NavigableSet<Integer> m,
1592 Integer i,
1593 Integer lower,
1594 Integer floor,
1595 Integer ceiling,
1596 Integer higher) {
1597 equal(m.lower(i), lower);
1598 equal(m.floor(i), floor);
1599 equal(m.ceiling(i), ceiling);
1600 equal(m.higher(i), higher);
1601 }
1602
1603 static final Random rnd = new Random();
1604 static void equalNext(final Iterator<?> it, Object expected) {
1605 if (rnd.nextBoolean())
1606 check(it.hasNext());
1607 equal(it.next(), expected);
1608 }
1609
1610 static void equalMaps(Map m1, Map m2) {
1611 equal(m1, m2);
1612 equal(m2, m1);
1613 equal(m1.size(), m2.size());
1614 equal(m1.isEmpty(), m2.isEmpty());
1615 equal(m1.toString(), m2.toString());
1616 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1617 }
1618
1619 @SuppressWarnings({"unchecked", "rawtypes"})
1620 static void testNavigableMapRemovers(NavigableMap m)
1621 {
1622 final Map emptyMap = new HashMap();
1623
1624 final Map singletonMap = new HashMap();
1625 singletonMap.put(1, 2);
1626
1627 abstract class NavigableMapView {
1628 abstract NavigableMap view(NavigableMap m);
1629 }
1630
1631 NavigableMapView[] views = {
1632 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1633 return m; }},
1634 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1635 return m.headMap(99, true); }},
1636 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1637 return m.tailMap(-99, false); }},
1638 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1639 return m.subMap(-99, true, 99, false); }},
1640 };
1641
1642 abstract class Remover {
1643 abstract void remove(NavigableMap m, Object k, Object v);
1644 }
1645
1646 Remover[] removers = {
1647 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1648 equal(m.remove(k), v); }},
1649
1650 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1651 equal(m.descendingMap().remove(k), v); }},
1652 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1653 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1654 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1655 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1656
1657 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1658 equal(m.headMap(86, true).remove(k), v); }},
1659 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1660 equal(m.tailMap(-86, true).remove(k), v); }},
1661 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1662 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1663
1664 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1665 check(m.keySet().remove(k)); }},
1666 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1667 check(m.navigableKeySet().remove(k)); }},
1668
1669 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1670 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1671 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1672 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1673 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1674 check(m.navigableKeySet().subSet(-86, true, 86, false)
1675 .remove(k)); }},
1676
1677 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1678 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1679 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1680 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1681 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1682 check(m.descendingKeySet().subSet(86, true, -86, false)
1683 .remove(k)); }},
1684 };
1685
1686 for (NavigableMapView view : views) {
1687 for (Remover remover : removers) {
1688 try {
1689 m.clear();
1690 equalMaps(m, emptyMap);
1691 equal(m.put(1, 2), null);
1692 equalMaps(m, singletonMap);
1693 NavigableMap v = view.view(m);
1694 remover.remove(v, 1, 2);
1695 equalMaps(m, emptyMap);
1696 } catch (Throwable t) { unexpected(t); }
1697 }
1698 }
1699 }
1700
1701 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1702 {
1703 clear(m);
1704 checkNavigableMapKeys(m, 1, null, null, null, null);
1705
1706 equal(m.put(1, 2), null);
1707 equal(m.put(3, 4), null);
1708 equal(m.put(5, 9), null);
1709
1710 equal(m.put(1, 2), 2);
1711 equal(m.put(3, 4), 4);
1712 equal(m.put(5, 6), 9);
1713
1714 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1715 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1716 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1717 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1718 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1719 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1720
1721 for (final Iterator<Integer> it :
1722 (Iterator<Integer>[])
1723 new Iterator<?>[] {
1724 m.descendingKeySet().iterator(),
1725 m.navigableKeySet().descendingIterator()}) {
1726 equalNext(it, 5);
1727 equalNext(it, 3);
1728 equalNext(it, 1);
1729 check(! it.hasNext());
1730 THROWS(NoSuchElementException.class, () -> it.next());
1731 }
1732
1733 {
1734 final Iterator<Map.Entry<Integer,Integer>> it
1735 = m.descendingMap().entrySet().iterator();
1736 check(it.hasNext()); equal(it.next().getKey(), 5);
1737 check(it.hasNext()); equal(it.next().getKey(), 3);
1738 check(it.hasNext()); equal(it.next().getKey(), 1);
1739 check(! it.hasNext());
1740 THROWS(NoSuchElementException.class, () -> it.next());
1741 }
1742
1743 prepMapForDescItrTests(m);
1744 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator());
1745 prepMapForDescItrTests(m);
1746 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());
1747 prepMapForDescItrTests(m);
1748 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator());
1749
1750 prepMapForDescItrTests(m);
1751 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator());
1752 prepMapForDescItrTests(m);
1753 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator());
1754 prepMapForDescItrTests(m);
1755 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator());
1756
1757 prepMapForDescItrTests(m);
1758 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator());
1759 prepMapForDescItrTests(m);
1760 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator());
1761 prepMapForDescItrTests(m);
1762 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator());
1763
1764 prepMapForDescItrTests(m);
1765 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator());
1766 prepMapForDescItrTests(m);
1767 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator());
1768 prepMapForDescItrTests(m);
1769 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator());
1770
1771 prepMapForDescItrTests(m);
1772 checkDescItrRmFirst((Collection)m.entrySet(),
1773 m.descendingMap().entrySet().iterator());
1774 prepMapForDescItrTests(m);
1775 checkDescItrRmMid((Collection)m.entrySet(),
1776 m.descendingMap().entrySet().iterator());
1777 prepMapForDescItrTests(m);
1778 checkDescItrRmLast((Collection)m.entrySet(),
1779 m.descendingMap().entrySet().iterator());
1780 }
1781
1782 private static void testNavigableSet(NavigableSet<Integer> s) {
1783 clear(s);
1784 checkNavigableSetKeys(s, 1, null, null, null, null);
1785
1786 check(s.add(1));
1787 check(s.add(3));
1788 check(s.add(5));
1789
1790 check(! s.add(1));
1791 check(! s.add(3));
1792 check(! s.add(5));
1793
1794 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1795 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1796 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1797 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1798 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1799 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1800
1801 for (final Iterator<Integer> it :
1802 (Iterator<Integer>[])
1803 new Iterator<?>[] {
1804 s.descendingIterator(),
1805 s.descendingSet().iterator()}) {
1806 equalNext(it, 5);
1807 equalNext(it, 3);
1808 equalNext(it, 1);
1809 check(! it.hasNext());
1810 THROWS(NoSuchElementException.class, () -> it.next());
1811 }
1812
1813 prepSetForDescItrTests(s);
1814 checkDescItrRmFirst(s, s.descendingIterator());
1815 prepSetForDescItrTests(s);
1816 checkDescItrRmMid(s, s.descendingIterator());
1817 prepSetForDescItrTests(s);
1818 checkDescItrRmLast(s, s.descendingIterator());
1819
1820 prepSetForDescItrTests(s);
1821 checkDescItrRmFirst(s, s.descendingSet().iterator());
1822 prepSetForDescItrTests(s);
1823 checkDescItrRmMid(s, s.descendingSet().iterator());
1824 prepSetForDescItrTests(s);
1825 checkDescItrRmLast(s, s.descendingSet().iterator());
1826 }
1827
1828 private static void prepSetForDescItrTests(Set s) {
1829 clear(s);
1830 check(s.add(1));
1831 check(s.add(3));
1832 check(s.add(5));
1833 }
1834
1835 private static void prepMapForDescItrTests(Map m) {
1836 clear(m);
1837 equal(m.put(1, 2), null);
1838 equal(m.put(3, 4), null);
1839 equal(m.put(5, 9), null);
1840 }
1841
1842 //--------------------------------------------------------------------
1843 // Check behavior of descending iterator when first element is removed
1844 //--------------------------------------------------------------------
1845 private static <T> void checkDescItrRmFirst(Collection<T> ascColl,
1846 Iterator<T> descItr) {
1847 T[] expected = (T[]) ascColl.toArray();
1848 int idx = expected.length -1;
1849
1850 equalNext(descItr, expected[idx--]);
1851 descItr.remove();
1852 while (idx >= 0 && descItr.hasNext()) {
1853 equalNext(descItr, expected[idx--]);
1854 }
1855 equal(descItr.hasNext(), false);
1856 equal(idx, -1);
1857 }
1858
1859 //-----------------------------------------------------------------------
1860 // Check behavior of descending iterator when a middle element is removed
1861 //-----------------------------------------------------------------------
1862 private static <T> void checkDescItrRmMid(Collection<T> ascColl,
1863 Iterator<T> descItr) {
1864 T[] expected = (T[]) ascColl.toArray();
1865 int idx = expected.length -1;
1866
1867 while (idx >= expected.length / 2) {
1868 equalNext(descItr, expected[idx--]);
1869 }
1870 descItr.remove();
1871 while (idx >= 0 && descItr.hasNext()) {
1872 equalNext(descItr, expected[idx--]);
1873 }
1874 equal(descItr.hasNext(), false);
1875 equal(idx, -1);
1876 }
1877
1878 //-----------------------------------------------------------------------
1879 // Check behavior of descending iterator when the last element is removed
1880 //-----------------------------------------------------------------------
1881 private static <T> void checkDescItrRmLast(Collection<T> ascColl,
1882 Iterator<T> descItr) {
1883 T[] expected = (T[]) ascColl.toArray();
1884 int idx = expected.length -1;
1885
1886 while (idx >= 0 && descItr.hasNext()) {
1887 equalNext(descItr, expected[idx--]);
1888 }
1889 equal(idx, -1);
1890 equal(descItr.hasNext(), false);
1891 descItr.remove();
1892 equal(ascColl.contains(expected[0]), false);
1893 }
1894
1895 //--------------------- Infrastructure ---------------------------
1896 static volatile int passed = 0, failed = 0;
1897 static void pass() { passed++; }
1898 static void fail() { failed++; Thread.dumpStack(); }
1899 static void fail(String msg) { System.out.println(msg); fail(); }
1900 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1901 static void check(boolean cond) { if (cond) pass(); else fail(); }
1902 static void equal(Object x, Object y) {
1903 if (x == null ? y == null : x.equals(y)) pass();
1904 else {System.out.println(x + " not equal to " + y); fail();}}
1905 static void equal(Object x, Object y, String msg) {
1906 if (x == null ? y == null : x.equals(y)) pass();
1907 else {System.out.println(x + " not equal to " + y + " : " + msg); fail();}}
1908 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1909 public static void main(String[] args) throws Throwable {
1910 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1911
1912 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1913 if (failed > 0) throw new Exception("Some tests failed");
1914 }
1915 interface Fun {void f() throws Throwable;}
1916 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1917 for (Fun f : fs)
1918 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1919 catch (Throwable t) {
1920 if (k.isAssignableFrom(t.getClass())) pass();
1921 else unexpected(t);}}
1922 static byte[] serializedForm(Object obj) {
1923 try {
1924 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1925 new ObjectOutputStream(baos).writeObject(obj);
1926 return baos.toByteArray();
1927 } catch (IOException e) { throw new Error(e); }}
1928 static Object readObject(byte[] bytes)
1929 throws IOException, ClassNotFoundException {
1930 InputStream is = new ByteArrayInputStream(bytes);
1931 return new ObjectInputStream(is).readObject();}
1932 @SuppressWarnings("unchecked")
1933 static <T> T serialClone(T obj) {
1934 try { return (T) readObject(serializedForm(obj)); }
1935 catch (Exception e) { throw new Error(e); }}
1936 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1937 ArrayList<E> list = new ArrayList<>();
1938 public boolean remove(Object obj) {
1939 return list.remove(obj);
1940 }
1941 public boolean add(E e) {
1942 return list.add(e);
1943 }
1944 public Iterator<E> iterator() {
1945 return list.iterator();
1946 }
1947 public int size() {
1948 return list.size();
1949 }
1950 }
1951 private static class NewAbstractSet<E> extends AbstractSet<E> {
1952 HashSet<E> set = new HashSet<>();
1953 public boolean remove(Object obj) {
1954 return set.remove(obj);
1955 }
1956 public boolean add(E e) {
1957 return set.add(e);
1958 }
1959 public Iterator<E> iterator() {
1960 return set.iterator();
1961 }
1962 public int size() {
1963 return set.size();
1964 }
1965 }
1966
1967 }