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