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
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(StableValue.list(0, i -> i));
224 testEmptyList(StableValue.list(3, i -> i).subList(0, 0));
225 testListMutatorsAlwaysThrow(List.of());
226 testListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
227 testListMutatorsAlwaysThrow(StableValue.list(0, i -> i));
228 testEmptyListMutatorsAlwaysThrow(List.of());
229 testEmptyListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
230 testEmptyListMutatorsAlwaysThrow(StableValue.list(0, i -> i));
231 testEmptyListMutatorsAlwaysThrow(StableValue.list(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 StableValue.list(0, i -> i),
255 StableValue.list(3, i -> i),
256 StableValue.list(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(StableValue.map(Set.of(), k -> k));
369 testMapMutatorsAlwaysThrow(StableValue.map(Set.of(), k -> k));
370 testEmptyMapMutatorsAlwaysThrow(StableValue.map(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 StableValue.map(Set.<Integer>of(), k -> k),
385 StableValue.map(Set.of(1), k -> k),
386 StableValue.map(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 testConcurrentCollection(Collection<Integer> c) {
891 try {
892 c.add(1);
893 Iterator<Integer> it = c.iterator();
894 check(it.hasNext());
895 clear(c);
896 check(it.next() instanceof Integer); // No CME
897 check(c.isEmpty());
898 }
899 catch (Throwable t) { unexpected(t); }
900 }
901
902 private static void testQueue(Queue<Integer> q) {
903 q.clear();
904 for (int i = 0; i < 5; i++) {
905 testQueueAddRemove(q, null);
906 testQueueAddRemove(q, 537);
907 q.add(i);
908 }
909 equal(q.size(), 5);
910 checkFunctionalInvariants(q);
911 q.poll();
912 equal(q.size(), 4);
913 checkFunctionalInvariants(q);
914 if ((q instanceof LinkedBlockingQueue) ||
915 (q instanceof LinkedBlockingDeque) ||
916 (q instanceof ConcurrentLinkedDeque) ||
917 (q instanceof ConcurrentLinkedQueue)) {
918 testQueueIteratorRemove(q);
919 }
920 }
921
922 private static void testQueueAddRemove(final Queue<Integer> q,
923 final Integer e) {
924 final List<Integer> originalContents = new ArrayList<>(q);
925 final boolean isEmpty = q.isEmpty();
926 final boolean isList = (q instanceof List);
927 final List asList = isList ? (List) q : null;
928 check(!q.contains(e));
929 try {
930 q.add(e);
931 } catch (NullPointerException npe) {
932 check(e == null);
933 return; // Null elements not supported
934 }
935 check(q.contains(e));
936 check(q.remove(e));
937 check(!q.contains(e));
938 equal(new ArrayList<Integer>(q), originalContents);
939
940 if (q instanceof Deque<?>) {
941 final Deque<Integer> deq = (Deque<Integer>) q;
942 final List<Integer> singleton = Collections.singletonList(e);
943
944 // insert, query, remove element at head
945 if (isEmpty) {
946 THROWS(NoSuchElementException.class,
947 () -> deq.getFirst(),
948 () -> deq.element(),
949 () -> deq.iterator().next());
950 check(deq.peekFirst() == null);
951 check(deq.peek() == null);
952 } else {
953 check(deq.getFirst() != e);
954 check(deq.element() != e);
955 check(deq.iterator().next() != e);
956 check(deq.peekFirst() != e);
957 check(deq.peek() != e);
958 }
959 check(!deq.contains(e));
960 check(!deq.removeFirstOccurrence(e));
961 check(!deq.removeLastOccurrence(e));
962 if (isList) {
963 check(asList.indexOf(e) == -1);
964 check(asList.lastIndexOf(e) == -1);
965 }
966 switch (rnd.nextInt(isList ? 4 : 3)) {
967 case 0: deq.addFirst(e); break;
968 case 1: check(deq.offerFirst(e)); break;
969 case 2: deq.push(e); break;
970 case 3: asList.add(0, e); break;
971 default: throw new AssertionError();
972 }
973 check(deq.peekFirst() == e);
974 check(deq.getFirst() == e);
975 check(deq.element() == e);
976 check(deq.peek() == e);
977 check(deq.iterator().next() == e);
978 check(deq.contains(e));
979 if (isList) {
980 check(asList.get(0) == e);
981 check(asList.indexOf(e) == 0);
982 check(asList.lastIndexOf(e) == 0);
983 check(asList.subList(0, 1).equals(singleton));
984 }
985 switch (rnd.nextInt(isList ? 11 : 9)) {
986 case 0: check(deq.pollFirst() == e); break;
987 case 1: check(deq.removeFirst() == e); break;
988 case 2: check(deq.remove() == e); break;
989 case 3: check(deq.pop() == e); break;
990 case 4: check(deq.removeFirstOccurrence(e)); break;
991 case 5: check(deq.removeLastOccurrence(e)); break;
992 case 6: check(deq.remove(e)); break;
993 case 7: check(deq.removeAll(singleton)); break;
994 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
995 case 9: asList.remove(0); break;
996 case 10: asList.subList(0, 1).clear(); break;
997 default: throw new AssertionError();
998 }
999 if (isEmpty) {
1000 THROWS(NoSuchElementException.class,
1001 () -> deq.getFirst(),
1002 () -> deq.element(),
1003 () -> deq.iterator().next());
1004 check(deq.peekFirst() == null);
1005 check(deq.peek() == null);
1006 } else {
1007 check(deq.getFirst() != e);
1008 check(deq.element() != e);
1009 check(deq.iterator().next() != e);
1010 check(deq.peekFirst() != e);
1011 check(deq.peek() != e);
1012 }
1013 check(!deq.contains(e));
1014 check(!deq.removeFirstOccurrence(e));
1015 check(!deq.removeLastOccurrence(e));
1016 if (isList) {
1017 check(isEmpty || asList.get(0) != e);
1018 check(asList.indexOf(e) == -1);
1019 check(asList.lastIndexOf(e) == -1);
1020 }
1021 equal(new ArrayList<Integer>(deq), originalContents);
1022
1023 // insert, query, remove element at tail
1024 if (isEmpty) {
1025 check(deq.peekLast() == null);
1026 THROWS(NoSuchElementException.class, () -> deq.getLast());
1027 } else {
1028 check(deq.peekLast() != e);
1029 check(deq.getLast() != e);
1030 }
1031 switch (rnd.nextInt(isList ? 6 : 4)) {
1032 case 0: deq.addLast(e); break;
1033 case 1: check(deq.offerLast(e)); break;
1034 case 2: check(deq.add(e)); break;
1035 case 3: deq.addAll(singleton); break;
1036 case 4: asList.addAll(deq.size(), singleton); break;
1037 case 5: asList.add(deq.size(), e); break;
1038 default: throw new AssertionError();
1039 }
1040 check(deq.peekLast() == e);
1041 check(deq.getLast() == e);
1042 check(deq.contains(e));
1043 if (isList) {
1044 ListIterator it = asList.listIterator(asList.size());
1045 check(it.previous() == e);
1046 check(asList.get(asList.size() - 1) == e);
1047 check(asList.indexOf(e) == asList.size() - 1);
1048 check(asList.lastIndexOf(e) == asList.size() - 1);
1049 int size = asList.size();
1050 check(asList.subList(size - 1, size).equals(singleton));
1051 }
1052 switch (rnd.nextInt(isList ? 8 : 6)) {
1053 case 0: check(deq.pollLast() == e); break;
1054 case 1: check(deq.removeLast() == e); break;
1055 case 2: check(deq.removeFirstOccurrence(e)); break;
1056 case 3: check(deq.removeLastOccurrence(e)); break;
1057 case 4: check(deq.remove(e)); break;
1058 case 5: check(deq.removeAll(singleton)); break;
1059 case 6: asList.remove(asList.size() - 1); break;
1060 case 7:
1061 ListIterator it = asList.listIterator(asList.size());
1062 it.previous();
1063 it.remove();
1064 break;
1065 default: throw new AssertionError();
1066 }
1067 if (isEmpty) {
1068 check(deq.peekLast() == null);
1069 THROWS(NoSuchElementException.class, () -> deq.getLast());
1070 } else {
1071 check(deq.peekLast() != e);
1072 check(deq.getLast() != e);
1073 }
1074 check(!deq.contains(e));
1075 equal(new ArrayList<Integer>(deq), originalContents);
1076
1077 // Test operations on empty deque
1078 switch (rnd.nextInt(isList ? 4 : 2)) {
1079 case 0: deq.clear(); break;
1080 case 1:
1081 Iterator it = deq.iterator();
1082 while (it.hasNext()) {
1083 it.next();
1084 it.remove();
1085 }
1086 break;
1087 case 2: asList.subList(0, asList.size()).clear(); break;
1088 case 3:
1089 ListIterator lit = asList.listIterator(asList.size());
1090 while (lit.hasPrevious()) {
1091 lit.previous();
1092 lit.remove();
1093 }
1094 break;
1095 default: throw new AssertionError();
1096 }
1097 testEmptyCollection(deq);
1098 check(!deq.iterator().hasNext());
1099 if (isList) {
1100 check(!asList.listIterator().hasPrevious());
1101 THROWS(NoSuchElementException.class,
1102 () -> asList.listIterator().previous());
1103 }
1104 THROWS(NoSuchElementException.class,
1105 () -> deq.iterator().next(),
1106 () -> deq.element(),
1107 () -> deq.getFirst(),
1108 () -> deq.getLast(),
1109 () -> deq.pop(),
1110 () -> deq.remove(),
1111 () -> deq.removeFirst(),
1112 () -> deq.removeLast());
1113
1114 check(deq.poll() == null);
1115 check(deq.pollFirst() == null);
1116 check(deq.pollLast() == null);
1117 check(deq.peek() == null);
1118 check(deq.peekFirst() == null);
1119 check(deq.peekLast() == null);
1120 check(!deq.removeFirstOccurrence(e));
1121 check(!deq.removeLastOccurrence(e));
1122
1123 check(deq.addAll(originalContents) == !isEmpty);
1124 equal(new ArrayList<Integer>(deq), originalContents);
1125 check(!deq.addAll(Collections.<Integer>emptyList()));
1126 equal(new ArrayList<Integer>(deq), originalContents);
1127 }
1128 }
1129
1130 private static void testQueueIteratorRemove(Queue<Integer> q) {
1131 System.err.printf("testQueueIteratorRemove %s%n",
1132 q.getClass().getSimpleName());
1133 q.clear();
1134 for (int i = 0; i < 5; i++)
1135 q.add(i);
1136 Iterator<Integer> it = q.iterator();
1137 check(it.hasNext());
1138 for (int i = 3; i >= 0; i--)
1139 q.remove(i);
1140 equal(it.next(), 0);
1141 equal(it.next(), 4);
1142
1143 q.clear();
1144 for (int i = 0; i < 5; i++)
1145 q.add(i);
1146 it = q.iterator();
1147 equal(it.next(), 0);
1148 check(it.hasNext());
1149 for (int i = 1; i < 4; i++)
1150 q.remove(i);
1151 equal(it.next(), 1);
1152 equal(it.next(), 4);
1153 }
1154
1155 // for any array of integer values, check that the result of lastIndexOf(1)
1156 // and indexOf(1) match assumptions for all types of List<Integer> we can
1157 // construct
1158 private static void testListIndexOf(final int index,
1159 final int lastIndex,
1160 final Integer ... values) {
1161 if (values.length == 0) {
1162 checkListIndexOf(emptyList(), index, lastIndex);
1163 } else if (values.length == 1) {
1164 checkListIndexOf(singletonList(values[0]), index, lastIndex);
1165 checkListIndexOf(nCopies(25, values[0]), index, lastIndex == 0 ? 24 : -1);
1166 }
1167 List<Integer> l = List.of(values);
1168 checkListIndexOf(l, index, lastIndex);
1169 checkListIndexOf(Arrays.asList(values), index, lastIndex);
1170 checkListIndexOf(new ArrayList(l), index, lastIndex);
1171 checkListIndexOf(new LinkedList(l), index, lastIndex);
1172 checkListIndexOf(new Vector(l), index, lastIndex);
1173 checkListIndexOf(new CopyOnWriteArrayList(l), index, lastIndex);
1174 }
1175
1176 private static void checkListIndexOf(final List<Integer> list,
1177 final int index,
1178 final int lastIndex) {
1179 String msg = list.getClass().toString();
1180 equal(list.indexOf(1), index, msg);
1181 equal(list.lastIndexOf(1), lastIndex, msg);
1182 equal(list.subList(0, list.size()).indexOf(1), index, msg);
1183 equal(list.subList(0, list.size()).lastIndexOf(1), lastIndex, msg);
1184 }
1185
1186 private static void testList(final List<Integer> l) {
1187 //----------------------------------------------------------------
1188 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
1189 // doesn't throw IndexOutOfBoundsException
1190 //----------------------------------------------------------------
1191 try {
1192 l.addAll(-1, Collections.<Integer>emptyList());
1193 fail("Expected IndexOutOfBoundsException not thrown");
1194 }
1195 catch (UnsupportedOperationException ignored) {/* OK */}
1196 catch (IndexOutOfBoundsException ignored) {/* OK */}
1197 catch (Throwable t) { unexpected(t); }
1198
1199 // equal(l instanceof Serializable,
1200 // l.subList(0,0) instanceof Serializable);
1201 if (l.subList(0,0) instanceof Serializable)
1202 check(l instanceof Serializable);
1203
1204 equal(l instanceof RandomAccess,
1205 l.subList(0,0) instanceof RandomAccess);
1206
1207 l.iterator();
1208 l.listIterator();
1209 l.listIterator(0);
1210 l.listIterator(l.size());
1211 THROWS(IndexOutOfBoundsException.class,
1212 () -> l.listIterator(-1),
1213 () -> l.listIterator(l.size() + 1));
1214
1215 if (l instanceof AbstractList) {
1216 try {
1217 int size = l.size();
1218 AbstractList<Integer> abList = (AbstractList<Integer>) l;
1219 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class });
1220 m.setAccessible(true);
1221 m.invoke(abList, new Object[] { 0, 0 });
1222 m.invoke(abList, new Object[] { size, size });
1223 equal(size, l.size());
1224 }
1225 catch (UnsupportedOperationException ignored) {/* OK */}
1226 catch (Throwable t) { unexpected(t); }
1227 }
1228
1229 int hashCode = 1;
1230 for (Integer i : l)
1231 hashCode = 31 * hashCode + (i == null ? 0 : i.hashCode());
1232 check(l.hashCode() == hashCode);
1233
1234 var t = new ArrayList<>(l);
1235 check(t.equals(l));
1236 check(l.equals(t));
1237 if (!l.isEmpty()) {
1238 equal(l.getFirst(), l.get(0));
1239 equal(l.getLast(), l.get(l.size() - 1));
1240 }
1241 }
1242
1243 private static void testCollection(Collection<Integer> c) {
1244 try { testCollection1(c); }
1245 catch (Throwable t) { unexpected(t); }
1246 }
1247
1248 private static void testCollection1(Collection<Integer> c) {
1249
1250 System.out.println("\n==> " + c.getClass().getName());
1251
1252 checkFunctionalInvariants(c);
1253
1254 if (! supportsAdd(c)) return;
1255 //System.out.println("add() supported");
1256
1257 if (c instanceof NavigableSet) {
1258 System.out.println("NavigableSet tests...");
1259
1260 NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
1261 testNavigableSet(ns);
1262 testNavigableSet(ns.headSet(6, false));
1263 testNavigableSet(ns.headSet(5, true));
1264 testNavigableSet(ns.tailSet(0, false));
1265 testNavigableSet(ns.tailSet(1, true));
1266 testNavigableSet(ns.subSet(0, false, 5, true));
1267 testNavigableSet(ns.subSet(1, true, 6, false));
1268 }
1269
1270 if (c instanceof Queue)
1271 testQueue((Queue<Integer>)c);
1272
1273 if (c instanceof List)
1274 testList((List<Integer>)c);
1275
1276 if (c instanceof Set) {
1277 int hashCode = 0;
1278 for (Integer i : c)
1279 hashCode = hashCode + (i == null ? 0 : i.hashCode());
1280 check(c.hashCode() == hashCode);
1281 }
1282
1283 check(supportsRemove(c));
1284
1285 try {
1286 oneElement(c);
1287 checkFunctionalInvariants(c);
1288 }
1289 catch (Throwable t) { unexpected(t); }
1290
1291 clear(c); testNullElement(c);
1292 oneElement(c); testNullElement(c);
1293
1294 clear(c); testStringElement(c);
1295 oneElement(c); testStringElement(c);
1296
1297 if (c.getClass().getName().matches(".*concurrent.*"))
1298 testConcurrentCollection(c);
1299
1300 //----------------------------------------------------------------
1301 // The "all" operations should throw NPE when passed null
1302 //----------------------------------------------------------------
1303 {
1304 clear(c);
1305 try {
1306 c.removeAll(null);
1307 fail("Expected NullPointerException");
1308 }
1309 catch (NullPointerException e) { pass(); }
1310 catch (Throwable t) { unexpected(t); }
1311
1312 oneElement(c);
1313 try {
1314 c.removeAll(null);
1315 fail("Expected NullPointerException");
1316 }
1317 catch (NullPointerException e) { pass(); }
1318 catch (Throwable t) { unexpected(t); }
1319
1320 clear(c);
1321 try {
1322 c.retainAll(null);
1323 fail("Expected NullPointerException");
1324 }
1325 catch (NullPointerException e) { pass(); }
1326 catch (Throwable t) { unexpected(t); }
1327
1328 oneElement(c);
1329 try {
1330 c.retainAll(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.addAll(null);
1339 fail("Expected NullPointerException");
1340 }
1341 catch (NullPointerException e) { pass(); }
1342 catch (Throwable t) { unexpected(t); }
1343
1344 oneElement(c);
1345 try {
1346 c.containsAll(null);
1347 fail("Expected NullPointerException");
1348 }
1349 catch (NullPointerException e) { pass(); }
1350 catch (Throwable t) { unexpected(t); }
1351 }
1352 }
1353
1354 //----------------------------------------------------------------
1355 // Map
1356 //----------------------------------------------------------------
1357 private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
1358 check(m.keySet().size() == m.entrySet().size());
1359 check(m.keySet().size() == m.size());
1360 checkFunctionalInvariants(m.keySet());
1361 checkFunctionalInvariants(m.values());
1362 check(m.size() != 0 ^ m.isEmpty());
1363 check(! m.containsKey(ABSENT_VALUE));
1364
1365 if (m instanceof Serializable) {
1366 //System.out.printf("Serializing %s%n", m.getClass().getName());
1367 try {
1368 Object clone = serialClone(m);
1369 equal(m instanceof Serializable,
1370 clone instanceof Serializable);
1371 equal(m, clone);
1372 } catch (Error xxx) {
1373 if (! (xxx.getCause() instanceof NotSerializableException))
1374 throw xxx;
1375 }
1376 }
1377 }
1378
1379 private static void testMap(Map<Integer,Integer> m) {
1380 System.out.println("\n==> " + m.getClass().getName());
1381
1382 int hashCode = 0;
1383 for (var e : m.entrySet()) {
1384 int entryHash = (e.getKey() == null ? 0 : e.getKey().hashCode()) ^
1385 (e.getValue() == null ? 0 : e.getValue().hashCode());
1386 check(e.hashCode() == entryHash);
1387 hashCode += entryHash;
1388 }
1389 check(m.hashCode() == hashCode);
1390
1391 if (m instanceof ConcurrentMap)
1392 testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
1393
1394 if (m instanceof NavigableMap) {
1395 System.out.println("NavigableMap tests...");
1396
1397 NavigableMap<Integer,Integer> nm =
1398 (NavigableMap<Integer,Integer>) m;
1399 testNavigableMapRemovers(nm);
1400 testNavigableMap(nm);
1401 testNavigableMap(nm.headMap(6, false));
1402 testNavigableMap(nm.headMap(5, true));
1403 testNavigableMap(nm.tailMap(0, false));
1404 testNavigableMap(nm.tailMap(1, true));
1405 testNavigableMap(nm.subMap(1, true, 6, false));
1406 testNavigableMap(nm.subMap(0, false, 5, true));
1407 }
1408
1409 checkFunctionalInvariants(m);
1410
1411 if (supportsClear(m)) {
1412 try { clear(m); }
1413 catch (Throwable t) { unexpected(t); }
1414 }
1415
1416 if (supportsPut(m)) {
1417 try {
1418 check(m.put(3333, 77777) == null);
1419 check(m.put(9134, 74982) == null);
1420 check(m.get(9134) == 74982);
1421 check(m.put(9134, 1382) == 74982);
1422 check(m.get(9134) == 1382);
1423 check(m.size() == 2);
1424 checkFunctionalInvariants(m);
1425 checkNPEConsistency(m);
1426 }
1427 catch (Throwable t) { unexpected(t); }
1428 }
1429 }
1430
1431 private static boolean supportsPut(Map<Integer,Integer> m) {
1432 // We're asking for .equals(...) semantics
1433 if (m instanceof IdentityHashMap) return false;
1434
1435 try { check(m.put(ABSENT_VALUE,12735) == null); }
1436 catch (UnsupportedOperationException t) { return false; }
1437 catch (Throwable t) { unexpected(t); }
1438
1439 try {
1440 check(m.containsKey(ABSENT_VALUE));
1441 check(m.remove(ABSENT_VALUE) != null);
1442 } catch (Throwable t) { unexpected(t); }
1443 return true;
1444 }
1445
1446 private static boolean supportsClear(Map<?,?> m) {
1447 try { m.clear(); }
1448 catch (UnsupportedOperationException t) { return false; }
1449 catch (Throwable t) { unexpected(t); }
1450 return true;
1451 }
1452
1453 //----------------------------------------------------------------
1454 // ConcurrentMap
1455 //----------------------------------------------------------------
1456 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
1457 System.out.println("ConcurrentMap tests...");
1458
1459 try {
1460 clear(m);
1461
1462 check(m.putIfAbsent(18357,7346) == null);
1463 check(m.containsKey(18357));
1464 check(m.putIfAbsent(18357,8263) == 7346);
1465 try { m.putIfAbsent(18357,null); fail("NPE"); }
1466 catch (NullPointerException t) { }
1467 check(m.containsKey(18357));
1468
1469 check(! m.replace(18357,8888,7777));
1470 check(m.containsKey(18357));
1471 try { m.replace(18357,null,7777); fail("NPE"); }
1472 catch (NullPointerException t) { }
1473 check(m.containsKey(18357));
1474 check(m.get(18357) == 7346);
1475 check(m.replace(18357,7346,5555));
1476 check(m.replace(18357,5555,7346));
1477 check(m.get(18357) == 7346);
1478
1479 check(m.replace(92347,7834) == null);
1480 try { m.replace(18357,null); fail("NPE"); }
1481 catch (NullPointerException t) { }
1482 check(m.replace(18357,7346) == 7346);
1483 check(m.replace(18357,5555) == 7346);
1484 check(m.get(18357) == 5555);
1485 check(m.replace(18357,7346) == 5555);
1486 check(m.get(18357) == 7346);
1487
1488 check(! m.remove(18357,9999));
1489 check(m.get(18357) == 7346);
1490 check(m.containsKey(18357));
1491 check(! m.remove(18357,null)); // 6272521
1492 check(m.get(18357) == 7346);
1493 check(m.remove(18357,7346));
1494 check(m.get(18357) == null);
1495 check(! m.containsKey(18357));
1496 check(m.isEmpty());
1497
1498 m.putIfAbsent(1,2);
1499 check(m.size() == 1);
1500 check(! m.remove(1,null));
1501 check(! m.remove(1,null));
1502 check(! m.remove(1,1));
1503 check(m.remove(1,2));
1504 check(m.isEmpty());
1505
1506 testEmptyMap(m);
1507 }
1508 catch (Throwable t) { unexpected(t); }
1509 }
1510
1511 private static void throwsConsistently(Class<? extends Throwable> k,
1512 Iterable<Fun> fs) {
1513 List<Class<? extends Throwable>> threw = new ArrayList<>();
1514 for (Fun f : fs)
1515 try { f.f(); threw.add(null); }
1516 catch (Throwable t) {
1517 check(k.isAssignableFrom(t.getClass()));
1518 threw.add(t.getClass());
1519 }
1520 if (new HashSet<Object>(threw).size() != 1)
1521 fail(threw.toString());
1522 }
1523
1524 private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
1525 m.clear();
1526 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
1527 ? (ConcurrentMap<T,Integer>) m
1528 : null;
1529 List<Fun> fs = new ArrayList<>();
1530 fs.add(() -> check(! m.containsKey(null)));
1531 fs.add(() -> equal(m.remove(null), null));
1532 fs.add(() -> equal(m.get(null), null));
1533 if (cm != null)
1534 fs.add(() -> check(! cm.remove(null,null)));
1535 throwsConsistently(NullPointerException.class, fs);
1536
1537 fs.clear();
1538 final Map<T,Integer> sm = singletonMap(null,1);
1539 fs.add(() -> { equal(m.put(null,1), null); m.clear();});
1540 fs.add(() -> { m.putAll(sm); m.clear();});
1541 if (cm != null) {
1542 fs.add(() -> check(! cm.remove(null,null)));
1543 fs.add(() -> equal(cm.putIfAbsent(null,1), 1));
1544 fs.add(() -> equal(cm.replace(null,1), null));
1545 fs.add(() -> equal(cm.replace(null,1, 1), 1));
1546 }
1547 throwsConsistently(NullPointerException.class, fs);
1548 }
1549
1550 //----------------------------------------------------------------
1551 // NavigableMap
1552 //----------------------------------------------------------------
1553 private static void
1554 checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1555 Integer i,
1556 Integer lower,
1557 Integer floor,
1558 Integer ceiling,
1559 Integer higher) {
1560 equal(m.lowerKey(i), lower);
1561 equal(m.floorKey(i), floor);
1562 equal(m.ceilingKey(i), ceiling);
1563 equal(m.higherKey(i), higher);
1564 }
1565
1566 private static void
1567 checkNavigableSetKeys(NavigableSet<Integer> m,
1568 Integer i,
1569 Integer lower,
1570 Integer floor,
1571 Integer ceiling,
1572 Integer higher) {
1573 equal(m.lower(i), lower);
1574 equal(m.floor(i), floor);
1575 equal(m.ceiling(i), ceiling);
1576 equal(m.higher(i), higher);
1577 }
1578
1579 static final Random rnd = new Random();
1580 static void equalNext(final Iterator<?> it, Object expected) {
1581 if (rnd.nextBoolean())
1582 check(it.hasNext());
1583 equal(it.next(), expected);
1584 }
1585
1586 static void equalMaps(Map m1, Map m2) {
1587 equal(m1, m2);
1588 equal(m2, m1);
1589 equal(m1.size(), m2.size());
1590 equal(m1.isEmpty(), m2.isEmpty());
1591 equal(m1.toString(), m2.toString());
1592 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1593 }
1594
1595 @SuppressWarnings({"unchecked", "rawtypes"})
1596 static void testNavigableMapRemovers(NavigableMap m)
1597 {
1598 final Map emptyMap = new HashMap();
1599
1600 final Map singletonMap = new HashMap();
1601 singletonMap.put(1, 2);
1602
1603 abstract class NavigableMapView {
1604 abstract NavigableMap view(NavigableMap m);
1605 }
1606
1607 NavigableMapView[] views = {
1608 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1609 return m; }},
1610 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1611 return m.headMap(99, true); }},
1612 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1613 return m.tailMap(-99, false); }},
1614 new NavigableMapView() { NavigableMap view(NavigableMap m) {
1615 return m.subMap(-99, true, 99, false); }},
1616 };
1617
1618 abstract class Remover {
1619 abstract void remove(NavigableMap m, Object k, Object v);
1620 }
1621
1622 Remover[] removers = {
1623 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1624 equal(m.remove(k), v); }},
1625
1626 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1627 equal(m.descendingMap().remove(k), v); }},
1628 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1629 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1630 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1631 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1632
1633 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1634 equal(m.headMap(86, true).remove(k), v); }},
1635 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1636 equal(m.tailMap(-86, true).remove(k), v); }},
1637 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1638 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1639
1640 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1641 check(m.keySet().remove(k)); }},
1642 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1643 check(m.navigableKeySet().remove(k)); }},
1644
1645 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1646 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1647 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1648 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1649 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1650 check(m.navigableKeySet().subSet(-86, true, 86, false)
1651 .remove(k)); }},
1652
1653 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1654 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1655 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1656 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1657 new Remover() { void remove(NavigableMap m, Object k, Object v) {
1658 check(m.descendingKeySet().subSet(86, true, -86, false)
1659 .remove(k)); }},
1660 };
1661
1662 for (NavigableMapView view : views) {
1663 for (Remover remover : removers) {
1664 try {
1665 m.clear();
1666 equalMaps(m, emptyMap);
1667 equal(m.put(1, 2), null);
1668 equalMaps(m, singletonMap);
1669 NavigableMap v = view.view(m);
1670 remover.remove(v, 1, 2);
1671 equalMaps(m, emptyMap);
1672 } catch (Throwable t) { unexpected(t); }
1673 }
1674 }
1675 }
1676
1677 private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1678 {
1679 clear(m);
1680 checkNavigableMapKeys(m, 1, null, null, null, null);
1681
1682 equal(m.put(1, 2), null);
1683 equal(m.put(3, 4), null);
1684 equal(m.put(5, 9), null);
1685
1686 equal(m.put(1, 2), 2);
1687 equal(m.put(3, 4), 4);
1688 equal(m.put(5, 6), 9);
1689
1690 checkNavigableMapKeys(m, 0, null, null, 1, 1);
1691 checkNavigableMapKeys(m, 1, null, 1, 1, 3);
1692 checkNavigableMapKeys(m, 2, 1, 1, 3, 3);
1693 checkNavigableMapKeys(m, 3, 1, 3, 3, 5);
1694 checkNavigableMapKeys(m, 5, 3, 5, 5, null);
1695 checkNavigableMapKeys(m, 6, 5, 5, null, null);
1696
1697 for (final Iterator<Integer> it :
1698 (Iterator<Integer>[])
1699 new Iterator<?>[] {
1700 m.descendingKeySet().iterator(),
1701 m.navigableKeySet().descendingIterator()}) {
1702 equalNext(it, 5);
1703 equalNext(it, 3);
1704 equalNext(it, 1);
1705 check(! it.hasNext());
1706 THROWS(NoSuchElementException.class, () -> it.next());
1707 }
1708
1709 {
1710 final Iterator<Map.Entry<Integer,Integer>> it
1711 = m.descendingMap().entrySet().iterator();
1712 check(it.hasNext()); equal(it.next().getKey(), 5);
1713 check(it.hasNext()); equal(it.next().getKey(), 3);
1714 check(it.hasNext()); equal(it.next().getKey(), 1);
1715 check(! it.hasNext());
1716 THROWS(NoSuchElementException.class, () -> it.next());
1717 }
1718
1719 prepMapForDescItrTests(m);
1720 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator());
1721 prepMapForDescItrTests(m);
1722 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());
1723 prepMapForDescItrTests(m);
1724 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator());
1725
1726 prepMapForDescItrTests(m);
1727 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator());
1728 prepMapForDescItrTests(m);
1729 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator());
1730 prepMapForDescItrTests(m);
1731 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator());
1732
1733 prepMapForDescItrTests(m);
1734 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator());
1735 prepMapForDescItrTests(m);
1736 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator());
1737 prepMapForDescItrTests(m);
1738 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator());
1739
1740 prepMapForDescItrTests(m);
1741 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator());
1742 prepMapForDescItrTests(m);
1743 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator());
1744 prepMapForDescItrTests(m);
1745 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator());
1746
1747 prepMapForDescItrTests(m);
1748 checkDescItrRmFirst((Collection)m.entrySet(),
1749 m.descendingMap().entrySet().iterator());
1750 prepMapForDescItrTests(m);
1751 checkDescItrRmMid((Collection)m.entrySet(),
1752 m.descendingMap().entrySet().iterator());
1753 prepMapForDescItrTests(m);
1754 checkDescItrRmLast((Collection)m.entrySet(),
1755 m.descendingMap().entrySet().iterator());
1756 }
1757
1758 private static void testNavigableSet(NavigableSet<Integer> s) {
1759 clear(s);
1760 checkNavigableSetKeys(s, 1, null, null, null, null);
1761
1762 check(s.add(1));
1763 check(s.add(3));
1764 check(s.add(5));
1765
1766 check(! s.add(1));
1767 check(! s.add(3));
1768 check(! s.add(5));
1769
1770 checkNavigableSetKeys(s, 0, null, null, 1, 1);
1771 checkNavigableSetKeys(s, 1, null, 1, 1, 3);
1772 checkNavigableSetKeys(s, 2, 1, 1, 3, 3);
1773 checkNavigableSetKeys(s, 3, 1, 3, 3, 5);
1774 checkNavigableSetKeys(s, 5, 3, 5, 5, null);
1775 checkNavigableSetKeys(s, 6, 5, 5, null, null);
1776
1777 for (final Iterator<Integer> it :
1778 (Iterator<Integer>[])
1779 new Iterator<?>[] {
1780 s.descendingIterator(),
1781 s.descendingSet().iterator()}) {
1782 equalNext(it, 5);
1783 equalNext(it, 3);
1784 equalNext(it, 1);
1785 check(! it.hasNext());
1786 THROWS(NoSuchElementException.class, () -> it.next());
1787 }
1788
1789 prepSetForDescItrTests(s);
1790 checkDescItrRmFirst(s, s.descendingIterator());
1791 prepSetForDescItrTests(s);
1792 checkDescItrRmMid(s, s.descendingIterator());
1793 prepSetForDescItrTests(s);
1794 checkDescItrRmLast(s, s.descendingIterator());
1795
1796 prepSetForDescItrTests(s);
1797 checkDescItrRmFirst(s, s.descendingSet().iterator());
1798 prepSetForDescItrTests(s);
1799 checkDescItrRmMid(s, s.descendingSet().iterator());
1800 prepSetForDescItrTests(s);
1801 checkDescItrRmLast(s, s.descendingSet().iterator());
1802 }
1803
1804 private static void prepSetForDescItrTests(Set s) {
1805 clear(s);
1806 check(s.add(1));
1807 check(s.add(3));
1808 check(s.add(5));
1809 }
1810
1811 private static void prepMapForDescItrTests(Map m) {
1812 clear(m);
1813 equal(m.put(1, 2), null);
1814 equal(m.put(3, 4), null);
1815 equal(m.put(5, 9), null);
1816 }
1817
1818 //--------------------------------------------------------------------
1819 // Check behavior of descending iterator when first element is removed
1820 //--------------------------------------------------------------------
1821 private static <T> void checkDescItrRmFirst(Collection<T> ascColl,
1822 Iterator<T> descItr) {
1823 T[] expected = (T[]) ascColl.toArray();
1824 int idx = expected.length -1;
1825
1826 equalNext(descItr, expected[idx--]);
1827 descItr.remove();
1828 while (idx >= 0 && descItr.hasNext()) {
1829 equalNext(descItr, expected[idx--]);
1830 }
1831 equal(descItr.hasNext(), false);
1832 equal(idx, -1);
1833 }
1834
1835 //-----------------------------------------------------------------------
1836 // Check behavior of descending iterator when a middle element is removed
1837 //-----------------------------------------------------------------------
1838 private static <T> void checkDescItrRmMid(Collection<T> ascColl,
1839 Iterator<T> descItr) {
1840 T[] expected = (T[]) ascColl.toArray();
1841 int idx = expected.length -1;
1842
1843 while (idx >= expected.length / 2) {
1844 equalNext(descItr, expected[idx--]);
1845 }
1846 descItr.remove();
1847 while (idx >= 0 && descItr.hasNext()) {
1848 equalNext(descItr, expected[idx--]);
1849 }
1850 equal(descItr.hasNext(), false);
1851 equal(idx, -1);
1852 }
1853
1854 //-----------------------------------------------------------------------
1855 // Check behavior of descending iterator when the last element is removed
1856 //-----------------------------------------------------------------------
1857 private static <T> void checkDescItrRmLast(Collection<T> ascColl,
1858 Iterator<T> descItr) {
1859 T[] expected = (T[]) ascColl.toArray();
1860 int idx = expected.length -1;
1861
1862 while (idx >= 0 && descItr.hasNext()) {
1863 equalNext(descItr, expected[idx--]);
1864 }
1865 equal(idx, -1);
1866 equal(descItr.hasNext(), false);
1867 descItr.remove();
1868 equal(ascColl.contains(expected[0]), false);
1869 }
1870
1871 //--------------------- Infrastructure ---------------------------
1872 static volatile int passed = 0, failed = 0;
1873 static void pass() { passed++; }
1874 static void fail() { failed++; Thread.dumpStack(); }
1875 static void fail(String msg) { System.out.println(msg); fail(); }
1876 static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1877 static void check(boolean cond) { if (cond) pass(); else fail(); }
1878 static void equal(Object x, Object y) {
1879 if (x == null ? y == null : x.equals(y)) pass();
1880 else {System.out.println(x + " not equal to " + y); fail();}}
1881 static void equal(Object x, Object y, String msg) {
1882 if (x == null ? y == null : x.equals(y)) pass();
1883 else {System.out.println(x + " not equal to " + y + " : " + msg); fail();}}
1884 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1885 public static void main(String[] args) throws Throwable {
1886 try { realMain(args); } catch (Throwable t) { unexpected(t); }
1887
1888 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1889 if (failed > 0) throw new Exception("Some tests failed");
1890 }
1891 interface Fun {void f() throws Throwable;}
1892 private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1893 for (Fun f : fs)
1894 try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1895 catch (Throwable t) {
1896 if (k.isAssignableFrom(t.getClass())) pass();
1897 else unexpected(t);}}
1898 static byte[] serializedForm(Object obj) {
1899 try {
1900 ByteArrayOutputStream baos = new ByteArrayOutputStream();
1901 new ObjectOutputStream(baos).writeObject(obj);
1902 return baos.toByteArray();
1903 } catch (IOException e) { throw new Error(e); }}
1904 static Object readObject(byte[] bytes)
1905 throws IOException, ClassNotFoundException {
1906 InputStream is = new ByteArrayInputStream(bytes);
1907 return new ObjectInputStream(is).readObject();}
1908 @SuppressWarnings("unchecked")
1909 static <T> T serialClone(T obj) {
1910 try { return (T) readObject(serializedForm(obj)); }
1911 catch (Exception e) { throw new Error(e); }}
1912 private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1913 ArrayList<E> list = new ArrayList<>();
1914 public boolean remove(Object obj) {
1915 return list.remove(obj);
1916 }
1917 public boolean add(E e) {
1918 return list.add(e);
1919 }
1920 public Iterator<E> iterator() {
1921 return list.iterator();
1922 }
1923 public int size() {
1924 return list.size();
1925 }
1926 }
1927 private static class NewAbstractSet<E> extends AbstractSet<E> {
1928 HashSet<E> set = new HashSet<>();
1929 public boolean remove(Object obj) {
1930 return set.remove(obj);
1931 }
1932 public boolean add(E e) {
1933 return set.add(e);
1934 }
1935 public Iterator<E> iterator() {
1936 return set.iterator();
1937 }
1938 public int size() {
1939 return set.size();
1940 }
1941 }
1942
1943 }