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