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